自适应遗憾在可能的情况下：只需两个查询
内容提要
该文综述多臂赌博机后悔最小化研究，涵盖批处理随机与线性赌博机、对抗性赌博机、非平稳线性臂、上下文推断及路径长度自适应遗憾等方向，提出多种实现最优或接近最优遗憾界的算法，并给出下界与不可能性结果。
延伸解读
从固定遗憾界到自适应难度
文章梳理的多项工作显示，赌博机遗憾最小化正从追求最坏情况下的固定界，转向让算法自动适应问题实际难度。例如批处理算法用对数批次达到最优期望遗憾，路径长度自适应算法则根据损失序列的波动调整界。这种自适应思路减少了对先验难度参数的依赖，更贴近实际部署中难度未知的场景。
批处理与对抗性设定的权衡
文章首次研究批处理对抗性多臂赌博机，并给出预定批处理大小下接近最优的遗憾界。与随机批处理设定不同，对抗性环境要求算法在更少信息反馈下保持稳健。读者需注意，批处理约束会限制探索频率，而对抗性假设又削弱了利用随机性的空间，两者叠加使遗憾界通常比随机设定更宽松。
非平稳环境下的重启与动态遗憾
针对非平稳线性臂，文章介绍基于重启策略的算法，通过定期重置来平衡利用与探索，并证明其动态遗憾。同时，上下文推断工作强调动态适应分布变化。这些结果表明，在环境变化时，主动遗忘旧信息可能比持续累积更有效。但重启频率的选择依赖对变化程度的假设，实际中需谨慎设定。
下界与不可能性结果的警示
文章包含对抗性赌博机的下界和两个不可能性结果：单臂最优和遗憾不能随损失范围提高而扩展，而完全信息设定下却可能。这提醒读者，部分算法性能上限并非技术不足，而是问题结构本身决定。评估新算法时，应对照这些下界判断其是否已接近理论极限，避免对遗憾界的改进空间产生不切实际预期。
Q&A
多臂赌博机中，当存在多个最优或近似最优臂时，如何最小化后悔？
论文提出自适应算法来自动适应问题的难度，从而在存在多个最优/近似最优臂的情况下最小化后悔，并在理论和实验上展示了优越性。
批处理随机多臂赌博机问题有哪些高效的算法？
论文提出了简单有效的算法，仅使用对数数量的批次就能实现最优期望遗憾界，适用于批处理随机多臂赌博机和线性随机多臂赌博机。
对抗性多臂赌博机问题中，批处理大小对遗憾界有什么影响？
论文首次研究了批处理对抗性多臂赌博机问题，发现了任何算法的最佳遗憾界（对数因子除外）所对应的预定批处理大小。
非平稳线性臂问题中，如何平衡利用和探索？
论文提出了一种基于重启策略的算法来平衡利用和探索，并证明了该算法的动态遗憾值，同时解决了现有算法中的严重技术缺陷。
上下文推断在非平稳环境中有什么高效算法？
论文开发了多种高效的上下文推断算法，能够动态适应分布变化，并在时间和空间成本上达到最优效果。
路径长度自适应遗憾在赌博机问题中如何实现？
论文研究了自适应遗憾边界，提出了新型算法来解决多臂赌博机和线性赌博机上的路径长度边界，并扩展到线性赌博机，提出了基于乐观镜像下降框架的简单追踪算法和动态遗憾结果。
