# An Analysis of Ensemble Sampling

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 52 references that are in the map.
- First posted on arXiv 2 Mar 2022.

## Builds on (most cited first, 25 of 25)

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Deep Neural Networks as Gaussian Processes](https://mlsanity.com/paper/1711.00165/) (2017)
- [Deep Exploration via Bootstrapped DQN](https://mlsanity.com/paper/1602.04621/) (2016)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [Randomized Prior Functions for Deep Reinforcement Learning](https://mlsanity.com/paper/1806.03335/) (2018)
- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Deep Exploration via Randomized Value Functions](https://mlsanity.com/paper/1703.07608/) (2017)
- [Simple Bayesian Algorithms for Best Arm Identification](https://mlsanity.com/paper/1602.08448/) (2016)
- [Online Learning with Feedback Graphs: Beyond Bandits](https://mlsanity.com/paper/1502.07617/) (2015)
- [Ensemble Sampling](https://mlsanity.com/paper/1705.07347/) (2017)
- [Hypermodels for Exploration](https://mlsanity.com/paper/2006.07464/) (2020)
- [Efficient Learning in Large-Scale Combinatorial Semi-Bandits](https://mlsanity.com/paper/1406.7443/) (2014)
- [Garbage In, Reward Out: Bootstrapping Exploration in Multi-Armed Bandits](https://mlsanity.com/paper/1811.05154/) (2018)
- [On the Performance of Thompson Sampling on Logistic Bandits](https://mlsanity.com/paper/1905.04654/) (2019)
- [Perturbed-History Exploration in Stochastic Linear Bandits](https://mlsanity.com/paper/1903.09132/) (2019)
- [From Predictions to Decisions: The Importance of Joint Predictive Distributions](https://mlsanity.com/paper/2107.09224/) (2021)
- [Targeting for long-term outcomes](https://mlsanity.com/paper/2010.15835/) (2020)
- [The Neural Testbed: Evaluating Joint Predictions](https://mlsanity.com/paper/2110.04629/) (2021)
- [Thompson sampling with the online bootstrap](https://mlsanity.com/paper/1410.4009/) (2014)
- [Coordinated Exploration in Concurrent Reinforcement Learning](https://mlsanity.com/paper/1802.01282/) (2018)
- [Variational inference for the multi-armed contextual bandit](https://mlsanity.com/paper/1709.03163/) (2017)
- [Deep Exploration for Recommendation Systems](https://mlsanity.com/paper/2109.12509/) (2021)
- [Scalable Thompson Sampling via Optimal Transport](https://mlsanity.com/paper/1902.07239/) (2019)
- [Anti-Concentrated Confidence Bonuses for Scalable Exploration](https://mlsanity.com/paper/2110.11202/) (2021)

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

- [Lifting the Information Ratio: An Information-Theoretic Analysis of Thompson Sampling for Contextual Bandits](https://mlsanity.com/paper/2205.13924/) (2022)
- [Ensembles for Uncertainty Estimation: Benefits of Prior Functions and Bootstrapping](https://mlsanity.com/paper/2206.03633/) (2022)
- [Sample-Efficient Alignment for LLMs](https://mlsanity.com/paper/2411.01493/) (2024)
- [Leveraging Demonstrations to Improve Online Learning: Quality Matters](https://mlsanity.com/paper/2302.03319/) (2023)
- [Scalable Neural Contextual Bandit for Recommender Systems](https://mlsanity.com/paper/2306.14834/) (2023)
- [Waypoint-Based Reinforcement Learning for Robot Manipulation Tasks](https://mlsanity.com/paper/2403.13281/) (2024)
- [Ensemble sampling for linear bandits: small ensembles suffice](https://mlsanity.com/paper/2311.08376/) (2023)
- [Adaptive Elicitation of Latent Information Using Natural Language](https://mlsanity.com/paper/2504.04204/) (2025)
- [Q-Star Meets Scalable Posterior Sampling: Bridging Theory and Practice via HyperAgent](https://mlsanity.com/paper/2402.10228/) (2024)
- [Online Bandit Learning with Offline Preference Data for Improved RLHF](https://mlsanity.com/paper/2406.09574/) (2024)
- [Improved Regret of Linear Ensemble Sampling](https://mlsanity.com/paper/2411.03932/) (2024)
- [Contextual Thompson Sampling via Generation of Missing Data](https://mlsanity.com/paper/2502.07064/) (2025)
- [Best Policy Learning from Trajectory Preference Feedback](https://mlsanity.com/paper/2501.18873/) (2025)
- [Enhancing Diversity in Parallel Agents: A Maximum State Entropy Exploration Story](https://mlsanity.com/paper/2505.01336/) (2025)
- [Multiplier Bootstrap-based Exploration](https://mlsanity.com/paper/2302.01543/) (2023)
- [Contextual Similarity Distillation: Ensemble Uncertainties with a Single Model](https://mlsanity.com/paper/2503.11339/) (2025)
- [Provable Anytime Ensemble Sampling Algorithms in Nonlinear Contextual Bandits](https://mlsanity.com/paper/2510.10730/) (2025)
- [Non-Stationary Contextual Bandit Learning via Neural Predictive Ensemble Sampling](https://mlsanity.com/paper/2310.07786/) (2023)
- [Rethinking Langevin Thompson Sampling from A Stochastic Approximation Perspective](https://mlsanity.com/paper/2510.05023/) (2025)
- [Sharp analysis of linear ensemble sampling](https://mlsanity.com/paper/2602.08026/) (2026)
- [Bayesian Bandit Algorithms with Approximate Inference in Stochastic Linear Bandits](https://mlsanity.com/paper/2406.14071/) (2024)
- [K-Myriad: Jump-starting reinforcement learning with unsupervised parallel agents](https://mlsanity.com/paper/2601.18580/) (2026)
- [DARTS: Targeting Prognostic Covariates in Budget-Constrained Sequential Experiments](https://mlsanity.com/paper/2605.06608/) (2026)
- [Linear Ensemble Sampling with Smaller Ensembles](https://mlsanity.com/paper/2609.13954/) (2026)

## Abstract (arXiv)

Ensemble sampling serves as a practical approximation to Thompson sampling when maintaining an exact posterior distribution over model parameters is computationally intractable. In this paper, we establish a regret bound that ensures desirable behavior when ensemble sampling is applied to the linear bandit problem. This represents the first rigorous regret analysis of ensemble sampling and is made possible by leveraging information-theoretic concepts and novel analytic techniques that may prove useful beyond the scope of this paper.