Thompson Sampling for the Price of an SGD Step

The figures step through like slides. Use → or ▶, and step back with ←.

1. Thompson sampling turns uncertainty into exploration

Sample one plausible model, act on it, observe, update: the agent goes where the models disagree, as often as they say it might pay off.

A greedy learner plays the best option of the average model and stays at the peak it already knows. Undirected noise, such as ε-greedy, a sampling temperature or an entropy bonus, spends trials everywhere, including on options already known to be bad, and keeps paying for them for as long as it runs. Thompson sampling needed no rule to stop exploring: as the posterior narrowed, the samples stopped disagreeing. Over 200 runs it earns 1.15 per round, against 0.79 for ε-greedy and 0.68 for greedy.

2. With a model, the posterior sample becomes the bottleneck

Every round changes the posterior, so every round needs a new sample, and that sample is the expensive step.

The update is cheap in both cases; the sample is not. What I want is a posterior sample for the price of one update step.

3. The idea: a model that maps simple noise to posterior samples

Give the model a second input, a random index ξ, and train it so that simple noise is pushed forward onto the posterior.

The model is $f_\nu(x, \xi)$, with one set of weights $\nu$ for every index. Sampling then costs one forward pass with a fresh index, and one update step moves every sample at once. In a linear model, where the exact posterior is known and every step can be checked, each sample is a point in parameter space:

The weights are a mean and M stored directions. The rest of this post builds them.

4. A cloud of particles moves with every data point

Store M particles; one cheap step per data point, with noise we inject ourselves, keeps the cloud on the exact posterior.

Two moves make it work. Sampling is a random combination: a Gaussian index weighting M stored arrows is exactly Gaussian, so the only thing to get right is the covariance of the cloud. Updating is a perturbed fit: each particle regresses on its own noisy copy of every response, anchored at its own prior draw:

When a data point arrives, the objective gains one term, so the update is one recursive step. Nothing is reweighted or resampled, which avoids the weight degeneracy of a particle filter (the idea goes back to the ensemble Kalman filter), and no data point is stored.

5. At any time, the same recipe gives a fresh sample

Mean plus stored arrows times a random index: a posterior sample with no square root anywhere.

This is Thompson sampling at the cost of one incremental step per data point and one index per action, with memory equal to the M particles. It rests on one property: the cloud keeps the right covariance as data arrive. Part 2 shows when that holds, why it is harder when the agent picks its own data, how few particles it takes (d log T), and what carries over to a network.

References

• Y. Li, J. Xu, B. Wang, Z.-Q. Luo. Scalable Exploration via Ensemble++. NeurIPS 2025.
• Y. Li, J. Xu, L. Han, Z.-Q. Luo. Q-Star Meets Scalable Posterior Sampling: Bridging Theory and Practice via HyperAgent. ICML 2024.
• Z. Li, Y. Li, Y. Zhang, T. Zhang, Z.-Q. Luo. HyperDQN: A Randomized Exploration Method for Deep Reinforcement Learning. ICLR 2022.
• D. Russo, B. Van Roy, A. Kazerouni, I. Osband, Z. Wen. A Tutorial on Thompson Sampling. 2018.

Citation

@inproceedings{li2025ensemble,
  title     = {Scalable Exploration via Ensemble++},
  author    = {Li, Yingru and Xu, Jiawei and Wang, Baoxiang and Luo, Zhi-Quan},
  booktitle = {Advances in Neural Information Processing Systems},
  year      = {2025}
}