Thompson采样在贝叶斯多臂赌博机中，错误选择次数不超过最优策略的两倍。
Thompson Sampling Is 2-Competitive for Mistakes
- 基于独立更新的臂模型，证明了Thompson采样的失误率有2倍最优上界。
- 在均值最优臂定义下，该2倍因子已不可改进。
- 适用于固定回合和几何折扣等多种权重场景，适合关注理论性能的读者。
我们研究贝叶斯多臂赌博机模型，证明Thompson采样期望失误次数（即选择次优臂的次数）不超过任何其他策略的两倍。该分析成立的前提是各臂的潜在过程相互独立，且仅在被选取时才演化。对于均值定义最优臂的随机多臂赌博机，此结果证实了Guha与Munagala于2014年提出的猜想，其中因子2已是紧致最优。该结论对任意非递增的轮次权重序列均成立，包括固定回合与几何折扣情形。
原文摘要 · Abstract (English)
We consider Bayesian bandit models and prove that Thompson sampling makes at most twice the expected number of mistakes (selections of a suboptimal arm) as any other policy. Our analysis applies as long as the latent arm processes are independent and each arm evolves only when played. For stochastic bandits with best arm defined via mean reward, this confirms a conjecture of Guha and Munagala from 2014, where the factor $2$ is already best possible. The result holds under any nonincreasing sequence of round weights, including fixed horizon and geometric discounting.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。