2pt plus 0.4ex


Proofs from Section : analysis of counterexamples
Proof of Lemma  REF
We first recall the statement of the result.
*

Let \(\Theta ^{\prime }\)  denote the set of parameter vectors satisfying the following properties:

\(\frac{\theta ^{(1)}_{1}+\theta ^{(1)}_{2}}{2}<\frac{\theta ^{(2)}_{1}+\theta ^{(2)}_{2}}{2}\) . This implies that the optimal arm is \(I^*=2\)

\(\min \lbrace  \theta ^{(1)}_{1}, \theta ^{(1)}_{2}\rbrace  > \theta ^{(2)}_{1}\) . This implies arm 1 appears to be best if arm 2 is only measured in the context \(x=1\) .

\(\theta ^{(1)}_{1}<0\) : This implies that arm 2 has at least a 1/2 chance of being sampled in the second period if arm 1 is sampled first.

Let \(\nu _{1,1}\sim N( \tilde{m}_{1,1}, \tilde{s}_{1,1}^2)\)  and \(\nu _{1,2}\sim N( \tilde{m}_{1,2}, \tilde{s}_{1,2}^2)\)  denote the sampled parameters. We denote the probability of playing arm 1 in the first period by
\(c_0 \triangleq \mathbb {P}( \nu _{1,1}> \nu _{1,2}) > 0.\) 
Conditioned on the event that \(\theta \in \Theta ^{\prime }\)  and \(I_1 = 1\) , we have \(\tilde{m}_{2,1} = \theta ^{(1)}_{1}\)  and the probability of playing arm 2 in the second period is
\(\mathbb {P}(\nu _{2,2} > \theta ^{(1)}_{1} \mid \theta \in \Theta ^{\prime }, I_1=1 ) \geqslant \frac{1}{2}\) 
where the inequality holds due to Condition 3 above. Conditioned on the event that \(I_1 = 1\)  and \(I_2 = 2\) , we have \(m_{2,1} = \theta ^{(1)}_{1}\)  and \(m_{2,2} = \theta ^{(2)}_{2}\) . Due to Condition 2, TS will always measure arm 1 afterwards. Hence,
\(\mathbb {E}[\Delta _T]&\geqslant \mathbb {E}\left[\left(\frac{\theta ^{(2)}_{1} + \theta ^{(2)}_{2}}{2} - \frac{\theta ^{(1)}_{1} + \theta ^{(1)}_{2}}{2}\right) \mathbf {1}(\theta \in \Theta ^{\prime })\mathbf {1}(I_1=1,I_2=2)\right]\\&\geqslant \frac{c_0}{2}\mathbb {E}\left[\left(\frac{\theta ^{(2)}_{1} + \theta ^{(2)}_{2}}{2} - \frac{\theta ^{(1)}_{1} + \theta ^{(1)}_{2}}{2}\right) \mathbf {1}(\theta \in \Theta ^{\prime })\right] > 0.\) 

This completes the proof.

Proof of Lemma  REF
We first recall the statement of the result.
*

Let \(U_{t,i}= m_{t,i} + z \cdot s_{t,i}\)  denote the UCB of arm \(i\) . Since \(U_{1,1}< U_{1,2}\) , the initial arm selection is \(I_1 = 2\) . When \(\theta ^{(2)}_{1}>0\)  the posterior mean and standard deviation satisfy \(m_{2,2} = \theta ^{(2)}_{2}/2 > 0 = m_{2,1}\)  and \(s_{2,2} = \frac{1}{2}\sqrt{{\rm Var}(\theta ^{(2)}_1 \mid H_2) + {\rm Var}(\theta ^{(2)}_2 \mid H_2) } = 1 >\sqrt{\frac{1}{2}} = s_{2,1}.\)  This implies \(U_{2,2} > U_{2,1}\)  and arm \(I_2=2\)  is again selected. This process repeats, showing that if \(\theta ^{(2)}_{1}>0\)  then arm 2 is chosen for each of the first \(T/2\)  periods. We can lower bound simple regret by imagining that the decision-maker has perfect knowledge of \(\theta ^{(2)}_{1}\) , \(\theta ^{(2)}_{2}\)  and \(\theta ^{(1)}_{2}\)  when selecting \(\hat{I}_T \in \operatornamewithlimits{arg\,max}_{i} \mathbb {E}\left[\left(\theta ^{(i)}_1 + \theta ^{(i)}_2\right)/2 \mid H_{T}^+ \right]\) , resulting in:
\(\mathbb {E}\left[\Delta _T \right] \geqslant \mathbb {E}\left[ \left( \max \left\lbrace  \frac{\theta ^{(1)}_{1} + \theta ^{(1)}_{2} }{2}\, ,\, \frac{\theta ^{(2)}_{1} + \theta ^{(2)}_{2} }{2} \right\rbrace  - \max \left\lbrace  \frac{ \theta ^{(1)}_{2} }{2}\, ,\, \frac{\theta ^{(2)}_{1} + \theta ^{(2)}_{2} }{2} \right\rbrace  \right) \mathbb {1}\left( \theta ^{(2)}_{1}>0 \right) \right] >0.\) 
The strict inequality is due to the gap in Jensen's inequality, reflecting the value of having perfect information about \(\theta _{1,1}\)  when making a decision.

Failure of contextual bandit algorithms
The goal in our formulation is to select among a very restricted set of decision-rules: those that choose a common action, irrespective of context. Experimentation should be tailored to this objective. Here, we give insight into potential failures when the exploration algorithm is designed with a different learning target in mind. Consider the following example. There are three actions, and the decision-maker would like to identify the best action to employ on average, across all contexts. Imagine that the context set describes two customer segments. Action 1 appeals to one segment, but is highly unappealing to the other. For action 2, the situation is reversed. Action 3 is not ideal for either segment, but is also not disliked by either. When personalization is inappropriate or costly, action 3 may be the preferred communal option.
The next example does not align with our formulation, because we take the prior distribution to be non-Gaussian. Similar issues can arise with a Gaussian prior, but its unbounded nature always allows for a nonzero– even if very small – chance that the mainstream action is better even for a specific segment. We omit analytical calculations of this more intricate case, since Example REF  seems already to capture the main intuition.
Example 4 (A mainstream action) 
Consider a problem with \(k=3\)  arms and 2 contexts given as \(\mathcal {X}= \lbrace e_1, e_2 \rbrace \) . The population distribution \(w\)  is uniform over \(\mathcal {X}\)  and \((X_t)_{t\in \mathbb {N}}\)  are drawn i.i.d from \(w\) . The components of the parameter vector \(\theta = (\theta _0, \theta _1, \theta _2)\)  are drawn independently with \(\theta _0 \sim {\rm Uniform}\left([0,1]\right)\)  and \(\theta _x \sim {\rm Uniform}\left(\lbrace  1,2 \rbrace \right)\)  for \(x\in [2]\) . Rewards are noiseless, with \(R_t= \mu (\theta , I_t, X_t)\) .
Observations are not subject to delay (i.e. \(L=1\) ).
Action 3's performance is insensitive to the context, and it always generates mean-reward \(\mu (\theta , 3,x) = \theta _0\) . Actions 1 and 2 generate mean rewards in context \(x\in \mathcal {X}\)  given by
\(\mu (\theta , 1, e_x)=1/2 + (1/2)\mathbb {1}( \theta _x=1), \quad \mu (\theta , 2, e_x)=1/2 + (1/2)\mathbb {1}( \theta _x=2).\) 

The next lemma formalizes that contextual Thompson sampling, which selects an action according to the posterior probability it is the optimal action for the current context, has simple regret that does not vanish even as the horizon grows. The same result applies to appropriate contextual versions of UCB. The simple reason is that action 3 is never sampled, because it does not maximize the reward in either context. This means no information about \(\theta _0\)  is gathered and the decision-maker cannot determine whether action 3 is the best arm to select. If the goal is to identify the best policy within a restricted class, the exploration algorithm needs to be designed so that it gathers the right information for this task. The proof follows from this argument and is omitted for brevity. At a high-level, contextual TS fails here because it does not reflect the true decision-objective.
Lemma 3 (Failure of contextual Thompson sampling) Suppose that \(\mathbb {P}(I_t = i \mid H_t) = \mathbb {P}( \operatornamewithlimits{arg\,max}_{j} \mu (\theta , j, X_t ) =i \mid H_t )\)  for each \(i\in [k]\) . Under Example REF , there is an absolute numerical constant \(c>0\)  such that for all \(T\in \mathbb {N}\) , \( \mathbb {E}\left[ \Delta _{T} \right] \geqslant c.\)


Proof of Proposition  REF
Matrix convex combinations.
Let \(\mathbb {S}^n\)  denote the set of symmetric \(n\times n\)  square matrices, and let \(\mathbb {S}^n_+\subset \mathbb {S}^n\)  denote the set of symmetric positive semidefinite matrices. A scalar function \(f: \mathbb {R} \rightarrow \mathbb {R}\)  can be extended to a function on symmetric matrices as follows. For any symmetric matrix \(A \in \mathbb {S}_n\) , one can write \(A=\sum _{i=1}^{n} \lambda _i u_i u_i^\top \)  where each \(\lambda _i\)  is a real eigenvalue and \(u_i\)  is the corresponding eigenvector. By defining \(f(A) = \sum _{i=1}^{n} f(\lambda _i) u_i u_i^\top \) , we have extended \(f\)  to a function mapping from \(\mathbb {S}_n\)  to \(\mathbb {S}_n\) . A function \(f\)  is said to be monotone increasing on the space of positive semidefinite matrices if for \(A,B \in \mathbb {S}^n_{+}\) , \(A\preceq B\)  implies \(f(A) \preceq f(B)\)  and monotone decreasing if this implies \(f(A) \succeq f(B)\) . A function \(f\)  is said to be operator convex on the space of positive definite matrices if for any \(A,B \in \mathbb {S}^n_{+}\)  and scalar \(\lambda \in [0,1]\) , \(f(\gamma A+(1-\gamma )B) \preceq \gamma f(A) + (1-\gamma ) f(B)\) . For our purposes, a key fact is that the inverse function \(f(A)= A^{-1}\)  is convex and monotone decreasing.
To prove Proposition REF , we need to leverage a generalization of Jensen's inequality that applies to matrix convex combinations. The following definitions and result can be found in [1]}. It provides a deep generalization of Jensen's inequality for operator convex functions, extending to a situation where the weights are matrices rather than scalars.
Definition 2 Let \(B_1, B_2\)  be Hermitian matrices. If \(A_1^\top A_1 + A_2^\top A_2=I\) , then the Hermitian matrix
\(A_1^\top B_1 A_1 + A_2^\top B_2 A_2\)  is called called a matrix convex combination of \(B_1\)  and \(B_2\) .

The next result in Theorem 8.5.2 in [1]} and a self-contained proof is given there.
Lemma 4 (Operator Jensen Inequality) 
Let \(f\)  be an operator convex on the space of symmetric positive semidefinite matrices \(\mathbb {S}_+^n\) . Let \(B_1, B_2 \in \mathbb {S}_+^n\) . If \(A_1^\top A_1 + A_2^\top A_2=I\)  then,
\(f\left(A_1^\top B_1 A_1 + A_2^\top B_2 A_2 \right) \preceq A_1^\top f(B_1) A_1 + A_2^\top f(B_2) A_2.\) 


Relating simple regret to posterior variance
Define the full information covariance matrix
\(S_{t, i} = {\rm Cov}(\theta ^{(i)} | H_t^+ ) = \left( \Sigma _{1}^{-1} + \sigma ^{-2} \sum _{\ell =1}^{t} \mathbb {1}\lbrace I_\ell = i\rbrace  X_{\ell } X_{\ell }^\top \right)^{-1}.\) 
This is posterior variance of \(\theta ^{(i)}\)  after observing reward generated by all \(t\)  actions measured prior to time \(t\) . See Section  for a discussion of the delayed history \(H_t\)  and the full information history \(H_t^+\) . One can also see that \(S_{t,i}=\Sigma _{t+L,i}\) .
The first key to our result reduces the problem of controlling the simple regret to the problem of controlling the expected posterior variance of the optimal arm.
[]lemmaregretFromVariance Under the conditions of Proposition REF ,
\(\mathbb {E}\left[\Delta _{T}\right] \leqslant \sqrt{ 2 \mathbb {H}(I^* \mid H^+_T) X_{\rm pop}^\top \mathbb {E}\left[ S_{T,I^*} \right] X_{\rm pop} }\) 


Define \(Z_i = \mu (\theta , i, w)\)  to be the uncertain population performance of arm \(i\) , \(M_{T,i}=\mathbb {E}\left[ Z_i | H_T^+ \right]= \left\langle X_{\rm pop}\, ,\, \mathbb {E}\left[\theta ^{(i)} \mid H_T^+ \right] \right\rangle \)  to be its posterior mean, and \(\sigma _{T,i}^2={\rm Var}\left( \mu (\theta , i, w) \mid H_T^+\right) = X_{\rm pop}^{\top } S_{T,i} X_{\rm pop}\)  to be its posterior variance. This notation is used only in this proof. Note that \(Z_{i}|H_T^+ \sim N(M_{T,i},\sigma _{T,i}^2 )\) . Take \(Z=(Z_1, \cdots , Z_k)\)  to be the vector. Let \(\tilde{I}\)  be a sample from the posterior distribution of \(I^*\) , i.e. \(\mathbb {P}(\tilde{I}=i \mid H_T^+) = \mathbb {P}(I^*=i \mid H_T^+)\)  but \(\tilde{I}\)  is independent of \((Z_1,\cdots , Z_k)\)  conditioned on \(H_T^+\) . We let \(I_{H_T^+}(Y_1; Y_2)\)  denote the mutual information between random variables \(Y_1\)  and \(Y_2\)  under the distribution \(\mathbb {P}((Y_1, Y_2)\in \cdot \mid H_T^+ )\) . This is random, due to its dependence on the history. Taking expectations yields the usual definition of mutual information, with \(\mathbb {E}\left[I_{H_T^+}\left( Y_1; Y_2 \right) \right] = I(Y_1; Y_2 \mid H_T^+)\) . This notation is used in this proof alone.
Recall that \(\hat{I}_T\in \operatornamewithlimits{arg\,max}_{i\in [k]} \mathbb {E}\left[ \mu (\theta , i, w) \mid H_T^+\right]\)  is the Bayes selection. Then
\(\mathbb {E}\left[ \Delta _{T}\right] = \mathbb {E}\left[ Z_{I^*} - Z_{ \hat{I}_T } \right] = \mathbb {E}\left[Z_{I^*} - \mathbb {E}\left[ Z_{ \hat{I}_T } \mid H_T^+ \right] \right] &\leqslant \mathbb {E}\left[Z_{I^*} - \mathbb {E}\left[ Z_{ \tilde{I} } \mid H_T^+ \right] \right] \\&=\mathbb {E}\left[Z_{I^*} - \mathbb {E}\left[ M_{T, \tilde{I}} \mid H_T^+ \right] \right]\\&\overset{(a)}{=}\mathbb {E}\left[Z_{I^*} - \mathbb {E}\left[ M_{T, I^*} \mid H_T^+ \right] \right]\\&= \mathbb {E}\left[ \mathbb {E}\left[Z_{I^*} - M_{T, I^*} \mid H^+_T \right]\right] \\&\overset{(b)}{\leqslant } \mathbb {E}\left[ \sqrt{ \mathbb {E}\left[ \sigma ^2_{T,I^*} \mid H_T^+\right] } \sqrt{ 2 I_{H_T^+}\left( I^* ; Z \right) } \right] \\&\overset{(c)}{\leqslant } \sqrt{ \mathbb {E}\left[ \mathbb {E}\left[ \sigma ^2_{T,I^*} \mid H_T^+\right] \right] } \sqrt{2\mathbb {E}\left[ I_{H_T^+}\left( I^* ; Z \right) \right]} \\&\overset{(d)}{=} \sqrt{ \mathbb {E}\left[ \sigma ^2_{T,I^*} \right] } \sqrt{2I\left( I^* ; Z \mid H^+_T\right)} \\&\leqslant \sqrt{ \mathbb {E}\left[ \sigma ^2_{T,I^*} \right] } \sqrt{2\mathbb {H}\left( I^* \mid H^+_T\right)}.\) 

