PaperlayerView exact revision on arXiv

Source-linked AI summary

Deep Bayesian Bandits Showdown: An Empirical Comparison of Bayesian Deep Networks for Thompson Sampling

Carlos Riquelme, George Tucker, Jasper Snoek

arXiv:1802.09127v1stat.MLcs.LG

TL;DR

Reliable uncertainty estimation is needed for exploration with deep neural networks, but exact posteriors are generally intractable and approximate methods have been insufficiently evaluated for sequential decisions. The paper benchmarks Bayesian posterior approximations combined with Thompson Sampling on contextual bandits and finds that many methods successful in supervised learning underperform online, especially when uncertainty estimates converge slowly. The results favor robust uncertainty estimation on learned representations while exposing practical limitations of coupled, heavily optimized approaches.

  • Problem

    Reliable uncertainty estimates are difficult for deep neural networks, yet they are needed to balance exploration and exploitation in sequential decision making.

  • Method

    The paper empirically benchmarks diverse approximate Bayesian posterior methods combined with Thompson Sampling across contextual bandit problems.

  • Results

    Many approximate methods underperformed in sequential decision making, while robust methods measured uncertainty on learned representations and coupled approaches required heavier training.

  • Takeaways & Limitations

    Decoupling representation learning from uncertainty estimation appears promising for practical online decision making.

  • Takeaways & Limitations

    The study is restricted to contextual bandits, and Thompson Sampling can fail when informative actions are not themselves optimal.

Abstract

from arXiv · show

Recent advances in deep reinforcement learning have made significant strides in performance on applications such as Go and Atari games. However, developing practical methods to balance exploration and exploitation in complex domains remains largely unsolved. Thompson Sampling and its extension to reinforcement learning provide an elegant approach to exploration that only requires access to posterior samples of the model. At the same time, advances in approximate Bayesian methods have made posterior approximation for flexible neural network models practical. Thus, it is attractive to consider approximate Bayesian neural networks in a Thompson Sampling framework. To understand the impact of using an approximate posterior on Thompson Sampling, we benchmark well-established and recently developed methods for approximate posterior sampling combined with Thompson Sampling over a series of contextual bandit problems. We found that many approaches that have been successful in the supervised learning setting underperformed in the sequential decision-making scenario. In particular, we highlight the challenge of adapting slowly converging uncertainty estimates to the online setting.

1 INTRODUCTION

Deep neural networks create a need for reliable uncertainty estimates to support exploration in sequential decision making. This paper benchmarks approximate Bayesian posterior methods within Thompson Sampling for contextual bandits.

  • Motivation: Uncertainty estimation remains challenging for neural networks on new data, although it is critical for effective exploration.Neural networks can map complex states to expected returns, but their uncertainty about unfamiliar data is difficult to quantify.
  • Exploration–Exploitation: Efficient sequential decision making requires balancing exploitation with exploratory actions coordinated across the entire process.This coordinated behavior is called deep exploration.
  • Thompson Sampling: Thompson Sampling addresses exploration by maintaining a posterior over models and selecting actions according to their probability of being optimal.Exact posterior maintenance is generally intractable for complex models, motivating approximate Bayesian methods.
  • Contribution: The paper develops a reproducible benchmark comparing established and recent Bayesian approximations under Thompson Sampling for contextual bandits.The implementations are intended to be released open-source for future development.
  • Related Work: Exploration methods based on parameter noise, dropout, and bootstrap sampling have emerged alongside simple strategies such as epsilon-greedy.These methods rely explicitly or implicitly on posterior sampling for exploration.
  • Findings: No single algorithm performed best on every bandit problem, while several methods improved some tasks but failed on challenging synthetic exploration problems.The results motivate examining how posterior approximations behave in sequential decision making rather than supervised learning alone.

2 DECISION-MAKING VIA THOMPSON SAMPLING

The paper studies how approximate model posteriors affect Thompson Sampling in contextual bandits. Thompson Sampling repeatedly samples a plausible model, acts optimally for that sample, observes a reward, and updates its posterior, but approximation errors can interact with data collection.

  • Contextual Bandits: In a contextual bandit, each arriving context is paired with an action choice, an observed reward, and a possible model update.The process continues over n rounds, producing cumulative reward and regret relative to an optimal policy.
  • Research Question: The research question is how approximate model posteriors affect Thompson Sampling decisions across empirical and synthetic contextual-bandit problems.The study compares multiple posterior-approximation approaches and problem types.
  • Thompson Sampling: Thompson Sampling samples a model from the posterior, selects the greedy action for that sampled model, observes the reward, and updates the posterior.The method requires posterior samples rather than direct access to the full posterior.
  • Assumptions and Caveats: The analysis assumes that accurate posterior approximations generally support efficient decisions, while acknowledging that Thompson Sampling can fail when informative actions are never optimal.The method also does not account for a known finite time horizon when allocating exploration.

