arXiv cs.LG· Vanessa Kosoy, Vinayak Pathak·· 9 小时前AI 评分17
鲁棒 bandits 的计算可解性研究：识别多项式时间可学习特例并证明其小推广为 NP-hard
On the Computational Tractability of Robust Bandits
AI 导读
针对鲁棒 bandits（原 imprecise bandits）此前只有 Θ(√T) 遗憾保证而无计算保证的问题，研究者识别出一个可用多项式时间学习器实现 Õ(√T) 遗憾的特例，并证明该特例的若干小推广均为 NP-hard，表明其处于可解性边界。作者称这是朝着用计算高效学习器解决 AI 对齐问题方向的一小步。
来源：arXiv cs.LG · arxiv.org