For decades, Thompson Sampling (TS) was treated as a "black box" heuristic—an algorithm that performed exceptionally well in practice but lacked the rigorous mathematical guarantees of its frequentist cousin, the Upper Confidence Bound (UCB) algorithm. Recent research has transformed this landscape, proving that randomized Bayesian exploration is not just a practical trick, but a theoretically optimal strategy for decision-making under uncertainty.
The Intuition of Probability Matching
The core mechanism of Thompson Sampling is probability matching: an agent selects an action with a probability equal to the probability that the action is optimal given the current data.
In practice, this is implemented by sampling a model from the posterior distribution and acting optimally according to that sample. As Shipra Agrawal and Navin Goyal demonstrated in their seminal work, Analysis of Thompson Sampling for the multi-armed bandit problem, this simple randomization naturally balances exploration and exploitation. When uncertainty is high, the posterior is wide, leading to diverse samples (exploration). As more data arrives, the posterior concentrates around the true parameters, and the agent increasingly selects the best action (exploitation).
Why Sampling Beats Rigid Optimism
Traditional frequentist algorithms like UCB rely on "optimism in the face of uncertainty." They construct a confidence interval for each action and pick the one with the highest upper bound. However, Ian Osband and Benjamin Van Roy argue in Why is Posterior Sampling Better than Optimism for Reinforcement Learning that this approach is often too conservative.
Optimistic algorithms typically use "hyper-rectangular" confidence sets—they treat every parameter as if it could simultaneously be at its most optimistic value. In contrast, Posterior Sampling for Reinforcement Learning (PSRL) captures the shape of the true uncertainty. By sampling a single coherent model of the world, PSRL accounts for the correlations between different states and actions. This allows it to achieve Bayesian regret bounds that scale with the square root of the state space, as shown in (More) Efficient Reinforcement Learning via Posterior Sampling, making it far more efficient for large-scale problems.
Measuring Complexity with the Eluder Dimension
To provide a unified theory for both UCB and TS, Daniel Russo and Benjamin Van Roy introduced the eluder dimension in Eluder Dimension and the Sample Complexity of Optimistic Exploration.
The eluder dimension measures how many observations are needed to "uniquely identify" a function within a class. If a reward function has a low eluder dimension (like linear or generalized linear models), Thompson Sampling is guaranteed to learn the optimal policy quickly. This framework allowed Daniel Russo to prove in Learning to Optimize Via Posterior Sampling that posterior sampling is theoretically as robust as deterministic UCB methods across a wide variety of structured reward functions.
Achieving Minimax Optimality
While standard Thompson Sampling is asymptotically optimal, it historically struggled with "worst-case" (minimax) regret because the tails of the posterior distribution could occasionally lead to excessive exploration.
Researchers have recently solved this by introducing "clipping" and "inflation" mechanisms. Pan Xu and colleagues developed MOTS (Minimax Optimal Thompson Sampling) in MOTS: Minimax Optimal Thompson Sampling, which prunes extreme samples to ensure the algorithm never explores more than necessary. Similarly, Tianyuan Jin introduced $\epsilon$-Exploring Thompson Sampling in Thompson Sampling with Less Exploration is Fast and Optimal, showing that by being greedy most of the time and only sampling with probability $\epsilon$, one can achieve the theoretical "gold standard" of simultaneous minimax and asymptotic optimality.
Bridging the Bayesian-Frequentist Divide
A fascinating recent direction is the use of Bayesian Upper Confidence Bounds (BUCB). Instead of sampling from the posterior, algorithms like BUCRL, proposed by Aristide C. Y. Tossou in Near-optimal Bayesian Solution For Unknown Discrete Markov Decision Process, use the quantiles of the posterior distribution to guide exploration.
This approach combines the best of both worlds: it uses the rich uncertainty information of a Bayesian posterior but applies it through a frequentist optimistic lens. As Henry Lam shows in Bayesian Bandit Algorithms with Approximate Inference in Stochastic Linear Bandits, these quantile-based methods can achieve minimax optimal regret even when the posterior is only approximately sampled, providing a robust path forward for complex, high-dimensional reinforcement learning.