arXiv：cs.LG· Vanessa Kosoy, Vinayak Pathak·· 4 小时前AI 评分33
鲁棒 Bandits 的计算可解性研究：识别多项式时间可学习的特例并证明其泛化的 NP 困难性
On the Computational Tractability of Robust Bandits
AI 导读
针对鲁棒 bandits（原不精确 bandits）此前只有 Θ(√T) 遗憾界却无计算保证的问题，本文识别出一个可用多项式时间学习器达到 Õ(√T) 遗憾的特例，并证明该特例的若干小型泛化均为 NP 困难，表明其处于可解边界。作者将其视为面向 AI 对齐问题的不可实现学习计算高效性的微小进展。
正文
Abstract: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.
| Subjects: | Machine Learning (cs.LG) |
| Cite as: | arXiv:2610.08740 [cs.LG] |
| (or arXiv:2610.08740v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.08740 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Vinayak Pathak [view email]
[v1]
Tue, 6 Oct 2026 17:38:34 UTC (50 KB)
来源：arXiv：cs.LG · arxiv.org