Ensemble Sampling

Introduction

Thompson sampling has emerged as an effective heuristic for trading off between exploration and exploitation in a broad range of online decision problems. To select an action, the algorithm samples a model of the system from the prevailing posterior distribution and then determines which action maximizes expected immediate reward according to the sampled model. In its basic form, the algorithm requires computing and sampling from a posterior distribution over models, which is tractable only for simple special cases.

With complex models such as neural networks, exact computation of posterior distributions becomes intractable. One can resort to to the Laplace approximation, as discussed, for example, in , but this approach is suitable only when posterior distributions are unimodal, and computations become an obstacle with complex models like neural networks because compute time requirements grow quadratically with the number of parameters. An alternative is to leverage Markov chain Monte Carlo methods, but those are computationally onerous, especially when the model is complex.

A practical approximation to Thompson sampling that can address complex models and problems requiring frequent decisions should facilitate fast incremental updating. That is, the time required per time period to learn from new data and generate a new sample model should be small and should not grow with time. Such a fast incremental method that builds on the Laplace approximation concept is presented in . In this paper, we study a fast incremental method that applies more broadly, without relying on unimodality. As a sanity check we offer theoretical assurances that apply to the special case of linear bandits. We also present computational results involving simple bandit problems as well as complex neural network models that demonstrate efficacy of the approach.

Our approach is inspired by , which applies a similar concept to the more complex context of deep reinforcement learning, but without any theoretical analysis. The essential idea is to maintain and incrementally update an ensemble of statistically plausible models, and to sample uniformly from this set in each time period as an approximation to sampling from the posterior distribution. Each model is initially sampled from the prior, and then updated in a manner that incorporates data and random perturbations that diversify the models. The intention is for the ensemble to approximate the posterior distribution and the variance among models to diminish as the posterior concentrates. We refine this methodology and bound the incremental regret relative to exact Thompson sampling for a broad class of online decision problems. Our bound indicates that it suffices to maintain a number of models that grows only logarithmically with the horizon of the decision problem, ensuring computational tractability of the approach.

Problem formulation

where the expectation is taken over the randomness in actions $A_{t}$ and outcomes $Y_{t}$, conditioned on $\theta$.

We illustrate with a couple of examples that fit our formulation.

(linear bandit) Let $\theta$ be drawn from $\Re^{N}$ and distributed according to a $N(\mu_{0},\Sigma_{0})$ prior. There is a set of $K$ actions $\mathcal{A}\subseteq\Re^{N}$. At each time $t=0,1,\ldots,T-1$, an action $A_{t}\in\mathcal{A}$ is selected, after which a reward $R_{t+1}=Y_{t+1}=\theta^{\top}A_{t}+W_{t+1}$ is observed, where $W_{t+1}\sim N(0,\sigma^{2}_{w})$.

(neural network) Let $g_{\theta}:\Re^{N}\mapsto\Re^{K}$ denote a mapping induced by a neural network with weights $\theta$. Suppose there are $K$ actions $\mathcal{A}\subseteq\Re^{N}$, which serve as inputs to the neural network, and the goal is to select inputs that yield desirable outputs. At each time $t=0,1,\ldots,T-1$, an action $A_{t}\in\mathcal{A}$ is selected, after which $Y_{t+1}=g_{\theta}(A_{t})+W_{t+1}$ is observed, where $W_{t+1}\sim N(0,\sigma^{2}_{w}I)$. A reward $R_{t+1}=R(Y_{t+1})$ is associated with each observation. Let $\theta$ be distributed according to a $N(\mu_{0},\Sigma_{0})$ prior. The idea here is that data pairs $(A_{t},Y_{t+1})$ can be used to fit a neural network model, while actions are selected to trade off between generating data pairs that reduce uncertainty in neural network weights and those that offer desirable immediate outcomes.

Algorithms

Thompson sampling is computationally tractable for some problem classes, like the linear bandit problem, where the posterior distribution is Gaussian with parameters $(\mu_{t},\Sigma_{t})$ that can be updated incrementally and efficiently via Kalman filtering as outcomes are observed. However, when dealing with complex models, like neural networks, computing the posterior distribution becomes intractable. Ensemble sampling serves as an approximation to Thompson sampling for such contexts.