Early steps of the proof use the tower property of conditional expectation. Step (a) is crucial and uses that fact that \(\tilde{I}\)  and \(I^*\)  have the same distribution conditions on \(H_T^+\)  and the vector \((M_{T,1},\cdots , M_{T,k})\)  is nonrandom conditioned on \(H_T^+\)  (formally is measurable with respect to the sigma-algebra \(H_T^+\)  generates). Step (b) applies Proposition 8 of [3]}. Step (c) applies the Hölder inequality, step (d) applies the tower property of conditional expectation, and the final step uses that entropy bounds mutual information.
In the setting of the next lemma, a standard sub-Gaussian maximal inequality would bound the largest deviation of \(Z_i\)  from its mean as \(\mathbb {E}\left[\max _{i\in [k]}| Z_i - \mu _i| \right] \leqslant (\max _{i\in [k] } \sigma _i) \sqrt{2 \log (n)}\) . For our purposes, the next result offers a critical improvement because it depends only on the variance at the likely realizations of \(I\) . A second improvement, which is the focus of the discussion in [3]}, is that the mutual information term \(I\left( Z; I \right)\)  could be much smaller than \(\log (n)\) .
Lemma (Proposition 8 of [3]}) 
Consider a random vector \(Z \in \mathbb {R}^n\)  and a random index \(I \in [n]\) . Suppose for each \(i\in [n]\)  that \(Z_i\)  has mean \(\mu _i\)  and the distribution of \(Z_i - \mu _i\)  is sub-Gaussian with variance proxy \(\sigma _i^2\) . Then
\(|\mathbb {E}\left[Z_I - \mu _I \right]| \leqslant \sqrt{ \mathbb {E}\left[ \sigma _I^2 \right] } \sqrt{2 I\left( Z; I \right) }.\) 


De-randomization
Even if we condition on \(X_{1:T}\)  as we do in Proposition REF , the posterior covariance is random because the actions \(I_1,\cdots ,I_T\)  are random. We consider the de-randomized analogue of the posterior covariance matrix,
\(\tilde{S}_{t,i} = \left( \Sigma _{1}^{-1} + \sigma ^{-2} \sum _{\ell =1}^{t} \mathbb {P}(I_{\ell }=i \mid H_{\ell }) X_{\ell } X_{\ell }^\top \right)^{-1},\) 
which effectively replaces \(\mathbb {1}(I_{\ell }=i)\)  with its conditional expectation, \(\alpha _{\ell ,i}=\mathbb {P}\left( I_{\ell }=i \mid H_{\ell } \right)\) . This matrix measures the extent to which the algorithm's allocation decisions \(\alpha _{1}, \cdots , \alpha _{t}\)  explore in each direction. This might be thought of as the posterior variance under Thompson sampling in a smoothed problem that allows for fractional arm measurement decisions.
The next lemma controls the impact of randomization, ensuring the posterior variance cannot be more than \(\iota \)  times larger in any direction than the idealized posterior covariance in (REF ). Using this, we focus on the idealized posterior covariance for the remainder of the proof of Propsition REF .
Lemma 5 (Controlling the impact of action randomization) 
For any \(T\in \mathbb {N}\) ,
\(\mathbb {E}\left[ S_{T,I^*} \right] \preceq \iota \cdot \mathbb {E}\left[\tilde{S}_{T, I^*}\right].\) 
where \(\iota \)  is defined as in Proposition REF .

The proof of Lemma REF , uses concentration techniques for matrix valued martingales that were popularized by [6]}, [7]}. By specializing a result like the matrix Friedman inequality of [6]}, we would be able to establish that an inequality like
\(\lambda _{\max }\left( S_{T,i}^{-1} - \tilde{S}_{T,i}^{-1} \ \right) \leqslant c \lambda _{\max }\left( \tilde{S}_{T,i}^{-1} \right) + \log (d/\delta ).\) 
We modify the proofs of [6]} to prove an inequality of the form
\(S_{T,i}^{-1} - \tilde{S}_{T,i}^{-1} \preceq c \tilde{S}_{T,i}^{-1} + \log (d/\delta ) I\) 
also holds with high probability. For our purposes (REF ) offers a critical improvement. The issue is that the decision-maker might gather very little information about some context directions and a lot of information about others. In that case, \(\tilde{S}_{T}^{-1}\)  would have some eigenvalues that are very small and others that are very large. To establish a result like Lemma REF , we need a result that bounds the scale of deviation along each particular direction in a more refined way. From (REF ), a direct (though messy) argument yields Lemma REF . This foray into matrix concentration is somewhat tangential, so we defer this proof until Subsection REF .

Using implicit propensity scores to complete the proof
Now, define
\(S_{{\rm full}} =\left(\Sigma _{1}^{-1} + \sigma ^{-2}\sum _{t=1}^{T} X_{t} X_{t}^\top \right)^{-1},\) 
which is the posterior covariance of \(\theta ^{(i)}\)  if the reward of arm \(i\)  were observed in every time period. The next lemma is the most essential one in our analysis. It upper bounds the idealized posterior covariance matrix by an expression that relates to the sampling variance of the inverse-propensity weighted least squares estimator. In particular, consider
\(\hat{\theta }^{(i)}_T = \operatornamewithlimits{arg\,min}_{\hat{\theta }\in \mathbb {R}^d} \sum _{t=1}^{T} (X_t^\top \hat{\theta } - \hat{R}_{t,i} )^2 + \sigma ^{2} \Vert  \hat{\theta }\Vert _{\Sigma _1^{-1}}^2 \quad \text{where} \quad \hat{R}_{t,i}=\frac{R_t \mathbb {1}(I_t=i) }{\mathbb {P}(I_t=i \mid H_t) },\) 
which is ridge regression applied to rewards that are de-biased by inverse propensity weighting. If \(\mathbb {P}(I_t=i\mid H_t) \)  and the \(X_t\)  were fixed and non-random, then the sampling variance of \(\hat{\theta }^{(i)}_T\)  could be shown to equal
\({\rm Cov}(\theta ^{(i)}_T \mid \theta , X_{1:T}) = S_{\rm full}\mathbb {E}\left[ \Sigma _{1}^{-1} + \sigma ^{-2}\sum _{t=1}^{T} \frac{ X_{t} X_{t}^\top (1+c_t) }{ \mathbb {P}(I_t=i \mid H_t) } \mid \theta , X_{1:T} \right] S_{{\rm full}}\) 
where \(c_t = \sigma ^{-2}\left( \mu (\theta , i, X_t) \right)^2\left(1-\mathbb {P}(I_t=i \mid H_t) \right)\geqslant 0\)  and this notation is used only temporarily to simplify this formula. This formula mirrors the behavior of the bound in Lemma REF . Lemma REF  can therefore be viewed as giving a bound on the posterior covariance by implicit propensity weighting.
*
 We use specialized notation in the proof. Since \(i\)  is fixed, drop it from notation and write \(p_{t}\equiv \mathbb {P}(I_t=i\mid H_t)\) . Set \(B_t = \sigma ^{-2} X_{t} X_{t}^\top \) . For notational convenience, set \(B_{0}=\Sigma _{1}^{-1}\)  and set \(p_{0}=1\) . We then can write \(\tilde{S}_{t,i}^{-1} = \sum _{t=0}^{T} p_{t} B_{t}\) . Define the full precision matrix \(\Lambda \equiv S_{{\rm full}}^{-1} = \sum _{t=0}^{T} B_{t}\) . We have,
\(\tilde{S}_{T,i} = \left(\sum _{t=0}^{T} p_{t} B_{t}\right)^{-1} &= \Lambda ^{-1/2}\left[ \Lambda ^{-1/2} \left(\sum _{t=0}^{T} p_{t} B_{t}\right) \Lambda ^{-1/2} \right]^{-1} \Lambda ^{-1/2}\\&=\Lambda ^{-1/2}\left[ \Lambda ^{-1/2} \left(\sum _{t=0}^{T} B_{t}^{1/2} [p_{t} I ] B_{t}^{1/2}\right) \Lambda ^{-1/2} \right]^{-1} \Lambda ^{-1/2} \\&=\Lambda ^{-1/2}\left[ \sum _{t=0}^{T} \left(\Lambda ^{-1/2} B_{t}^{1/2}\right) [p_{t} I ] \left( B_{t}^{1/2} \Lambda ^{-1/2} \right) \right]^{-1} \Lambda ^{-1/2} \\&\preceq \Lambda ^{-1/2}\left[ \sum _{t=0}^{T} \left(\Lambda ^{-1/2} B_{t}^{1/2}\right) [p_{t} I ]^{-1} \left( B_{t}^{1/2} \Lambda ^{-1/2} \right) \right] \Lambda ^{-1/2} \\&= \Lambda ^{-1} \left( \sum _{t=0}^{T} \frac{B_{t}}{p_{t} } \right) \Lambda ^{-1}.\) 

The inequality applies the operator Jensen inequality in Lemma REF , using that
\(\sum _{t= 0}^{T} \left(\Lambda ^{-1/2} B_{\ell }^{1/2}\right) \left(\Lambda ^{-1/2} B_{t}^{1/2} \right)^\top = \Lambda ^{-1/2} \left(\sum _{t=0}^{T} B_{t} \right) \Lambda ^{-1/2} = \Lambda ^{-1/2} \Lambda \Lambda ^{-1/2} = I.\) 

To simplify the discussion, consider the case where DTS is applied with \(\beta _t=1\) . Then, conditional probability some action \(i\in [k]\)  is selected is the posterior probability it is optimal, i.e. \(\mathbb {P}(I_t=i \mid H_t) = \mathbb {P}(I^*=i \mid H_t)\) . The challenge with using the posterior probabilities as inverse propensity weights is that they often decay to zero at an exponential rate for some actions. The key to our proof is that we only need to control the propensity assigned to the optimal action and this does not shrink, due to the next lemma. Recall \(\alpha _{t,i}=\mathbb {P}(I^*=i \mid H_t)\)  is best-arm learning problems.
Lemma 6 (Inverse propensity of the optimal action)  For any \(t\in \mathbb {N}\) , \(\mathbb {E}\left[ 1/ \alpha _{t,I^*} \right] = k\) .

By the tower property of conditional expectation, and the fact that \(\alpha _{t,i}\)  is \(H_t\)  measurable,
\(\mathbb {E}\left[ \frac{1}{ \alpha _{t,I^*} } \right] = \sum _{i=1}^{k} \mathbb {E}\left[ \frac{ \mathbb {1}(I^*=i) }{ \alpha _{t,i} } \right] = \sum _{i=1}^{k} \mathbb {E}\left[ \mathbb {E}\left[ \frac{ \mathbb {1}(I^*=i) }{ \alpha _{t,i} } \, \bigg \vert \, H_t \right] \right]= \sum _{i=1}^{k} \mathbb {E}\left[ \frac{ \alpha _{t,i} }{ \alpha _{t,i} } \right] =k.\) 
Below, we use this to bounding the \(\mathbb {E}\left[ S_{T,I^*} \right]\)  term in Lemma REF , which, crucially, down-weights the importance of having low posterior variance at arms that are unlikely to be optimal. Combining the next lemma, Lemma REF  and Lemma REF  completes the proof of Proposition REF .
Lemma 7 (Posterior variance bound)  Under the conditions of Proposition REF ,
\(\mathbb {E}\left[ \tilde{S}_{T,I^*} \right] \preceq 2 k \cdot S_{\rm full}\) 

Under DTS with \(\beta _t \geqslant 1/2\) , we have \(\mathbb {P}(I_t= i \mid H_t) \geqslant \alpha _{t,i}/2\) . By Lemma REF ,
\(\tilde{S}_{T,i} \preceq S_{{\rm full}} \left( \Sigma _{1}^{-1} + \sigma ^{-2}\sum _{t=1}^{T} \frac{ X_{t} X_{t}^\top }{ \mathbb {P}(I_t=i \mid H_t) } \right) S_{{\rm full}} \preceq S_{{\rm full}} \left( \Sigma _{1}^{-1} + \sigma ^{-2}\sum _{t=1}^{T} \frac{2 X_{t} X_{t}^\top }{ \alpha _{t,i} } \right) S_{{\rm full}}.\) 
Applying this with Lemma REF  gives
\(\mathbb {E}\left[\tilde{S}_{T,I^* }\right] \preceq S_{{\rm full}} \left( \Sigma _{1}^{-1} + 2\sigma ^{-2}\sum _{t=1}^{T} X_{t} X_{t}^\top \mathbb {E}\left[ \frac{1}{\alpha _{t, I^*}} \right] \right) S_{{\rm full}} &\preceq S_{{\rm full}} \left( \Sigma _{1}^{-1} + 2k\sigma ^{-2}\sum _{t=1}^{T} X_{t} X_{t}^\top \right) S_{{\rm full}} \\&\preceq S_{{\rm full}} \left( 2k \Sigma _{1}^{-1} + 2k\sigma ^{-2}\sum _{t=1}^{T} X_{t} X_{t}^\top \right) S_{{\rm full}}\\&= 2k \cdot S_{{\rm full}}.\) 

