On the Computational Tractability of Robust Bandits

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 appro