What Does Thompson Sampling Optimize?

Thompson Sampling is one of the most widely used and studied bandit algorithms, known for its simple structure, low regret performance, and solid theoretical guarantees. Yet, in stark contrast to most other families of bandit algorithms, the exact mechanism through which posterior sampling (as introduced by Thompson) is able to "properly" balance exploration and exploitation, remains a mystery. In this paper, we show that the core insight to address this question stems from recasting Thompson Sampling as an online optimization algorithm. To distill this, we introduce a time invariant notion of regret that summarizes cumulative regret across horizons (through a regret bound), leading to a time invariant Bellman-optimal policy. It turns out that Thompson Sampling admits an online optimization form that mimics the structure of the Bellman-optimal policy, where greediness is regularized by a measure of residual uncertainty. When viewed through this new lens of online optimization, Thompson Sampling can be understood and improved in a principled manner, by comparing it against the Bellman-optimal benchmark.

Multi-armed bandits model decisions that require learning while acting, such as choosing treatments or recommendations. Thompson Sampling is a widely used bandit algorithm that makes these decisions by sampling from its current beliefs, but its heuristic nature has made its optimization logic hard to pin down. We show that Thompson Sampling can be understood as an online optimization algorithm, where greediness is balanced against a measure of residual uncertainty. This view connects Thompson Sampling to a Bellman-optimal benchmark, providing a principled way to understand and improve Thompson Sampling.