Proof of Corollary  REF
[Proof of Corollary REF ]
Our goal is to show that \(V(x_{1:T})\preceq \sigma ^2 /T\)  where
\(V(x_{1:T}) = X_{\rm pop}^\top \left( \Sigma _1^{-1} + \sigma ^{-2}\sum _{t=1}^{T} x_t x_t^\top \right)^{-1} X_{\rm pop} \preceq X_{\rm pop}^\top \left( \underbrace{ \lambda _{\min }\left(\Sigma _1^{-1}\right) I + \sigma ^{-2}\sum _{t=1}^{T} X_{\rm pop}X_{\rm pop}^\top }_{:=\Lambda } \right)^{-1} X_{\rm pop}.\) 
The matrix \(\Lambda \)  has an eigenvector \(v=\mathbb {E}[X_{\rm pop}] \)  with eigenvalue \(\lambda = \lambda _{\min }(\Sigma _1^{-1})+ \sigma ^{-2} T\Vert  \mathbb {E}[X_{\rm pop}]\Vert ^2_2 \) . Then \(v\)  is also an eigenvalue of \(\Lambda ^{-1}\)  with corresponding eigenvalue \(1/\lambda \) . Therefore \(v^\top \Lambda ^{-1} v = v^\top \left[ v /\lambda \right]= \Vert v\Vert _2^2 /\lambda \leqslant \sigma ^2 / T\) .

Returning to prove Lemma  REF
Notation
For most of the remainder of this proof, we fix an arm \(i\) . It is cleaner to omit \(i\)  from the notation for the time being. We then face the following problem. There is a random process \((Z_{t})_{t \in \mathbb {N}}\)  where \(Z_t \in \lbrace 0,1\rbrace \)  (\(\cdots \)  think of \(Z_t\)  as \(\mathbb {1}(I_t=i)\) ) and a deterministic sequence of vectors \((x_t)_{t \in \mathbb {N}}\)  where \(x_t \in \mathbb {R}^d\)  satisfies \(\Vert x_t\Vert _2\leqslant 1\) . Suppose that \((Z_{t})_{t \in \mathbb {N}}\)  is adapted to some filtration \((\mathcal {F}_t)_{t\in \mathbb {N} }\) . We take \(\mathbb {P}_{t}(\cdot )=\mathbb {P}(\cdot \mid \mathcal {F}_{t-1} )\) . We are interested in the random matrices
\(S_T^{-1} = \Sigma _1^{-1} + \sum _{t=1}^{T} Z_t x_t x_t^\top \quad \text{and} \quad \tilde{S}_T^{-1}= \Sigma _1^{-1} + \sum _{t=1}^{T} p_t x_t x_t^\top \) 
where \(p_{t}=\mathbb {P}_{t-1}(Z_t=1)\) .
Define \(D_t = (p_t-Z_t) x_t x_t^\top \) . We study
\(A_0 := 0 \qquad \text{and} \qquad A_{t} := \tilde{S}_t^{-1}- S_t^{-1} = \sum _{\ell =1}^{t} D_\ell ,\) 
which in the sum of matrix martingale differences . We will follow [6]} fairly closely. Define \(\phi _t(\gamma ):=\log \mathbb {E}_{t-1}\left[ e^{\gamma D_t} \right]\) . Then set
\(\Phi _0 := 0 \quad \text{and} \quad \Phi _t(\gamma ) := \sum _{\ell =1}^{t}\phi _\ell (\gamma ).\) 
Here \(\Phi _T(\gamma )\)  measures the total variability of the process. Our aim is to show that \(A_T\)  can only be large if \(\Phi _T(\gamma )\)  is large.

A Bernstein-type bound on the cumulants.
We first recall a random matrix analogue of Bernstein's bound on the moment generating function of bounded random variables.
Lemma 8 (Lemma 6.7 of [7]}) 
Suppose \(D\)  is a random self-adjoint matrix that satisfies
\(\mathbb {E}D = 0 \quad \text{and} \quad \mathbb {P}\left(\lambda _{\max }(D)\leqslant 1\right)=1.\) 
Then
\(\mathbb {E}e^{\gamma D} \preceq \exp \left( (e^{\gamma } - \gamma -1) \mathbb {E}[D^2] \right)\) 

As a consequence of this, we can bound the sum of cumulants \(\Phi _t(\gamma )\)  by a simpler quantity that closely mimics \(\tilde{S}_T\) .
Lemma 9 
For any \(\gamma >0\) ,
\(\Phi _T(\gamma ) \preceq \left( e^{\gamma } - \gamma -1 \right)\sum _{t=1}^{T} p_t x_t x_t^\top .\) 

For notional convenience define \(f(\gamma )=e^{\gamma } - \gamma -1.\)  We have \(\lambda _{\max }(D_t)\leqslant | \alpha _t - Z_t | {\rm tr}\left( x_t x_t^\top \right) \leqslant \Vert x_t\Vert _2^2 \leqslant 1\) , which will allow us to apply the matrix Bernestin inequality above. We have immediately that
\(\phi _t(\gamma ) \preceq f(\gamma ) \mathbb {E}_{t-1}\left[ D_t^2\right]\) . Using this gives,
\(\Phi _{T}(\gamma ) \preceq f(\gamma )\sum _{t=1}^{T} \mathbb {E}_{t-1}\left[D_t^2\right] &= f(\gamma )\sum _{t=1}^{T} \mathbb {E}_{t-1}\left[(p_t- Z_t)^2\right] \left(x_t x_t^\top \right)\left(x_t x_t^\top \right) \\&= f(\gamma )\sum _{t=1}^{T} \alpha _t (1-p_t) \Vert  x_t \Vert _2^2 \, x_t x_t^\top \\&\preceq f(\gamma )\sum _{t=1}^{T} p_t x_t x_t^\top .\) 

An exponential super-martingale.
Again, our goal is to show that \(A_t\)  can only be large if \(\Phi _t(\gamma )\)  is large. To this end, define
\(M_{t}(\gamma ) = {\rm tr} \exp \lbrace  \gamma A_t - \Phi _t(\gamma ) \rbrace  \qquad t\in \lbrace 0,1,\cdots \rbrace \) 
where \({\rm tr}\)  denotes the trace operator. We now show that \(M_{t}(\gamma )\)  is a super-martingale, following the proof of Lemma 2.1 of [6]}. We first state a powerful result of [13]} and then recall a simple corollary that is stated also in [6]}.
Theorem (Lieb, 1973)  Fix a self-adjoint matrix \(H\) . The function \(A \mapsto {\rm tr} \exp (H+ \log (A))\)  is concave on the positive-definite cone.

Corollary 2 
Fix a self-adjoint matrix \(H\) . For a random self-adjoint matrix \(X\) ,
\(\mathbb {E}\left[ {\rm tr} \exp (H+X) \right] \leqslant {\rm tr} \exp ( H + \log ( \mathbb {E}e^{X} ) ).\) 

We now conclude that \(M_{t}(\gamma )\)  is a super-martingale.
Corollary 3 
For each \(\gamma >0\) , \(\lbrace  M_t(\gamma ) : t=0, 1, \cdots \rbrace \)  is a super-martingale with initial value \(M_0(\gamma )=d\) .

By definition,
\(M_0(\gamma )= {\rm tr}\exp \lbrace  \gamma A_0 - \Phi _{0}(\gamma ) \rbrace  = {\rm tr}\exp \lbrace  0 \rbrace = {\rm tr} I = d.\) 
For \(t>0\) , taking conditional expectations gives
\(\mathbb {E}_{t-1}\left[ M_{t}(\gamma )\right] &= \mathbb {E}_{t-1}\left[ {\rm tr} \exp \lbrace  \gamma A_{t-1} - \Phi _{t}(\gamma ) + \gamma D_t \rbrace  \right]\\&\leqslant {\rm tr} \exp \lbrace  \gamma A_{t-1} - \Phi _{t}(\gamma ) + \phi _{t}(\gamma ) \rbrace  \\&= {\rm tr} \exp \lbrace  \gamma A_{t-1} - \Phi _{t-1}(\gamma ) \rbrace  = M_{t-1}(\gamma ),\) 

where the inequality follows by Corollary REF .

Boundary crossing probabilities.
Here is where we begin to deviate somewhat from [6]}. The next result gives a boundary that \(A_t\)  is unlikely to ever cross. The proof applies the same stopping time argument as the proof of one of Doob's martingale inequalities.
Lemma 10 
For any fixed \(\delta >0\)  and \(\gamma >0\) , with probability exceeding \(1-\delta \) ,
\(A_{t} \preceq \frac{1}{\gamma } \left[\Phi _{t}(\gamma ) + \log (d/\delta ) I\right]\) 
holds simultaneously for all \(t\in \mathbb {N}\) .

Fix \(\gamma >0\)  throughout. We have
\(\mathbb {P}\left( \lambda _{\max }\left( \gamma A_{t} - \Phi _{t}(\gamma ) \right) \geqslant y \right) = \mathbb {P}\left( e^{\lambda _{\max }\left( \gamma A_{t} - \Phi _{t}(\gamma ) \right)} \geqslant e^y \right) &\leqslant \mathbb {P}\left( {\rm tr} \, e^{\left( \gamma A_{t} - \Phi _{t}(\gamma ) \right)} \geqslant e^{y}\right) \\&\leqslant e^{-y} \mathbb {E}\left[ {\rm tr} \, e^{\left( \gamma A_{t} - \Phi _{t}(\gamma ) \right)} \right] \\ &= e^{-y}\mathbb {E}\left[ M_{t}(\gamma ) \right].\) 

The same inequalities hold for any bounded stopping time \(\tau \) , yielding
\(\mathbb {P}\left( \lambda _{\max }\left( \gamma A_{\tau } - \Phi _{\tau }(\gamma ) \right) \geqslant y \right) \leqslant e^{-y} \mathbb {E}\left[ M_{\tau }(\gamma )\right].\) 
Take \(\tau = \inf \lbrace  t \in \mathbb {N} : \lambda _{\max }\left( \gamma A_{t} - \Phi _{t }(\gamma ) \right) \geqslant y \rbrace \) , with the convention that \(\tau =\infty \)  if \( \lambda _{\max }\left( \gamma A_{t} - \Phi _{t }(\gamma ) \right) < y\)  for every \(t\in \mathbb {N}\) . Then,
\(\mathbb {P}\left( \exists t \leqslant N : \lambda _{\max }\left( \gamma A_{t} - \Phi _{t }(\gamma ) \right) \geqslant y \right) = \mathbb {P}\left( \lambda _{\max }\left( \gamma A_{\tau \wedge N} - \Phi _{\tau \wedge N }(\gamma ) \right) \geqslant y\right) \leqslant \mathbb {E}\left[ M_{\tau \wedge N}(\gamma )\right] e^{-y}\leqslant d e^{-y}.\) 
That \(\mathbb {E}\left[ M_{\tau \wedge N}(\gamma ) \right] \leqslant d\)  uses Corollary REF  and Doob's optional sampling theorem. Taking \(N\rightarrow \infty \)  and applying the monotone convergence theorem gives,
\(\mathbb {P}\left( \exists t \in \mathbb {N} : \lambda _{\max }\left( \gamma A_{t} - \Phi _{t }(\gamma ) \right) \geqslant y \right) \leqslant d e^{-y}.\) 
Choosing \(y=\log (d/\delta )\) , we have that with probability at least \(1-\delta \) , the inequality
\(\lambda _{\max }\left( \gamma A_{t} - \Phi _{t }(\gamma ) \right) \leqslant \log \left( d/\delta \right)\) 
holds for every \(t\in \mathbb {N}\) .
The next result bounds the deviation \(S_t^{-1} - \tilde{S}_{t}^{-1}\)  in terms of \(\tilde{S}_{t}^{-1}\) . Notice that \(2-e<0\) , so the right hand side if this inequality is a negative definite matrix. But we also get the inequality \(S_t^{-1} \succeq (3-e)\tilde{S}_{t}^{-1} - \log (d/\delta ) I\)  and here it is important that \(3-e >0\) .
Lemma 11  For any given \(\delta >0\) , with probability at least \(1-\delta \) , the inequality
\(S_{t}^{-1} -\tilde{S}_{t}^{-1} \succeq \left(2-e \right) \tilde{S}_{t}^{-1} -\log (d/\delta ) I\) 
holds for every \(t\in \mathbb {N}\) .

Define \(f(\gamma )=e^{\gamma } - \gamma -1\) . Recall \(A_{t} := \tilde{S}_t^{-1}- S_t^{-1}\) . By applying Lemma REF  and Lemma REF , we get that with probability at least \(1-\delta \) ,
\(S_{t}^{-1} - \tilde{S}^{-1}_t = -A_t \succeq - \frac{1}{\gamma } \left[\Phi _{t}(\gamma ) + \log (d/\delta ) I\right] \succeq -\frac{1}{\gamma } \left[f(\gamma )\sum _{t=1}^{t} p_{\ell } x_{\ell } x_{\ell }^\top + \log (d/\delta ) \right] .\) 

Picking \(\gamma =1\) , we have
\(S_{t}^{-1} - \tilde{S}^{-1}_t \succeq (2-e) \sum _{\ell =1}^{t} p_\ell x_\ell x_\ell ^\top - \log (d/\delta ) I= (2-e) \tilde{S}_{t}^{-1} - \log (d/\delta ) I.\) 

Multiplicative ratio deviation inequality.
Lemma 12 For any \(\delta >0\) , with probability exceeding \(1-\delta \) , the following inequality holds simultaneously for every \(t\in \mathbb {N}:\)
\(S_{t} \preceq c_\delta \tilde{S}_{t} \quad \text{where} \quad c_\delta = \max \left\lbrace 8 \log (d/\delta ) \cdot \lambda _{\max }(\Sigma _1) \, , \, 8 \right\rbrace \) 