The posterior can be interpreted as a distribution of “statistically plausible” models, by which we mean models that are sufficiently consistent with prior beliefs and the history of observations. With this interpretation in mind, Thompson sampling can be thought of as randomly drawing from the range of statistically plausible models. Ensemble sampling aims to maintain, incrementally update, and sample from a finite set of such models. In the spirit of particle filtering, this set of models approximates the posterior distribution. The workings of ensemble sampling are in some ways more intricate than conventional uses of particle filtering, however, because interactions between the ensemble of models and selected actions can skew the distribution.

While elements of ensemble sampling require customization, a general template is presented as Algorithm 1. The algorithm begins by sampling $M$ models from the prior distribution. Then, over each time period, a model is sampled uniformly from the ensemble, an action is selected to maximize expected reward under the sampled model, the resulting outcome is observed, and each of the $M$ models is updated. To produce an explicit algorithm, we must specify a model class, prior distribution, and algorithms for sampling from the prior and updating models.

For a concrete illustration, let us consider the linear bandit (Example 1). Though ensemble sampling is unwarranted in this case, since Thompson sampling is efficient, the linear bandit serves as a useful context for understanding the approach. Standard algorithms can be used to sample models from the $N(\mu_{0},\Sigma_{0})$ prior. One possible procedure for updating models maintains a covariance matrix, updating it according to

and generates model parameters incrementally according to

We present computational results in Section 5.2 that demonstrate viability of this approach.

Analysis of ensemble sampling for the linear bandit

Past analyses of Thompson sampling have relied on independence between models sampled over time periods. Ensemble sampling introduces dependencies that may adversely impact performance. It is not immediately clear whether the degree of degradation should be tolerable and how that depends on the number of models in the ensemble. In this section, we establish a bound for the linear bandit context. Our result serves as a sanity check for ensemble sampling and offers insight that should extend to broader model classes, though we leave formal analysis beyond the linear bandit for future work.

This inequality bounds the regret realized by ensemble sampling by a sum of the regret realized by Thompson sampling and an error term $\epsilon\Delta(\theta)T$. Since we are talking about cumulative regret, the error term bounds the per-period degradation relative to Thompson sampling by $\epsilon\Delta(\theta)$. The value of $\epsilon$ can be made arbitrarily small by increasing $M$. Hence, with a sufficiently large ensemble, the per-period loss will be small. This supports the viability of ensemble sampling.

An important implication of this result is that it suffices for the ensemble size to grow logarithmically in the horizon $T$. Since Thompson sampling requires independence between models sampled over time, in a sense, it relies on $T$ models – one per time period. So to be useful, ensemble sampling should operate effectively with a much smaller number, and the logarithmic dependence is suitable. The bound also grows with $|\mathcal{A}|\log|\mathcal{A}|$, which is manageable when there are a modest number of actions. We conjecture that a similar bound holds that depends instead on a multiple of $N\log N$, where $N$ is the linear dimension, which would offer a stronger guarantee when the number of actions becomes large or infinite, though we leave proof of this alternative bound for future work.

The bound of Theorem 3 is on a notion of regret conditioned on the realization of $\theta$. A Bayesian regret bound that removes dependence on this realization can be obtained by taking an expectation, integrating over $\theta$:

We provide a complete proof of Theorem 3 in the appendix. Due to space constraints, we only offer a sketch here.

A naive application of the union bound over all deterministic action sequences would establish that, for any $A$ (deterministic or stochastic),

which, after some algebraic manipulations, leads to

The result then follows from some straightforward algebra. ∎

Computational results

In this section, we present computational results that demonstrate viability of ensemble sampling. We will start with a simple case of independent Gaussian bandits in Section 5.1 and move on to more complex models of neural networks in Section 5.2. Section 5.1 serves as a sanity check for the empirical performance of ensemble sampling, as Thompson sampling can be efficiently applied in this case and we are able to compare the performances of these two algorithms. In addition, we provide simulation results that demonstrate how the ensemble size grows with the number of actions. Section 5.2 goes beyond our theoretical analysis in Section 4 and gives computational evidence of the efficacy of ensemble sampling when applied to more complex models such as neural networks. We show that ensemble sampling, even with a few models, achieves efficient learning and outperforms $\epsilon$-greedy and dropout on the example neural networks.

We consider a Gaussian bandit with $K$ actions, where action $k$ has mean reward $\theta_{k}$. Each $\theta_{k}$ is drawn i.i.d. from $N(0,1)$. During each time step $t=0,\dots,T-1$, we select an action $k\in\{1,\dots,K\}$ and observe reward $R_{t+1}=\theta_{k}+W_{t+1}$, where $W_{t+1}\sim N(0,1)$. Note that this is a special case of Example 1. Since the posterior distribution of $\theta$ can be explicitly computed in this case, we use it as a sanity check for the performance of ensemble sampling.

