Vanessa Kosoy and I recently uploaded a new paper to arXiv. In this post, I briefly describe what the paper does, and attempt to explain in a self-contained way why this is a useful thing to do for ASI alignment. For a more complete background, see severalpreviousarticles.
The technical contribution of the paper is two-fold. First, we identify a class of instances of the robust bandits problem that can be learned both statistically and computationally efficiently. Previous work on the problem had only identified a class that was statistically tractable. Second, we show that most ways to generalize this class of instances makes the problem NP-hard. Thus in some sense this class is at the boundary of what's computationally tractable.
But what does the computational tractability of robust bandits have to do with ASI alignment? The thesis motivating this paper is that for ASI alignment, we need to build learning algorithms that: a) come with proofs of their statistical and computational efficiency, and b) work in environments where classical learning theoretic frameworks fail to capture phenomena that arise due to embedded agency. The "robust" in robust bandits is a way to handle embedded agency, and similar ideas have been used before for learning problems other thanbandits, albeit with different names. Bandits are one of the simplest learning problems to study that still involve interactions with the environment, thus they are a good stepping stone before solving robust versions of more complex problems. Below, I will first explain why we think an aligned ASI will be a learning agent, then I will define what we mean by computational and statistical complexity and motivate why it is important for the learner to be tractable, and finally explain how we use robustness to tackle embeddedness.
Why learning?
Unless we stop ASI development altogether, the only remaining possibilities are: a) make currently existing ASI development approaches safe, b) invent a new approach that has safety baked into it. In either case we are likely going to deal with entities that are very good at learning. This is pretty much by design. ASI development is inherently about automating tasks that we do not have the specs for. First of all, we are not able to write down the laws of the universe that the ASI is supposed to operate in because we simply don't know them. Also, we aren't even able to precisely write down the goals and objectives we want the ASI to pursue. We think in terms of concepts that seem intuitively clear to us, but are hard to describe precisely. We can see a picture of a cat and know that it's a cat, but we can't write a program from scratch that does the same. We sort of know what's good and what's bad for us but, again, we aren't able to define it. Thus an entity that is able to operate in this universe and pursue goals that are aligned with our intentions needs to both learn about the universe and learn about our intentions. This becomes even more complicated once we realize there will exist other similar entities occupying the universe at the same time trying to learn about each other. Thus learning is going to be an important aspect of ASI alignment.
Computational and statistical tractability
Of course we want our learners to be implementable in the real world with a reasonable amount of computational resources and data. Thus we need them to satisfy some notion of computational and statistical tractability. Below I will make that notion more precise.
One might say that neural networks already require only a reasonable amount of compute and data. So don't they already meet the requirement? For ASI alignment, we want to be able to mathematically prove that the learner will exhibit the desired behaviour after spending a known amount of resources, and we want to be able to prove this before we actually deploy the learner on real-world data. We are nowhere near this sort of guarantee for our current training pipeline. Modern training pipelines have very few provable guarantees, and thus most claims need to be tested with fresh experiments. We cannot afford to do this as model capabilities scale, since a fresh experiment, run without mathematical guarantees, might prove to be catastrophic.
Tractability is a notion that is already studied in computer science and we could attempt to use it directly and require that our learner run in polynomial time and require a polynomial amount of data in the worst case. But this is likely an unnecessarily stringent requirement and neural network training does provide evidence for that. Indeed, it can be shown that neural network training is NP-hard in the worst case, but somehow it still works in the real world. One explanation is that the real world isn't producing worst-case inputs. Thus what we ideally want is a learning algorithm and a property of the data distribution such that: a) we have a mathematical proof that exhibits the desired behaviour with a polynomial amount of data and compute on distributions that satisfy , b) there is good empirical evidence to suggest that the data distribution generated by the universe satisfies , and importantly, c) whether the universe satisfies should be testable in a safe way without having to run .[1] As an analogy, once we have the laws of classical mechanics worked out, we can prove that a missile launched will not hit unintended targets, but establishing the laws themselves doesn't require launching missiles. Our current training pipeline satisfies neither of the three desiderata.
The guarantees provided in both the AIXI and the SLT literature can be considered from the point of view of this framework. Instead of providing a property directly, they provide a complexity measure (Kolmogorov complexity in case of AIXI and RLCT for SLT) of the data distribution and define as . However, neither provides a computationally and statistically efficient learning algorithm, and moreover, the guarantees one generally gets in SLT depend not only on but other properties of the data distribution that are not quantified. As a result, it is impossible to calculate from the known bounds how much data and compute will be needed in order to get to a specific level of performance. The recentstringologicalsequence provides an interesting collection of 's and 's.
Our paper provides uniform bounds for the class of bandits considered. That is, we provide bounds on statistical and computational complexity that hold for all instances of the robust bandits problem within the class. Thus for the goal of getting a high reward for an unknown bandit instance, we satisfy (a) and (c). We hope that building on this research, in the future we will have something that will also satisfy (b).
Embeddedness and robustness
Learning theory provides several frameworks in which one can study the problem of learning. However, they have shortcomings when it comes to analyzing the kind of learning that an aligned ASI will need to do. In particular, issues around embedded agency do not have a good solution in the classical frameworks.
Consider, for example, the problem of binary sequence prediction such as the one tackled by Solomonoff induction. Let's consider a simpler version where we have a class of infinite sequences of 0's and 1's where itself is finite, and . In the realizable case, one assumes that nature has picked some sequence and reveals it one bit at a time. The learner's job is to predict each bit just before it is revealed while making at most a finite number of mistakes in the long run. The learner knows but does not know . Obviously, since there are at most possible sequences, the learner does not need to make more than mistakes. A slightly more clever algorithm, called the halving algorithm ensures at most mistakes. Note that this upper bound on the number of mistakes does not depend on the true sequence . This kind of learning problem is called sequence prediction with expert advice in the literature. Unlike in Solomonoff induction, this problem admits a uniform mistake bound.
Now imagine that the learner is an ASI and the true sequence is being produced by the actual universe. This renders the assumption that we know some finite quite unrealistic. This isn't because we lack a complete understanding of the laws of our universe, but rather, because the learner is a part of the universe and so in principle the universe can simulate it. This means no matter what algorithm the learner chooses to run, the universe can simply run it and produce the bit that's opposite of the one outputted by the algorithm. In this case, the learner would have no scope of correctly predicting the universe. Even if the universe has no "motivation" to do this, it can contain other ASI's that do. Thus the problem, as formulated by sequence prediction with expert advice, isn't exactly the sort of problem that an aligned ASI is going to encounter.
But if the universe can predict the learner and simply flip the bit, what guarantee can we even hope to obtain? Clearly, for this worst case universe, the situation is completely and utterly hopeless, and we shouldn't complain even if the learner gets none of its predictions right. But maybe the universe is not a perfect predictor, in which case we should aim to design a learner that can achieve whatever is the best level of prediction possible for this universe. Classically, this is attempted in the form of agnostic guarantees. Here it is assumed that the true sequence is being generated by an adversary, and thus it isn't expected to be in . However, the hope is to ensure that if the sequence happens to be close to some , then the learner gets close to it as well. In particular, if the best makes mistakes, then the learner should make at most mistakes, where is a function of . Classical results show that this isn't possible either, but if one allows the learner to have some private random bits, one can make to be sublinear. The issues with allowing private random bits have been discussed at lengthbefore.
We take a different approach at formulating these kinds of problems. We stay realizable, but say that each is only a partial specification of the universe. Thus instead of specifying a sequence of bits, each specifies a sequence of credal sets over , which in this case is simply an interval where . Suppose at time , the interval is , then the adversary, after seeing what the learner is going to predict, picks a and samples a bit from . If , then this models the all-powerful universe that can always fool the learner. However, suppose , then in principle, for that round, the learner can be right with probability 0.9 by predicting the label 1. We assume that is a set of these partial specifications. The learner knows but not and is asked to match the performance of an algorithm that only knows the true but not the precise actions of the adversary. We would call this a robust version of the sequence prediction problem. One can show that several issues with agnostic learning can be resolved by formulating the problem in this way. For a broader introduction to learning with these partial specifications, see Brittany Gelb’s sequence on infra-Bayesianism.
Sequence prediction is among the simplest of the learning problems. An actual ASI will likely interact with the environment instead of merely making predictions. One of the simplest learning frameworks that model interactions is that of bandits. A bandit problem proceeds sequentially, where at each , the learner picks an arm from a set of arms, and is given a reward based on the arm it picks. The rewards are determined using some unknown function . Thus the reward received at time is stochastic and is sampled from the distribution . In the realizable case, it is assumed that the learner knows some such that and is asked to match the performance as with an algorithm that does know . Once again, assuming that the learner knows such an is unrealistic if the environment can predict the learner, and once again, agnostic guarantees do not give us anything useful (in fact no guarantees even exist when the number of arms is infinite).
Our results
In our paper, we apply similar reasoning as before and define a robust version of the bandit problem using partial specifications of the environment. The exact formulation was proposed in a previous paper, where only the statistical complexity of the problem was explored. Here we identify a general class of instances where learning can be done in a computationally efficient way. We also identify several instances where efficient learning is NP-hard.
More concretely, the learner chooses an arm from a Euclidean ball and observes an outcome in another Euclidean ball . The reward is a known linear function . Each hypothesis specifies affine constraints on the expected value of the adversary's chosen outcome distribution, of the form
The learner does not know the matrices or the vector . These constraints need not determine the expected outcome uniquely, so the adversary still has a choice of distributions at each arm.
We give a learner with expected regret after rounds. Here regret compares the learner's total expected reward with times the best reward per round guaranteed by the true hypothesis. The bound grows polynomially with the problem parameters, and hides logarithmic factors in . The learner runs in time polynomial in and the size of the instance description. Thus we obtain both a statistical guarantee and an algorithm that can achieve it efficiently. The dependence is optimal up to logarithmic factors.
We also show that several natural changes to this setting make the problem NP-hard. For example, this happens if we replace the outcome ball by a simplex, or allow the arm set to be a general convex polytope specified by linear inequalities.
This gives us the first steps towards building computationally and statistically efficient learners in environments that are able to simulate the learner. Next step is to generalize the results to learning protocols that involve more complex interactions.
Thanks to Vanessa Kosoy and Marcus Ogren for reviewing a draft and making several suggestions that significantly improved the quality of this article.
Vanessa Kosoy and I recently uploaded a new paper to arXiv. In this post, I briefly describe what the paper does, and attempt to explain in a self-contained way why this is a useful thing to do for ASI alignment. For a more complete background, see several previous articles.
The technical contribution of the paper is two-fold. First, we identify a class of instances of the robust bandits problem that can be learned both statistically and computationally efficiently. Previous work on the problem had only identified a class that was statistically tractable. Second, we show that most ways to generalize this class of instances makes the problem NP-hard. Thus in some sense this class is at the boundary of what's computationally tractable.
But what does the computational tractability of robust bandits have to do with ASI alignment? The thesis motivating this paper is that for ASI alignment, we need to build learning algorithms that: a) come with proofs of their statistical and computational efficiency, and b) work in environments where classical learning theoretic frameworks fail to capture phenomena that arise due to embedded agency. The "robust" in robust bandits is a way to handle embedded agency, and similar ideas have been used before for learning problems other than bandits, albeit with different names. Bandits are one of the simplest learning problems to study that still involve interactions with the environment, thus they are a good stepping stone before solving robust versions of more complex problems. Below, I will first explain why we think an aligned ASI will be a learning agent, then I will define what we mean by computational and statistical complexity and motivate why it is important for the learner to be tractable, and finally explain how we use robustness to tackle embeddedness.
Why learning?
Unless we stop ASI development altogether, the only remaining possibilities are: a) make currently existing ASI development approaches safe, b) invent a new approach that has safety baked into it. In either case we are likely going to deal with entities that are very good at learning. This is pretty much by design. ASI development is inherently about automating tasks that we do not have the specs for. First of all, we are not able to write down the laws of the universe that the ASI is supposed to operate in because we simply don't know them. Also, we aren't even able to precisely write down the goals and objectives we want the ASI to pursue. We think in terms of concepts that seem intuitively clear to us, but are hard to describe precisely. We can see a picture of a cat and know that it's a cat, but we can't write a program from scratch that does the same. We sort of know what's good and what's bad for us but, again, we aren't able to define it. Thus an entity that is able to operate in this universe and pursue goals that are aligned with our intentions needs to both learn about the universe and learn about our intentions. This becomes even more complicated once we realize there will exist other similar entities occupying the universe at the same time trying to learn about each other. Thus learning is going to be an important aspect of ASI alignment.
Computational and statistical tractability
Of course we want our learners to be implementable in the real world with a reasonable amount of computational resources and data. Thus we need them to satisfy some notion of computational and statistical tractability. Below I will make that notion more precise.
One might say that neural networks already require only a reasonable amount of compute and data. So don't they already meet the requirement? For ASI alignment, we want to be able to mathematically prove that the learner will exhibit the desired behaviour after spending a known amount of resources, and we want to be able to prove this before we actually deploy the learner on real-world data. We are nowhere near this sort of guarantee for our current training pipeline. Modern training pipelines have very few provable guarantees, and thus most claims need to be tested with fresh experiments. We cannot afford to do this as model capabilities scale, since a fresh experiment, run without mathematical guarantees, might prove to be catastrophic.
Tractability is a notion that is already studied in computer science and we could attempt to use it directly and require that our learner run in polynomial time and require a polynomial amount of data in the worst case. But this is likely an unnecessarily stringent requirement and neural network training does provide evidence for that. Indeed, it can be shown that neural network training is NP-hard in the worst case, but somehow it still works in the real world. One explanation is that the real world isn't producing worst-case inputs. Thus what we ideally want is a learning algorithm
The guarantees provided in both the AIXI and the SLT literature can be considered from the point of view of this framework. Instead of providing a property
Our paper provides uniform bounds for the class of bandits considered. That is, we provide bounds on statistical and computational complexity that hold for all instances of the robust bandits problem within the class. Thus for the goal of getting a high reward for an unknown bandit instance, we satisfy (a) and (c). We hope that building on this research, in the future we will have something that will also satisfy (b).
Embeddedness and robustness
Learning theory provides several frameworks in which one can study the problem of learning. However, they have shortcomings when it comes to analyzing the kind of learning that an aligned ASI will need to do. In particular, issues around embedded agency do not have a good solution in the classical frameworks.
Consider, for example, the problem of binary sequence prediction such as the one tackled by Solomonoff induction. Let's consider a simpler version where we have a class
Now imagine that the learner is an ASI and the true sequence is being produced by the actual universe. This renders the assumption that we know some finite
But if the universe can predict the learner and simply flip the bit, what guarantee can we even hope to obtain? Clearly, for this worst case universe, the situation is completely and utterly hopeless, and we shouldn't complain even if the learner gets none of its predictions right. But maybe the universe is not a perfect predictor, in which case we should aim to design a learner that can achieve whatever is the best level of prediction possible for this universe. Classically, this is attempted in the form of agnostic guarantees. Here it is assumed that the true sequence is being generated by an adversary, and thus it isn't expected to be in
We take a different approach at formulating these kinds of problems. We stay realizable, but say that each
Sequence prediction is among the simplest of the learning problems. An actual ASI will likely interact with the environment instead of merely making predictions. One of the simplest learning frameworks that model interactions is that of bandits. A bandit problem proceeds sequentially, where at each
Our results
In our paper, we apply similar reasoning as before and define a robust version of the bandit problem using partial specifications of the environment. The exact formulation was proposed in a previous paper, where only the statistical complexity of the problem was explored. Here we identify a general class of instances where learning can be done in a computationally efficient way. We also identify several instances where efficient learning is NP-hard.
More concretely, the learner chooses an arm
The learner does not know the matrices
We give a learner with expected regret
We also show that several natural changes to this setting make the problem NP-hard. For example, this happens if we replace the outcome ball
This gives us the first steps towards building computationally and statistically efficient learners in environments that are able to simulate the learner. Next step is to generalize the results to learning protocols that involve more complex interactions.
Thanks to Vanessa Kosoy and Marcus Ogren for reviewing a draft and making several suggestions that significantly improved the quality of this article.
This has parallels with the Towards Guaranteed Safe AI research agenda. ↩︎