From Lemma REF , we have that \(S_t^{-1} \succeq (3-e)\tilde{S}_{t}^{-1} - \log (d/\delta ) I.\)  We also know that \(S_{t}^{-1} \succeq \Sigma _{1}^{-1}\) . Combining these implies that for any arbitrary unit vector \(u\) ,
\(u^\top S_{t}^{-1} u \geqslant \max \left\lbrace  \lambda _{\min }(\Sigma _1^{-1}), \left(3-e \right) u^\top \tilde{S}_{t}^{-1} u - \log (d/\delta ) \right\rbrace .\) 
If \( \left(3-e \right) u^\top \tilde{S}_{t}^{-1} u \geqslant 2\log (d/\delta )\) , we have \(u^\top S_{t}^{-1} u \geqslant \frac{3-e}{2} u^\top \tilde{S}_{t}^{-1} u .\) 
On the other hand, if \(\left(3-e \right) u^\top \tilde{S}_{t}^{-1} u \leqslant 2\log (d/\delta )\) , we have
\(u^\top S_{t}^{-1} u \geqslant \lambda _{\min }(\Sigma _1^{-1}) = \frac{\lambda _{\min }(\Sigma _1^{-1}) }{ 2\log (d/\delta ) } \cdot 2\log (d/\delta ) \geqslant \frac{\lambda _{\min }(\Sigma _1^{-1}) }{ \log (d/\delta ) } \cdot \frac{3-e}{2} \cdot u^\top \tilde{S}_{t}^{-1} u \) 
In either case we have that for an arbitrary unit vector \(u\) ,
\(u^\top S_{t}^{-1} u \geqslant c_1 u^\top \tilde{S}_{t}^{-1} u \quad \text{where} \quad c_1= \min \left\lbrace  \frac{\lambda _{\min }(\Sigma _1^{-1}) }{ \log (d/\delta ) } \, , \, 1 \right\rbrace  \cdot \frac{3-e}{2}\) 
Viewing this as a relation of the form \(S_{t}^{-1} \succeq c_1 \tilde{S}_{t}^{-1}\)  and taking the inverse gives the result. We also simplify the expression using that \(\frac{2}{3-e} <8\) .

Completing the proof of Lemma  REF
The remainder of the proof follows by a messy calculation.
[Proof of Lemma REF ]
For any \(\delta >0\) , with probability exceeding \(1-\delta \) , the following inequality holds simultaneously for every \(T\in \mathbb {N}\) :
\(S_{T,i} \preceq c_\delta \tilde{S}_{T,i} \quad \text{where} \quad c_\delta = \max \left\lbrace 8 \log (d/\delta ) \cdot \lambda _{\max }(\Sigma _1) \, , \, 8 \right\rbrace \) 
Combining this with the fact that \(S_{T,i} \preceq \Sigma _{1}\)  almost surely, we have, that for every \(\delta >0\)
\(\mathbb {E}\left[ S_{T,i} \right] \preceq c_\delta \mathbb {E}\left[\tilde{S}_{T,i} \right] + \delta \Sigma _{1}.\) 
Using also that \(\tilde{S}_{T,i} \succeq S_{\rm Full}\)  almost surely and choosing \(\delta ^* = \lambda _{\min }( S_{\rm full}) / \lambda _{\max }(\Sigma _{1})\)  gives,
\(\mathbb {E}\left[ S_{T,i} \right] \preceq c_{\delta ^*} \mathbb {E}\left[\tilde{S}_{T,i} \right] + \delta ^* \Sigma _{1}\preceq c_{\delta ^*} \mathbb {E}\left[\tilde{S}_{T,i} \right] + \lambda _{\min }( S_{\rm full}) I \preceq \left(c_{\delta ^*} +1\right) \mathbb {E}\left[\tilde{S}_{T,i} \right].\) 
Now,
\(c_{\delta ^*}+1 &= \max \left\lbrace 8 \log (d/\delta ^*) \cdot \lambda _{\max }(\Sigma _1) \, , \, 8 \right\rbrace  +1 \\&\leqslant \max \left\lbrace 9 \log (d/\delta ^*) \cdot \lambda _{\max }(\Sigma _1) \, , \, 9 \right\rbrace  \\&= \max \left\lbrace 9 \log \left( \frac{d\lambda _{\max }(\Sigma _1) }{\lambda _{\min }(S_{\rm Full})} \right) \cdot \lambda _{\max }(\Sigma _1) \, , \, 9 \right\rbrace  \\&= \max \left\lbrace 9 \log \left( d\lambda _{\max }(\Sigma _1) \lambda _{\max }(S_{\rm Full}^{-1}) \right) \cdot \lambda _{\max }(\Sigma _1) \, , \, 9 \right\rbrace  \\&\leqslant \max \left\lbrace 9 \log \left( d\lambda _{\max }(\Sigma _1)\left[ \lambda _{\max }\left(\Sigma _1^{-1}\right) + T \right] \right) \cdot \lambda _{\max }(\Sigma _1) \, , \, 9 \right\rbrace .\) 

The last step uses that \(S_{\rm Full}^{-1} =\left(\Sigma _1^{-1} + \sum _{t=1}^{T} x_t x_t^\top \right) \preceq \left( \lambda _{\max }\left(\Sigma _1^{-1}\right) + T \right) I \) .

Efficient Implementation of Algorithm REF  and Proof of Lemma  REF
In this section, we show that the tuning parameter \(\beta _t\)  in Algorithm REF  can be calculated by solving a one-dimensional fixed-point equation. This could be implemented efficiently by using bisection search or by Newton's method.
If \(\operatornamewithlimits{arg\,max}_{i\in [k]} m_{t,i}\)  is not unique, Algorithm REF  simply sets \(\beta _t = \beta _{t-1}\) . Now suppose \(\operatornamewithlimits{arg\,max}_{i\in [k]} m_{t,i}\)  is unique. Recall \(\hat{I}_t=\operatornamewithlimits{arg\,max}_{i\in [k]} m_{t,i}\) , and
define \(\Delta _{t,i}\triangleq m_{t,\hat{I}_t} - m_{t,i}\)  for each \(i\in [k]\) . Equation (REF ) implies there exists \(y>0\)  such that
\(\frac{1+ \hat{p}_{\hat{I}_t}\hat{p}_i^{-1}}{\Delta _{t,i}^2} = y,\quad \forall i\ne \hat{I}_t.\) 
Clearly \(y >\max _{i\ne \hat{I}_t} \Delta _{t,i}^{-2} \)  and
\(\frac{\hat{p}_{\hat{I}_t}}{\hat{p}_i} = \Delta _{t,i}^2 y - 1, \quad \forall i\ne \hat{I}_t.\) 
Equation (REF ) together with Equation () imply
\(\sum _{i\ne \hat{I}_t} \left(\Delta _{t,i}^2y-1\right)^{-2} = 1.\) 
Let \(y_t\)  solves Equation (REF ). We can solve this fixed-point equation for \(y\)  using, for example, bisection search or Newton's method. Notice that if Newton's method is used, one may wish to save the value of \(y_{t-1}\)  solved in the previous time period, which provides an effective initial point for finding an updated value \(y_t\) .
Finally \(\sum _{i\in [k]} \hat{p}_i = 1\)  and Equation (REF ) imply
\(\beta _t = \hat{p}_{\hat{I}_t} = \frac{1}{1+ \sum _{i\ne \hat{I}_t}\left(\Delta _{t,i}^2y_t-1\right)^{-1}}.\) 
This completes the proof of Lemma  REF
In this section, we also include the following uniform bounds on the tuning parameters produced by Algorithm REF .
Lemma 13 
Under Algorithm REF , for any \(t\in \mathbb {N}\) ,
\(\frac{1}{1+\sqrt{k-1}}\leqslant \beta _t \leqslant 1/2.\) 

We prove this result by induction. Under Algorithm REF , \(\beta _1 = 1/2\)  satisfies Equation (REF ), and suppose \(\beta _{t-1}\)  satisfies Equation (REF ).
If \(\operatornamewithlimits{arg\,max}_{i\in [k]} m_{t,i}\)  is not unique, we are done since \(\beta _t = \beta _{t-1}\) .
Now suppose \(\hat{I}_t=\operatornamewithlimits{arg\,max}_{i\in [k]} m_{t,i}\)  is unique, and we are going to show \(\beta _t = \hat{p}_{\hat{I}_t}\)  satisfies Equation (REF ) where
\(\hat{p}=p^*(\mu _{t})\)  is the solution to Equations (REF ) and ().
By Equation (),
\(\hat{p}_{\hat{I}_t} = \sqrt{\sum _{i\ne \hat{I}_t} \hat{p}_i^2} \leqslant \sum _{i\ne \hat{I}_t} \hat{p}_i = 1 - \hat{p}_{\hat{I}_t},\) 
which gives \(\hat{p}_{\hat{I}_t}\leqslant 1/2\) . On the other hand, by using the Cauchy-Schwarz inequality, we have
\(\hat{p}_{\hat{I}_t} = \sqrt{\sum _{i\ne \hat{I}_t} \hat{p}_i^2} \geqslant \frac{\sum _{i\ne \hat{I}_t} \hat{p}_i}{\sqrt{k-1}} = \frac{1-\hat{p}_{\hat{I}_t}}{\sqrt{k-1}},\) 
which gives \(\hat{p}_{\hat{I}_t} \geqslant \frac{1}{1+\sqrt{k-1}}\) .
This completes the proof.

Proof of the Lower Bound in Proposition  REF
The lower bound in Proposition REF  follows from the next proposition, which characterizes the sample size required to ensure simple regret vanishes at a desired rate. To see this, suppose that (REF ) does not hold. Since \(c\tau \geqslant 0\) , this implies \(\mathbb {E}\left[ \Delta _{\tau } \mid \theta = \theta _1 \right] = O(c \log (1/c))\)  for every \(\theta _1\) . Then (REF ) implies
\(\mathbb {E}\left[ c \tau + \Delta _{\tau } \mid \theta = \theta _0 \right] \geqslant c\mathbb {E}\left[ \tau \mid \theta = \theta _0 \right] \geqslant c\left[\Gamma _{\theta _0} +o_{\theta _0}(1)\right]\log \left(1/ [c\log (1/c)]\right) =c\left[\Gamma _{\theta _0} +o_{\theta _0}(1)\right]\log (1/ c). \) 
Proposition 4  Suppose Assumption REF  holds. Under any admissible sampling rule, stopping rule \(\tau =\tau (\delta )\) , and selection rule, if as \(\delta \rightarrow 0\) ,
\(\mathbb {E}\left[ \Delta _{\tau } \mid \theta = \theta _0 \right] = O_{\theta _0}\left( \delta \right) \quad \text{for all } \theta _0 \in \Theta ,\) 
then
\(\mathbb {E}\left[ \tau \mid \theta = \theta _0 \right] \geqslant \left[\Gamma _{\theta _0} +o_{\theta _0}(1)\right]\log (1/\delta ) \qquad \text{for all } \theta _0\in \Theta .\) 

In this section we describe the sequence of results that lead to the lower bound in Proposition REF .
It is derived formally as the solution to a two-player zero-sum game between an experimenter and nature.
A general change of measure argument.
Consider two alternative states of nature \(\theta _0, \theta _1 \in \Theta \)  under which the optimal arm differs (i.e. \(I^*(\theta _0) \ne I^*(\theta _1))\) . The decision-maker would like to reach the correct decision in each case. That is, if the decision-maker stops at time \(\tau \)  and picks arm \(\hat{I}^+_{\tau }\) , they would like \(\mathbb {P}(\hat{I}^+_{\tau } = I^*(\theta _0) \mid \theta = \theta _0)\)  and \(\mathbb {P}(\hat{I}^+_{\tau } = I^*(\theta _1) \mid \theta = \theta _1)\)  to each be close to one. Stated differently, they would like there to be a large divergence between the distribution of \(\hat{I}^+_{\tau }\)  under \(\theta _0\)  and \(\theta _1\) . The next result makes this formal.
Lemma 14 (Bretagnolle–Huber inequality) 
Fix any \(\theta _0, \theta _1 \in \Theta \) . If \(\mathbb {P}(\tau < \infty \mid \theta =\theta _0)=1\) ,
\(\mathbb {P}\left( \hat{I}^+_\tau \ne I^*(\theta _0) \mid \theta = \theta _0 \right) + \mathbb {P}\left( \hat{I}^+_\tau = I^*(\theta _0) \mid \theta = \theta _1 \right) \geqslant \frac{1}{2} \exp \left\lbrace  - D_{\rm KL}\left(\mathbb {P}(H^+_{\tau } \in \cdot \mid \theta = \theta _0) \, || \, \mathbb {P}(H^+_{\tau } \in \cdot \mid \theta = \theta _1)\right) \right\rbrace .\) 

See [16]}.

If (REF ) holds as \(\delta \rightarrow 0\) , the the left-hand-side in the lemma above is \(O(\delta )\) . Taking the logarithm of both sides and dividing each side by \(\log (1/\delta )\)  yields the next corollary.
Corollary 4 
Suppose (REF ) holds as \(\delta \rightarrow 0\) . Fix any \(\theta _1\in \Theta \)  such that \(I^*(\theta _1) \ne I^*(\theta _0)\) . Then,
\(\limsup _{\delta \rightarrow 0} \frac{D_{\rm KL}\left(\mathbb {P}(H^+_{\tau } \in \cdot \mid \theta = \theta _0) \, || \, \mathbb {P}(H^+_{\tau } \in \cdot \mid \theta = \theta _1)\right)}{\log (1/\delta )} \geqslant 1.\) 

If the decision-maker wants to reach a correct decision with high probability, they need to gather a collection of observations (or history) that discriminates between \(\theta _0\)  and \(\theta _1\)  in the sense of making the divergence above large. Thankfully, this divergence has an explicit expression, which is given in the lemma below.
Lemma 15 
Fix any \(\theta _0, \theta _1 \in \Theta \) . If \(\mathbb {P}(\tau < \infty \mid \theta =\theta _0)=1\)  then,
\(D_{\rm KL}( \mathbb {P}\left( H^+_\tau \in \cdot \mid \theta = \theta _0 \right) \, || \, \mathbb {P}\left( H^+_\tau \in \cdot \mid \theta = \theta _1 \right) )=\frac{1}{2\sigma ^2}\sum _{i\in [k]} \left(\theta _0^{(i)} - \theta _{1}^{(i)}\right)^\top \mathbb {E}\left[ \sum _{t=1}^{\tau }\mathbb {1}(I_t =i) X_t X_t^\top \mid \theta =\theta _0\right]\left(\theta _0^{(i)} - \theta _1^{(i)}\right).\) 

