Further Optimal Regret Bounds for Thompson Sampling
Shipra Agrawal Microsoft Research India Navin Goyal Microsoft Research India
Abstract
Thompson Sampling is one of the oldest heuristics for multi-armed bandit problems. It is a randomized algorithm based on Bayesian ideas, and has recently generated significant interest after several studies demonstrated it to have better empirical performance compared to the state of the art methods. In this paper, we provide a novel regret analysis for Thompson Sampling that simultaneously proves both the optimal problem-dependent bound of $(1+\epsilon)\sum_{i}\frac{\ln T}{\Delta_{i}}+O(\frac{N}{\epsilon^{2}})$ and the first near-optimal problem-independent bound of $O(\sqrt{NT\ln T})$ on the expected regret of this algorithm. Our near-optimal problem-independent bound solves a COLT 2012 open problem of Chapelle and Li. The optimal problem-dependent regret bound for this problem was first proven recently by Kaufmann et al. [14]. Our novel martingale-based analysis techniques are conceptually simple, easily extend to distributions other than the Beta distribution, and also extend to the more general contextual bandits setting [2].
中文速览
汤普森采样（Thompson Sampling）是一种经典的多臂老虎机（multi-armed bandit）算法，虽然在实际中表现优异、广泛应用，但长期缺乏严格的理论保证。这篇论文用一套基于鞅（martingale）的新分析框架，同时证明了两类遗憾界：与信息论下界匹配的最优"问题相关界"$O(\ln T / \Delta_i)$，以及首个近最优"问题无关界"$O(\sqrt{NT \ln T})$，后者解决了 Chapelle 和 Li 在 COLT 2012 上提出的公开问题。核心思路是证明：在任意历史条件下，算法选择某个次优臂的概率，可以被选择最优臂的概率的线性函数所控制，且该线性系数随最优臂被选次数的增加呈指数衰减。这一分析方法不仅比已有工作更简洁，还能自然推广到 Beta 分布以外的奖励分布以及更复杂的上下文老虎机（contextual bandits）场景，为汤普森采样的广泛应用提供了坚实的理论支撑。
原文 arXiv:1209.3353;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1209.3353v1