# On the Computational Tractability of Robust Bandits

arXiv: https://arxiv.org/abs/2610.08740 · HTML: https://mlsanity.com/paper/2610.08740/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 81 references that are in the map.
- First posted on arXiv 6 Oct 2026.

## Builds on (most cited first, 23 of 23)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Deep reinforcement learning from human preferences](https://mlsanity.com/paper/1706.03741/) (2017)
- [Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2204.05862/) (2022)
- [Concrete Problems in AI Safety](https://mlsanity.com/paper/1606.06565/) (2016)
- [Open Problems and Fundamental Limitations of Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2307.15217/) (2023)
- [Scalable agent alignment via reward modeling: a research direction](https://mlsanity.com/paper/1811.07871/) (2018)
- [Cooperative Inverse Reinforcement Learning](https://mlsanity.com/paper/1606.03137/) (2016)
- [Risks from Learned Optimization in Advanced Machine Learning Systems](https://mlsanity.com/paper/1906.01820/) (2019)
- [The Alignment Problem from a Deep Learning Perspective](https://mlsanity.com/paper/2209.00626/) (2022)
- [Inverse Reward Design](https://mlsanity.com/paper/1711.02827/) (2017)
- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Reward-rational (implicit) choice: A unifying formalism for reward learning](https://mlsanity.com/paper/2002.04833/) (2020)
- [Occam's razor is insufficient to infer the preferences of irrational agents](https://mlsanity.com/paper/1712.05812/) (2017)
- [Preferences Implicit in the State of the World](https://mlsanity.com/paper/1902.04198/) (2019)
- [Embedded Agency](https://mlsanity.com/paper/1902.09469/) (2019)
- [Robust Cooperation in the Prisoner's Dilemma: Program Equilibrium via Provability Logic](https://mlsanity.com/paper/1401.5577/) (2014)
- [When is Agnostic Reinforcement Learning Statistically Tractable?](https://mlsanity.com/paper/2310.06113/) (2023)
- [A Formal Solution to the Grain of Truth Problem](https://mlsanity.com/paper/1609.05058/) (2016)
- [Reflective Oracles: A Foundation for Classical Game Theory](https://mlsanity.com/paper/1508.04145/) (2015)
- [Learning with Multiple Correct Answers -- Regret Bounds under Different Feedback Models](https://mlsanity.com/paper/2602.09402/) (2026)
- [Imprecise Multi-Armed Bandits](https://mlsanity.com/paper/2405.05673/) (2024)
- [Limit-Computable Grains of Truth for Arbitrary Computable Extensive-Form (Un)Known Games](https://mlsanity.com/paper/2508.16245/) (2025)
- [Agnostic Reinforcement Learning: Foundations and Algorithms](https://mlsanity.com/paper/2506.01884/) (2025)

## Abstract (arXiv)

Learning when the environment does not belong to the learner's hypothesis class is typically handled using agnostic learning guarantees. However, for anything beyond supervised learning, agnostic guarantees are difficult to come by. Recently, imprecise bandits (Kosoy, 2025) (later renamed to robust bandits in Appel and Kosoy, 2025) were introduced as another approach to unrealizable learning in the bandits setting and a Theta(√T) regret learner was shown for a large class. However, no computational guarantees were provided. In this paper we identify a special case that admits a polynomial-time learner with tildeO(√T) regret. We also show that several small generalizations of this special case are NP-hard thus indicating that the special case is at the boundary of what is tractable. It has been recently suggested (Kosoy, 2018) that computationally efficient learners for unrealizable learning problems are crucial for solving the AI alignment problem. This work is a small step in that direction.