Variational Bayesian Optimistic Sampling

Brendan O'Donoghue, Tor Lattimore

TL;DR: VBOS is a novel framework for online decision-making that replaces the random sampling step of Thompson Sampling with a convex optimization problem. By selecting policies from a mathematically defined "optimistic set," VBOS achieves state-of-the-art performance and theoretical guarantees in complex scenarios—such as zero-sum games and constrained bandits—where traditional Thompson Sampling fails.

Introduction: The Limits of Thompson Sampling

In online learning scenarios like the multi-armed bandit problem, an agent must constantly balance exploration (trying new actions to gather information) and exploitation (choosing the best-known action to maximize reward).

Thompson Sampling (TS) is the classic Bayesian approach to this dilemma: the agent samples from its current posterior beliefs about the environment and acts greedily based on that sample. While elegant and often effective, TS suffers from three major limitations:

  1. Intractability: Sampling from complex, non-standard posterior distributions can be computationally expensive or entirely intractable.
  2. Fragility: Small approximation errors during the sampling process can compound, leading to terrible performance (linear regret).
  3. Inflexibility: TS struggles to incorporate external constraints (e.g., budget limits or safety requirements) or account for adversarial opponents in game-theoretic settings.

To address these weaknesses, the authors introduce a more robust, optimization-based alternative that retains the benefits of Bayesian learning while offering greater flexibility and stability.

The VBOS Approach

Instead of generating a single random sample, Variational Bayesian Optimistic Sampling (VBOS) computes an entire probability distribution (a policy) by solving a convex optimization problem.

The VBOS objective function explicitly balances exploitation (expected reward) and exploration (uncertainty penalty).

Key technical components of the VBOS framework include:

  • The Optimistic Set: The authors define a set of policies that satisfy a specific "optimism inequality." They prove that any policy residing in this set—which includes Thompson Sampling—will achieve low regret.
  • Cumulant Generating Functions (CGFs): VBOS uses CGFs of the posterior distributions to bound uncertainty. This mathematical tool allows the algorithm to work with any distribution, freeing it from the assumption of simple, well-behaved distributions like Gaussians.
  • Convex Optimization: Finding the optimal VBOS policy involves maximizing a concave "optimism map" over a probability simplex. For complex problems, this is formulated as an exponential cone program, which modern solvers can handle efficiently.
  • Extension to Saddle-Point Problems: The authors extend this logic to bilinear saddle-point problems, encompassing zero-sum games and bandits with safety or budget constraints.

Experimental Validation

The paper validates the theoretical properties of VBOS using several synthetic experimental setups:

Evolution of the optimistic set (blue region) over time in a 3-armed bandit problem. Both Thompson Sampling (TS) and VBOS remain within this set as it shrinks toward the optimal arm.
  • Three-armed Gaussian Bandits: Used to visualize how the "optimistic set" shrinks and evolves over time as the agent learns the optimal action.
  • 50x50 Random Zero-Sum Games: VBOS was compared against TS, K-learning, UCB, and EXP3 in both self-play and against a best-response opponent.
  • 50x25 Constrained Bandit Problem: A complex scenario featuring 50 actions and 25 hidden constraints that the agent must learn to satisfy while simultaneously maximizing its reward.

Key Findings and Insights

  • TS is Just One Point in a Larger Set: The most significant conceptual insight is that Thompson Sampling is merely a specific instance of a broader class of "optimistic" policies. By viewing the problem through this variational lens, we can actively optimize to find better points within that set.
  • VBOS as "Stochastic Bayesian UCB": While traditional Upper Confidence Bound (UCB) methods require a carefully tuned exploration schedule, VBOS naturally derives its exploration "bonus" directly from the posterior distribution itself.
  • Why TS Fails in Games and Constraints: In zero-sum games or constrained environments, TS can produce policies that are easily exploited by an opponent or violate safety rules because the naive sampling step doesn't account for the opponent's potential reactions or the constraint boundaries. VBOS solves this by including the opponent's feasible space directly in the optimization objective.
  • Theoretical and Empirical Superiority: The authors prove a Bayesian regret bound of $\tilde{O}(\sqrt{AT})$ for bandits and $\tilde{O}(\sqrt{mAT})$ for games/constrained problems, matching the best-known theoretical rates. Empirically, VBOS significantly outperformed all other tested algorithms in zero-sum games against a best-response opponent. In the constrained bandit experiment, VBOS achieved sub-linear regret and zero constraint violations, whereas Thompson Sampling suffered linear regret and failed to satisfy the constraints.

Limitations and Future Directions

While powerful, VBOS does introduce computational overhead. Solving a convex optimization problem at every time step is more computationally intensive than taking simple greedy actions, though the authors argue it is often more efficient than running complex MCMC sampling for intractable distributions.

Currently, the framework focuses on "stateless" problems (bandits and one-step games). Extending VBOS to Markov Decision Processes (MDPs) and full Reinforcement Learning is a promising next frontier. Additionally, using deep neural networks to parameterize the VBOS policy could allow the method to scale to massive, real-world action spaces.

Summary updated

Abstract

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(\sqrt{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.
BibTeX
@inproceedings{odonoghue2021variational,
  author = {Brendan O'Donoghue and Tor Lattimore},
  title = {{Variational Bayesian Optimistic Sampling}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=NtivXxYNhjc},
}
Figure