Recall that \(H^+_t = ( (X_\ell , I_\ell , R_\ell ) : \ell =1,\cdots , t)\) . Let \(\mathbb {P}_i = \mathbb {P}( \cdot \mid \theta = \theta _i)\)  and \(\mathbb {E}_i = \mathbb {E}[ \cdot \mid \theta = \theta _i]\)  for \(i=1,2\) . The chain rule for stopping times in Lemma REF  implies
\(D_{\rm KL}\left( \mathbb {P}_0( H_\tau ^{+} \in \cdot ) \, || \, \mathbb {P}_1( H^+_\tau \in \cdot ) \right) =& \mathbb {E}_0 \left[ \sum _{t=1}^{\tau } D_{\rm KL}\left( \mathbb {P}_0( (X_t, I_t, R_t) \in \cdot \mid H^+_{t-1}) \, || \, \mathbb {P}_1( (X_t, I_t, R_t) \in \cdot \mid H^+_{t-1}) \right) \right] \\=& \mathbb {E}_0 \left[ \sum _{t=1}^{\tau } D_{\rm KL}\left( \mathbb {P}_0( (X_t, I_t) \in \cdot \mid H^+_{t-1}) \, || \, \mathbb {P}_1( (X_t, I_t) \in \cdot \mid H^+_{t-1}) \right) \right]\\&+ \mathbb {E}_0 \left[ \sum _{t=1}^{\tau } D_{\rm KL}\left( \mathbb {P}_0( R_t \in \cdot \mid H^+_{t-1}, X_t, I_t) \, || \, \mathbb {P}_1( R_t \in \cdot \mid H^+_{t-1}, X_t, I_t) \right) \right]\\=& \mathbb {E}_0 \left[ \sum _{t=1}^{\tau } \frac{1}{2\sigma ^2} \left( X_t^\top \left( \theta _0^{(I_t)} - \theta _1^{(I_t)} \right)\right)^2 \right].\) 

The result then follows from a simple calculation. The second equality above applies the chain rule. The final equality uses that, conditioned on \(H^+_{t-1}\) , \((X_t, I_t)\)  have the same distribution under each \(\mathbb {P}_i\)  and that under \(\mathbb {P}_i\) , \(R_t \mid H^+_{t-1}, X_t, I_t \sim N(X_t^\top \theta _i^{(I_t)} \,, \, \sigma ^2 )\) .
Lemma 16 (Chain rule with stopping times) 
Consider two probability spaces \((\Omega , \mathcal {F}, \mathbb {P})\)  and \((\Omega , \mathcal {F}, \mathbb {Q})\)  where \(\mathbb {Q}\)  is absolutely continuous with respect to \(\mathbb {P}\) . Take \(\tau \)  to be a \(\mathbb {P}\) -almost-surely finite stopping time adapted to \((Z_t)_{t\in \mathbb {N}}\) . Then,
\(D_{\rm KL}\left( \mathbb {P}(Z_{1:\tau } \in \cdot ) \,||\, \mathbb {Q}(Z_{1:\tau } \in \cdot ) \right) = \mathbb {E}_{\mathbb {P}}\left[\sum _{t=1}^{\tau }D_{\rm KL}\left( \mathbb {P}(Z_{t} \in \cdot \mid Z_{1:(t-1)} ) \, ||\, \mathbb {Q}(Z_{t} \in \cdot \mid Z_{1:(t-1)}) \right) \right]\) 

The result follows by applying the usual chain rule to the censored random variables \(\tilde{Z}_{t} = Z_t \mathbb {1}(\tau \geqslant t)\) . It is clear that the sequence \(Z_{1:\tau }=(Z_1, \cdots , Z_{\tau })\)  contains the same information as \(\tilde{Z}_{1:\infty }=(\tilde{Z}_1, \tilde{Z}_2, \cdots )\) . Formally, there exists a function \(f\)  with \(\tilde{Z}_{1:\infty } = f(Z_{1:\tau })\)  and \(Z_{1:\tau }= f^{-1}(\tilde{Z}_{1:\infty })\) . It follows by the data-processing inequality that
\(D_{\rm KL}\left( \mathbb {P}(Z_{1:\tau } \in \cdot ) \, ||\, \mathbb {Q}(Z_{1:\tau } \in \cdot ) \right) = D_{\rm KL}\left( \mathbb {P}(\tilde{Z}_{1:\infty } \in \cdot ) \, || \, \mathbb {Q}(\tilde{Z}_{1:\infty } \in \cdot ) \right).\) 
Now,
\(D_{\rm KL}\left( \mathbb {P}(\tilde{Z}_{1:\infty } \in \cdot ) \, || \, \mathbb {Q}(\tilde{Z}_{1:\infty } \in \cdot ) \right) &= \lim _{T\rightarrow \infty } D_{\rm KL}\left( \mathbb {P}(\tilde{Z}_{1:T} \in \cdot ) \, ||\, \mathbb {Q}(\tilde{Z}_{1:T} \in \cdot ) \right)\\&=\lim _{T\rightarrow \infty } \mathbb {E}\left[ \sum _{t=1}^{T} D_{\rm KL}\left( \mathbb {P}(\tilde{Z}_t \in \cdot \mid \tilde{Z}_{1:(t-1)} ) \, || \, \mathbb {Q}(\tilde{Z}_t \in \cdot \mid \tilde{Z}_{1:(t-1)} ) \right) \right] \\&=\lim _{T\rightarrow \infty } \mathbb {E}\left[ \sum _{t=1}^{\tau \wedge T} D_{\rm KL}\left( \mathbb {P}(\tilde{Z}_t \in \cdot \mid \tilde{Z}_{1:(t-1)} ) \, || \, \mathbb {Q}(\tilde{Z}_t \in \cdot \mid \tilde{Z}_{1:(t-1)} ) \right) \right]\\&=\mathbb {E}\left[ \sum _{t=1}^{\tau } D_{\rm KL}\left( \mathbb {P}(\tilde{Z}_t \in \cdot \mid \tilde{Z}_{1:(t-1)} ) \, || \, \mathbb {Q}(\tilde{Z}_t \in \cdot \mid \tilde{Z}_{1:(t-1)} ) \right) \right]\\&=\mathbb {E}\left[ \sum _{t=1}^{\tau } D_{\rm KL}\left( \mathbb {P}(Z_t \in \cdot \mid Z_{1:(t-1)} ) \, || \, \mathbb {Q}(Z_t \in \cdot \mid Z_{1:(t-1)} ) \right) \right].\) 

The first equality is Corollary 5.2.5 in [17]}. The second equality is the usual chain rule for KL-divergences. The third equality recognizes that conditioned on \(\tau <t\) , \(\tilde{Z}_t =0\)  almost surely under both \(\mathbb {P}(\cdot )\)  and \(\mathbb {Q}(\cdot )\)  and so \(D_{\rm KL}\left( \mathbb {P}(\tilde{Z}_t \in \cdot \mid \tilde{Z}_{1:(t-1)} ) \, || \, \mathbb {Q}(\tilde{Z}_t \in \cdot \mid \tilde{Z}_{1:(t-1)} ) \right) =0\) . The fourth equality uses that KL-divergences are non-negative and applies the monotone convergence theorem to interchange the limit and expectation.

Two player game.
Based on the expression above, we define a two player zero-sum game between the experimenter, who tries to gather convincing evidence, and nature, who picks an alternative \(\theta _1\)  for which the experimenter's evidence least convincing. The value of this game will determine our lower bound. Mimicking the expression for the KL divergence, define for a sequence of positive semidefinite matrices \(M=(M_1, \cdots , M_k)\) ,
\(\Gamma ^{-1}_{\theta }( M , \theta _a) \triangleq \frac{1}{2\sigma ^2}\sum _{i\in [k]} \left(\theta ^{(i)} - \theta _a^{(i)}\right)^\top M_i \left(\theta ^{(i)} - \theta _a^{(i)}\right).\) 
The KL divergence appearing in Lemma REF  is equal to \(\mathbb {E}[\tau \mid \theta =\theta _0]\Gamma ^{-1}_{\theta _0}( M , \theta _a)\)  if one were to plug-in a value \(M_{i}= \mathbb {E}\left[\sum _{t=1}^{\tau }\mathbb {1}(I_t =i) X_t X_t^\top \mid \theta _0 \right] / \mathbb {E}[\tau \mid \theta = \theta _0]\) . Notice then that there is a natural constraint on how large the components of \(M\)  can be, since
\(\sum _{i\in [k]}^{} M_{i} = \mathbb {E}[X_1 X_1^\top ] \triangleq \Lambda .\) 
(The notation \(\Lambda \)  is used only this proof. That variable has different meaning elsewhere. Notice that \(\Lambda =\sigma ^2 A^{-1}\) .) To bound the possible accumulation of information, we consider an experimenter who is free to select matrices from the family
\(\mathbb {M} = \left\lbrace  (M_1, \cdots , M_k) : \sum _{i\in [k]} M_i = \Lambda \, , \, M_i \succeq 0 \, , \, M_i=M_i^\top \, \forall i \in [k] \right\rbrace .\) 
Nature will respond to the player by picking some alternative state of nature \(\theta _a \in {\rm Alt}(\theta _0) \triangleq \left\lbrace \theta ^{\prime }\in \mathbb {R}^{dk}\,:\, I^*(\theta ^{\prime })\ne I^*(\theta _0)\right\rbrace \)  that the design \(M\)  does a poor job of ruling out. The equilibrium value of this game is \(\sup _{M \in \mathbb {M}} \inf _{\theta _a \in {\rm Alt}(\theta )} \Gamma ^{-1}_{\theta }( M, \theta _a).\)
The next proposition describes an equilibrium of this game. The value of the game is shown to equal the simplified complexity term \(\Gamma _{\theta }^{-1}\)  defined in (REF ). The experimenter's equilibrium strategy mimics context-independent sampling with proportions given by the optimal proportions in (REF ) and (). Nature plays a distribution over just \(k-1\)  vectors, defined as follows: for each arm \(i\ne I^*\)  define \(\hat{\theta }_{i} = (\hat{\theta }_i^{(1)}, \cdots ,\hat{\theta }_i^{(k)})\)  by
\(\hat{\theta }^{(i)}_i = \theta ^{(i)} +\frac{\eta }{p^*_{i}} \Lambda ^{-1} X_{\rm pop} \quad \hat{\theta }_{i}^{(I^*)}= \theta ^{(I^*)} -\frac{\eta }{p^*_{I^*}} \Lambda ^{-1} X_{\rm pop}, \quad \hat{\theta }^{(j)}_i =\theta ^{(j)} \,\, \forall j \notin \lbrace  i, I^* \rbrace \) 
where
\(\eta =\frac{ \left(\mu (\theta , I^*, w) - \mu (\theta , i, w)\right)^2 }{ 2 \Vert X_{\rm pop}\Vert ^2_{\Lambda ^{-1}} \left[(p_i^*)^{-1}+ (p^*_{I^*})^{-1} \right]} \quad \forall \, i\ne I^*.\) 
That \(\eta \)  does not depend on \(i\)  follows from (REF ). Let \(\mathcal {D}\left({\rm Alt}(\theta _0)\right)\)  denote the set of distributions over alternative states of nature and overload notation to write \(\Gamma ^{-1}_{\theta }( M, q)= \mathbb {E}_{\theta _a \sim q}\left[ \Gamma ^{-1}_{\theta }( M, \theta _a)\right]\)  for \(q\in \mathcal {D}\left({\rm Alt}(\theta )\right)\) .
Proposition 5  The complexity term \(\Gamma _{\theta }^{-1}\)  defined in (REF ) satisfies
\(\Gamma _{\theta }^{-1} =\sup _{M \in \mathbb {M}} \inf _{\theta _a \in {\rm Alt}(\theta )} \Gamma ^{-1}_{\theta }(M, \theta _a).\) 
Let \(M^*_i = p^*_i A\)  where \((p^*_1,\cdots , p^*_k)\)  is defined by (REF ) and ().
Let \(q^*\)  be a distribution supported on \(\lbrace  \hat{\theta }_i : i \ne I^* \rbrace \) , defined in (REF ), where \(q^*(\hat{\theta }_i) = \left(p_i^* /p^*_{I^*}\right)^2\) . Then,
\(\sup _{M \in \mathbb {M}}\Gamma _{\theta }^{-1}(M, q^* ) = \Gamma _{\theta }^{-1}(M^*, q^* ) = \inf _{q \in \mathcal {D}\left( {\rm Alt}(\theta )\right)} \Gamma _{\theta }^{-1}(M^*, q ).\) 

To start, we consider the best-response of nature, \(\min _{\theta _a\in {\rm Alt}(\theta _0)}\Gamma ^{-1}_{\theta }( M^*, \theta _a)\) . Throughout the proof use \(I^*\)  to denote \(I^*(\theta )\) . It is immediate that
\(\min _{\theta _a\in {\rm Alt}(\theta )} \,\,\frac{1}{2\sigma ^2}\sum _{i\in [k]} \Vert  \theta ^{(i)} - \theta ^{(i)}_{a}\Vert _{M^*_i}^{2} = \min _{i\ne I^*} \min _{X_{\rm pop}^\top (\theta _a^{(i)} - \theta _a^{(I^*)}) \geqslant 0 } \Vert  \theta ^{(i)} - \theta _a^{(i)}\Vert _{M^*_i}^2+ \Vert  \theta ^{(I^*)} - \theta _a^{(I^*)}\Vert _{M^*_{I^*}}^2.\) 
Apply the transformation of variables \(Z_{j}=\theta ^{(j)} - \theta _a^{(j)}\) . Then for each alternative arm \(i\)  we have the optimization problem
\(\min &\quad \frac{1}{2\sigma ^2}\Vert  Z_{i}\Vert _{M^*_i}^2+ \frac{1}{2\sigma ^2}\Vert  Z_{I^*}\Vert _{M^*_{I^*}}^2 \\\nonumber {\rm subject \,\, to} & \quad \left(Z_{i}-Z_{I^*}\right)^\top X_{\rm pop} \geqslant \Delta _{i}\) 

where \(\Delta _i = \mu (\theta , I^*, w) - \mu (\theta , i, w)= {X_{\rm pop}^\top \left(\theta ^{(I^*)} - \theta ^{(i)} \right)}\) .
The KKT conditions for the problem (REF ) are
\(M^*_i Z_i = \eta X_{\rm pop} \\M^*_{I^*} Z_{I^*} = -\eta X_{\rm pop}\\\eta \left[ \left(Z_{i}-Z_{I^*}\right)^\top X_{\rm pop} -\Delta _{i} \right] = 0\\\eta \geqslant 0.\) 
 A solution is given by
