Source-linked AI summary
Ensemble Sampling
Xiuyuan Lu, Benjamin Van Roy
TL;DR
Thompson sampling is difficult to apply when computing and sampling from model posteriors is intractable. This paper develops incremental ensemble sampling as an approximation and analyzes it for linear bandits. Computational results report efficacy on Gaussian bandits and neural-network models.
Problem
Computing and sampling from posterior distributions over models, as basic Thompson sampling requires, is tractable only for simple special cases and becomes intractable for complex models.
Source: §1 · p. 2Method
Ensemble sampling maintains and incrementally updates a finite set of plausible models, sampling from that ensemble to approximate posterior sampling.
Source: §1 · p. 2Results
Computational results show ensemble sampling increasingly approximates Thompson sampling as model count rises on Gaussian bandits and performs better than the reported alternatives in neural-network experiments.
Source: §5.1 · p. 7, §5.2 · p. 8Takeaways & Limitations
The paper provides theoretical assurances for linear bandits and computational evidence of efficacy with complex neural-network models.
Source: §6 · p. 9The formulation assumes a fixed, known reward function and a Bayesian model index θ representing prior uncertainty about the system.
Source: §2 · p. 3
Abstract
from arXiv · showhide
Thompson sampling has emerged as an effective heuristic for a broad range of online decision problems. In its basic form, the algorithm requires computing and sampling from a posterior distribution over models, which is tractable only for simple special cases. This paper develops ensemble sampling, which aims to approximate Thompson sampling while maintaining tractability even in the face of complex models such as neural networks. Ensemble sampling dramatically expands on the range of applications for which Thompson sampling is viable. We establish a theoretical basis that supports the approach and present computational results that offer further insight.
1 Introduction
Thompson sampling selects actions using models sampled from a posterior, but posterior computation can become intractable for complex models. The paper introduces an incremental ensemble approximation, analyzes it for linear bandits, and reports computational results for bandit and neural-network problems.
1 Introduction
- Posterior computation and sampling become intractable for complex models such as neural networks, limiting the tractability of Thompson sampling.The paper notes that Laplace approximations require unimodal posteriors and can be computationally costly for neural networks, while MCMC can also be onerous.Source: §1 · p. 2
- The approach is designed to work without relying on unimodality, with theoretical assurances for linear bandits and computational results on simple bandits and neural networks.The stated regret bound requires a number of models that grows only logarithmically with the decision horizon.Source: §1 · pp. 2–3
- Ensemble sampling incrementally updates statistically plausible models and samples uniformly from the ensemble to approximate posterior sampling.The models are initialized from the prior and updated using data and random perturbations.Source: §1 · p. 2
2 Problem formulation
The formulation models sequential decisions under uncertainty about a system model, with actions producing outcomes and known rewards. It includes linear-bandit and neural-network examples.
2 Problem formulation
- The decisionmaker chooses actions and observes outcomes whose distribution depends on the model index and the preceding action, but not directly on time.Randomness in the model index θ represents prior uncertainty about which model describes the system.Source: §2 · p. 3
- Actions come from a finite set and are selected by a randomized, time-indexed policy, with each action sampled independently from its policy distribution.The reward function is fixed and known, and the optimal action maximizes expected reward under the model.Source: §2 · p. 3
- In the linear-bandit example, the observed reward is the parameter-weighted action plus Gaussian noise.The example specifies a Gaussian prior for the parameter and a finite set of actions.Source: §2 · p. 3
- In the neural-network example, actions are network inputs and observations are network outputs plus noise, with rewards assigned to the observations.The example frames action selection as balancing useful training data against desirable immediate outcomes.Source: §2 · p. 3
3 Algorithms
The algorithms approximate posterior-based action selection by sampling models from an ensemble and updating those models incrementally. The paper describes a perturbed-observation procedure for linear bandits and an analogous neural-network approach.
3 Algorithms
- The ensemble is intended to represent statistically plausible models, but interactions between selected actions and the ensemble can skew its distribution.This interaction makes the approximation more intricate than conventional particle filtering.Source: §3 · p. 4
- Ensemble sampling draws a model uniformly from the ensemble each period, chooses its reward-maximizing action, observes the outcome, and updates every model.The general template requires specifying the model class, prior, and procedures for sampling and updating models.Source: §3 · p. 4
- For linear bandits, each ensemble parameter is fit to a randomly perturbed prior and randomly perturbed observations.For deterministic action sequences, the resulting models are conditionally independent posterior samples; as ensemble size increases, regret approaches that of Thompson sampling.Source: §3 · p. 4
- The neural-network version initializes models from a prior and incrementally updates each with stochastic-gradient steps on a loss function.The paper points to computational results in Section 5.2 as evidence of the approach's viability.Source: §3 · p. 5
4 Analysis of ensemble sampling for the linear bandit
The linear-bandit analysis bounds ensemble sampling's regret relative to Thompson sampling and examines how the discrepancy depends on ensemble size and the action set. The stated bound allows per-period degradation to shrink with a sufficiently large ensemble, while its proof addresses dependencies introduced by ensemble sampling.
4 Analysis of ensemble sampling for the linear bandit
- The analysis addresses dependence between models sampled over time by bounding regret differences as a function of the reward gap, ensemble size, and number of actions.For deterministic action sequences the ensemble models are posterior samples, but the analysis must handle stochastic action sequences selected by ensemble sampling.Source: §4 · pp. 5–6
- Increasing ensemble size can make the per-period regret degradation relative to Thompson sampling arbitrarily small, and the stated bound needs only logarithmic ensemble growth with horizon T.The bound also grows with |A| log |A|; the authors leave a conjectured alternative dependence on the linear dimension for future work.Source: §4 · p. 5
- A Bayesian regret bound can be obtained from the bound conditioned on θ by taking an expectation over θ.The passage presents this as an expectation-based conversion of the conditioned result.Source: §4 · p. 5
- The proof uses action counts and coupling arguments to control the ensemble approximation along stochastic action processes.The authors describe the result as a linear-bandit sanity check and leave formal analysis beyond linear bandits for future work.Source: §4 · pp. 5–6
5 Computational results
The experiments move from Gaussian bandits, where ensemble sampling can be checked against tractable Thompson sampling, to neural-network bandits, where it is compared with ε-greedy and dropout.
5.1 Gaussian bandits with independent arms
- At T = 2000 and ε = 0.03, the minimum ensemble size appears to grow sublinearly with action count; on 50-arm Gaussian bandits, more models better approximate Thompson sampling.Results were averaged over 2,000 realizations for the 50-arm comparison and 10,000 realizations for the ensemble-size comparison.Source: §5.1 · p. 7, Figure 1 · p. 8
5.2 Neural networks
- Ensemble sampling initializes models from the prior, selects one uniformly at random per period, takes its greedy action, and incrementally updates each model using stochastic-gradient steps.The update uses a loss with independently drawn perturbations.Source: §5.2 · p. 8
- On the single-neuron bandit, 10 models outperform best-tuned ε-greedy, and 50 models achieve orders-of-magnitude lower regret.Increasing ensemble size further improves performance.Source: §5.2 · p. 8, Figure 2 · p. 9
- On two-layer neural networks, a moderate-sized ensemble significantly outperforms ε-greedy and dropout.Annealing ε-greedy tends to outperform fixed ε-greedy, while dropout seems to perform worse than ε-greedy.Source: §5.2 · p. 8, Figure 3 · p. 9
6 Conclusion
The conclusion presents ensemble sampling as a potentially efficient approximation to Thompson sampling for complex models, supported by linear-bandit analysis and neural-network experiments. It distinguishes uncertainty representation from ensemble learning and notes that other approximate approaches remain open for analysis.
6 Conclusion
- Ensemble sampling offers a potentially efficient way to approximate Thompson sampling with complex models, with theoretical assurances for linear bandits and computational evidence for neural networks.Source: §6 · p. 9
- Analysis of other forms of approximate Thompson sampling remains open.The conclusion names other approaches to neural-network uncertainty, including.Source: §6 · p. 9
- Unlike ensemble learning’s goal of combining models for accuracy, ensemble sampling uses multiple models to represent posterior uncertainty.Combining the two approaches may offer practical benefit.Source: §6 · pp. 9–10
A Proof of Theorem 3
The proof relates ensemble sampling to Thompson sampling by first establishing posterior-sampling properties and then bounding regret for the ensemble policy.
A Proof of Theorem 3
- For a deterministic action sequence, ensemble particles conditioned on observed rewards are i.i.d. from the posterior Gaussian distribution.Their mean and covariance are the posterior mean and covariance.Source: A Proof of Theorem 3 · p. 10
- For deterministic action sequences, ensemble sampling's action distribution is close to Thompson sampling's with high probability.The proof invokes Sanov’s Theorem to bound the divergence probability.Source: A Proof of Theorem 3 · p. 11
- For any deterministic action sequence, the relevant action probabilities depend on action counts, not the order of past actions and observations.Source: A Proof of Theorem 3 · p. 12
- The proof extends its divergence bound to any adapted action process using a union bound over action-count histories.The number of possible count vectors is bounded by the number of count histories.Source: A Proof of Theorem 3 · p. 12
- The regret argument separates periods with large and small KL divergence, then couples ensemble-sampling and Thompson-sampling actions.Lemma 11 uses the coupling to obtain its regret comparison.Source: A Proof of Theorem 3 · pp. 13–14
- The proof combines Lemmas 10 and 11 to establish its stated main result.The supplied passage does not state the result's bound.Source: A Proof of Theorem 3 · p. 14