Figure 1(a) shows the per-period regret of Thompson sampling and ensemble sampling applied to a Gaussian bandit with 50 independent arms. We see that as the number of models increases, ensemble sampling better approximates Thompson sampling. The results were averaged over 2,000 realizations. Figure 1(b) shows the minimum number of models required so that the expected per-period regret of ensemble sampling is no more than $\epsilon$ plus the expected per-period regret of Thompson sampling at some large time horizon $T$ across different numbers of actions. All results are averaged over 10,000 realizations. We chose $T=2000$ and $\epsilon=0.03$. The plot shows that the number of models needed seems to grow sublinearly with the number of actions, which is stronger than the bound proved in Section 4.

2 Neural networks

In this section, we follow Example 2 and show computational results of ensemble sampling applied to neural networks. Figure 2 shows $\epsilon$-greedy and ensemble sampling applied to a bandit problem where the mapping from actions to expected rewards is represented by a neuron. More specifically, we have a set of $K$ actions $\mathcal{A}\subseteq\Re^{N}$. The mean reward of selecting an action $a\in\mathcal{A}$ is given by $g_{\theta}(a)=\max(0,\theta^{\top}a)$, where weights $\theta\in\Re^{N}$ are drawn from $N(0,\lambda I)$. During each time period, we select an action $A_{t}\in\mathcal{A}$ and observe reward $R_{t+1}=g_{\theta}(A_{t})+Z_{t+1}$, where $Z_{t+1}\sim N(0,\sigma_{z}^{2})$. We set the input dimension $N=100$, number of actions $K=100$, prior variance $\lambda=10$, and noise variance $\sigma_{z}^{2}=100$. Each dimension of each action was sampled uniformly from $$, except for the last dimension, which was set to 1.

In Figure 3, we consider a bandit problem where the mapping from actions to expected rewards is represented by a two-layer neural network with weights $\theta\equiv(W_{1},W_{2})$, where $W_{1}\in\Re^{D\times N}$ and $W_{2}\in\Re^{D}$. Each entry of the weight matrices is drawn independently from $N(0,\lambda)$. There is a set of $K$ actions $\mathcal{A}\subseteq\Re^{N}$. The mean reward of choosing an action $a\in\mathcal{A}$ is $g_{\theta}(a)=W_{2}^{\top}\max(0,W_{1}a)$. During each time period, we select an action $A_{t}\in\mathcal{A}$ and observe reward $R_{t+1}=g_{\theta}(A_{t})+Z_{t+1}$, where $Z_{t+1}\sim N(0,\sigma_{z}^{2})$. We used $N=100$ for the input dimension, $D=50$ for the dimension of the hidden layer, number of actions $K=100$, prior variance $\lambda=1$, and noise variance $\sigma_{z}^{2}=100$. Each dimension of each action was sampled uniformly from $$, except for the last dimension, which was set to 1.

Besides ensemble sampling, there are other heuristics for sampling from an approximate posterior distribution over neural networks, which may be used to develop approximate Thompson sampling. Gal and Ghahramani proposed an approach based on dropout to approximately sample from a posterior over neural networks. In Figure 3, we include results from using dropout to approximate Thompson sampling on the two-layer neural network bandit.

To facilitate gradient flow, we used leaky ReLUs of the form $\max(0.01x,x)$ internally in all agents, while the target neural nets still use regular ReLUs as described above. We took 3 stochastic gradient steps with a minibatch size of 64 for each model update. We used a learning rate of 1e-1 for $\epsilon$-greedy and ensemble sampling, and a learning rate of 1e-2, 1e-2, 2e-2, and 5e-2 for dropout with dropping probabilities $0.25$, $0.5$, $0.75$, and $0.9$ respectively. All results were averaged over around 1,000 realizations.

Figure 2 plots the per-period regret of $\epsilon$-greedy and ensemble sampling on the single neuron bandit. We see that ensemble sampling, even with 10 models, performs better than $\epsilon$-greedy with the best tuned parameters. Increasing the size of the ensemble further improves the performance. An ensemble of size 50 achieves orders of magnitude lower regret than $\epsilon$-greedy.

