# Thompson Sampling with Approximate Inference

arXiv: https://arxiv.org/abs/1908.04970 · HTML: https://mlsanity.com/paper/1908.04970/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Aug 2019.

## Built on by (most cited first, 15 of 15)

- [Bayesian decision-making under misspecified priors with applications to meta-learning](https://mlsanity.com/paper/2107.01509/) (2021)
- [From Predictions to Decisions: The Importance of Joint Predictive Distributions](https://mlsanity.com/paper/2107.09224/) (2021)
- [Low-rank extended Kalman filtering for online learning of neural networks from streaming data](https://mlsanity.com/paper/2305.19535/) (2023)
- [Langevin Monte Carlo for Contextual Bandits](https://mlsanity.com/paper/2206.11254/) (2022)
- [Efficient Online Bayesian Inference for Neural Bandits](https://mlsanity.com/paper/2112.00195/) (2021)
- [Accelerating Approximate Thompson Sampling with Underdamped Langevin Monte Carlo](https://mlsanity.com/paper/2401.11665/) (2024)
- [Variational Bayesian Optimistic Sampling](https://mlsanity.com/paper/2110.15688/) (2021)
- [Fast online inference for nonlinear contextual bandit based on Generative Adversarial Network](https://mlsanity.com/paper/2202.08867/) (2022)
- [Bayesian brains and the R'enyi divergence](https://mlsanity.com/paper/2107.05438/) (2021)
- [Martingale Posterior Neural Networks for Fast Sequential Decision Making](https://mlsanity.com/paper/2506.11898/) (2025)
- [Remote Contextual Bandits](https://mlsanity.com/paper/2202.05182/) (2022)
- [Multiplier Bootstrap-based Exploration](https://mlsanity.com/paper/2302.01543/) (2023)
- [Optimal Regret Is Achievable with Bounded Approximate Inference Error: An Enhanced Bayesian Upper Confidence Bound Framework](https://mlsanity.com/paper/2201.12955/) (2022)
- [Regularized OFU: an Efficient UCB Estimator forNon-linear Contextual Bandit](https://mlsanity.com/paper/2106.15128/) (2021)
- [Bayesian Bandit Algorithms with Approximate Inference in Stochastic Linear Bandits](https://mlsanity.com/paper/2406.14071/) (2024)

## Abstract (arXiv)

We study the effects of approximate inference on the performance of Thompson sampling in the k-armed bandit problems. Thompson sampling is a successful algorithm for online decision-making but requires posterior inference, which often must be approximated in practice. We show that even small constant inference error (in α-divergence) can lead to poor performance (linear regret) due to under-exploration (for α<1) or over-exploration (for α>0) by the approximation. While for α > 0 this is unavoidable, for α ≤ 0 the regret can be improved by adding a small amount of forced exploration even when the inference error is a large constant.