Approximate Thompson Sampling for Sequential Decision Making

This direction is no longer present in the current build. Its last version stays readable and citable here.

Version 1 of 136 papers56 conceptsfrozen 2026-10-04

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:

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.

Papers in this version

History & citationVersion 1 · 2026-10-04

No longer present in the current build · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_approximate_thompson_sampling_for_sequen_cea367c4,
  title = {Approximate Thompson Sampling for Sequential Decision Making},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/approximate-thompson-sampling-for-sequential-decision-making/rdr_cea367c4dc6342e3a3ff452e04ab86c7},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_approximate_thompson_sampling_for_sequen_cea367c4_v1,
  title = {Approximate Thompson Sampling for Sequential Decision Making},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/approximate-thompson-sampling-for-sequential-decision-making/rdr_cea367c4dc6342e3a3ff452e04ab86c7/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}