Thompson Sampling is a cornerstone of online decision-making, prized for its ability to balance exploration and exploitation by sampling from a Bayesian posterior. In its ideal form, an agent maintains a distribution over possible worlds, draws a sample, and acts as if that sample were the truth.
However, a significant gap exists between this theoretical elegance and practical implementation. In complex, high-dimensional environments—such as those involving neural networks or combinatorial constraints—calculating the exact posterior is often computationally impossible. For years, the prevailing theoretical wisdom was pessimistic: any constant error in posterior approximation would inevitably lead to linear regret, meaning the agent would fail to converge to the optimal strategy and continue making mistakes indefinitely.
Recent research has overturned this pessimism, demonstrating that Thompson Sampling can remain robust and achieve optimal logarithmic regret even when the posterior is approximated.
The Fragility of Bayesian Exploration
The primary challenge in approximate Thompson Sampling (TS) is that small errors in the sampling process can be amplified by the iterative feedback loop of bandit problems. As Emile Timothy Anand and Sarah Liaw observe in Feel-Good Thompson Sampling for Contextual Bandits, these inaccuracies lead to high run-to-run variability and instability.
In the combinatorial setting, Siwei Wang and Wei Chen showed in Thompson Sampling for Combinatorial Semi-Bandits that utilizing an approximation oracle instead of an exact one can prevent the algorithm from ever identifying the optimal strategy. Similarly, Eric Mazumdar and Michael I. Jordan established in On Approximate Thompson Sampling with Langevin Algorithms that to maintain optimal performance, the approximation error must not just be small—it must actually decrease as the agent gathers more observations.
Efficient Sampling via Langevin Dynamics
To bridge the gap between theory and practice, researchers have turned to gradient-based sampling methods like Langevin Monte Carlo (LMC). These methods allow agents to sample from complex distributions without needing the "conjugate priors" (like Beta or Gaussian distributions) that traditional TS requires.
A major breakthrough in this area involves improving the speed and accuracy of these samplers:
- Acceleration: Haoyang Zheng and Wei Deng introduced Underdamped Langevin Monte Carlo (ULMC) in Accelerating Approximate Thompson Sampling with Underdamped Langevin Monte Carlo, which uses momentum to reduce sample complexity from $\tilde{O}(d)$ to $\tilde{O}(\sqrt{d})$, enabling faster decisions in high-dimensional spaces.
- Broadening Assumptions: Traditional RL theory often relies on restrictive Gaussian assumptions. Christos Dimitrakakis and Emilio Jorge leveraged the Log-Sobolev Inequality (LSI) in Isoperimetry is All We Need to prove that Langevin-based sampling can achieve sublinear regret even in multimodal or perturbed environments.
Achieving Optimality with Constant Error
Perhaps the most surprising recent insight is that we do not always need vanishingly small errors to succeed. Ziyi Huang, Henry Lam, and Haofeng Zhang demonstrated in Optimal Regret Is Achievable with Bounded Approximate Inference Error that Bayesian bandit algorithms can achieve optimal $O(\log T)$ regret even with constant inference error.
The key is not perfect accuracy, but rather ensuring the error remains within specific divergence-based thresholds (such as $\alpha$-divergence). This explains why practitioners often see Thompson Sampling succeed in the wild even when using "imperfect" variational inference or MCMC methods. As further explored in Bayesian Bandit Algorithms with Approximate Inference in Stochastic Linear Bandits, this framework proves that approximate inference preserves the original regret growth rates, justifying the use of computationally efficient methods in production systems.
Robustness to Noisy Contexts and Non-Stationarity
The move toward approximate sampling also enables agents to handle more realistic, "messy" data.
- Measurement Error: Standard bandits fail when context is noisy, a phenomenon known as attenuation bias. Yongyi Guo and Susan A. Murphy developed the Measurement Error Bandit (MEB) in Online learning in bandits with predicted context to maintain sublinear regret when context is predicted rather than observed.
- Deep Representations: In Recurrent Neural-Linear Posterior Sampling, Aditya A. Ramesh and Jürgen Schmidhuber showed that linear posterior sampling can maintain bounded regret even when the underlying features are learned by a recurrent neural network, allowing agents to exploit periodic patterns in non-stationary environments.
By shifting the focus from exact Bayesian updates to bounded approximate inference, this research direction provides the theoretical foundation for deploying Thompson Sampling in the complex, high-stakes environments where it is most needed.