3 ALGORITHMS

The benchmark evaluates linear, neural, variational, sampling-based, dropout, bootstrap, noise-injection, and Gaussian-process approaches for approximating posteriors in Thompson Sampling. A central design choice is whether representation learning and uncertainty estimation are coupled or separated.

  • Algorithmic Scope: The evaluated methods span linear models, Neural Linear, Neural Greedy, variational inference, expectation propagation, dropout, MCMC, bootstrapping, noise injection, and Gaussian processes.These design principles are compared in the paper’s contextual-bandit simulations.
  • Linear Methods: Exact Bayesian linear regression provides a computationally efficient online baseline for models with linear reward structure and Gaussian noise.The method uses closed-form posterior updates.
  • Posterior Approximations: Diagonal covariance approximations replace full parameter correlations when computing the complete posterior is too expensive.The study examines two diagonal approximations motivated by high-dimensional function approximators.
  • Neural Linear: Neural Linear learns a deep representation independently and applies Bayesian linear regression to estimate uncertainty over the resulting linear reward model.The network and regression can be updated at different time scales, with regression updates incorporating new data immediately.
  • Approximate Inference: Variational inference optimizes a tractable distribution toward the posterior, while expectation propagation updates local approximation factors using message passing.The implemented black-box α-divergence method connects different α values to common inference algorithms.
  • Sampling-Based Methods: Dropout, bootstrap, and direct noise injection generate decision-time randomness through stochastic subnetworks, sampled models, or perturbed network weights.Bootstrap models receive new observations independently with probability p before one model is sampled for action selection.
  • Gaussian Processes: Gaussian processes serve as a nonlinear Bayesian baseline, but standard implementations scale cubically with the number of observations.This computational scaling limits their applicability to larger sequential datasets.

4 FEEDBACK LOOP IN THE LINEAR CASE

The section examines how posterior approximations interact with sequential data collection, creating a feedback loop absent from static supervised learning. Linear examples show that approximation-induced disagreement can alter decisions and regret.

  • Static versus dynamic settings: Sequential posterior quality is harder to assess because approximate posteriors influence the actions that determine future observations.Unlike static learning with i.i.d. data, dynamic data collection depends on the estimate used for decision-making.
  • Static versus dynamic settings: Posterior closeness to the Thompson Sampling reference posterior is associated with strong performance, but comparing posteriors becomes difficult after different decisions collect different data.The paper notes that action-dependent data makes posterior distributions difficult to compare across algorithms.
  • Linear setup: The illustrative setup uses k = 6 arms, contextual dimension d = 20, and a Gaussian prior β ∼N(0, λ I_d).The example models rewards linearly and uses Bayesian linear-regression posteriors.
  • Linear feedback loop: After 500 pulls, independently collected data produced stronger posterior disagreement for diagonal approximations than when the same approximation used data collected by the exact posterior.The comparison isolates the feedback loop from the diagonal approximation’s inability to represent correlations.
  • Linear feedback loop: The linear examples compare the exact posterior with Diag and PrecisionDiag approximations and examine their consequences for cumulative regret.Figure 2 visualizes the exact, diagonal, and precision-based posterior approximations alongside regret behavior.

5 EMPIRICAL EVALUATION

The empirical evaluation tests posterior-sampling algorithms on real-world and synthetic contextual bandits using cumulative and simple regret. It includes shared neural-network and update settings, linear baselines, and a wheel bandit with controllable exploration demands.

  • Experimental framework: The evaluation covers synthetic and real-world contextual bandits, separating experiments by data-generation process and the models fitted by the algorithms.Real datasets include Mushroom, Statlog, Covertype, Financial, Jester, Adult, Census, and Song.
  • Implementation: Neural-network algorithms share a fully connected network with two hidden layers of 100 units, ReLU activations, and one output per action.Each training point observes only the loss associated with the selected action.
  • Implementation: Neural networks are trained for 20 or 100 mini-batches every 20 time-steps, while linear algorithms are updated after each time-step.The schedule reflects the tension between updating frequently and making decisions immediately online.
  • Metrics: The reported metrics are cumulative regret and simple regret, with simple regret approximated by mean cumulative regret over the last 500 time-steps.Cumulative regret uses the best expected reward as its reference.
  • Baselines: Linear models provide a baseline because their exact posterior can be computed, enabling direct comparison with approximate posterior methods.The same datasets are used for the linear comparison.
  • Wheel bandit: The wheel bandit sets d = 2, k = 5, and varies δ ∈(0, 1) to control the region where context-dependent high-reward actions are optimal.Action 1 is context-independent, while actions 2–5 are optimal in different regions outside the central circle.

