🤖 machine learning

A Broader View of Thompson Sampling

This paper elucidates the mechanism behind Thompson Sampling's success by recasting it as an online optimization algorithm that mimics a stationary Bellman-optimal policy, where greediness is regularized by residual uncertainty, thereby offering a new framework for understanding its dynamics and improving policies.

Original authors: Yanlin Qu, Hongseok Namkoong, Assaf Zeevi

Published 2026-05-28

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Yanlin Qu, Hongseok Namkoong, Assaf Zeevi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Solving the "Mystery" of a Famous Algorithm

Imagine you are a chef trying to find the best recipe for a new dish. You have two ingredients (let's call them Arm 1 and Arm 2), but you don't know which one tastes better. You have to keep cooking to learn, but you also want to serve the best dish to your customers right now. This is the classic "Multi-Armed Bandit" problem: balancing exploration (trying new things to learn) and exploitation (using what you know works best).

For decades, one specific method called Thompson Sampling has been the gold standard. It's famous because it works incredibly well in practice. However, unlike other methods where the rules are clear (like "always pick the option with the highest confidence score"), Thompson Sampling felt a bit like magic. It works, but nobody could quite explain why it balances learning and earning so perfectly.

This paper pulls back the curtain. The authors show that Thompson Sampling isn't just a lucky guess; it is actually a sophisticated online optimization algorithm. They discovered that it works by trying to minimize a specific type of "regret" (the difference between what you got and what you could have gotten) while being "regularized" (guided) by a measure of uncertainty.

The Core Idea: A New Way to Measure "Regret"

To understand the paper, we need to look at how they measure success.

The Old Way (Discounted Rewards):
Imagine you are playing a video game where points you get now are worth 100%, but points you get later are worth only 90%, then 81%, and so on. This is called "discounting." The famous Gittins Index policy uses this. It's great for the game, but it has a flaw: it might stop exploring a potentially better option too early because the future points don't seem worth the risk. In the real world, where we want to learn everything possible over a long time, this can be a mistake.

The Paper's New Way (Squared Regret):
The authors propose a new way to look at the problem. Instead of discounting the future, they look at the square of the regret.

Analogy: Imagine you are driving a car.
- Linear Regret: If you drive 1 mile off course, you are 1 mile off. If you drive 10 miles off, you are 10 miles off.
- Squared Regret: If you drive 1 mile off, you are 1 mile off. But if you drive 10 miles off, you are now 100 "units" of bad driving.
- Why this matters: By squaring the error, the algorithm becomes very sensitive to big mistakes. It forces the system to avoid huge errors, which naturally leads to a strategy that explores enough to avoid getting stuck on a bad path, but not so much that it wastes time.

The authors call this "Faithful Stationarization." It's a fancy way of saying: "We found a mathematical rule that stays the same over time (stationary) but still perfectly captures the goal of minimizing long-term mistakes (faithful)."

The "Secret Sauce": Uncertainty vs. Tension

The paper reveals that Thompson Sampling works by solving a math problem that looks like this:

Minimize (Mistake) + (Uncertainty Penalty)

The authors break this down into two competing forces:

Greediness (Exploitation): You want to pick the arm that looks best right now to get the most reward.
Regularization (Exploration): You need a "penalty" to stop you from being too greedy. This penalty is based on how much you don't know.

The Discovery:
The authors found that Thompson Sampling uses a specific type of penalty called Biserial Covariance.

The Metaphor: Imagine you are betting on a horse race.
- Thompson Sampling's Logic: "I am unsure which horse will win. The more unsure I am (the more the horses look similar), the more I should bet on the underdog to see if they can win." It measures Uncertainty.
- The "Bellman-Optimal" Logic (The Ideal): The authors calculated what the perfect algorithm would do. They found the perfect algorithm doesn't just look at uncertainty; it looks at Tension.
- The Metaphor: "I am unsure, but is it worth the risk to switch? If the leading horse is actually very strong and the underdog is weak, even if I'm a little unsure, I shouldn't switch. But if the leading horse is shaky and the underdog is strong, the tension is high, and I must switch."

The Problem:
Thompson Sampling sometimes gets "too curious." It keeps exploring an underperforming option just because there is some uncertainty, even when the "tension" (the benefit of switching) is actually low. It's like checking the oven every 30 seconds because you are nervous, even though the recipe says the cake is fine.

The Solution: A "One-Step" Fix

The paper doesn't just criticize Thompson Sampling; it offers a way to fix it using the same logic that powers the "perfect" algorithm.

They propose a Policy Improvement step.

Analogy: Imagine you are a student taking a test.
- Thompson Sampling: You answer the questions based on your current gut feeling.
- The Improvement: Before you turn in the paper, you take a moment to look at your answers and ask, "If I had known what I know after answering this question, would I have changed my answer?"
- The Result: The authors show that doing this one single step of "looking ahead" fixes almost all of Thompson Sampling's flaws. It transforms the algorithm from being driven purely by "uncertainty" to being driven by "tension."

In their experiments, this single tweak closed 90% of the performance gap between the famous Thompson Sampling and their theoretical "perfect" algorithm.

Summary of Key Takeaways

Thompson Sampling is an Optimizer: It's not just a heuristic; it's an algorithm that minimizes a specific type of squared error.
The Flaw: It relies on "Uncertainty" (how confused I am) rather than "Tension" (is it worth the effort to switch?). This makes it sometimes explore too much.
The Fix: By applying a standard "policy improvement" step (looking one step ahead), we can change the algorithm to focus on "Tension."
The Result: This simple adjustment makes the algorithm nearly perfect, performing almost as well as the theoretical best possible strategy, without needing complex new math.

The paper essentially says: "We figured out the secret recipe for Thompson Sampling. It's great, but if you tweak the spice (the regularization) just a little bit to focus on the right kind of tension, it becomes even better."

Technical Summary: A Broader View of Thompson Sampling

Problem Statement
Thompson Sampling (TS) is a widely used heuristic for the Multi-Armed Bandit (MAB) problem, known for its empirical success and theoretical regret bounds. However, unlike Upper Confidence Bound (UCB) or Gittins index policies, the explicit optimization principle governing TS's balance between exploration and exploitation remains opaque. While Gittins (1979) formulated the Bayesian MAB as a Markov Decision Process (MDP) to derive an optimal policy, that approach relies on infinite-horizon discounted rewards. This formulation leads to "incomplete learning" (failing to identify the optimal arm infinitely often), which contradicts the finite-horizon regret minimization objective central to the MAB literature (Robbins 1952; Lai and Robbins 1985). The paper addresses the gap in understanding TS by seeking a "faithful" stationary formulation that aligns with finite-horizon regret minimization while retaining the tractability of dynamic programming.

Methodology
The authors propose a framework of faithful stationarization to recast the non-stationary finite-horizon regret minimization problem into a stationary online optimization problem.

Squared Regret Objective: Instead of minimizing cumulative regret $R_T$ directly or using discounted rewards, the authors introduce minimizing the cumulative squared regret $R_2$ . They establish a bound $R_T \leq \sqrt{R_2 \cdot T}$ . Minimizing the infinite-horizon sum of squared regrets $R_2(Q; \pi_0) = \mathbb{E}[\sum r^2(q_t; \pi_t)]$ ensures the policy achieves the optimal $O(\sqrt{T})$ regret rate while providing a stationary objective.
Stationary Bellman Equation: This new objective yields a stationary Bellman equation for the value function $V(\pi_t)$ (the minimal future squared regret):
$V(\pi_t) = \min_{q_t} \left[ r^2(q_t; \pi_t) + q_t \cdot \mathbb{E}_{\pi_t}[V(\pi_{t+1}) | A_t = \cdot] \right]$
Unlike the Gittins index (which maximizes linear discounted reward), this minimization is quadratic in the action probabilities, leading to a randomized optimal policy rather than a deterministic one.
Online Optimization Form: Through a change of variables focusing on the expected next-round reward $x_t$ , the authors derive that the $R_2$ -optimal policy ( $Q_{R2}$ ) takes the form of an online optimization problem:
$x_{R2}^t = \arg\min_{x_t} \left[ (\mathbb{E}_{\pi_t}[\max(\theta_1, \theta_2)] - x_t)^2 + \nu_{R2}(\pi_t) x_t \right]$
Here, the first term represents instantaneous exploitation (greediness), and the second term is a linear regularization representing exploration. The regularizer $\nu_{R2}(\pi_t)$ is derived from the Bellman equation and measures the tension between exploration and exploitation (the difference in future value between pulling arms).
Reinterpreting Thompson Sampling: The authors demonstrate that Thompson Sampling admits the exact same online optimization form:
$x_{TS}^t = \arg\min_{x_t} \left[ (\mathbb{E}_{\pi_t}[\max(\theta_1, \theta_2)] - x_t)^2 + \nu_{TS}(\pi_t) x_t \right]$
However, its regularizer $\nu_{TS}(\pi_t)$ is the biserial covariance between the reward gap ( $\theta_1 - \theta_2$ ) and the identity of the optimal arm ( $\text{sign}(\theta_1 - \theta_2)$ ). This regularizer measures uncertainty about which arm is better, rather than the tension between immediate reward and future value.

Key Contributions

Faithful Stationarization: The paper introduces a stationary formulation (minimizing squared regret) that preserves the essence of finite-horizon regret minimization, bridging the gap between heuristic sampling and principled dynamic programming.
Structural Unification: It reveals that both Thompson Sampling and the Bellman-optimal policy ( $Q_{R2}$ ) are instances of online optimization algorithms that trade off greediness against a regularizer.
Mechanism Identification: The paper identifies the specific mechanism driving TS: it regularizes greediness based on uncertainty (biserial covariance), whereas the optimal policy regularizes based on tension (future value difference).
Policy Improvement: Leveraging the Bellman framework, the authors propose a standard policy improvement step for TS. By evaluating the value function of TS and plugging it back into the Bellman equation, they derive an improved policy ( $Q_{TS'}$ ) that uses a tension-based regularizer.

Results

Performance Gap: Numerical experiments on Gaussian and Bernoulli bandits show that the $R_2$ -optimal policy ( $Q_{R2}$ ) achieves significantly lower cumulative regret than Thompson Sampling. The gap is attributed to TS's regularizer being an uncertainty measure that fails to capture the "tension" when the leading arm is uncertain but the suboptimal arm is over-explored.
Information-Directed Sampling (IDS): The paper finds that IDS, another heuristic, shares the same tension-based regularizer structure as $Q_{R2}$ and performs nearly identically to the Bellman-optimal policy, bridging information-theoretic and dynamic programming perspectives.
One-Step Improvement: A single policy improvement step applied to Thompson Sampling closes approximately 90% of the performance gap between TS and the Bellman-optimal benchmark. This improvement effectively transforms TS's regularizer from an uncertainty measure to a tension measure.
Structural Property in K-armed Case: In the $K$ -armed setting, the Bellman-optimal policy (and the improved TS) assigns positive probability to at most two arms at any round, whereas standard TS may assign positive probability to all arms. The policy improvement step grants TS this structural sparsity.

Significance
The paper claims to provide a "broader view" of Thompson Sampling by recasting it as an online optimization algorithm. This lens:

Explains the Heuristic: It clarifies that TS balances exploration and exploitation by regularizing greediness with a measure of residual uncertainty.
Identifies Limitations: It pinpoints that TS's reliance on uncertainty rather than tension leads to suboptimal behavior in specific regimes (e.g., when the optimal arm is uncertain but the suboptimal arm is clearly over-explored).
Enables Principled Improvement: It offers a rigorous framework for improving posterior sampling algorithms. By aligning the regularizer with the Bellman-optimal tension measure, the authors demonstrate that TS can be significantly enhanced with minimal computational overhead (a single policy iteration step), moving it closer to the theoretical optimum without abandoning its sampling-based nature.