Every time an autonomous agent interacts with an unknown environment, it faces a fundamental dilemma: should it exploit its current best guess to maximize immediate reward, or explore uncertain options to gather more information? Greedy strategies quickly stall in local optima by ignoring potentially superior choices, while purely random exploration (such as $\epsilon$-greedy) wastes resources on obviously poor options.
Thompson Sampling (also known as posterior sampling) solves this elegantly by framing exploration as a Bayesian optimization problem. Instead of maintaining a single point estimate of an action's value, the agent maintains a probability distribution over its possible values. To choose an action, the agent draws a single sample from each distribution and acts optimally according to those samples.
Why It Works: The Intuition of Posterior Sampling
Why does this simple sampling step perfectly balance exploration and exploitation?
Consider two choices available to an agent:
- Option A (Well-Understood): The agent has tried this option many times. Its reward distribution is narrow, tightly centered around a known, moderate value.
- Option B (Highly Uncertain): The agent has rarely tried this option. Its reward distribution is wide, spanning both very low and very high potential rewards.
Probability Density
^
| | Option A (Narrow)
| / \
| / \ Option B (Wide)
| / \ /---------\
+---/-------\-/-----------\-----> Estimated Reward
When the agent draws a random sample from each distribution, Option A's sample will almost always be close to its known average. However, because Option B's distribution is wide, a random sample drawn from it has a reasonable chance of landing far out in its right tail—yielding a value significantly higher than Option A's sample.
When this happens, the agent selects Option B, effectively exploring it. If Option B turns out to be poor, the feedback shifts its distribution leftward and narrows it, reducing the chance of future high samples. If it turns out to be excellent, its mean shifts rightward, leading to consistent exploitation.
As noted by Joseph Jay Williams et al. in Combining Dynamic A/B Experimentation and Recommender Systems in MOOCs, this mechanism allows Thompson Sampling to achieve lower cumulative regret than standard heuristics by naturally adapting as user feedback is collected.
Extending to Dynamic and Deceptive Environments
The power of Thompson Sampling extends far beyond static multi-armed bandits. In many real-world scenarios, environments are dynamic or even deceptive.
In "restless bandits," the underlying reward distributions change over time regardless of the agent's actions. Young Hun Jung et al. demonstrate in Regret Bounds for Thompson Sampling in Episodic Restless Bandit Problems. that Thompson Sampling can efficiently track and adapt to these shifting dynamics, providing strong theoretical guarantees on learning performance even when the system's dynamics are completely unknown.
When feedback is intentionally or stochastically misleading, standard search heuristics fail. To address this, Sondre Glimsdal et al. combine Thompson Sampling with a comprehensive Bayesian model of the solution space in Thompson Sampling Guided Stochastic Searching on the Line for Deceptive Environments with Applications to Root-Finding Problems. By learning the reliability of the environment's feedback in real-time, the algorithm maintains robust exploration even when individual data points are deceptive.
Bridging Learning and Control
In continuous control systems, exploration can be dangerous or highly inefficient. Traditional control theory often separates system identification (learning the dynamics) from control synthesis (optimizing actions). Thompson Sampling unifies them.
In Control of unknown linear systems with Thompson sampling, Yi Ouyang 0002 et al. apply posterior sampling to the Linear Quadratic control problem. By sampling system parameters directly from the posterior, the controller naturally balances the need to identify unknown system matrices with the mandate to minimize operational costs.
Similarly, Xin Chen et al. leverage this synergy in Online Learning and Distributed Control for Residential Demand Response, combining Gaussian Processes and Thompson Sampling to learn customer opt-out behaviors while dynamically adjusting power consumption in smart grids.
Injecting Uncertainty into Large Language Models
Modern Large Language Models (LLMs) are typically deployed using greedy decoding or temperature-based sampling, which lack a formal notion of epistemic uncertainty (what the model does not know). This often leads to severe under-exploration in sequential decision-making tasks.
To remedy this, Nicolò Felicioni et al. show in On the Importance of Uncertainty in Decision-Making with Large Language Models that integrating Thompson Sampling via Laplace Approximations or Epinets enables LLM agents to actively explore highly uncertain actions, preventing them from prematurely dismissing optimal choices.
This exploration-exploitation perspective also transforms discrete search tasks. In Code Repair with LLMs gives an Exploration-Exploitation Tradeoff, Hao Tang models the iterative refinement of buggy code as a bandit problem. By maintaining Beta distributions over the success probabilities of different code candidates, the proposed REx algorithm decides whether to continue polishing a promising candidate (exploitation) or pivot to an untested branch (exploration), accelerating the search for correct code by up to five times.
Multi-Agent Coordination and Game Theory
Can independent agents using Thompson Sampling coordinate without explicit communication? In game-theoretic settings, the interaction of multiple learning agents often causes instability or collusion.
Surprisingly, Ningyuan Chen et al. prove in No Algorithmic Collusion in Two-Player Blindfolded Games with Thompson Sampling that when two players independently use Thompson Sampling in a repeated game with unknown payoffs, they naturally converge to a Nash equilibrium rather than colluding. The sample-path-wise exploration driven by Thompson Sampling ensures that neither agent gets locked into suboptimal, collusive loops.
Furthermore, in imperfect-information planning, Rinu Boney et al. demonstrate in Learning to Play Imperfect-Information Games by Imitating an Oracle Planner that Thompson Sampling serves as an effective action-selection mechanism for complex planning agents, outperforming standard model-free alternatives.
Widespread Practical Applications
Because Thompson Sampling relies on a clean Bayesian foundation, it scales seamlessly across diverse real-world domains:
- Human-AI Collaboration: Alex James Chan et al. utilize Thompson Sampling in Optimising Human-AI Collaboration by Learning Convincing Explanations to adaptively learn which explanations best foster human trust and decision accuracy. Similarly, Sichao Song et al. use it in What You Reward Is What You Learn: Comparing Rewards for Online Speech Policy Optimization in Public HRI to optimize social robot speech policies based on varying human feedback signals.
- Mobile Health: In Personalized HeartSteps: A Reinforcement Learning Algorithm for Optimizing Physical Activity, Peng Liao et al. incorporate prior knowledge into Thompson Sampling to deliver just-in-time physical activity interventions, drastically reducing learning variance in noisy environments.
- Scientific and Engineering Optimization: Anthony Bilodeau et al. apply it to super-resolution microscopy in Contextual bandit optimization of super-resolution microscopy, balancing image quality against biological sample damage. For large-scale evaluation, Chang Li et al. combine a divide-and-conquer strategy with Thompson Sampling in MergeDTS: A Method for Effective Large-Scale Online Ranker Evaluation to rapidly isolate optimal search rankers. Finally, Pratik Rakesh Singh et al. use it in In-Domain African Languages Translation Using LLMs and Multi-armed Bandits to dynamically select the best neural machine translation models for low-resource languages.
Key Foundational Work
Control of unknown linear systems with Thompson sampling (2017) — contributed 2 concept elements to this direction.
Combining Dynamic A/B Experimentation and Recommender Systems in MOOCs (2016) — contributed 2 concept elements to this direction.