Figure 3a and 3b show different versions of $\epsilon$-greedy applied to the two-layer neural network model. We see that $\epsilon$-greedy with an annealing schedule tends to perform better than a fixed $\epsilon$. Figure 3c plots the per-period regret of the dropout approach with different dropping probabilities, which seems to perform worse than $\epsilon$-greedy. Figure 3d plots the per-period regret of ensemble sampling on the neural net bandit. Again, we see that ensemble sampling, with a moderate number of models, outperforms the other approaches by a significant amount.

Conclusion

Ensemble sampling offers a potentially efficient means to approximate Thompson sampling when using complex models such as neural networks. We have provided an analysis that offers theoretical assurances for the case of linear bandit models and computational results that demonstrate efficacy with complex neural network models.

We are motivated largely by the need for effective exploration methods that can efficiently be applied in conjunction with complex models such as neural networks. Ensemble sampling offers one approach to representing uncertainty in neural network models, and there are others that might also be brought to bear in developing approximate versions of Thompson sampling . The analysis of various other forms of approximate Thompson sampling remains open.

Ensemble sampling loosely relates to ensemble learning methods , though an important difference in motivation lies in the fact that the latter learns multiple models for the purpose of generating a more accurate model through their combination, while the former learns multiple models to reflect uncertainty in the posterior distribution over models. That said, combining the two related approaches may be fruitful. In particular, there may be practical benefit to learning many forms of models (neural networks, tree-based models, etc.) and viewing the ensemble as representing uncertainty from which one can sample.

This work was generously supported by a research grant from Boeing and a Marketing Research Award from Adobe.

References

Appendix A Proof of Theorem 3

Say $A=(a_{0},\ldots,a_{T-1})$, where $a_{0},\ldots,a_{T-1}\in\mathcal{A}$. Let $X$ be an $t\times N$ matrix with the $j^{\text{th}}$ row equal to $a_{j-1}$. Let $y=(R_{1},\dots,R_{t})^{\top}$. Then,

The following lemma shows that for any deterministic action sequence, conditioned on $\theta$, the action distribution that ensemble sampling would sample from is close to the action distribution that Thompson sampling would sample from with high probability.

For any deterministic action sequence $a\in\mathcal{A}^{T}$,

If $a\in\mathcal{A}^{T}$ is deterministic, then conditioned on $(R_{1},\dots,R_{t})$, $\hat{p}^{a}_{t}$ and $p^{a}_{t}$ are independent of $\theta$. Thus, we have

Since $c_{t}$ has $|\mathcal{A}|$ components, and each component takes a value in $\{0,\ldots,t+1\}$, we have

The following lemma establishes that, for any deterministic action sequence $a\in\mathcal{A}^{T}$, $p_{t}^{a}$ and $\hat{p}_{t}^{a}$ depend on $a$ only through its action counts, $c_{t-1}^{a}$; in other words, $p_{t}^{a}$ and $\hat{p}_{t}^{a}$ do not depend on the ordering of past actions and observations.

For any $t=0,\ldots,T-1$, if $a,\overline{a}\in\mathcal{A}^{T}$ are deterministic sequences such that $c_{t-1}^{a}=c_{t-1}^{\overline{a}}$, then $p_{t}^{a}=p_{t}^{\overline{a}}$ and $\hat{p}_{t}^{a}=\hat{p}_{t}^{\overline{a}}$.

where $(a)$ follows from Lemma 6, $(b)$ follows from the union bound, and $(c)$ follows from Lemma 5 and the fact that the total number of counts $|C_{t-1}|\leq(t+1)^{|\mathcal{A}|}$. ∎

The expected cumulative regret of ensemble sampling conditioned on $\theta$ can be decomposed as

We will bound the per-period regret for the case where the divergence $d_{\text{KL}}(\hat{p}_{t}\|p_{t})$ is large and the case where the divergence is small, respectively.

This follows directly from the definition of $\Delta(\theta)$ and Lemma 7. ∎

For simplicity, assume $0<\epsilon<1$ and $0<\delta<1$ are such that $\frac{|\mathcal{A}|T}{\epsilon\delta}\geq 9$.

We show that if $M$ satisfies the condition above, then

since Assumption 9 implies that $\frac{|\mathcal{A}|T}{\epsilon\delta}\geq 4\log\frac{|\mathcal{A}|T}{\epsilon\delta}$. The result then follows from Lemma 8. ∎

Combining Lemma 10 and Lemma 11 delivers a proof for our main result. In particular, we have

where the inequality follows from Lemma 10, with $\delta=\epsilon/2$, and Lemma 11. ∎