\(Z_{i} = \eta (M_{i}^{*})^{-1} X_{\rm pop} = \frac{\eta \Lambda ^{-1} X_{\rm pop}}{p_i^*} \quad \text{and} \quad Z_{I^*} = -\eta (M_{I^*}^{*})^{-1} X_{\rm pop} = - \frac{\eta \Lambda ^{-1} X_{\rm pop}}{p_{I^*}^*}\) 

where
\(\eta = \frac{\Delta _i}{ 2 X_{\rm pop}^\top \left[ (M^*_i)^{-1} +(M^*_{I^*})^{-1}\right] X_{\rm pop}} = \frac{ \left(\mu (\theta , I^*, w) - \mu (\theta , i, w)\right)^2 }{ 2 \Vert X_{\rm pop}\Vert ^2_{\Lambda ^{-1}} \left[(p_i^*)^{-1}+ (p^*_{I^*})^{-1} \right]}\) 
Since the optimization problem is convex, satisfying the KKT conditions is sufficient to imply optimality. Recalling the transformation of variables \(\theta _a^{(i)} = \theta ^{(i)}+Z_{i}\) , we find the optimal solution to (REF ) is exactly \(\hat{\theta }_i\)  in (REF ). Plugging in shows that the optimal objective value of (REF ) is equal to \(\eta / \sigma ^2\) . By the information balance property (REF ), \(\eta \)  does not depend on \(i\) . In summary, we have shown that for each arm \(i\ne I^*\)
\(\min _{\theta _a\in {\rm Alt}(\theta )} \Gamma ^{-1}_{\theta }( M^*, \theta _a) = \Gamma ^{-1}_{\theta }( M^*, \hat{\theta }_i) = \frac{\eta }{\sigma ^2} = \Gamma _{\theta }^{-1}.\) 
The last equality recalls the definition of \(\Gamma _{\theta }\)  in (REF ) and that \(\Lambda =\sigma ^{2} A^{-1}\) .
Since we have just shown that each \(\hat{\theta }_i\)  is a best response, so is the randomized strategy \(q^*\) .
Now, consider experiment's choice of \(M \in \mathbb {M}\)  in response to nature's choice of \(q^*\) . We denote the standard inner product on matrices by \(\langle A\, , \, B\rangle = {\rm Trace} (A^\top B)\) . For any \(M\in \mathbb {M}\) ,
\(\Gamma ^{-1}_{\theta }(M, q^* ) &= \sum _{j\ne I^*} q^*( \hat{\theta }_{j}) \left\lbrace  \frac{1}{2\sigma ^2}\sum _{i\in [k]} \left(\theta ^{(i)} - \hat{\theta }_j^{(i)}\right)^\top M_i \left(\theta ^{(i)} - \hat{\theta }_j^{(i)}\right) \right\rbrace  \\&= \frac{1}{2\sigma ^2} \sum _{j\ne I^*} q^*( \hat{\theta }_{j}) \left[ \left\Vert \frac{\eta }{p^*_{j}} \Lambda ^{-1} X_{\rm pop} \right\Vert _{ M_j }^2 + \left\Vert \frac{\eta }{p^*_{I^*}} \Lambda ^{-1} X_{\rm pop} \right\Vert _{ M_{I^*} }^2 \right]\\&= \frac{\eta ^2}{2\sigma ^2} \sum _{j\ne I^*} q^*( \hat{\theta }_{j}) \left[ \frac{1}{(p_j^*)^2} \left\Vert  \Lambda ^{-1} X_{\rm pop} \right\Vert _{ M_j }^2 + \frac{1}{(p^*_{I^*} )^2}\left\Vert  \Lambda ^{-1} X_{\rm pop} \right\Vert _{ M_{I^*} }^2 \right]\\&= \frac{\eta ^2}{2\sigma ^2} \sum _{j\ne I^*} q^*( \hat{\theta }_{j}) \left[ \frac{ \langle B, M_j \rangle }{(p_j^*)^2} + \frac{ \langle B, M_{I^*} \rangle }{(p^*_{I^*})^2} \right] \quad \text{where}\quad B= (\Lambda ^{-1} X_{\rm pop})(\Lambda ^{-1} X_{\rm pop})^\top \\&= \frac{\eta ^2}{2\sigma ^2} \sum _{j\ne I^*} \left[\frac{q^*( \hat{\theta }_{j})}{(p_j^*)^2} \right] \langle B, M_j \rangle + \left[ \frac{1}{(p^*_{I^*})^2}\right] \langle B, M_{I^*} \rangle \\&= \frac{\eta ^2}{2\sigma ^2} \sum _{j\ne I^*} \left[ \frac{1}{(p^*_{I^*})^2}\right] \langle B, M_j \rangle + \left[ \frac{1}{(p^*_{I^*})^2}\right] \langle B, M_{I^*} \rangle \qquad \left( \text{since} \, q^*( \hat{\theta }_{j}) = \left(\frac{p_j^*}{p^*_{I^*}}\right)^2 \right) \\&= \frac{\eta ^2}{2\sigma ^2 (p^*_{I^*})^2} \langle B\, , \, \sum _{i=1}^{k} M_i \rangle \\&= \frac{\eta ^2}{2\sigma ^2 (p^*_{I^*})^2} \langle B\, , \, \Lambda \rangle .\) 

When nature selects \(q^*\) , the experimenter is indifferent between all \(M=(M_1, \cdots , M_k) \in \mathbb {M}\) . This implies in particular that \(M^* \in \operatornamewithlimits{arg\,max}_{M \in \mathbb {M}} \Gamma ^{-1}(M, q^* )\) .
We have established (REF ). In particular, \(M^*\)  and \(q^*\)  form an equilibrium. We have already shown \(\Gamma _{\theta }^{-1} = \Gamma _{\theta }^{-1}(M^*, q^*)\) , so the simplified complexity \(\Gamma _{\theta }^{-1}\)  is the equilibrium value of the game. We have to show (REF ). Since \(M^*\)  and \(q^*\)  form an equilibrium,
\(\inf _{q \in \mathcal {D}\left( {\rm Alt}(\theta )\right)} \sup _{M \in \mathbb {M}}\Gamma ^{-1}_{\theta }(M, q ) \leqslant \sup _{M \in \mathbb {M}}\Gamma ^{-1}_{\theta }(M, q^* ) = \Gamma ^{-1}_{\theta }(M^*, q^* ) = \inf _{q \in \mathcal {D}\left( {\rm Alt}(\theta )\right)} \Gamma ^{-1}_{\theta }(M^*, q ) \leqslant \sup _{M \in \mathbb {M}} \inf _{q \in \mathcal {D}\left( {\rm Alt}(\theta )\right)} \Gamma ^{-1}_{\theta }(M, q ).\) 
The reverse inequality,
\(\sup _{M \in \mathbb {M}} \inf _{q \in \mathcal {D}\left( {\rm Alt}(\theta )\right)} \Gamma ^{-1}_{\theta }(M, q )\leqslant \inf _{q \in \mathcal {D}\left( {\rm Alt}(\theta )\right)} \sup _{M \in \mathbb {M}}\Gamma _{\theta }^{-1}(M, q ),\) 
also holds, and so the inequalities above must hold with equality. Inequality (REF ) is a general result known as the max-min inequality ([18]}).

Completing the proof.
A slight subtlety arises in completing the proof. The property (REF ), which underlies Corollary REF , is assumed to only hold for parameters in \(\Theta \) . This is the set of parameters with distinct arm means. The parameters \(\hat{\theta }_j\)  played by nature in equilibrium are in the closure of \(\Theta \) , but not in \(\Theta \)  itself. To complete the proof, we fix \(k-1\)  parameters \((\theta _j : j \ne I^*)\)  where each \(\theta _j \in \Theta \)  and then later take a limit as \(\theta _j\rightarrow \hat{\theta }_j\) . Combining the results described above, we find
\(&\log (1/\delta )[1+o_{\theta }(1)]\\\leqslant & \sum _{j\ne I^*(\theta _0)} q^*( \hat{\theta }_j) D_{\rm KL}( \mathbb {P}\left( H^+_\tau \in \cdot \mid \theta \right) \, || \, \mathbb {P}\left( H^+_\tau \in \cdot \mid \theta = \theta _j \right) ) \\=& \mathbb {E}\left[ \tau \mid \theta \right]\sum _{j\ne I^*(\theta _0)}q^*( \hat{\theta }_j) \frac{1 }{2\sigma ^2}\sum _{i\in [k]} \left(\theta ^{(i)} - \theta _{j}^{(i)}\right)^\top \frac{\mathbb {E}\left[ \sum _{t=1}^{\tau }\mathbb {1}(I_t =i) X_t X_t^\top \mid \theta \right]}{\mathbb {E}\left[ \tau \mid \theta \right] }\left(\theta ^{(i)} - \theta _j^{(i)}\right)\\\leqslant & \mathbb {E}\left[ \tau \mid \theta \right] \sup _{M\in \mathbb {M}} \sum _{j\ne I^*(\theta )} q^*( \hat{\theta }_j) \Gamma _{\theta }^{-1}\left( M, \theta _j \right).\) 

The first inequality uses Corollary REF . Notice that it is critical that Nature's equilibrium strategy randomizes over a finite set of vectors as this allows us to pass a limit through the sumIf there is a family of function \(f_i(\delta )\) , indexed by \(i\in I\) , with \(f_{i}=o(1)\)  for each fixed \(i\) . This means \(\lim _{\delta \rightarrow 0} f_{i}(\delta )=0\)  for each given \(i\in I\) . When \(I\)  is finite, it follows that \(\sum _{i \in I} f_{i}(\delta ) = o(1)\)  but this may not hold if \(I\)  is infinite.. The second inequality uses that matrices of the form \(M_i = \frac{\mathbb {E}\left[ \sum _{t=1}^{\tau }\mathbb {1}(I_t =i) X_t X_t^\top \mid \theta =\theta _0\right]}{\mathbb {E}\left[ \tau \mid \theta = \theta _0\right] }\)  are a feasible choice for the experimenter.
Dividing each side by \(\log (1/\delta )\) , taking \(\delta \rightarrow 0\)  and then taking \(\theta _j \rightarrow \hat{\theta }_j\)  gives
\(\liminf _{\delta \rightarrow 0} \frac{ \mathbb {E}\left[ \tau \mid \theta \right]}{\log (1/\delta )} \geqslant \sup _{M\in \mathbb {M}} \sum _{j\ne I^*(\theta )} q^*( \hat{\theta }_j) \Gamma _{\theta }^{-1}\left( M, \theta _j \right) &\longrightarrow \sup _{M\in \mathbb {M}}\sum _{j\ne I^*(\theta )} q^*( \hat{\theta }_j) \Gamma _{\theta }^{-1}\left( M, \hat{\theta }_j \right)\\& = \sup _{M\in \mathbb {M}} \Gamma ^{-1}_{\theta }(M, q^*) = \Gamma ^{-1}_{\theta }.\) 
Remark 2 (Novelty in the lower bound proof) 
There are two main points of novelty in this argument. The first is in the characterization of the experimenter's equilibrium choice of \(M\)  in Proposition REF . This shows that context-independent sampling is asymptotically efficient. The second point of novelty is that Proposition REF  places a relatively weak constraint on the algorithm. The constraint (REF ) holds for each given \(\theta _0\) , but not uniformly.
The challenges this causes are subtle. Arguments like those in [19]} seem to rely on a uniform constraint like \(\sup _{\theta _1 \in \Theta } \mathbb {P}(\hat{I}^+_{\tau } \ne I^*(\theta _1) \mid \theta =\theta _1) \leqslant \delta \) . Each choice of \(\theta _1\)  leads to a bound that is roughly of the form \(\mathbb {E}[\tau \mid \theta = \theta _0] \geqslant \Gamma _{\theta _0}^{-1}(M,\theta _1)\log (1/\delta )\) . Optimal results are derived by first maximizing over \(\theta _1\)  and then minimizing over \(M\) . This argument breaks in our case, because
(REF ) does not restrict \(\sup _{\theta _1 \in \Theta } \mathbb {E}[\Delta _{\tau } \mid \theta = \theta _1]\) , since the set \(\Theta \)  is infinite. We avoid this problem by showing Nature's worst-case behavior in Proposition REF  randomizes only over a finite number of states of nature. This is used at the very end of the proof.


Proof of the Upper Bound in Proposition  REF
Validity of the stopping time
We begin with a result bounding the simple regret incurred when the stopping rule in (REF ) is used. In the statement, \(f(\theta , \delta )=\mathbb {E}\left[ \Delta _{\tau } \mathbb {1}(\tau <\infty ) \mid \theta \right]\)  is viewed as some function of the state of nature and of the parameter \(\delta \)  of the stopping time. The notation \(f(\theta , \delta ) = O_{\theta }(\delta )\)  means \(\limsup _{\delta \rightarrow 0} \frac{f(\theta , \delta )}{\delta } <\infty \) .
Proposition 6 
Let \(\tau \)  denote the stopping time in (REF ). Then,
\(\mathbb {E}\left[ \Delta _{\tau } \mathbb {1}(\tau <\infty ) \mid \theta \right] \leqslant O_{\theta }(\delta ).\) 