6 DISCUSSION

The benchmark reveals that online uncertainty estimation remains a central weakness: slowly converging methods can make poor decisions when optimization is truncated, while decoupling representation learning from uncertainty estimation appears promising. Performance is strongly problem-dependent, with no single algorithm consistently best across bandits.

  • Overall Findings: Slowly converging uncertainty estimates are disadvantaged online because practical optimization must be truncated between frequent model updates.Partially optimized uncertainty estimates can lead to catastrophic decisions and poor performance.
  • Linear Methods: Linear methods provide surprisingly strong baselines because their uncertainty estimates are informative and their updates are immediate, deterministic, and exact.Their limited representation power remains a constraint, but they can react quickly to unexpected or extreme rewards.
  • Linear Methods: Diagonalizing the precision matrix performs dramatically better than diagonalizing the covariance matrix in diagonal linear approximations.
  • NeuralLinear: NeuralLinear appears promising because it separates representation learning from uncertainty estimation and solves the Bayesian linear component exactly.In the Wheel problem, its performance was almost an order of magnitude better than RMS-based algorithms and greedy linear approaches.
  • Variational Inference: Bayes By Backprop improves with more training epochs but remains worse than the exact mean-field solution, indicating that partial variational optimization is insufficient online.The effect of training-step count outweighed the difference between the mean-field approximation and the exact posterior.

7 CONCLUSIONS AND FUTURE WORK

The paper empirically studies approximate model posteriors for Thompson Sampling in contextual bandits and finds that exact uncertainty estimation atop learned representations is most robust. Jointly learning representations and uncertainty can require heavier training, creating a drawback for online decision-making.

  • The most robust methods measured uncertainty exactly, even when using potentially incorrect model assumptions, on top of complex representations learned in parallel.
  • Methods that jointly learn representations and uncertainty appeared to require heavier training, which is an important drawback in online scenarios.

APPENDIX

The appendix documents benchmark summaries, training defaults, regret and runtime tables, and posterior visualizations used to compare algorithms across contextual bandit problems.

  • Figure 5 summarizes each algorithm’s ranks across the benchmark suite using boxplots, with red and black lines marking median and mean rank.
  • The default nonlinear-experiment configuration uses ts = 20 mini-batches per training period and tf = 20 contexts between training periods.
  • The default linear-experiment configuration increases training to ts = 100 mini-batches while retaining tf = 20 contexts between training periods.
  • The appendix reports cumulative regret, simple regret, and elapsed time across the real-data bandits, with results averaged over independent trials and normalized where specified.
  • Wheel-bandit tables evaluate cumulative and simple regret as the exploration parameter δ increases, while Figure 6 compares posterior sample distributions with true functions.

A REAL-WORLD DATASETS

The real-world benchmark suite spans eight datasets converted into contextual bandits with varied dimensions, action counts, reward structures, sample sizes, and exploration demands.

  • The Mushroom bandit asks whether to eat each mushroom, rewarding safe choices with +5 and making poisonous-mushroom rewards stochastic at +5 or -35.
  • Statlog predicts one of k = 7 shuttle radiator states from d = 9 indicators, with reward 1 for the correct state and 0 otherwise; one action is optimal in 80% of cases.
  • Covertype classifies forest areas into k = 7 classes using d = 54 features, with reward 1 for a correct class and 0 otherwise.
  • Financial uses d = 21 stock-price contexts to choose among k = 8 synthetic portfolio arms over n = 3713 days.
  • Jester recommends one of k = 8 jokes using d = 32 user-rating features, with the selected joke’s rating as reward.
  • Adult and Census predict occupations from d = 94 and d = 389 covariates, using k = 14 and k = 9 actions respectively with binary rewards for correct predictions.
  • Song predicts one of k = 10 year buckets from d = 90 audio features, assigning decreasing Gaussian rewards based on distance from the correct bucket.
Loading 1802.09127v1…