Variational Bayesian Optimistic Sampling

Brendan O'Donoghue, Tor Lattimore

Abstract

Variational Bayesian Optimistic Sampling (VBOS) introduces a principled framework for online decision-making that replaces the stochastic sampling of Thompson Sampling with a deterministic convex optimization problem. By identifying policies within a mathematically defined "optimistic set," VBOS addresses the computational bottlenecks and structural failures of traditional methods in complex environments, such as zero-sum games and constrained bandits.

The Exploration-Exploitation Dilemma

In online learning, agents must constantly balance the exploration-exploitation tradeoff: exploiting known high-reward actions versus exploring new ones to reduce uncertainty. Thompson Sampling (TS) has long been the standard approach, acting greedily based on samples from a posterior distribution. Despite its elegance, TS faces significant hurdles:

  1. Computational Complexity: Sampling from complex posteriors often requires slow Markov Chain Monte Carlo (MCMC) methods.
  2. Rigidity: Incorporating hard safety constraints or adversarial dynamics is non-trivial.
  3. Structural Failure: In multi-player games or constrained settings, TS can suffer from "linear regret," failing to converge to an optimal strategy.

VBOS aims to retain the theoretical strengths of Bayesian methods while providing a more robust and flexible framework for these challenging scenarios.

Methodology: The Optimistic Set

The core innovation of VBOS is the transition from sampling to optimization. Instead of a single action sample, the framework defines an Optimistic Set of policies that are statistically plausible given the current posterior.

Key Components

  • The Optimism Map ($G$): This function balances exploitation (expected reward) with exploration (an uncertainty bonus). The bonus is derived from the Cumulant Generating Function (CGF) of the posterior, which effectively captures tail risks.
  • Variational Optimization: VBOS selects a policy $\pi$ by solving a concave maximization problem over a probability simplex. This approach is computationally efficient and avoids the pitfalls of non-smooth or multi-modal posteriors.
  • Exponential Cone Programming: For complex tasks like zero-sum games, VBOS can be formulated as an exponential cone program, allowing for rapid resolution using modern convex solvers.
Evolution of the optimistic set over time (t=1, 32, 256). As the agent gathers data, the set of optimistic policies shrinks toward the optimal strategy.

Experimental Evaluation

The authors tested VBOS against several benchmarks:

  • Three-armed Gaussian Bandits: To visualize the convergence of the optimistic set.
  • 50x50 Random Zero-Sum Games: Testing performance against adversarial "best-response" opponents.
  • Constrained Bandits: A high-dimensional setup (50 variables, 25 unknown constraints) requiring the agent to maximize rewards while maintaining feasibility.

Key Results and Insights

VBOS demonstrates significant advantages over traditional algorithms:

  • Theoretical Robustness: The authors prove that any policy chosen from the optimistic set achieves a Bayesian regret of $\tilde{O}(\sqrt{AT})$, matching the theoretical gold standard.
  • Superior Performance in Games: In large matrix games, VBOS significantly outperforms TS, UCB, and EXP3. While TS can produce policies that are "not optimistic enough" to handle adversarial exploitation, VBOS remains within the theoretically safe optimistic region.
  • Constraint Satisfaction: In constrained environments, VBOS achieves sub-linear regret and converges to zero constraint violations. In contrast, Thompson Sampling often continues to violate constraints indefinitely.
Regret comparison in a complex decision-making task. VBOS maintains low, sub-linear regret, while traditional methods like UCB and TS exhibit significantly higher regret.

Discussion and Future Directions

VBOS reveals that Thompson Sampling is essentially a specific, sometimes suboptimal, way to select a policy from an optimistic set. Unlike Upper Confidence Bound (UCB) methods, VBOS does not require manual tuning of exploration schedules; its exploration is driven naturally by posterior uncertainty. Furthermore, because VBOS explicitly solves for a distribution ($\pi$), it provides direct access to the agent's strategy, which is vital for safety-critical applications.

While VBOS requires a tractable CGF and involves per-step optimization, it offers a powerful alternative to MCMC-based sampling. Future research may extend these principles to Reinforcement Learning (MDPs) and high-dimensional "Deep VBOS" architectures using neural network parameterization.

Summary updated

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