鲁棒 Bandits 的计算可行性边界

论文研究 bandits 中环境不属于学习者假设类时的不可实现学习问题。此前 Kosoy 等提出的不精确/鲁棒 bandits 已有 Θ(√T) 后悔值学习器，但无计算保证。本文识别出一个可用多项式时间学习器达到 Õ(√T) 后悔值的特例，并证明其若干小幅推广为 NP-hard，表明该特例位于可解边界。作者援引观点称不可实现学习问题的高效学习器对 AI 对齐很重要，但本文只是其中一小步。

AI推荐理由 研究鲁棒（不精确）bandits 的计算可行性：识别出一个可用多项式时间学习器达到 Õ(√T) 后悔值的特例，并证明其若干小幅推广为 NP-hard，说明该特例处于可解边界。新信息是首次为该类不可实现学习问题给出计算保证，并刻画其难解边界；作者提及计算高效学习器对 AI 对齐问题的重要性，但属理论工作，短期落地价值有限。