{'fraction_non_alphanumeric': 0.045824295010845985, 'fraction_numerical': 0.01782809110629067, 'mean_word_length': 4.107322139518781, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An Analysis of Ensemble Sampling

Ensemble sampling serves as a practical approximation to Thompson sampling when maintaining an exact posterior distribution over model parameters is computationally intractable. In this paper, we establish a Bayesian regret bound that ensures desirable behavior when ensemble sampling is applied to the linear bandit problem. This represents the first rigorous regret analysis of ensemble sampling and is made possible by leveraging information-theoretic concepts and novel analytic techniques that may prove useful beyond the scope of this paper.


Introduction
Thompson sampling (TS) is a popular heuristic for balancing between exploration and exploitation in bandit learning. In its basic form, TS operates maintains a posterior distribution over model parameters. When the prior distribution and likelihood function exhibit conjugacy properties, the posterior can be maintained through computationally tractable Bayesian inference. However, many practical contexts call for more complex models for which exact Bayesian inference becomes computationally intractable. For such contexts, ensemble sampling (ES) can serve as a practical approximation to TS [Lu and Van Roy, 2017].
Instead of the posterior distribution, ES maintains an ensemble of statistically plausible models that can be updated in an efficient incremental manner. The corresponding discrete distribution represents an approximation to the posterior distribution. At the start of each timestep, a model is sampled uniformly from the ensemble and an action is selected to optimize expected reward with respect to the sampled model. Each model is initially sampled from the prior distribution and evolves through an updating process that adapts to observations and random perturbations.
While a growing literature [Osband et al., 2016, Russo et al., 2018, Lu et al., 2018, Osband et al., 2019, Dwaracherla et al., 2020 presents applications of ES, there has been no rigorous theory that ensures desirable behavior similar to that enjoyed by TS. A regret bound for ES applied to the linear bandit is provided by Lu and Van Roy [2017], but a flaw in the associated analysis has brought this result into question. Since the publication of that paper, several researchers have tried to remedy the analysis or otherwise establish performance guarantees for ES, but these efforts have gone without success.
We offer in this paper the first rigorous regret analysis of ES. Like Lu and Van Roy [2017], we study ES applied to the linear bandit. This serves as a simple sanity check for the approach. We establish a Bayesian regret bound (Theorem 1) that consists of two terms. The first term is identical to a Bayesian regret bound established for TS. The second term accounts for posterior distribution mismatch and can be made arbitrarily small by increasing the ensemble size. Our analysis leverages information-theoretic concepts and novel analytic techniques that may prove useful beyond the scope of this paper.
As a stepping stone in our analysis, we establish a general Bayesian regret bound that applies to any learning algorithm applied to a linear bandit (Theorem 2). In particular, this regret bound is based on the Hellinger distance between the action selection distribution of the learning algorithm and the posterior distribution of the optimal action at each time step. We believe that this Bayesian regret bound is of independent interest and might be useful in analyzing other learning algorithms, such as other approximate TS algorithms, in the future.
The remainder of this paper is organized as follows: Section 2 reviews related work, and Section 3 formulates the considered linear bandit problem and describes the ensemble sampling (ES) algorithm. Section 4 presents the main result of this paper: a Bayesian regret bound for ES in linear bandits. Before diving into the analysis, we define notation used in this paper in Section 5. Then, we motivate and derive the general regret bound in Section 6 and sketch the proof of the main result in Section 7. Finally, we conclude the paper and discuss future directions in Section 8. Detailed proofs are provided in the appendices. Thompson sampling [Thompson, 1933, Chapelle and Li, 2011, Russo et al., 2018 is a commonly used heuristic for balancing exploration and exploitation in bandit [Lattimore and Szepesvári, 2020] and reinforcement learning [Sutton and Barto, 2018] problems. However, the basic form of Thompson sampling can be computationally intractable unless the prior distribution and likelihood function exhibit conjugacy properties. To overcome this computational challenge, variants of approximate versions of TS (see Chapter 5 of Russo et al. [2018]) have been developed, including approximate TS using Laplace approximation [Chapelle and Li, 2011], bootstrapping Kaptein, 2014, Kveton et al., 2019], variational inference [Urteaga andWiggins, 2018, Yu et al., 2020], Markov chain Monte Carlo [Casella andGeorge, 1992, Roberts andTweedie, 1996], hypermodels [Dwaracherla et al., 2020], and optimal transport [Zhang et al., 2019].

Related work
Ensemble sampling (ES) is also an approximate version of Thompson sampling, and was formally proposed by Lu and Van Roy [2017]. It has been one of the most popular methods in approximate Bayesian inference and has wide applications in sequential decision making. For example, variations of ES have been applied to (deep) reinforcement learning [Osband et al., 2016[Osband et al., , 2019, online recommendation [Lu et al., 2018, Hao et al., 2020, Zhu and Van Roy, 2021, multi-agent reinforcement learning [Dimakopoulou and Van Roy, 2018], behavioral sciences [Eckles and Kaptein, 2019], and marketing strategies [Yang et al., 2020]. Recently,  has developed a testbed to compare and rank agents for uncertainty modeling, including variants of the ensemble agents.
A lot of work has attempted to analyze ensemble sampling, but none of them has been successful. In their original paper, Lu and Van Roy [2017] try to analyze ES in linear-Gaussian bandits, but there is a mistake in the final step of the analysis where they compare the regret of ES to that of TS. In particular, in the proof of Lemma 8, the random variables A TS t are defined on histories of actions selected by ensemble sampling, instead of TS. Therefore, the sum of regret incurred by these hypothetical Thompson sampling actions A TS t is not equal to the cumulative regret of applying a TS agent throughout all time steps. The paper incorrectly claims that they are equal.
In addition to Lu and Van Roy [2017], Phan et al. [2019] aims to analyze general approximate TS with approximation errors measured in α-divergence for K-armed bandit. To demonstrate the main result, Phan et al. [2019] uses ensemble sampling as an example, but also inherits the technical flaw in Lu and Van Roy [2017]. In addition, though Phan et al. [2019] show that an approximate version of Thompson sampling that uses uniform sampling achieves sublinear regret, this result mainly benefits from forced exploration.
There are also papers aiming to analyze bandit algorithms with approximate inference. A recent paper [Huang et al., 2022] proposes and analyzes an upper-confidence-bound (UCB) type algorithm for bandit problems with approximate inference. Another recent paper [Ash et al., 2021] proposes and analyzes an ensemble based UCB algorithm for bandit problems.

Preliminaries
We begin by introducing a formulation of the linear bandit and an ensemble sampling (ES) algorithm suited for this environment.

Linear bandit
The linear bandit [Abbasi-Yadkori et al., 2011, Lattimore andSzepesvári, 2020] has received much attention in the bandit learning literature. It serves as a simple didactic environment, often used to sanity-check agent designs. In this spirit, we will analyze ES as applied to the linear bandit.
We consider a linear bandit with a Gaussian prior distribution and Gaussian noise. An instance is characterized by a tuple E = (A, µ 0 , Σ 0 , σ 2 ), where A ⊂ R d is a finite action set, µ 0 and Σ 0 are the prior mean vector and covariance matrix, and σ 2 is the noise variance. Note that actions are vectors of dimension d. Let K = |A| denote the cardinality of the action set. The prior distribution over the coefficient vector θ ∈ R d , P(θ ∈ ·), is multivariate Gaussian N(µ 0 , Σ 0 ). Rewards are generated by a random sequence (R t : t = 1, 2, . . .) of K-dimensional vectors, which is i.i.d. conditioned on θ. In particular, for each t and a, R t,a = a θ + W t,a , for an i.i.d. sequence (W t : t = 1, 2, . . .) of K-dimensional vectors with each element distributed N(0, σ 2 I).
An agent interacts with the linear bandit as follows: at each time t = 0, 1, . . ., the agent executes an action A t ; then, it observes a reward R t+1,A t . Note that only the reward associated with the executed action is observed through what is termed bandit feedback. The agent's experience through time t is encoded by a history H t = (A 0 , R 1,A 0 , . . . , A t−1 , R t,A t−1 ). The agent's objective is to maximize expected reward over some long duration T: This is equivalent to minimizing the Bayesian regret: where A * ∼ unif arg max a∈A a θ . Note that in both Equations (1) and (2), the expectations integrate over random reward realizations, algorithmic randomness, and the coefficient vector θ. Note that A * is also a random variable since it depends on θ as well the uniform sampling among maximizers, which breaks ties.

Ensemble sampling
In the absence of conjugacy properties that enable efficient Bayesian inference, TS in its exact form becomes computationally infeasible. ES serves as a practical approximation to TS [Lu and Van Roy, 2017], often suitable for such contexts. The key idea behind ES is to maintain an ensemble of statistically plausible models that can be updated in an efficient incremental manner and to treat the discrete distribution represented by this set of models as an approximation to the posterior distribution. The algorithm begins by sampling M models from the prior distribution, where M is a hyperparameter. Then, at the start of each timestep, a model is sampled uniformly from this set and an action is selected to optimize the immediate expected reward with respect to the sampled model. Each model is updated incrementally based on the observed reward and a random perturbation. Algorithm 1 presents the associated pseudo-code for ES. The posterior distribution at time t + 1 is Gaussian with covariance matrix and mean vector While this highlights conjugacy properties of a sort that allow for efficient Bayesian inference and thus tractable implementation of exact TS, the linear bandit with Gaussian prior distribution and likelihood Algorithm 1 Ensemble Sampling 1: Sample:θ 0,1 , . . . ,θ 0,M ∼ P(θ ∈ ·) 2: for t = 0, . . . , T − 1 do 3: Execute: A t ∼ unif arg max a∈A a θ t,m

Regret bound for ensemble sampling
In this paper, we establish the following Bayesian regret bound for ES (Algorithm 1) when it is applied to linear bandits described in Section 3.1: Theorem 1. Suppose ES Algorithm (Algorithm 1) is applied to linear bandit with prior P(θ ∈ ·) = N(µ 0 , Σ 0 ) and M models, then where d is the dimension of actions, T is the time horizon, K is the number of actions, H(A * ) is the entropy of the optimal action A * under the prior, and and Note that if we treat the noise variance σ 2 , prior mean vector µ 0 , and prior covariance matrix Σ 0 as constants, then κ = O( log K), and whereÕ hides the logarithmic factors. Theorem 1 represents the first rigorously proved regret bound that ensures some degree of robustness in application of ES to a nontrivial bandit problem. A limitation is that the result applies only to the linear bandit with Gaussian prior distribution and likelihood function, which admits tractable application of exact TS. Nevertheless, this result represents a beginning to the theory of ES, offering hope that the approach is sound and analyses might be extended to broader problem classes in the future. In the remainder of this section, we compare our regret bound to others presented in closely related literature.

Comparison with the regret bound on TS
The regret bound in Theorem 1 consists of two terms. The first term (a) is exactly the regret bound achieved by TS with exact posterior [Russo and Van Roy, 2016]. Note that H(A * ) is the entropy of the optimal action A * and we always have H(A * ) log K. As discussed in Russo and Van Roy [2016], this term is order optimal. On the other hand, the second term (b) is an incremental term and accounts for posterior distribution mismatch. Recall that M is the number of models used by ES, and κ depends on K, the noise variance σ 2 , prior mean vector µ 0 , and prior covariance matrix Σ 0 . Note that asymptotically, as M → ∞, the second term converges to 0 and the regret bound in Theorem 1 reduces to that of TS with exact posterior. Moreover, even when M is finite and satisfies M KT/d, the regret bound in Theorem 1 has the same order as that of TS in terms of K and T, up to logarithmic factors.

Comparison with the regret bound of Lu and Van Roy [2017]
In our Theorem 1, the upper bound is on the Bayesian regret where the prior over θ is N(µ 0 , Σ 0 ), and the regret also takes expectation over θ. Lu and Van Roy [2017] studies ES in the frequentist setting where unknown θ is fixed, and tries to upper bound the frequentist regret of ES by that of TS plus some approximation term due to posterior mismatch, similar to (b) in our Bayesian regret bound in Theorem 1. However, there are some technical issues in the analysis, as is discussed in Section 2. Theorem 3 in Lu and Van Roy [2017] suggests that for any > 0, when the number of models M =Θ K/ 2 (whereΘ hides the logarithmic factors), the approximation term is ∆(θ)T where ∆(θ) = max a∈A a θ − min a∈A a θ, while the approximation term (b) in our Bayesian regret bound in Theorem 1 is linear in κ = O( log K). To make our approximation term (b) scale asÕ ( T), the number of required models M is stillΘ K/ 2 . We conjecture that the number of required models can be further reduced toΘ d/ 2 , but leave it to future work.

Notations
Before proceeding, we define some notations including Kullback-Leibler divergence, Hellinger distance, Shannon entropy and mutual information.

Kullback-Leibler divergence and Hellinger distance
For two probability distributions P and Q, the Kullback-Leibler (KL) divergence between P and Q is defined as The Hellinger distance between P and Q is defined as which is symmetric in P and Q. In the special case of discrete distributions P = (p 1 , . . . , p n ) and Q = (q 1 , . . . , q n ), the KL divergence and Hellinger distance between P and Q can be written as The following inequality hold for Hellinger distance and KL divergences: Tsybakov [2009]). For two probability distributions P and Q, we have In other words, the Hellinger distance is upper bounded by KL divergences in both directions. We will use Fact 1 in Section 6.

Measures in information theory
Consider a discrete random variable X whose support is a finite set X and general random variable Y and Z. The Shannon entropy of X is defined as The entropy of X conditional on Y = y is H(X|Y = y) − ∑ x∈X P (X = x|Y = y) log P(X = x|Y = y), and the conditional entropy of X given Y is, where the expectation is taken with respect to the marginal distribution of Y.
The mutual information between X and Y is the KL divergence between the joint distribution of X and Y and the product of the marginal distributions, and the conditional mutual information between X and Y given Z is where the expectation is taken with respect to the marginal distribution of Z.

General regret bound
In this section, we derive a general Bayesian regret bound for any learning algorithm (Theorem 2), based on the Hellinger distance between the (conditional) action-selection distribution specified by the algorithm and the posterior distribution of the optimal action A * , and use it to establish the regret bound for ES in Theorem 1. We believe that this Bayesian regret bound is of independent interest and might be used to analyze other bandit algorithms, such as variants of approximate TS algorithms, in the future.
To simplify the exposition, we first define some shorthand notations to simplify the exposition of this paper. First, we use subscript t to denote conditioning on H t , specifically, we define In addition, we define probability distributions p t and p t over action set A as p t (·) P t (A t = ·) and p t (·) P t (A * = ·).
Given the history H t , p t is the conditional distribution of action A t and p t is the posterior distribution of the optimal action A * . Both p t and p t are specified by the algorithm. Note that under TS, given the history H t , p t and p t are the same, but they are not under other algorithms. We conjecture that for approximate TS algorithms, when the approximation is accurate, p t is close to p t . We have the following Bayesian regret bound for any learning algorithm: Theorem 2. For linear bandits considered in Section 3.1, under any learning algorithm, where ι is defined in Equation (5) and Note that the expectation in Equation (9) is taken with respect to the prior over θ.

Discussion on the regret bound in Theorem 2
The regret bound in Theorem 2 holds for any learning algorithm. Note H(A * ) is the entropy of the optimal action A * and we always have H(A * ) log K. The first term matches the regret bound of TS derived in Russo and Van Roy [2016]. In the second term, ∑ T−1 t=0 E d 2 H (p t p t ) quantifies the cumulative distance between the conditional distribution of the action A t and the posterior distribution the optimal action A * . Under TS with exact posterior, d 2 H (p t p t ) = 0 due to the posterior matching property of TS, i.e., p t = p t . Moreover, for approximate TS algorithms, if the approximation is accurate, d 2 H (p t p t ) should be small. In the regret bound in Theorem 2, the constant η depends on the prior over θ. If the prior over θ is Gaussian random vector, a θ is Gaussian random variable for any a ∈ A. It is well-known that the expectation of the maximum of K (potentially correlated) Gaussian random variables is Θ(log K). We show in the appendix that the expectation of the maximum of K squares of Gaussian random variables is O(log K). See Lemma 9 in the appendix, which immediately leads to the following corollary. Corollary 1. Suppose the prior over θ is N(µ 0 , Σ 0 ). We have η κ, where η and κ are defined in Equations (9) and (6), respectively.
Regret bound in terms of KL divergence between p t and p t It is sometimes more convenient to analyze the KL divergence between p t and p t . Since the squared Hellinger distance is symmetric and upper bound by the KL divergence (Fact 1), we obtain the regret upper bound with the approximation error in terms of two forms of KL divergence between p t and p t .

Corollary 2. For linear bandits considered in Section 3.1, under any learning algorithm,
where ι and η are defined in Equations (5) and (9), respectively.
We will show in Section 7 that for ensemble sampling, d KL (p t p t ) can be bounded in terms of the number of models M. It is noteworthy that in some other problems, it is more convenient to bound the other form d KL (p t p t ). One such example is the Bayesian regret bound developed in .

Proof sketch of Theorem 2
To prove Theorem 2, we first rewrite the cumulative regret as the expectation of the sum of T conditional regret as follows where in the last equality, G t and D t are the per-period "main regret term" and "approximation error term", respectively, defined in the following lemma.
Lemma 1. For each time t = 0, . . . , T − 1, we have and Now we are going to upper bound (11), respectively. We first The strategy is to upper bound each G t by the mutual information between the optimal action A * and the action-reward pair (A t , R t+1,A t ) conditioning on a given history H t : Lemma 2. For each time t = 0, . . . , T − 1, with probability 1, where ι is defined in Equation (5) and

on a given history H t .
This result extends Lemma 5 (and the statement in Corollary 1 for linear bandit) in Russo and Van Roy [2016] to the case that A t and A * are not identically distributed given the history H t . Then, similar to the analysis in Russo and Van Roy [2016], using the Cauchy-Schwarz inequality and the chain rule for mutual information, we obtain the following result. (5), the following inequality holds.

Lemma 3. With ι defined in Equation
The upper bound in the above result is the first term in the regret bound in Theorem 2.
To upper bound the approximation term D t defined in Equation (13), we need to deal with the (potentially) unbounded prior and noises. By carefully using the Cauchy-Schwarz inequality, we obtain the following result: Lemma 4. With η defined in Equation (9), for t = 0, . . . , T − 1, Summing over t gives the second term in the regret bound of Theorem 2.

Approximation error under ensemble sampling
In this section, we are going to bound the cumulative approximation error ∑ T−1 t=0 E [d KL (p t p t )] in Theorem 2 for ensemble sampling, where p t is the conditional distribution of the chosen action A t and p t is the posterior distribution of the optimal action A * . The whole section is devoted to proving the following lemma.
Plugging Lemma 5 and the bound on η under Gaussian prior (Corollary 1) into the general regret bound in Theorem 2, we achieve the regret bound for ensemble sampling in Theorem 1.
We first discuss the behavior of ensemble sampling. ES first uniformly samples a model m ∈ {1, . . . , M}, and then chooses the action A t uniformly from the setÃ t,m arg max a∈A a θ t,m . We define the following approximation of p t (a):p where |Ã t,m | is the cardinality of the setÃ t,m (with probability 1, |Ã t,m | = 1). ES is a simple variant of approximate TS. At time t, TS would sample an action from the posterior distribution of the optimal action A * , while ES would sample an action from the approximationp t . Notice that the history H t does not include independent random perturbationW t ∼ N(0, σ 2 I) used in updating M models (see Equation (4)). Therefore, given H t ,p t (a) is still a random variable, and its expectation is the conditional probability of sampling action a, i.e., Lemma 6. For t = 0, . . . , Proof. By convexity of KL divergence, the per-period approximation error Taking expectation on both sides completes the proof. (15),

Now it suffices to upper bound the RHS of Equation
. Given the following relationship between the expectation and cumulative distribution function, our strategy is to derive an upper bound of P (d KL (p t p t ) > ) for any > 0. For simplicity, we first study this quantity under a deterministic action sequence a 0:t−1 (a 0 , . . . , a t−1 ). To explicitly indicate the dependence on the action sequence, we use the superscript a 0:t−1 and write p a 0:t−1 t (·) P t (A * = ·|a 0 , R 1,a 0 , . . . , a t−1 , R t,a t−1 ). Lu and Van Roy [2017] shows that under the deterministic action sequence a 0,t−1 ,θ a 0:t−1 t,1 , . . . ,θ a 0:t−1 t,M , conditioned on the history of corresponding rewards, are i.i.d. from the posterior over the coefficient vector θ. Therefore, the approximationp a 0:t−1 t is an empirical distribution of samples drawn from p a 0:t−1 t . By Sanov's theorem,

Lemma 1 in
By applying the union bound over action counts, instead of action sequences, we reproduce the following result implied by the proof of Lemma 4 in Lu and Van Roy [2017].
In the following result, we relate the KL divergence associated with stochastic action sequence to that with deterministic action sequence. Note that this result is implied by the proof of Lemma 4 in Lu and Van Roy [2017], but some steps in the original proof are not easy to follow: Lemma 8. Let > 0. For t = 0, . . . , T − 1, To explicitly indicate the dependence on the action sequence, letp A 0:t−1 t p t and p A 0:t−1 t p t where A 0:t−1 (A 0 , . . . , A t−1 ) is the stochastic action sequence sampled by ES adaptively. We have where step (a) follows from that conditioning on θ, the event {A 0:t−1 = a 0:t−1 } is independent of the event This completes the proof. Now we are ready to complete the proof of Lemma 5.
Proof of Lemma 5. Fix t. For > 0, by Lemmas 7 and 8 and P(·) = E[P(·|θ)], Then for any threshold δ 0, By taking the derivative of the RHS, we get the optimal δ * = , which gives shown in Lemma 6, we complete the proof.

Concluding remarks
We have presented the first rigorous regret analysis of ensemble sampling (ES), leading to a Bayesian regret bound (Theorem 1). This regret bound approaches an existing Bayesian regret bound for TS as the ensemble size grows. As a stepping stone, we have also established a general Bayesian regret bound that applies to any learning algorithm for linear bandits (Theorem 2). This depends on the Hellinger distance between p t and p t at each time t, where p t is the conditional distribution of the action A t executed by the algorithm and p t is the posterior distribution of A * . It is worth mentioning that ES is developed for broader and more challenging bandit and reinforcement learning problems, and the linear bandit serves only as a simple sanity check. In particular, ES can be used to approximate TS in the absence of conjugacy properties, when it is intractable to maintain an exact posterior. As discussed in Section 2, a substantial literature has been devoted to research in this direction. It is also noteworthy that in many practical problems, ES with a moderate number of models (e.g. 30 models) outperforms other state-of-the-art benchmarks [Lu and Van Roy, 2017, Lu et al., 2018, Osband et al., 2019.
The general regret bound of Theorem 2 may be of independent interest, since it can be used to analyze other learning algorithms, such as other varieties of approximate TS (e.g. approximate TS with epistemic neural networks). Based on this result, for any posterior approximation scheme, one only need to bound the Hellinger distance between p t and p t at each time step t to establish a regret bound. Also, it might be straightforward to extend this theorem to linear bandits with sub-Gaussian prior distributions and sub-Gaussian likelihood functions.
Finally, we believe that the analytic techniques developed in this paper can be used to analyze ES and approximate TS in more general bandit, online learning, and reinforcement learning problems. In particular, we believe that it is straightforward to extend the results of this paper to online learning with full information feedback [Shalev-Shwartz et al., 2011] and "graph" information feedback [Alon et al., 2015], combinatorial semi-bandits , and pure exploration problems [Bubeck et al., 2009, Russo, 2016, Komiyama et al., 2021. We also conjecture that the results of this paper can be extended to generalized linear bandits [Filippi et al., 2010, Dong et al., 2019 and episodic reinforcement learning [Osband et al., 2013], but leave these extensions for future work.

A.1 Proof of Lemma 1
Conditioned on H t , the regret can be written as follows.

A.2 Proof of Lemma 2
Fix t. Recall the probability distributions p t and p t over action set A: p t (·) = P t (A t = ·) and p t (·) = P t (A * = ·).
We first rewrite I t (A * ; (A t , R t+1,A t )) as follows: where the first equality uses the chain rule of mutual information (Fact 3); the second and fourth equalities follow from that conditioning on the history H t , A t is jointly independent of A * and R t+1 = (R t+1,1 , . . . , R t+1,K ); the fifth equality follows from the KL divergence form of mutual information (Fact 4). For notational convenience, we write A = {a 1 , . . . , a K }. Define M ∈ R K×K by For each a i ∈ A, conditional on H t , the coefficient vector θ ∼ N(µ t , Σ t ), and then R t+1,a i = a i θ + W t,a i ∼ N a i µ t , a i Σ t a i + σ 2 .
The updating rule on covariance matrix in Equation (3) implies Σ t Σ 0 , and thus a i Σ t a i a i Σ 0 a i max a∈A a Σ 0 a.
Hence, for each a i ∈ A, conditional on H t R t+1,a i is sub-Gaussian with variance proxy max a∈A a Σ 0 a + σ 2 .
Then by Lemma 11, we have On the other hand, G t defined in Lemma 1 can be written as This shows, by Fact 2, that We now show Rank(M) d. Define and then for any i, j ∈ [K], Since M is the product of one K × d matrix and the other d × K matrix, Rank(M) d.

A.3 Proof of Lemma 3
where the first and second inequalities follow from Lemma 2 and Cauchy-Schwarz inequality, respectively, and the last equality applies the chain rule for mutual information (Fact 3).

A.4 Proof of Lemma 4
Fix t. By Cauchy-Schwarz inequality, where the second inequality follows from the definition of the Hellinger distance and the fact that variance is always non-negative, and the second-to-last equality uses A t is independent of R t+1 = (R t+1,1 , . . . , R t+1,K ).
Using Cauchy-Schwarz inequality again, we have Then minimizing the RHS above over 0 < t Var(X a ) + µ 2 a max a∈ [K] σ 2 a + max a∈ [K] µ 2 a .

B.2 Lemmas and facts from Russo and Van Roy [2016]
We present the lemmas and facts from Russo and Van Roy [2016] used in the proof of our Theorem 2.
Fact 4 (Fact 6 in Russo and Van Roy [2016]: KL divergence form of mutual information). The mutual information between random variables X and Y can be written as, = ∑ x∈X P(X = x)d KL (P(Y|X = x) || P(Y)) .