# Variational Bayesian Optimistic Sampling

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 41 references that are in the map.
- First posted on arXiv 29 Oct 2021.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Reinforcement Learning with Deep Energy-Based Policies](https://mlsanity.com/paper/1702.08165/) (2017)
- [Reinforcement Learning and Control as Probabilistic Inference: Tutorial and Review](https://mlsanity.com/paper/1805.00909/) (2018)
- [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)
- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Why is Posterior Sampling Better than Optimism for Reinforcement Learning?](https://mlsanity.com/paper/1607.00215/) (2016)
- [Variational Bayesian Reinforcement Learning with Regret Bounds](https://mlsanity.com/paper/1807.09647/) (2018)
- [Making Sense of Reinforcement Learning and Probabilistic Inference](https://mlsanity.com/paper/2001.00805/) (2020)
- [Combining policy gradient and Q-learning](https://mlsanity.com/paper/1611.01626/) (2016)
- [Operator splitting for a homogeneous embedding of the linear complementarity problem](https://mlsanity.com/paper/2004.02177/) (2020)
- [Thompson Sampling with Approximate Inference](https://mlsanity.com/paper/1908.04970/) (2019)
- [On Thompson Sampling with Langevin Algorithms](https://mlsanity.com/paper/2002.10002/) (2020)
- [A Note on KL-UCB+ Policy for the Stochastic Bandit](https://mlsanity.com/paper/1903.07839/) (2019)
- [A short variational proof of equivalence between policy gradients and soft Q learning](https://mlsanity.com/paper/1712.08650/) (2017)

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

- [ReLOAD: Reinforcement Learning with Optimistic Ascent-Descent for Last-Iterate Convergence in Constrained MDPs](https://mlsanity.com/paper/2302.01275/) (2023)
- [Probabilistic Inference in Reinforcement Learning Done Right](https://mlsanity.com/paper/2311.13294/) (2023)
- [Efficient Exploration via Epistemic-Risk-Seeking Policy Optimization](https://mlsanity.com/paper/2302.09339/) (2023)
- [Thompson Sampling via Fine-Tuning of LLMs](https://mlsanity.com/paper/2510.13328/) (2025)
- [LITE: Efficiently Estimating Gaussian Probability of Maximality](https://mlsanity.com/paper/2501.13535/) (2025)
- [Optimal Regret Is Achievable with Bounded Approximate Inference Error: An Enhanced Bayesian Upper Confidence Bound Framework](https://mlsanity.com/paper/2201.12955/) (2022)
- [Thompson Sampling for Learning in Zero-Sum Games](https://mlsanity.com/paper/2610.18899/) (2026)

## Abstract (arXiv)

We consider online sequential decision problems where an agent must balance exploration and exploitation. We derive a set of Bayesian `optimistic' policies which, in the stochastic multi-armed bandit case, includes the Thompson sampling policy. We provide a new analysis showing that any algorithm producing policies in the optimistic set enjoys tilde O(√AT) Bayesian regret for a problem with A actions after T rounds. We extend the regret analysis for optimistic policies to bilinear saddle-point problems which include zero-sum matrix games and constrained bandits as special cases. In this case we show that Thompson sampling can produce policies outside of the optimistic set and suffer linear regret in some instances. Finding a policy inside the optimistic set amounts to solving a convex optimization problem and we call the resulting algorithm `variational Bayesian optimistic sampling' (VBOS). The procedure works for any posteriors, ie, it does not require the posterior to have any special properties, such as log-concavity, unimodality, or smoothness. The variational view of the problem has many useful properties, including the ability to tune the exploration-exploitation tradeoff, add regularization, incorporate constraints, and linearly parameterize the policy.