α-TS算法破解汤普森采样难题，遗憾界达最优O(d^{3/2}√T)！
Posterior Tempering Explains Variance Inflation in Linear and Generalized Linear Thompson Sampling
📖 AI 总结
该研究提出了一种名为α-TS的汤普森采样变体，用于解决随机广义线性老虎机问题。现有汤普森采样分析通常需要人为膨胀后验方差以获得接近最优的遗憾界，而本研究通过引入分数阶α-后验正式化了这一方差膨胀机制。主要贡献在于识别了先验与奖励分布的一般正则条件，使得无需对后验分布做可处理近似即可完成α-TS的遗憾分析，突破了以往工作的局限。当选择α与d⁻¹成比例时，该算法在指数族和次高斯奖励分布下均达到目前已知最优的O(d^{3/2}√T log T)遗憾界。研究还提供了依赖α的下界，证明遗憾常数取决于αd的乘积，并解释了上界中d^{3/2}因子的来源。该工作融合了线性老虎机分析的最新进展与贝叶斯统计中的一阶和二阶后验集中理论。
🔑 关键词速览
| Thompson Sampling (TS) | 一种基于贝叶斯后验采样的在线决策算法，用于平衡探索与利用。 |
| α-TS | 使用分数或α后验的汤普森采样变体，通过调整α来控制后验方差膨胀。 |
| generalized linear bandit | 广义线性老虎机，一种在线学习问题，奖励通过广义线性模型与上下文特征关联。 |
| regret bound | 遗憾界，衡量算法性能与最优策略之间累积差异的上界。 |
| posterior concentration | 后验集中，指随着观测数据增加，后验分布逐渐集中于真实参数的性质。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