The proof is developed over the next few subsections.
Latent reward and context tables
Because DTS is arm sampling under DTS is context independent (see (REF )), we can analyze its behavior as if contexts are observed only after an arm is sampled.
With this view, we have written down a model where, DTS selects and action \(I_t\)  and then observes the context \(X_t\)  and reward \(R_t=\langle X_t \,,\, \theta ^{(I_t)} \rangle + W_t\) . An alternative description of the probability space would generate all the randomness upfront, using what [16]} call a reward table and a context table. Precisely, let \(\tilde{X}_{n,i}\sim p_X\)  and \(\tilde{W}_{n,i}\sim N(0, \sigma ^2)\)  denote virtual contexts and rewards drawn i.i.d across \(n\in \mathbb {N}\)  and \(i\in [k]\) . Assume \((\tilde{X}_{n,i})_{n\in \mathbb {N},i\in [k]}\) , \((\tilde{R}_{n,i})_{n\in \mathbb {N},i\in [k]}\)  and the algorithm's internal randomness (used for arm sampling) are jointly independent. Let \(\tilde{R}_{n,i}= \langle \theta ^{(i)} \, , \, \tilde{X}_{n,i} \rangle + \tilde{W}_{n,i}\)  denote the reward corresponding to the \(n\) th play of arm \(i\) . Then for \(t\in \mathbb {N}\)
\((I_t, X_{t}, R_t) \overset{D}{=} \left(I_t, \tilde{X}_{N_{t, I_t}+1, I_t}, \tilde{R}_{N_{t, I_t}+1, I_t}\right)\) 
where \(\overset{D}{=}\)  denotes equality in distribution (or “in law”).
We define \(\mathbb {N}_0\triangleq \mathbb {N}\cup \lbrace 0\rbrace \) . For \((n,i)\in \mathbb {N}_0\times [k]\) , the distribution of \(\theta ^{(i)}\)  conditioned on \((\tilde{X}_{\ell ,i})_{\ell \in [n]}\)  is multivariate Gaussian with covariance and mean given by
\(\tilde{\Sigma }_{n,i} = \left( \tilde{\Sigma }_{0,i}^{-1} + \sigma ^{-2} \sum _{\ell =1}^{n} \tilde{X}_{\ell ,i} \tilde{X}_{\ell ,i}^\top \right)^{-1}\quad \text{and}\quad \tilde{\mu }_{n,i} = \tilde{\Sigma }_{n,i}\left( \tilde{\Sigma }_{0,i}^{-1} \tilde{\mu }_{0,i} + \sigma ^{-2}\sum _{\ell =1}^{n} \tilde{X}_{\ell ,i} \tilde{R}_{\ell ,i} \right)\) 
where \((\tilde{\mu }_{0,i},\tilde{\Sigma }_{0,i})\)  equals the prior mean and variance \((\mu _{1,i},\Sigma _{1,i})\)  used by the algorithm.A side note is that here we overload the notations. In the definition of a context unaware algorithm in Section , we use \(\tilde{\mu }_{t,i}\)  and \(\tilde{\Sigma }_{t,i}\)  to denote an (incorrect) posterior mean and standard deviation at time \(t\) , while here \(\tilde{\mu }_{n,i}\)  and \(\tilde{\Sigma }_{n,i}\)  are the true posterior mean and standard deviation after having \(n\)  samples based on the latent reward and context tables.
Equation (REF ) mimics the updating rule in Equation (REF ), but is based on latent reward and context tables.
Another difference is that
\((\tilde{\mu }_{n,i},\tilde{\Sigma }_{n,i})\)  in Equation (REF ) starts from \(n=0\)  (when the arm has not been sampled, the corresponding number of observations is 0), while
\(({\mu }_{t,i},{\Sigma }_{t,i})\)  in Equation (REF ) starts from time \(t=1\)  where \(({\mu }_{1,i},{\Sigma }_{1,i})\)  is the prior mean and variance (when there is no observation seen so far).
Since \(\mu (\theta , i, w) \)  is a linear in \(\theta ^{(i)}\) , it also has a Gaussian posterior given the latent reward and context tables. We write
\(\mu (\theta , i, w) \mid (\tilde{X}_{\ell ,i}, \tilde{R}_{\ell ,i})_{\ell \in [n]} \sim N( \tilde{m}_{n,i}, \tilde{s}^2_{n,i} )\) 
where similar to those in Equation (REF ), we let
\(\tilde{s}^2_{n,i} = X_{\rm pop}^\top \tilde{\Sigma }_{n,i} X_{\rm pop}\quad \text{and}\quad \tilde{m}_{n,i} = \langle X_{\rm pop}\, , \, \tilde{\mu }_{n,i}\rangle .\) 

Frequentist distribution of the posterior mean
When conditioning on \(\theta \) , the posterior mean can be viewed as some function of the observed data. We characterize the sampling distribution of the error in the posterior mean. It is normally distributed. The variance of the sampling distribution is close to the posterior variance term \(\tilde{s}_{n,i}^2\)  tracked by the algorithm: it is never larger (\(\ldots \)  since the posterior calculation is factoring in believed variance in \(\theta \) , which is not present here) and the difference is a negligible fraction of \(\tilde{s}_{n,i}^2\)  as \(n\)  grows. The average error is nearly zero, but there is bias due to regularization toward the prior mean. The magnitude of bias is on the order of the \(\tilde{s}_{n,i}\) , implying it shrinks as evidence is gathered. We emphasize again that all analysis in this section is implicitly conditioned on \(\theta \) .
Lemma 17  For any \(n\in \mathbb {N}_0\)  and \(i \in [k]\) ,
\(\tilde{m}_{n,i} - \mu (\theta , i, w) \mid \theta ,\, \left\lbrace \tilde{X}_{n^{\prime },i^{\prime }}\right\rbrace _{(n^{\prime },i^{\prime })\in \mathbb {N}\times [k]} \sim N\left( \tilde{B}_{n,i} \, , \, \tilde{s}_{n,i}^2 - \left\Vert \tilde{\Sigma }_{n,i}X_{\rm pop}\right\Vert ^2_{\tilde{\Sigma }_{0,i}^{-1}} \right)\) 
where the bias is given by
\(\tilde{B}_{n,i} \triangleq \left\langle X_{\rm pop}\, , \, \tilde{\Sigma }_{n,i}\tilde{\Sigma }_{0,i}^{-1}\left(\tilde{\mu }_{0,i}-\theta ^{(i)}\right)\right\rangle .\) 
In addition, the following bounds hold:
\(|\tilde{B}_{n,i}|\leqslant \tilde{s}_{n,i} \Vert  \tilde{\mu }_{0,i}-\theta ^{(i)} \Vert _{\tilde{\Sigma }_{0,i}^{-1}}\quad \text{and} \quad \tilde{s}^2_{n,i}\left[ 1- \lambda _{\max }\left( \tilde{\Sigma }_{n,i}^{1/2} \tilde{\Sigma }_{0,i}^{-1} \tilde{\Sigma }_{n,i}^{1/2} \right) \right]\leqslant \tilde{s}_{n,i}^2 - \left\Vert \tilde{\Sigma }_{n,i}X_{\rm pop}\right\Vert ^2_{\tilde{\Sigma }_{0,i}^{-1}}\leqslant \tilde{s}^2_{n,i}\) 

Fix \((n,i)\in \mathbb {N}_0 \times [k]\) . We can write
\(\tilde{m}_{n,i} - \mu (\theta , i, w) - \tilde{B}_{n,i} = \left\langle X_{\rm pop}\,,\, \left(\tilde{\mu }_{n,i} - \theta ^{(i)}\right) - \tilde{\Sigma }_{n,i}\tilde{\Sigma }_{0,i}^{-1}\left(\tilde{\mu }_{0,i}-\theta ^{(i)}\right)\right\rangle \triangleq P_{n,i}.\) 
A little linear algebra shows that
\(\tilde{\Sigma }_{n,i}^{-1}\tilde{\mu }_{n,i}-\tilde{\Sigma }_{0,i}^{-1}\tilde{\mu }_{0,i}&= \sigma ^{-2}\sum _{\ell =1}^{n}\tilde{X}_{\ell ,i} \tilde{R}_{\ell ,i} \\&= \left(\sigma ^{-2}\sum _{\ell =1}^{n} \tilde{X}_{\ell ,i}\tilde{X}_{\ell ,i}^\top \right)\theta ^{(i)} + \sigma ^{-2}\sum _{\ell =1}^{n} \tilde{X}_{\ell ,i}\tilde{W}_{\ell ,i} \\&= \left(\tilde{\Sigma }_{n,i}^{-1}-\tilde{\Sigma }_{0,i}^{-1}\right)\theta ^{(i)} + \sigma ^{-2}\sum _{\ell =1}^{n}\tilde{X}_{\ell ,i}\tilde{W}_{\ell ,i},\) 

which gives
\(\tilde{\Sigma }_{n,i}^{-1}\left(\tilde{\mu }_{n,i}-\theta ^{(i)}\right) - \tilde{\Sigma }_{0,i}^{-1}\left(\tilde{\mu }_{0,i}-\theta ^{(i)}\right)=\sigma ^{-2}\sum _{\ell =1}^{n}\tilde{X}_{\ell ,i}\tilde{W}_{\ell ,i},\) 
and thus
\(P_{n,i}=\sigma ^{-2} \sum _{\ell =1}^{n} \left\langle X_{\rm pop}\,,\, \tilde{\Sigma }_{n,i}\tilde{X}_{\ell ,i}\right\rangle \tilde{W}_{\ell ,i}.\) 
Notice that
\(\sum _{\ell =1}^{n} \left\langle X_{\rm pop}\,,\, \tilde{\Sigma }_{n,i}\tilde{X}_{\ell ,i}\right\rangle ^2&= X_{\rm pop}^\top \tilde{\Sigma }_{n,i}\left(\sum _{\ell =1}^{n}\tilde{X}_{\ell ,i}\tilde{X}_{\ell ,i}^\top \right)\tilde{\Sigma }_{n,i}X_{\rm pop}\\&= \sigma ^{2}X_{\rm pop}^\top \tilde{\Sigma }_{n,i} \left(\tilde{\Sigma }_{n,i}^{-1}-\tilde{\Sigma }_{0,i}^{-1}\right)\tilde{\Sigma }_{n,i}X_{\rm pop}\\&= \sigma ^{2}X_{\rm pop}^\top \tilde{\Sigma }_{n,i}X_{\rm pop}- \sigma ^{2}X_{\rm pop}^\top \tilde{\Sigma }_{n,i} \left(\tilde{\Sigma }_{0,i}^{-1}\right)\tilde{\Sigma }_{n,i}X_{\rm pop}\\ &= \sigma ^{2} \tilde{s}_{n,i}^2 - \sigma ^{2} \Vert  \tilde{\Sigma }_{n,i}X_{\rm pop}\Vert ^2_{\tilde{\Sigma }_{0,i}^{-1}}.\) 

which implies the first claim.
To bound the bias, we use
\(\tilde{B}_{n,i} = \left\langle X_{\rm pop}\, , \, \tilde{\Sigma }_{n,i}\tilde{\Sigma }_{0,i}^{-1}\left(\tilde{\mu }_{0,i}-\theta ^{(i)}\right)\right\rangle &= \left\langle X_{\rm pop}\, , \, \tilde{\Sigma }_{0,i}^{-1}\left(\tilde{\mu }_{0,i}-\theta ^{(i)}\right)\right\rangle _{\tilde{\Sigma }_{n,i}} \\&\leqslant \Vert X_{\rm pop}\Vert _{\tilde{\Sigma }_{n,i}} \Vert \tilde{\Sigma }_{0,i}^{-1}\left(\tilde{\mu }_{0,i}-\theta ^{(i)}\right) \Vert _{\tilde{\Sigma }_{0,i}} \\&= \Vert X_{\rm pop}\Vert _{\tilde{\Sigma }_{n,i}} \Vert  \tilde{\mu }_{0,i}-\theta ^{(i)} \Vert _{\tilde{\Sigma }^{-1}_{0,i}} \, ,\) 

where we use the notation \(\langle x, y\rangle _A = x^\top A y\)  for a positive definite matrix \(A\) , the first inequality is Cauchy-Schwartz, and the final equality can be seen by directly writing out the expressions for the two norms.
Finally, the offset term for the variance can by bounded as,
\(\left\Vert \tilde{\Sigma }_{n,i}X_{\rm pop}\right\Vert ^2_{\tilde{\Sigma }_{0,i}^{-1}} = X_{\rm pop}^\top \tilde{\Sigma }_{n,i} \tilde{\Sigma }_{0,i}^{-1} \tilde{\Sigma }_{n,i} X_{\rm pop}= X_{\rm pop}^\top \tilde{\Sigma }_{n,i}^{1/2} \left(\tilde{\Sigma }_{n,i}^{1/2} \tilde{\Sigma }_{0,i}^{-1} \tilde{\Sigma }_{n,i}^{1/2} \right) \tilde{\Sigma }_{n,i}^{1/2} X_{\rm pop}\leqslant \lambda _{\max }\left( \tilde{\Sigma }_{n,i}^{1/2} \tilde{\Sigma }_{0,i}^{-1} \tilde{\Sigma }_{n,i}^{1/2} \right) \tilde{s}^2_{n,i}.\) 

Proof of Proposition  REF
We now use Lemma REF  to prove Proposition REF .

Let \(X=\left\lbrace \tilde{X}_{n^{\prime },i^{\prime }}\right\rbrace _{(n^{\prime },i^{\prime })\in \mathbb {N}\times [k]} \) .
Our goal is to show that \(\mathbb {E}\left[\Delta _{\tau _\delta } \mathbb {1}(\tau _\delta < \infty ) \mid \theta , \, X\right] = O_{\theta }(\delta )\) . This big-O notation is equivalent to the statement
\(\limsup _{\delta \rightarrow 0} \frac{\mathbb {E}\left[\Delta _{\tau _\delta } \mathbb {1}(\tau _\delta < \infty ) \mid \theta ,\, X \right]}{\delta } < \infty .\) 
Following Subsubsection REF , for each \(i,j\in [k]\)  and \(n_i,n_j \in \mathbb {N}_0\) , we define the latent variable
\(\tilde{Z}_{n_i, n_j, i, j} = \frac{\tilde{m}_{n_i,i} - \tilde{m}_{n_j,j}}{\sqrt{\tilde{s}_{n_i,i}^2 + {\tilde{s}_{n_j,j}^2}}}.\) 
This definition aligns with the z-scores used in the stopping rule (REF ). If arms \(i\)  and \(j\)  have been played \(n_i\)  and \(n_j\)  times by time \(t\) , then \(Z_{t,i,j} = \tilde{Z}_{n_i,n_j,i,j}\) .
Then we have
\(&\mathbb {E}\left[\Delta _{\tau _\delta } \mathbb {1}(\tau _\delta < \infty ) \mid \theta , \, X\right] \\=& \mathbb {E}\left[\left(\mu (\theta ,I^*,w) - \mu (\theta ,\hat{I}_{\tau _{\delta }} ,w)\right) \mathbb {1}(\tau _\delta < \infty ) \mid \theta , \, X\right] \nonumber \\=& \sum _{ i \ne I^* }\left(\mu (\theta ,I^*,w) - \mu (\theta ,i,w)\right)\mathbb {P}\left(\tau _\delta < \infty , \hat{I}_{\tau _\delta } = i \mid \theta ,\, X\right)\nonumber \\\leqslant & \sum _{i\ne I^*} \left(\mu (\theta ,I^*,w) - \mu (\theta ,i,w)\right)\mathbb {P}\left(\exists t\in \mathbb {N} \,:\, Z_{t,i,I^*} \geqslant \gamma _{t,\delta }+\sqrt{\gamma _{t,\delta }}\mid \theta \,,\, X\right)\\\leqslant &\sum _{i\ne I^*} \left(\mu (\theta ,I^*,w) - \mu (\theta ,i,w)\right)\mathbb {P}\left(\exists t\in \mathbb {N} \,:\, Z_{t,i,I^*} \geqslant \gamma _{t,\delta }+\sqrt{\gamma _{t,\delta }}\mid \theta \,,\, X\right)\nonumber \\\leqslant & \sum _{i\ne I^*} \left(\mu (\theta ,I^*,w) - \mu (\theta ,i,w)\right)\mathbb {P}\left(\exists n_i, n_{I^*}\in \mathbb {N}_0 \,:\,\tilde{Z}_{n_i, n_{I^*},i, I^*} \geqslant \gamma _{n_i + n_{I^*}+1,\delta } +\sqrt{\gamma _{n_i + n_{I^*}+1,\delta }}\mid \theta \, , \, X \right)\) 

