线性赌博机新框架：推断质量达√t即可实现最优遗憾！
A Unified Optimism-Agnostic Framework for Linear Bandits over Spherical Action Sets
📖 AI 总结
本文研究球面动作集上的线性赌博机问题，提出一个不依赖乐观原则的统一分析框架。作者证明，只要探索带来的推断质量（以设计矩阵最小特征值衡量）随时间以约根号t的速度增长，且动作分布足够集中以支持利用，算法即可在时间跨度T上达到最优的高概率O(根号T乘logT)遗憾率。该分析不针对特定算法，为经典基于乐观的椭圆势论证提供了替代路径。随后作者表明UCB和Thompson采样及其变体均满足上述推断与集中条件，因而同样享有最优遗憾率。这一模块化框架将参数估计质量与最优遗憾积累显式关联，为线性赌博机算法的分析提供了统一工具。
🔑 关键词速览
| 线性赌博机 | 一种序贯决策模型，其中奖励是决策变量的线性函数，并带有噪声。 |
| 上置信界 (UCB) | 一种基于乐观原则的算法，通过置信上界来平衡探索与利用。 |
| 汤普森采样 (TS) | 一种基于贝叶斯后验采样的算法，通过概率匹配实现探索与利用的平衡。 |
| 遗憾 (Regret) | 衡量算法性能的指标，表示相对于最优策略的累积奖励损失。 |
| 设计矩阵 | 在线性赌博机中，由历史动作向量构成的设计矩阵，其最小特征值影响参数估计质量。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