Search papers, labs, and topics across Lattice.
This paper investigates the computational tractability of robust bandits, a setting for unrealizable learning where the environment may not conform to the learner's hypothesis class. The authors identify a specific tractable regime that achieves $\tilde{O}(\sqrt{T})$ regret, while demonstrating that minor generalizations of this regime are NP-hard, thus delineating the tractability boundary. This work contributes to the pursuit of computationally efficient learners for unrealizable settings, which are considered crucial for AI alignment.
Robust bandit learning is tractable in a specific setting, but even minor deviations lead to NP-hardness, pinpointing a critical boundary for efficient unrealizable learning.
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(\sqrt{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 $\tilde{O}(\sqrt{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.