where in the final inequality,
since \(n_i+n_{I^*} \leqslant t-1\) , by monotonicity, \(\gamma _{n_i+n_{I^*}+1,\delta }\leqslant \gamma _{t,\delta }\) .
By Lemma REF  and the bounds therein, conditioned on \(\theta \)  and \(X\) , \(\tilde{Z}_{n_i, n_{I^*}, i, I^*}\)  follows Gaussian distribution with
\({\rm Var}\left[ \tilde{Z}_{n_i, n_{I^*}, i, I^*} \mid \theta \, , \, X \right] \leqslant 1\) 
and
\(\mathbb {E}\left[ \tilde{Z}_{n_{i}, n_{I^*}, i, I^*} \mid \theta \, , \, X \right] &= \frac{ \mu (\theta , i, w) - \mu (\theta , I^*, w) }{ \sqrt{\tilde{s}_{n, i}^2+\tilde{s}_{n,I^*}^2}} + \frac{ B_{n,i} - B_{n,I^*} }{ \sqrt{\tilde{s}_{n, i}^2+\tilde{s}_{n,I^*}^2} }\\& \leqslant \frac{ \mu (\theta , i, w) - \mu (\theta , I^*, w) }{ \sqrt{\tilde{s}_{n, i}^2+\tilde{s}_{n,I^*}^2}} + \frac{ |B_{n,i}| + |B_{n,I^*}|}{ \sqrt{ \tilde{s}_{n,i}^2 + \tilde{s}_{n,I^*}^2} } \\&\leqslant \frac{ \mu (\theta , i, w) - \mu (\theta , I^*, w) }{ \sqrt{\tilde{s}_{n, i}^2+\tilde{s}_{n,I^*}^2}} + \frac{ \tilde{s}_{n,i} \Vert  \tilde{\mu }_{0,i}-\theta ^{(i)} \Vert _{\tilde{\Sigma }_{0,i}^{-1}} + \tilde{s}_{n,I^*} \Vert  \tilde{\mu }_{0,I^*}-\theta ^{(i)} \Vert _{\tilde{\Sigma }_{0,I^*}^{-1}} }{ \sqrt{ \tilde{s}_{n,i}^2 + \tilde{s}_{n,I^*}^2} } \\& \leqslant \frac{ \mu (\theta , i, w) - \mu (\theta , I^*, w) }{ \sqrt{\tilde{s}_{n,I^*}^2+\tilde{s}_{n, i}^2 }} + \epsilon (\theta ) \\&\leqslant \epsilon (\theta ),\) 

where
\(\epsilon (\theta )\triangleq 2\max _{j\in [k]}\Vert \tilde{\mu }_{0,j}-\theta ^{(j)} \Vert _{\tilde{\Sigma }_{0,j}^{-1}}\)  in the second-to-last inequality, and we use the Cauchy–Schwarz inequality .
For any \(\theta \) , there is a \(\delta _{\theta }\)  such that for every \(\delta \leqslant \delta _{\theta }\) , we have \(\epsilon (\theta ) \leqslant \sqrt{\gamma _{1, \delta }}\) . Then, for \(\delta \leqslant \delta _{\theta }\)  we have
\(\mathbb {P}\left( \tilde{Z}_{n_i,n_{I^*},i, I^*} \geqslant \gamma _{n_i+n_{I^*}+1, \delta } + \sqrt{ \gamma _{n_i+n_{I^*}+1, \delta }} \mid \theta \, , \, X \right) &\leqslant \Phi \left( -\gamma _{n_i+n_{I^*}+1,\delta } - \sqrt{\gamma _{n_i+n_{I^*}+1,\delta }}+ \epsilon (\theta ) \right) \\&\leqslant \Phi \left( -\gamma _{n_i+n_{I^*}+1,\delta } - \sqrt{\gamma _{1,\delta }}+ \epsilon (\theta ) \right)\\&\leqslant \Phi \left( -\gamma _{n_i+n_{I^*}+1,\delta } \right)\\&\leqslant \exp \left( - \gamma _{n_i+n_{I^*}+1, \delta }^2 /2 \right) \\&= \frac{\delta }{ (1+n_{i}+n_{I^*})^3 }\) 

where the first inequality follows from the monotonicity of \(\gamma _{t,\delta }\)  in \(t\) , and the last inequality applies a common upper bound on the tail of the Gaussian CDF.
This shows that for \(\delta \leqslant \delta _\theta \) ,
\(\mathbb {E}\left[\Delta _{\tau _\delta } \mathbb {1}(\tau _\delta < \infty ) \mid \theta \right] &= \mathbb {E}\left[\mathbb {E}\left[\Delta _{\tau _\delta } \mathbb {1}(\tau _\delta < \infty ) \mid \theta , \, X\right] \, \mid \theta \right] \\&\leqslant \sum _{ i \ne I^* }\left(\mu (\theta ,I^*,w) - \mu (\theta ,i,w)\right) \left( \sum _{n_{i} = 0}^{\infty } \sum _{n_{I^*} = 0}^{\infty } \frac{\delta }{ (1+n_{i}+n_{I^*})^3 }\right) ,\) 

which implies (REF ).

Bounding the average sample size
Condition on \(\theta = \theta _0\)  for some \(\theta _0\in \Theta \) . Consider any sampling rule that is “ergodic” in the sense of (REF ). That is, for each \(i\in [k]\)  there exits \(p_i=p_i(\theta _0)>0\) , such that \(\lim _{t\rightarrow \infty } p_{t,i} = p_i\) . Equation (REF ) implies
\(\lim _{t\rightarrow \infty } \frac{Z_{t,i,j}^2}{t} = \frac{ \left(\mu (\theta _0, w, i) - \mu (\theta _0, w, j)\right)^2 }{ | X_{\rm pop}\Vert _{A}^2 \left[ (p_{i})^{-1} + (p_{j})^{-1}\right]},\) 
for any \(i,j\in [k]\) . Recall that \(\hat{I}_t \in \operatornamewithlimits{arg\,max}_{i \in [k]} m_{t,i}\)  is the empirical best-arm at time \(t\) . With probability 1, for sufficiently large \(t\)  (i.e. for \(t\)  larger than some sample path dependent time), \(\hat{I}_t = I^*(\theta _0)\)  is the true optimal arm. So
\(\lim _{t\rightarrow \infty } \frac{Z_{t,\hat{I}_t ,j}^2}{t} = \frac{ \left(\mu (\theta _0, w, I^*(\theta _0)) - \mu (\theta _0, w, j)\right)^2 }{ | X_{\rm pop}\Vert _{A}^2 \left[ (p_{I^*})^{-1} + (p_{j})^{-1}\right]}.\) 
We gave proof sketches in Section  which suggest that under DTS, \(\lim _{t\rightarrow \infty } p_{t,i} = p^*_i(\theta _0)\)  with probability 1. Assuming this holds, we have that for each \(j\in [k]\) , with probability 1,
\(\lim _{t\rightarrow \infty } \frac{Z_{t,\hat{I}_t ,j}^2}{t} = \frac{ \left(\mu (\theta _0, w, I^*(\theta _0)) - \mu (\theta _0, w, j)\right)^2 }{ \Vert  X_{\rm pop}\Vert _{A}^2 \left[ (p^*_{I^*})^{-1} + (p^*_{j})^{-1}\right]} =2\Gamma _{\theta _0}^{-1},\) 
where the second equality is the definition of the optimal allocation \(p^*(\theta _0)\)  and optimal exponent \(\Gamma _{\theta _0}\)  in (REF ).
Writing out the definition almost sure convergence explicitly, this means the following: for every \(\epsilon >0\)  there exists a random time \(T\)  with \(\mathbb {P}(T<\infty \mid \theta =\theta _0)=1\) , such that for every \(t\geqslant T\)
\(\left|\frac{Z_{t,\hat{I}_t,j}^2}{t} - 2\Gamma _{\theta _0}^{-1} \right| \leqslant \epsilon \quad \text{for all}\,\,\, j \in [k].\) 
The following proposition strengthens this notion of convergence.
Proposition 7 
Suppose DTS is applied with \(\beta _t\)  set by Algorithm REF  and condition on the event that \(\theta =\theta _0\)  for some \(\theta _0 \in \Theta \) . For every \(\epsilon >0\) , there exists a random time \(T\)  with \(\mathbb {E}[T \mid \theta = \theta _0]<\infty \)  such that (REF ) holds for each \(t\geqslant T\) .

[Notes on the proof]
First, suppose that there are no contexts. That is, assume \(X_t\in \mathbb {R}\)  and \(X_t=1\)  for each \(t\)  almost surely. In that case DTS is just the top-two Thompson sampling algorithm proposed in [21]}. Argument like the ones in [21]} imply almost sure convergence to the optimal proportions, i.e. \(\lim _{t\rightarrow \infty } p_{t,i}=p^*_i(\theta _0)\)  with probability 1. This means there exists \(T\)  with \(\mathbb {P}(T<\infty \mid \theta =\theta _0)=1\)  such that (REF ) holds for \(t\geqslant T\) . [23]} studies a different top-two sampling algorithm and shows one can ensure \(\mathbb {E}[T]<\infty \) . [24]} show this kind of result for top-two Thompson sampling.
The result above requires extending to the the case with contexts. We have already sketched in Proposition REF  why \(p_{t,i}\rightarrow p^*_i\)  for each \(i\in [k]\) , if they converge at all. Because arm-sampling under DTS is context independent, the presence of contexts did not substantially influence the argument there. Indeed, the context independence property in (REF ) means one can analyze DTS as if an arm is sampled and then the algorithm observes \((X_t, R_t)\) . So a contextual extension requires controlling for the noise in contexts and not just noise in rewards.
Unfortunately, the the proofs of [23]} and [24]} are very long and detailed. Rewriting each line here, while adding in factors that deal with the noise in realized contexts, would add 25 pages to this paper and detract from our focus. For reproducibility, we have written a complete argument and make that available as a supplementary report.
Given the convergence above, it is not hard to bound the average sample size under DTS. Notice that the condition that \(\mathbb {E}[T \mid \theta ]<\infty \) , rather than usual condition that \(\mathbb {P}(T<\infty \mid \theta )=1\) , plays a critical role in the proof.
Proposition 8 Suppose DTS is applied with \(\beta _t\)  set by REF . Let \(\tau \)  denote the stopping time defined in (REF ). Then for any \(\theta _0 \in \Theta \)
\(\mathbb {E}[ \tau \mid \theta =\theta _0] \leqslant \left(\Gamma _{\theta _0} + o_{\theta _0}(1)\right)\log (1/\delta )\) 
as \(\delta \rightarrow 0\) .

Fix \(\epsilon > 0\) . There exists \(T\)  with \(\mathbb {E}[T \mid \theta = \theta _0]<\infty \)  such that for \(t\geqslant T\) ,
\(\min _{i\ne \hat{I}_t} Z_{t,\hat{I}_t,i} \geqslant \sqrt{2t\left(\Gamma ^{-1}_{\theta _0}-\epsilon \right)}.\) 
The algorithm stops as soon as \(\min _{i\ne \hat{I}_t} Z_{t,\hat{I}_t,i}\geqslant \gamma _t\)  and thus
\(\tau \leqslant \max \lbrace T, t_\delta \rbrace  \leqslant T + t_\delta \) 
where \(t_\delta \)  is a deterministic time defined as
\(t_\delta &\triangleq \inf \left\lbrace t \in \mathbb {N} : \sqrt{2t\left(\Gamma ^{-1}_{\theta _0}-\epsilon \right)} \geqslant \gamma _{t,\delta } + \sqrt{\gamma _{t,\delta }}\right\rbrace  \\&= \inf \left\lbrace t \in \mathbb {N} : t\left(\Gamma ^{-1}_{\theta _0}-\epsilon \right) \geqslant \log (1/\delta ) + 3\log (t)+ \sqrt{\log (1/\delta ) + 3\log (t)}\right\rbrace .\) 

The second equality just recalls the definition of \(\gamma _t\) .
Taking expectations and dividing by \(\log (1/\delta )\)  gives
\(\limsup _{\delta \rightarrow 0} \frac{ \mathbb {E}[\tau \mid \theta =\theta _0]}{ \log (1/\delta )} \leqslant \limsup _{\delta \rightarrow 0} \frac{\mathbb {E}[T \mid \theta = \theta _0]}{\log (1/\delta )} + \limsup _{\delta \rightarrow 0} \frac{t_{\delta }}{\log (1/\delta )} = \limsup _{\delta \rightarrow 0} \frac{t_{\delta }}{\log (1/\delta )} = \frac{1}{\Gamma _{\theta _0}^{-1}-\epsilon }.\) 
Since the bound holds for arbitrary \(\epsilon \) , taking \(\epsilon \downarrow 0\)  gives the result.

Completing the proof of the upper bound in Proposition  REF
We note that the upper bound in Proposition REF  follows immediately from the results we have just established. In particular, we know that for \(\delta =c\)
\(\mathbb {E}[ \tau \mid \theta =\theta _0] \leqslant \left(\Gamma _{\theta _0} + o_{\theta _0}(1)\right)\log (1/c).\) 
In addition, when \(\delta =c\) ,
\(\mathbb {E}\left[ \Delta _{\tau } \mid \theta = \theta _0\right] =\mathbb {E}\left[ \Delta _{\tau } \mathbb {1}(\tau <\infty ) \mid \theta =\theta _0 \right] \leqslant O_{\theta _0}(c)= o_{\theta _0}(c\log (1/c)),\) 
where the first equality holds since \(\mathbb {E}[\tau | \theta = \theta _0]<\infty \)  ensures \(\tau \)  is finite almost surely. Putting the two together gives the desired result:
\(\mathbb {E}[ c\tau + \Delta _{\tau } \mid \theta =\theta _0] \leqslant c\left(\Gamma _{\theta _0} + o_{\theta _0}(1)\right)\log (1/c).\) 
