论文提出鲁棒老虎机首个多项式时间学习器
On the Computational Tractability of Robust Bandits
搞 bandit 或理论机器学习的可以看看：这论文给 robust bandits 找到了第一个多项式时间算法，遗憾 Õ(√T)，还划清了 NP-hard 边界。
arXiv 论文《On the Computational Tractability of Robust Bandits》研究了无法实现情形下的 bandit 学习。此前 Kosoy（2025）提出的 imprecise bandits 只给出 Θ(√T) 遗憾界，没有计算复杂度保证。本文识别出一个特例，构造出运行时间为多项式、遗憾为 Õ(√T) 的学习器，并证明该特例的几种小幅度推广是 NP-hard 的，说明该特例恰好处于可计算的边界。论文指出这与 Kosoy（2018）关于可计算高效学习器对 AI 对齐重要的观点相关。
On the Computational Tractability of Robust Bandits
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 $Θ(\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.
