多臂老虎机遗憾界大突破：从根号KT/A直接降到(K-A)/根号KA！
Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivit
📖 AI 总结
本文研究具有多个最优臂的多臂老虎机问题，其动机在于许多实际决策场景存在多个正确答案。针对含A个最优臂的K臂老虎机，作者首先对已有的子采样算法进行更精细的分析，将最小最大遗憾从先前的Õ(√(KT/A))改进为Õ((K−A)/√(KA)·√T)，并给出匹配的下界，证明该速率在对数因子范围内接近最优。研究进一步表明，要获得近最优遗憾，必须知道A至多相差Õ(1)倍，因为针对某一最优臂数量的近最优算法在最优臂数量更少时会带来显著更大的遗憾。该工作完整刻画了1≤A≤K−1整个范围内K臂老虎机的最小最大遗憾特性，为多最优解场景下的决策问题提供了理论基准。
🔑 关键词速览
| 多臂老虎机 (MAB) | 一种序贯决策模型，智能体在多个选项（臂）中选择并观察奖励，目标是在探索与利用之间权衡以最大化累积奖励。 |
| 最优臂 (Optimal Arms) | 在多臂老虎机中，指那些具有最高期望奖励的臂，可能存在多个。 |
| 极小极大遗憾 (Minimax Regret) | 衡量算法在最坏情况下的性能损失，即算法累积奖励与最优策略累积奖励之差的最大值。 |
| 子采样算法 (Sub-sampling Algorithms) | 一类通过从原始臂集合中随机或确定性子采样来减少有效臂数量的算法，常用于处理多个最优臂的情况。 |
| 下界 (Lower Bound) | 理论证明任何算法在特定问题实例上的遗憾至少达到某个值，用于评估算法的近似最优性。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