Policy Choice and Best Arm Identification: Asymptotic Analysis of Exploration Sampling

abstract\begingroup \footnote{We thank Edoardo Airoldi, Hidehiko Ichimura, Daniel Russo, and Xuedong Shang for insightful comments and discussion. This draft was produced following communication with the authors of the original manuscript.} \addtocounter{footnote}{-1} \endgroup We consider the “policy choice” problem-- otherwise known as best arm identification in the bandit literature-- proposed by Kasy2021 for adaptive experimental design. Theorem 1 of Kasy2021 provides three asymptotic results that give theoretical guarantees for exploration sampling developed for this setting. We first show that the proof of Theorem 1 (1) has technical issues, and the proof and statement of Theorem 1 (2) are incorrect. We then show, through a counterexample, that Theorem 1 (3) is false. For the former two, we correct the statements and provide rigorous proofs. For Theorem 1 (3), we propose an alternative objective function, which we call posterior weighted policy regret, and derive the asymptotic optimality of exploration sampling.

remark[BAI] This problem setting is known as BAI in the multi-armed bandit literature even2002pac, Mannor2004, EvanDar2006, Audibert2010. Though the problem of BAI itself goes back decades, variants go as far back as the 1950s, in the context of sequential testing problems Wald1945,Chernoff1959. Some of the earliest advances on this topic are summarized in bechhofer1968sequential. Another literature on ordinal optimization has been studied in the operation research community and a modern formulation was established in the 2000s chen2000,glynn2004large. Most of those studies have considered the estimation of optimal allocations separately from the error rate under known optimal allocations. In the 2010s, the machine learning community reformulated the problem to synthesize both issues and explicitly discussed them. For a more detailed survey, see, for example, the Introduction section of Kaufman2016complexity and Section 33 of lattimore2020.

theoremkasyConsider exploration sampling, with fixed wave size $N_t = N \geq 1$. Assume that the optimal arm $d^{(1)} = \underset{d\in\{1,\ldots,k\}}{\rm{argmax}}\,\theta^d$ is unique and that $\theta^{d^{(1)}} < 1$. As $T\to \infty$, the followings hold: \begin{description} • The share of observations $\frac{m^{d^{(1)}}_T}{NT}$ assigned to the best treatment $d^{(1)}$ converges in probability to $\frac{1}{2}$, that is, \[ \frac{m^{d^{(1)}}_T}{NT} \xrightarrow{p} \frac{1}{2}. \] • The share of observations $\frac{m^d_T}{NT}$ assigned to each treatment $d\neq d^{(1)}$ converges in probability to a non-random share $\rho^d$, that is, \[ \frac{m^d_T}{NT} \xrightarrow{p} \rho^d, \quad \forall d\neq d^{(1)}, \] where the limit assignment shares $\bm{\rho} = (\rho^1, \ldots, \rho^k)$ (with $\rho^{d^{(1)}} =\frac{1}{2}$) is such that $-\frac{1}{NT}\log p^d_T \xrightarrow{p} \Gamma^*$ for some $\Gamma^* > 0$ that is constant across $d\neq d^{(1)}$. • Expected policy regret converges to $0$ at the same rate $\Gamma^*$, that is, \[ -\frac{1}{NT}\log \mathrm{R}_{\bm{\theta}}(T) \xrightarrow{} \Gamma^*. \] No algorithm with limit assignment shares $\hat{\bm{\rho}}\neq \bm \rho$ with $\hat{\rho}^{d^{(1)}} = \frac{1}{2}$ exists for which $\mathrm{R}_{\bm{\theta}}(T)$ goes to $0$ at a faster rate than $\Gamma^*$. \end{description}

remark[Almost sure convergence and convergence in probability] \rm The original statement of Russo2016 states $-\frac{1}{NT}\log \left(\sum_{d\neq d^{(1)}}p^d_T\right) \xrightarrow{\mathrm{a.s.}} \Lambda^*$, whereas Kasy2021 incorrectly cites the result as $-\frac{1}{NT}\log p^d_T \xrightarrow{p} \Gamma^*$. Almost sure convergence describes an event that holds on each sample path, whereas convergence in probability describes an event that holds for a single $t$, which is weaker than almost sure convergence. During the proofs, one can find many steps that essentially require pathwise discussions. For example, to apply the law of large numbers, it is required that we have infinitely many samples for almost all sample paths. The derivation of the limit rate $\Lambda^*$ in our corrected theorem is via a bound of the posterior probabilities of the form $\exp(-(1\pm\epsilon)NT\Lambda^*)$ that holds over all $t > T_0(\epsilon)$ in Appendix (ref) (proof of Lemma (ref)).

remark[General prior] \rm Results in Shang2020 are limited to the uniform prior (i.e., $\mathrm{Beta}(1,1)$). In this paper, we extend the results in Shang2020 to $\mathrm{Beta}(\alpha_0^d,\beta_0^d)$ priors for each $d \in \{1, \ldots, k\}$, where the constants $\alpha_0^1, \ldots, \alpha_0^k, \beta_0^1, \ldots ,\beta_0^k>0$ can be arbitrary.

theorem{\rm (Lower bound on the expected policy regret.)} There exists a problem instance $\bm{\theta}$ and an infinite subsequence of integers $\{T_n\}_{n=1}^\infty$ such that for any $T_n$, the expected policy regret of any algorithm is lower bounded as \begin{equation*} \mathrm{R}_{\bm{\theta}}(T_n) \ge \exp\left(-\frac{C}{\log(k)}\Gamma^*(\bm{\theta})T_n\right) \end{equation*} for some constant $C>0$.

theorem[Corrected Theorem 1 of Kasy2021] Consider exploration sampling, for Bernoulli bandits with $\mathrm{Beta}(\alpha_0^d,\beta_0^d)$ priors for each $d \in \{1, \ldots, k\}$, where the constants $\alpha_0^1, \ldots, \alpha_0^k, \beta_0^1, \ldots ,\beta_0^k>0$ can be arbitrary. Let the wave size be fixed $N_t = N \geq 1$. Assume that the optimal arm $d^{(1)} = \underset{d\in\{1,\ldots,k\}}{\rm{argmax}}\,\theta^d$ is unique and that $\theta^{d^{(1)}} < 1$. The following statements hold: \begin{description} • The share of observations $\frac{m^{d^{(1)}}_T}{NT}$ assigned to the best treatment $d^{(1)}$ converges almost surely to $\frac{1}{2}$, that is, \[ \frac{m^{d^{(1)}}_T}{NT} \xrightarrow{\mathrm{a.s.}} \frac{1}{2}. \] • The share of observations $\frac{m^{d}_T}{NT}$ assigned to each treatment $d\neq d^{(1)}$ converges almost surely to a non-random share $\lambda^d$, that is, \[ \frac{m^d_T}{NT} \xrightarrow{\mathrm{a.s.}} \lambda^d, \quad \forall d\neq d^{(1)}, \] where the limit assignment shares $\bm{\lambda} = (\lambda^1, \ldots, \lambda^k)$ (with $\lambda^{d^{(1)}} = \frac{1}{2}$) is such that $-\frac{1}{NT}\log\left( \sum_{d\neq d^{(1)}} p^d_T\right) \xrightarrow{\mathrm{a.s.}} \Lambda^*$, which is the optimal value of the optimization problem defined in (ref). • The posterior weighted policy regret converges almost surely to $0$ at the same rate $\Lambda^*$, that is, \[-\frac{1}{NT}\log \mathrm{W}_{\bm{\theta}}(T) \xrightarrow{\mathrm{a.s.}} \Lambda^*.\] No algorithm with limit assignment shares $\hat{\bm{\lambda}}\neq \bm{\lambda}$ with $\hat{\lambda}^{d^{(1)}} = \frac{1}{2}$ exists for which $\mathrm{W}_{\bm{\theta}}(T)$ goes to $0$ at a faster rate than $\Lambda^*$. \end{description}

appendix\section{Proof of Theorem (ref)} Let us define the problem complexity as \begin{equation*} H(\bm{\theta}) = \sum_{d \notin {\underset{d' \in \{1, \ldots, k\}}{argmax} \theta^{d'}}} \frac{1}{\left(\Delta^d\right)^2} = \sum_{d \notin {\underset{d' \in \{1, \ldots, k\}}{argmax} \theta^{d'}}} \frac{1}{\left(\theta^{d^{(1)}} - \theta^d\right)^2}, \end{equation*} where $d^{(1)} \in \underset{d'\in\{1,\ldots,k\}}{\rm{argmax}}\ \theta^{d'}$. To show Theorem (ref), we use the following results. \begin{lemma}{\rm (Lower bound on $\Gamma^*(\bm{\theta})$)} Consider $\bm{\theta} =(\theta^1,\ldots,\theta^k)$ such that $d^{(1)} = \underset{d\in\{1,\ldots,k\}}{\rm{argmax}}\ \theta^d$ is unique. We have \begin{equation*} \Gamma^*(\bm{\theta}) \ge \frac{1}{2H(\bm{\theta})}. \end{equation*} \end{lemma} \begin{proof} Recall that $\Gamma^* (\bm{\theta})$ is the solution of the optimization problem defined in (ref). We have, \begin{align*} \Gamma^*(\bm{\theta}) &= \max_{\bm{w}}\min_{d\neq d^{(1)}} G_j \left(w^{d^{(1)}}, w^d \right) \\ &\ge 2 \max_{\bm{w}}\min_{d\neq d^{(1)}} \min_{x \in \left[\theta^d, \theta^{d^{(1)}}\right]} \left[w^{d^{(1)}} \left(x - \theta^{d^{(1)}}\right)^2 + w^d \left(x - \theta^d\right)^2\right]\\ &\quad\quad \ \ \ (by Pinsker's inequality) \\ &\ge 2 \max_{\bm{w}}\min_{d\neq d^{(1)}} \min_{x \in \left[\theta^d, \theta^{d^{(1)}}\right]} \min\{w^{d^{(1)}}, w^d\} \cdot \left[\left(x - \theta^{d^{(1)}}\right)^2 + \left(x - \theta^d\right)^2 \right]\\ &= 2 \max_{\sum_{d\neq d^{(1)}}w^d=1/2}\min_{d\neq d^{(1)}} \min_{x \in \left[\theta^d, \theta^{d^{(1)}}\right]} w^d \left[\left(x - \theta^{d^{(1)}}\right)^2 + \left(x - \theta^d\right)^2 \right]\\ &\quad\quad\ \ \ \left(since w^{d^{(1)}} = 1/2\geq w^d \right)\\ &\ge \max_{\sum_{d\neq d^{(1)}}w^d=1/2}\min_{d\neq d^{(1)}} w^{d} \left(\theta^{d^{(1)}} - \theta^d\right)^2\\ &\quad\quad\ \ \ \left(since the inner minimization achieves optimality at x=\frac{\theta^{d^{(1)}}+\theta^d}{2}\right)\\ &\geq \frac{1}{2}\left(\sum_{d \ne d^{(1)}}\frac{1}{\left(\theta^{d^{(1)}} - \theta^d\right)^2}\right)^{-1} = \frac{1}{2H(\bm{\theta})} \end{align*} where the last inequality holds by considering a specific choice $\left(w^d\right)_{d\neq d^{(1)}}$ with $\sum_{d\neq d^{(1)}}w^d=1/2$, such that \[ w^d = \frac{1}{2}\frac{1}{\left(\theta^{d^{(1)}} - \theta^d\right)^2}\left(\sum_{d' \ne d^{(1)}}\frac{1}{\left(\theta^{d^{(1)}} - \theta^{d'}\right)^2}\right)^{-1}, \quad \forall d\neq d^{(1)}. \] \end{proof} Next, we define $k$ problem instances as follows. Let us denote the parameter of the problem instance $i\in\{1,\dots, k\}$ by $\bm{\theta}_{i} = (\theta^1_{i}, \dots, \theta^k_{i})$, i.e., the instance $i$'s average potential outcome of the treatment $d$ is denoted as $\theta^d_i$. \begin{definition}{\rm (Problem instances)} The first problem instance denoted by $\bm{\theta}_{1} = \left(\theta_1^1,\ldots,\theta_1^k\right)$ is defined as \begin{align*} \theta^{1}_{1} &= \frac{1}{2} \quad and \quad \theta^d_{1} = \frac{1}{2} - f^d \quad \forall d\neq 1, \end{align*} where $f^d := \frac{d}{4k}$. \\ The other $(k-1)$ problem instances are denoted by $\bm{\theta}_{i}$ for $i = 2,3,\dots,k$, and each $\bm{\theta}_{i}=(\theta_i^1,\ldots,\theta_i^k)$ is defined as the ones where the average potential outcome of the treatment $i$ is replaced by $\frac{1}{2} + f^i$ so that treatment $i$ is the best treatment in the problem instance $i$, that is, \begin{align*} \theta^i_{i} = \frac{1}{2} + f^i \quad \text{and} \quad \theta^{d}_{i} &= \theta^{d}_{1} \quad \forall d\neq i. \end{align*} \end{definition} We use the following proposition. \begin{proposition}{\rm (Theorem 2 in Carpentier2016.)} Let $k \geq 2$. Consider the problem instances $\{\bm{\theta}_{1},\dots,\bm{\theta}_{k}\}$ in Definition (ref). For any algorithm, for each $T$, there exists at least one $\bm{\theta} \in \{\bm{\theta}_{1},\dots,\bm{\theta}_{k}\}$ such that \begin{equation*} \mathrm{R}_{\bm{\theta}} (T) \ge \frac{1}{6} \exp\left(- \frac{60T}{h^* H\left(\bm{\theta}\right)} - 2\sqrt{T \log(6Tk)}\right) \end{equation*} where $h^*\geq \frac{3}{10}\log(k)$. \end{proposition} This proposition gives the following corollary. \begin{corollary} Let $k \ge 2$. Consider the problem instances $\{\bm{\theta}_{1},\dots,\bm{\theta}_{k}\}$ in Definition (ref). For any algorithm, there exists an instance $\bm{\theta} \in \{\bm{\theta}_{1},\dots,\bm{\theta}_{k}\}$ and an infinite subsequence of integers $\{T_n\}_{n=1}^\infty$ such that for any $T_n$, \[\frac{200T_n}{\log (k) H\left(\bm{\theta}\right)} \ge 2\sqrt{T_n \log(6T_nk)},\] and thus \begin{align*} \mathrm{R}_{\bm{\theta}} (T_n) &\ge \frac{1}{6} \exp\left(- \frac{200T_n}{\log(k) H\left(\bm{\theta}\right)} - 2\sqrt{T_n \log(6T_nk)}\right) \ge \frac{1}{6} \exp\left(- \frac{400T_n}{\log(k) H\left(\bm{\theta}\right)}\right). \end{align*} \end{corollary} {Corollary (ref) directly follows from the fact that $\sqrt{T \log T} = o(T)$ and Proposition (ref).} Corollary (ref) states that the exponent of the expected policy regret is at most $\frac{400T_n}{\log(k) H\left(\bm{\theta}\right)}$ in one of the $k$ problem instances of Definition (ref). Combining Lemma (ref) and Corollary (ref), for any $T_n$, \begin{align*} -\frac{1}{T_n}\log \mathrm{R}_{\bm{\theta}} (T_n) &\le \frac{400}{\log(k) H\left(\bm{\theta}\right)} \le \frac{800 \Gamma^*(\bm{\theta})}{\log(k) } , \end{align*} which implies (ref) with $C=800$. Therefore, the statement in Theorem 1 (3) does not hold. This concludes the proof. \section{Corrected Lemmata} Here, we correct the lemmata associated with the corrected theorem. \begin{lemma}[Corrected Lemma 2 (2) of Kasy2021] Consider $\mathrm{Beta}(\alpha_0^d,\beta_0^d)$ priors for each $d \in \{1, \ldots, k\}$. Under any allocation rule satisfying $\frac{m^{d^{(1)}}_T}{NT}~\to~\frac{1}{2}$, \begin{align*} \limsup_{T\to\infty} -\frac{1}{NT}\log\left(\sum_{d\neq d^{(1)}}p^d_T \right)\leq \Lambda^*, \end{align*} and under any allocation rule satisfying $\frac{m^{d}_T}{NT} \to \lambda^{d}$ for each $d\in\{1,\dots, k\}$, \begin{align*} \lim_{T\to\infty} -\frac{1}{NT}\log\left(\sum_{d\neq d^{(1)}}p^d_T \right)= \Lambda^*. \end{align*} \end{lemma} \begin{lemma}[Corrected Lemma 4 of Kasy2021. From Lemma 12 of Russo2016 and Lemma 30 of Shang2020] Consider any adaptive allocation rule. If \begin{align} \lim_{T\to\infty}\frac{1}{T} \sum_{t=1}^T q_t^{d^{(1)}} = \frac{1}{2} \end{align} and \begin{align} \sum^\infty_{t=1}q^d_T\cdot\mathbbm{1}\left\{\frac{1}{T} \sum_{t=1}^T q_{t}^{d} > \lambda^d + \delta\right\} < \infty\quad \forall d\neq d^{(1)}, \delta > 0, \end{align} then \[\lim_{T\to\infty}\frac{1}{T} \sum_{t=1}^T q_t^{d^{(1)}} = \lambda^d.\] \end{lemma} \begin{lemma}[Corrected Lemma 5 of Kasy2021. From Lemma 13 of Russo2016 and Lemma 29 of Shang2020] Fix any $\xi > 0$ and $d\neq d^{(1)}$. Under any allocation rule, if ${\lim_{T\to \infty} m^d_T/(NT) = 1/2}$, there exists $\xi' > 0$ and a sequence $\varepsilon_T$ with ${ \lim_{T\to \infty}\varepsilon_T =0}$ such that for any $T\in\mathbb{N}$, \begin{align*} \frac{m^d_T}{NT}\geq \lambda^d + \xi \Longrightarrow \frac{p^d_T}{\max_{d\neq d^{(1)}}p^d_T} \leq \exp\left(-T(\xi' + \varepsilon_T)\right), \end{align*} almost surely. \end{lemma} \begin{lemma}[Corrected Lemma 6 of Kasy2021.] Denote with $\overline{D}$ the arms that are sampled only a finite amount of times: \begin{align*} \overline{D} = \left\{ d\in\{1,\dots, k\}: \forall t, m^d_t < \infty \right\}. \end{align*} If $\overline{D}$ is empty, $p^{d^{(1)}}_t$ converges almost surely to $1$. If $\overline{D}$ is non-empty, then for every $d\in \overline{D}$, we have $\liminf_{T\to\infty} p^d_T > 0$ almost surely. \end{lemma} Lemma (ref) basically follows from Theorem 6 of Shang2020. We prove this lemma in Appendix (ref). We extend the result from Beta-Bernoulli bandit model with the $\mathrm{Beta}(1, 1)$ prior to that with $\mathrm{Beta}(\alpha_0^d,\beta_0^d)$ priors for each $d \in \{1, \ldots, k\}$, where the constants $\alpha_0^1, \ldots, \alpha_0^k, \beta_0^1, \ldots ,\beta_0^k>0$ can be arbitrary. Lemmata (ref) and (ref) are corrected citation of Russo2016 and Shang2020. We derive Lemma (ref) with the help of Lemma 28 in Shang2020. \section{Auxiliary Results} In addition to Lemmata (ref)--(ref), which correspond to Lemmata 2 (2), 4--6 in Kasy2021, we additionally use the following results, Proposition (ref), (ref), and (ref), from Shang2020 and Kasy2021. We further state and prove Lemma (ref) and (ref), which is required for the proof of Lemma (ref). \begin{proposition}[From Lemma 4 of Shang2020] There exists a random variable $W$ with $\mathbb{E}\left[\exp\left( \lambda W\right)\right] < \infty$ for any $\lambda > 0$ such that \begin{align*} \ \left| m^d_T - N\sum^T_{t=1}q^d_t \right|\leq W\sqrt{(NT+1)\log(e^2 + NT)},\; \text{almost surely}, \; \forall T\in\mathbb{N}, d\in\{1,\ldots,k\}. \end{align*} \end{proposition} \begin{proposition}[From Step 2 of the proof of Theorem 1 in Kasy2021] Under exploration sampling, for each $d\in\{1,2,\dots, k\}$ and all $t\in\mathbb{N}$, \begin{align*} \frac{p^d_t}{p^d_t + 1} \leq q^d_t \leq \frac{1}{2}. \end{align*} \end{proposition} \begin{proposition}[Lemma 26 of Shang2020] Let $X \sim \mathrm{Beta}(a_0,a_1)$ and $Y \sim \mathrm{Beta}(a_2, a_3)$ {such that} $$0 < \frac{a_0-1}{a_0+a_1 -1} < \frac{a_2-1}{a_2+a_3 -1}.$$ Then, we have $$ \mathbb{P}(X>Y) \le D \exp(-C), $$ where $$ C = \inf_{\frac{a_0-1}{a_0+a_1 -1} \le y \le \frac{a_2-1}{a_2+a_3 -1}} C_{a_0,a_1}(y) + C_{a_2,a_3}(y), $$ $$ C_{a_0,a_1}(y) = (a_0 + a_1 -1)d_{\mathrm{KL}}\left( \frac{a_0-1}{a_0+a_1 -1}, y\right), $$ and $$ D = 3 + \min \left\{ C_{a_0,a_1}\left(\frac{a_2-1}{a_2+a_3 -1}\right) , C_{a_2,a_3}\left(\frac{a_0-1}{a_0+a_1 -1}\right) \right\}. $$ \end{proposition} Proposition (ref) is used for showing almost sure convergence of the shares of observations (see Remark (ref)). Here, we note that from Proposition (ref), we can insist that with probability $1$, \begin{align*} \lim_{T\to\infty}\frac{m^{d}_T}{NT} = \lambda^d\ \Longleftrightarrow\ \lim_{T\to\infty}\frac{1}{T} {\sum^T_{t=1}q^{d}_t} = \lambda^d. \end{align*} Besides, to prove Lemma (ref), we show the following lemmata. \begin{lemma}[Lower bound on the deviation probability of Beta distribution] Let $X \sim \mathrm{Beta}(a_0, a_1)$. We have \begin{align*} & \mathbb{P}(X \ge x) \ge \frac{\exp\left( - (a_0 + a_1 - 1) d_{\mathrm{KL}} \left(\frac{a_0-1}{a_0 + a_1 -1},x\right)\right)}{a_0 + a_1}, \\ \text{and}\quad \quad & \mathbb{P}(X \le x) \ge \frac{\exp\left( - (a_0 + a_1 - 1) d_{\mathrm{KL}} \left(\frac{a_0-1}{a_0 + a_1 -1},x\right)\right)}{a_0 + a_1}. \end{align*} \end{lemma} \begin{proof}[Proof of Lemma (ref)] We use following facts (see e.g., Appendix I.1 of Shang2020.). Let $F_{a_0, a_1}^{\text{Beta}}(x)$ be the cumulative distribution function of a Beta distribution with parameters $a_0$ and $a_1$. Similarly, let $F_{a_0,a_1}^{\text{B}}(x)$ be the cumulative distribution function of a Binomial distribution with parameters $a_0$ and $a_1$. We have a following relationship (Beta-Binomial trick) \begin{align*} F_{a_0, a_1}^{\text{Beta}}(x) = 1 - F_{a_0 + a_1 - 1, x}^{\text{B}}( a_0 -1). \end{align*} Therefore, we have \begin{align*} \mathbb{P}(X \ge x) & = \mathbb{P}(B(a_0 + a_1-1,x) \le a_0 - 1) \\ & = \mathbb{P}(B(a_0 + a_1-1,1 - x) \ge a_1), \end{align*} where $B(a_0,a_1)$ is a Binomial Distribution with parameters $a_0$ and $a_1$. From Sanov's inequality (Appendix I.1 of Shang2020), we have \begin{align*} \frac{\exp\left( - n d_{\mathrm{KL}}(x/n, p)\right)}{n+1}\le \mathbb{P}(B(n,p) \ge x)\le \exp\left( - n d_{\mathrm{KL}}(x/n, p)\right). \end{align*} We get \begin{align*} \mathbb{P}(X \ge x) & = \mathbb{P}(B(a_0 + a_1-1,1 - x) \ge a_1) \\ & \ge \frac{1}{a_0 + a_1} \exp\left( - (a_0 + a_1 - 1)d_{\mathrm{KL}}\left( \frac{a_1}{a_0 + a_1 - 1},1-x\right) \right) \\ & = \frac{1}{a_0 + a_1} \exp\left( - (a_0 + a_1 - 1)d_{\mathrm{KL}}\left( \frac{a_0 - 1}{a_0 + a_1 - 1},x\right) \right), \end{align*} and \begin{align*} \mathbb{P}(X \le x) & = \mathbb{P}(B(a_0 + a_1-1,x) \ge a_0 - 1) \\ & \ge \frac{1}{a_0 + a_1} \exp\left( - (a_0 + a_1 - 1)d_{\mathrm{KL}}\left( \frac{a_0 - 1}{a_0 + a_1 - 1},x\right) \right). \end{align*} This concludes the proof. \end{proof} Then, based on Lemma (ref), we have the following lemma, which has an exponent that matches the exponent of Proposition (ref). \begin{lemma} Let $X \sim \mathrm{Beta}(a_0,a_1)$ and $Y \sim \mathrm{Beta}(a_2, a_3)$ {such that} $$0 < \frac{a_0-1}{a_0+a_1 -1} < \frac{a_2-1}{a_2+a_3 -1}.$$ Then, we have $$ \mathbb{P}(X>Y) \ge D \exp(-C), $$ where $$ C = \inf_{\frac{a_0-1}{a_0+a_1 -1} \le y \le \frac{a_2-1}{a_2+a_3 -1}} C_{a_0,a_1}(y) + C_{a_2,a_3}(y), $$ $$ C_{a_0,a_1}(y) = (a_0 + a_1 -1)d_{\mathrm{KL}}\left( \frac{a_0-1}{a_0+a_1 -1}, y\right), $$ and $$ D = \frac{1}{(a_0+ a_1)(a_2+a_3)}. $$ \end{lemma} \begin{proof}[Proof of Lemma (ref)] For each $y \in \left[\frac{a_0-1}{a_0+a_1 -1}, \frac{a_2-1}{a_2+a_3 -1}\right]$, we have \begin{align*} & \mathbb{P}(X>Y) \\ & \ge \mathbb{P} \left(\{X > y\}\cap \{Y < y\}\right) \\ & \ge \frac{\exp\left( - \left( (a_0 + a_1 - 1) d_{\mathrm{KL}} \left(\frac{a_0-1}{a_0 + a_1 -1},y\right) + (a_2 + a_3 - 1) d_{\mathrm{KL}} \left(\frac{a_2-1}{a_2 + a_3 -1},y\right)\right)\right)}{(a_0 +a_1)(a_2 + a_3)}, \end{align*} where the last inequality is from Lemma (ref). Optimizing the right hand side of the previous inequality over $y$, we conclude the proof. \end{proof} \section{Proof of Theorem (ref)} In this section, we show the proofs of Theorem (ref) (1) and (2) in Section (ref) and Theorem (ref) (3) in Section (ref). The proof procedure in Section (ref) follows that of Kasy2021 as closely as possible. \subsection{Proof of Theorem (ref) (1) and (2)} From Lemma (ref), under any allocation rule, given the event $\lim_{T\to \infty} \frac{m^{d}_T}{NT} = \lambda^{d}$, which occurs with probability $1$; we can conclude that \begin{align*} -\frac{1}{NT}\log \left( \sum_{d\neq d^{(1)}}p^d_T \right) \xrightarrow{\mathrm{a.s.}} \Lambda^*. \end{align*} To prove Theorem (ref) (1) and (2), it suffices to show that under the exploration sampling, for each $d\in\{1,\dots,k\}$, \begin{align} \frac{m^{d}_T}{NT} \xrightarrow{\mathrm{a.s}} \lambda^d. \end{align} To show that the exploration sampling satisfies (ref), we correct the following three steps in the proof of Kasy2021, i.e., \begin{description} • Each treatment is assigned infinitely often, that is, $m^d_T \xrightarrow{\mathrm{a.s.}} \infty,\forall d \in \{1, \ldots, k\}$. • The share of observations $m^{d^{(1)}}_T/(NT)$ assigned to the best treatment $d^{(1)}$ converges to $\lambda^{d^{(1)}} = 1/2$ almost surely as $T\to\infty$. • The share of observations $m^{d}_T/(NT)$ assigned to each treatment $d\neq d^{(1)}$ converges to $\lambda^d$ almost surely as $T\to\infty$. \end{description} We use Step 1 to show the almost sure convergence of the posterior probability. Then, because the share of observations is determined by the posterior probability, we can show Step 2 and 3, which directly implies (ref). \begin{proof}[Proof of Theorem (ref) (1) and (2)]$\ $ \textbf{Step 1: Each treatment is assigned infinitely often.} We show $m^d_T \xrightarrow{\mathrm{a.s.}} \infty$ for each $d\in\{1,2,\dots, k\}$ using proof by contradiction. Suppose that there exists $d'\in\{1,2,\dots, k\}$, such that $\lim_{T\to\infty} m^{d'}_T < \infty$. Under the exploration sampling, from Proposition (ref), we have $q^{d'}_T \geq \frac{p^{d'}_T}{p^{d'}_T + 1}$; therefore, by Lemma (ref), if $d'\in\overline{D} = \{d\in\{1,\dots, k\}: \forall T, m^d_T < \infty\}$, then $\liminf_{T\to\infty} p^{d'}_T > 0$, which implies that $\sum^\infty_{t=1}q^{d'}_T = \infty$. By Proposition (ref), we have $m^d_T \xrightarrow{\mathrm{a.s.}} \infty$. This causes a contradiction with probability $1$. Therefore, $m^d_T \xrightarrow{\mathrm{a.s.}} \infty$, for all $d\in\{1,\dots, k\}$. \textbf{Step 2: The share of observations $m^{d^{(1)}}_T/(NT)$ assigned to the best treatment $d^{(1)}$ converges to $1/2$ almost surely as $T\to\infty$.} Because $m^d_T \xrightarrow{\mathrm{a.s.}} \infty$ for all $d\in\{1,\dots, k\}$, we have $p^{d^{(1)}}_T\xrightarrow{\mathrm{a.s.}}1$ from Lemma (ref). Then, from Proposition (ref), we conclude that $ m^{d^{(1)}}_T/(NT) \xrightarrow{\mathrm{a.s.}}1/2$. \textbf{Step 3: The share of observations $m^{d}_T/(NT)$ assigned to each treatment $d\neq d^{(1)}$ converges to $\lambda^d$ almost surely as $T\to\infty$.} Our final step is to show (ref). From Proposition (ref), we can obtain this result if (ref) and (ref) hold almost surely. Firstly, using Proposition (ref), $m_T^{d^{(1)}}/(NT)\xrightarrow{\mathrm{a.s.}}1/2$ (the result of {\bf Step 2}) leads to \begin{align*} \frac{1}{T} \sum_{t=1}^T q_t^{d^{(1)}} \xrightarrow{\mathrm{a.s.}} \frac{1}{2}. \end{align*} Thus, (ref) holds. Next, we check that (ref) holds. For $d \ne d^{(1)}$, let us define an event $\mathcal{F}^d$ as \begin{align*} \mathcal{F}^d = \left\{ \lim_{T \to \infty} p_T^d = 0 \quad \text{and} \quad\forall T\in\mathbb{N},\ \left| m^d_T - N\sum^T_{t=1}q^d_t \right|\leq W\sqrt{(NT+1)\log(e^2 + NT)}\right\}, \end{align*} where $W$ is a random variable defined in Proposition (ref). This event $\mathcal{F}^d$ occurs with probability $1$ by Lemma (ref) and Proposition (ref). Because each treatment is assigned infinitely often from Step 1, $\lim_{T \to \infty} p_T^d = 0$ for $d \ne d^{(1)}$ almost surely from Lemma (ref). The second element of $\mathcal{F}^d$ occurs with probability $1$ from Proposition (ref). Under this event $\mathcal{F}^d$, for each constant $\xi > 0$, there exists $s$ such that for all $T \geq s$, we have \begin{align} \left| \frac{1}{T}\sum_{t=1}^T q_t^d - \frac{m_T^d}{NT} \right| \leq \xi. \end{align} This is because from the second element of $\mathcal{F}^d$, for all $T$, \[\left| \frac{m^d_T}{NT} - \frac{1}{T}\sum^T_{t=1}q^d_t \right|\leq \frac{W}{NT}\sqrt{(NT+1)\log(e^2 + NT)}\] holds, which implies that for each each constant $\xi > 0$, (ref) holds for sufficiently large $T$. Then, the following relationship holds almost surely: \begin{align*} \mathbbm{1}\left\{ \frac{1}{T}\sum_{t=1}^T q_t^d \geq \lambda^d + 2 \xi \right\} \leq \mathbbm{1}\left\{ \frac{m_T^d}{NT} \geq \lambda^d + \xi \right\}, \end{align*} where for an event $\mathcal{E}$, $\mathbbm{1}\left\{\mathcal{E}\right\} = 1$ if the event $\mathcal{E}$ occurs. Under the event $\mathcal{F}^d$, the exists $t_0>0$ such that for all $t\ge t_0$, $ p_t^d \le 1/2$. As Kasy2021 shows in Step 3 of the proof in Theorem 1, when $\max_{d\neq d^{(1)}} p^{d}_t \leq 1/2$, we have \begin{align*} q^d_t \leq 2\frac{p^d_t}{\max_{d\neq d^{(1)}} p^{d}_t}. \end{align*} Besides, Lemma (ref) insists that given the event ${m_T^d}/{NT} \to 1/2$, there exists $\xi' > 0$ and a sequence $\varepsilon_T$ with $\varepsilon_T \to 0$ such that for any $T\in\mathbb{N}$, \[\frac{m_T^d}{NT} \geq \lambda^d + \xi \Longrightarrow \frac{p^d_T}{\max_{d\neq d^{(1)}}p^d_T} \leq \exp\left(-T(\xi' + \varepsilon_T)\right).\] Therefore, for $d\neq d^{(1)}$, under the event $ \mathcal{F}^d$, the following inequality holds with probability $1$. \begin{align*} \sum^T_{t\geq \max\{s,t_0\}}q^d_t\mathbbm{1}\left\{ \frac{1}{T}\sum_{t=1}^T q_t^d \geq \lambda^d + 2 \xi \right\} & \leq \sum^T_{t\geq \max\{s,t_0\}}q^d_t\mathbbm{1}\left\{\frac{m_T^d}{NT} \geq \lambda^d + \xi \right\} \\ & \leq \sum^T_{t\geq \max\{s,t_0\}}\exp\left(-t(\xi' + \varepsilon_t)\right) \\ & < \infty. \end{align*} Therefore, (ref) holds with probability 1. By combining these results, from Lemma (ref), (ref) holds. This concludes the proof. \end{proof} \subsection{Proof of Theorem (ref) (3)} We prove Theorem (ref) (3) by using Lemma (ref). The proof consists of two parts: derivation of the upper bound under the exploration sampling and lower bound under any allocation rule. \begin{proof}[Proof of Theorem (ref) (3)] First, we prove $-\frac{1}{NT}\log \mathrm{W}_{\bm{\theta}}(T) \xrightarrow{\mathrm{a.s.}} \Lambda^*$. The logarithmic posterior policy regret can be decomposed as \begin{align*} \log \mathrm{W}_{\bm{\theta}}(T) &= \log \left(\sum_{d\in\{1,\dots,k\}}\Delta^{d}\cdot p^d_T\right)\\ &= \log \left( \sum_{d\neq d^{(1)}} \Delta^{d}\cdot p^d_T\right) \leq \log \left(\max_{d\in\{1,\ldots,k\}} \Delta^{d} \sum_{d\neq d^{(1)}} p^d_T\right). \end{align*} Therefore, \[-\frac{1}{NT}\log \mathrm{W}_{\bm{\theta}}(T) \geq -\frac{1}{NT}\log \left(\max_{d\in\{1,\ldots,k\}} \Delta^{d}\right) - \frac{1}{NT}\log \left( \sum_{d\neq d^{(1)}} p^d_T\right).\] While $\max_{d\in\{1,\ldots,k\}} \Delta^{d}$ is constant, $\sum_{d\neq d^{(1)}} p^d_T$ decays exponentially, that is, the first converges to $0$ and the second term converges to constant, $\Lambda^*$. Similarly, we can also show that \[-\frac{1}{NT}\log \mathrm{W}_{\bm{\theta}}(T) \leq -\frac{1}{NT}\log \left(\min_{d\in\{1,\ldots,k\}} \Delta^{d}\right) - \frac{1}{NT}\log \left( \sum_{d\neq d^{(1)}} p^d_T\right).\] By taking the limit from the lower and upper bounds, we show the statement. Next, we prove the second statement of Theorem (ref) (3), which is the theoretical lower bound of algorithms. From Lemma (ref), under any adaptive allocation rule satisfying $\frac{m^{d^{(1)}}_T}{NT} \xrightarrow{\mathrm{a.s.}} \frac{1}{2}$, $\limsup_{T\to\infty}-\frac{1}{NT}\log \left( \sum_{d\neq d^{(1)}}p^d_T \right) \leq \Lambda^*$ almost surely. This implies that under any adaptive allocation rule satisfying $\frac{m^{d^{(1)}}_T}{NT} \xrightarrow{\mathrm{a.s.}} \frac{1}{2}$, $\limsup_{T\to\infty}-\frac{1}{NT}\log \mathrm{W}_{\bm{\theta}}(T) \leq \Lambda^*$ almost surely. Thus, the limit of the logarithmic posterior policy regret under the exploration sampling matches the lower bound. This concludes the proof. \end{proof} \section{Proof of Lemma (ref)} The proof follows similar steps to the proof of Theorem 6 in Shang2020. Note that the original proof has a technical issue, and we also correct it in our proof.\footnote{In particular, transformation of Eq. (ref) fixes the issue of Theorem 6 of Shang2020 by utilizing Lemma (ref).} \begin{proof} We restate the set $\overline{D}$ for the sake of readability: \begin{align*} \overline{D} = \left\{ d\in\{1,\dots, k\}: \forall t, m^d_t < \infty \right\}. \end{align*} First, we prove the first part of the Lemma (ref), a lower bound on the posterior probabilities $\sum_{d\neq d^{(1)}}p^d_T$, by giving separate proofs for the cases where $D$ is the empty set or not. \textbf{Case 1. A lower bound on the posterior probabilities when $\overline{D}$ is not empty.} The posterior variance $ \sigma_{T, d}^2 $ is computed as \begin{align*} \sigma_{T, d}^2 & = \frac{\alpha_T^d\beta_T^d}{\left(\alpha_T^d + \beta_T^d\right)^2\left(\alpha_T^d + \beta_T^d+1\right)} = \frac{\left(\alpha_0^d + r_{T-1}^d\right)\left(\beta_0^d + m_{T-1}^d- r_{T-1}^d\right)}{\left(\alpha_0^d + \beta_0^d + m_{T-1}^d\right)^2\left(\alpha_0^d + \beta_0^d + m_{T-1}^d + 1\right)}. \end{align*} Thus, when $d \in \overline{D}$, we have $\liminf_{T \to \infty}\sigma_{T, d}>0$ and $\liminf_{T \to \infty}p_T^d>0$. This means that $\limsup_{T\to \infty}p_T^{d^{(1)}} <1$. Thus, we have \begin{align*} \limsup_{T\to\infty} -\frac{1}{TN}\log\left(\sum_{d\neq d^{(1)}}p^d_T \right) & = \limsup_{T\to\infty} -\frac{1}{TN}\log\left(1 - p^{d^{(1)}}_T \right) \\ & = 0 \\ & \le \Lambda^*. \end{align*} \textbf{Case 2. A lower bound on the posterior probabilities when $\overline{D}$ is empty.} When $\overline{D}$ is empty, we have \begin{align} \max_{d \neq d^{(1)}} \mathbb{P}\left(\tilde{\theta}^d \ge \tilde{\theta}^{d^{(1)}} | \bm m_{T-1}, \bm r_{T-1}\right) & \le 1 - p_T^{d^{(1)}} \nonumber \\ &\le \sum_{d\neq d^{(1)}} \mathbb{P}\left(\tilde{\theta}^d \ge \tilde{\theta}^{d^{(1)}} | \bm m_{T-1}, \bm r_{T-1}\right) \nonumber \\ & \le (k-1) \max_{d \neq d^{(1)}} \mathbb{P}\left(\tilde{\theta}^d \ge \tilde{\theta}^{d^{(1)}} | \bm m_{T-1}, \bm r_{T-1}\right) . \end{align} Since all the arms are sampled infinitely often, there exists $t_0$ such that for all $T \ge t_0$, for all $d \neq d^{(1)}$, \begin{align*} \frac{\alpha_0^d -1 + r_{T-1}^d}{\alpha_0^d + \beta_0^d -1 + m_{T-1}^d} < \frac{\alpha_0^{d^{(1)}} -1 + r_{T-1}^{d^{(1)}}}{\alpha_0^{d^{(1)}} + \beta_0^{d^{(1)}} -1 + m_{T-1}^{d^{(1)}}}. \end{align*} For each $d \neq d^{(1)}$, define the interval, \begin{align*} I_d = \left[ \frac{\alpha_0^d -1 + r_{T-1}^d}{\alpha_0^d + \beta_0^d -1 + m_{T-1}^d}, \frac{\alpha_0^{d^{(1)}} -1 + r_{T-1}^{d^{(1)}}}{\alpha_0^{d^{(1)}} + \beta_0^{d^{(1)}} -1 + m_{T-1}^{d^{(1)}}}\right]. \end{align*} Using Proposition (ref) with $a_0 = \alpha_0^d + r_{T-1}^d$, $a_1 = \beta_0^d + m_{T -1}^d - r_{T-1}^d$, $a_2= \alpha_0^{d^{(1)}} + r_{T-1}^{d^{(1)}}$, and $a_3 = \beta_0^{d^{(1)}} + m_{T -1}^{d^{(1)}} - r_{T-1}^{d^{(1)}}$, we get \begin{align*} \mathbb{P}\left(\tilde{\theta}^d \ge \tilde{\theta}^{d^{(1)}} | \bm m_{T-1}, \bm r_{T-1}\right) & \le D \exp\left( - \inf_{y \in I_d} C_{a_0,a_1}(y) + C_{a_2,a_3}(y)\right). \end{align*} We have \begin{align*} D & \le 3 + (a_0 + a_1 -1 ) d_{\mathrm{KL}} \left(\frac{a_0-1}{a_0+a_1-1}, \frac{a_2-1}{a_2+a_3-1}\right) \\ & = 3 + \left(\alpha_0^d + \beta_0^d -1 + m_{T-1}^d\right) d_{\mathrm{KL}}\left(\frac{\alpha_0^d -1 + r_{T-1}^d}{\alpha_0^d + \beta_0^d -1 + m_{T-1}^d}, \frac{\alpha_0^{d^{(1)}} -1 + r_{T-1}^{d^{(1)}}}{\alpha_0^{d^{(1)}} + \beta_0^{d^{(1)}} -1 + m_{T-1}^{d^{(1)}}}\right) \\ & \le 3 + 2T N d_{\mathrm{KL}}\left(0, \frac{\alpha_0^{d^{(1)}} -1 + TN}{\alpha_0^{d^{(1)}} + \beta_0^{d^{(1)}} -1 + TN}\right) \\ & \le C\left(\alpha_0^{d^{(1)}}, \beta_0^{d^{(1)}} \right) TN \log TN, \end{align*} with some positive constant $ C\left(\alpha_0^{d^{(1)}}, \beta_0^{d^{(1)}} \right)$. We get \begin{align} & \limsup_{T \to \infty}\frac{1}{NT} \log \left( \frac{\mathbb{P}\left(\tilde{\theta}^d \ge \tilde{\theta}^{d^{(1)}} | \bm m_{T-1}, \bm r_{T-1}\right)}{\exp\left( - \inf_{y \in I_d} C_{a_0,a_1}(y) + C_{a_2,a_3}(y)\right)}\right) \nonumber \\ & \le \limsup_{T \to \infty}\frac{1}{NT} \log \left(C\left(\alpha_0^{d^{(1)}}, \beta_0^{d^{(1)}} \right) TN \log TN\right) \nonumber \\ & = 0. \end{align} Using Lemma (ref) with $a_0 = \alpha_0^d + r_{T-1}^d$, $a_1 = \beta_0^d + m_{T -1}^d - r_{T-1}^d$, $a_2= \alpha_0^{d^{(1)}} + r_{T-1}^{d^{(1)}}$, and $a_3 = \beta_0^{d^{(1)}} + m_{T -1}^{d^{(1)}} - r_{T-1}^{d^{(1)}}$, we get, \begin{align*} \mathbb{P}\left(\tilde{\theta}^d \ge \tilde{\theta}^{d^{(1)}} | \bm m_{T-1}, \bm r_{T-1}\right) & \ge D \exp\left( - \inf_{y \in I_d} C_{a_0,a_1}(y) + C_{a_2,a_3}(y)\right), \end{align*} where $D = \frac{1}{\left(\alpha_0^d + \beta_0^d + m_{T -1}^d\right)\left(\alpha_0^{d^{(1)}} + \beta_0^{d^{(1)}} + m_{T -1}^{d^{(1)}}\right)}$. We get \begin{align} & \liminf_{T \to \infty} \frac{1}{NT} \log \left( \frac{\mathbb{P}\left(\tilde{\theta}^d \ge \tilde{\theta}^{d^{(1)}} | \bm m_{T-1}, \bm r_{T-1}\right)}{\exp\left( - \inf_{y \in I_d} C_{a_0,a_1}(y) + C_{a_2,a_3}(y)\right)}\right) \nonumber \\ & \ge \liminf_{T \to \infty} \frac{1}{NT} \log D \nonumber \\ & \ge \liminf_{T \to \infty} \frac{1}{NT} \log \frac{1}{4(NT)^2} \nonumber \\ & \ge 0 \end{align} Therefore, for each $d \neq d^{(1)}$, similarly to the proof of Theorem 6 of Shang2020, we get \begin{align} & 1 - p_{T}^{d^{(1)}} \\\nonumber & \underset{ (ref)}{\doteq} \max_{d \neq d^{(1)}} \mathbb{P}\left(\tilde{\theta}^d \ge \tilde{\theta}^{d^{(1)}} | \bm m_{T-1}, \bm r_{T-1}\right) \\\nonumber & \underset{(ref) \text{ and } (ref)}{\doteq} \exp\Bigg( -TN \min_{d \neq d^{(1)}} \inf_{y \in I_d} \Bigg[\frac{\alpha_0^d + \beta_0^d -1 + m_{T-1}^d}{TN} d_{\mathrm{KL}}\left( \frac{\alpha_0^d -1 + r_{T-1}^d}{\alpha_0^d + \beta_0^d -1 + m_{T-1}^d},y\right) \\ & \qquad\qquad\qquad + \frac{\alpha_0^{d^{(1)}} + \beta_0^{d^{(1)}} -1 + m_{T-1}^{d^{(1)}}}{TN}d_{\mathrm{KL}}\left(\frac{\alpha_0^{d^{(1)}} -1 + r_{T-1}^{d^{(1)}}}{\alpha_0^{d^{(1)}} + \beta_0^{d^{(1)}} -1 + m_{T-1}^{d^{(1)}}},y \right)\Bigg]\Bigg) \\\nonumber & \ge \exp\Bigg( -TN \max_{\bm w} \min_{d \neq d^{(1)}} \inf_{y \in I_d} \Bigg[ w_d d_{\mathrm{KL}}\left( \frac{\alpha_0^d -1 + r_{T-1}^d}{\alpha_0^d + \beta_0^d -1 + m_{T-1}^d},y\right)\\ & \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad + \frac{1}{2}d_{\mathrm{KL}}\left(\frac{\alpha_0^{d^{(1)}} -1 + r_{T-1}^{d^{(1)}}}{\alpha_0^{d^{(1)}} + \beta_0^{d^{(1)}} -1 + m_{T-1}^{d^{(1)}}},y\right) \Bigg] \Bigg),\nonumber \end{align} where for two real-valued sequences $(a_n)$ and $(b_n)$, $a_n \doteq b_n$ denotes logarithmic equivalence, that is, \begin{align*} \lim_{n\to\infty} \frac{1}{n}\log\left(\frac{a_n}{b_n}\right) = 0. \end{align*} For each $\varepsilon>0$, there exists $t_1(\varepsilon)>0$ such that for all $ T \ge t_1$, for all $d \neq d^{(1)}$, \begin{align*} I_d \subset [\theta^d+ \varepsilon, \theta^{d^{(1)}}- \varepsilon] = I_{d, \varepsilon}^*. \end{align*} As the Kullback-Leibler divergence is uniformly continuous on $I_{d, \varepsilon}^*$, there exists $t_2(\varepsilon)>0$ such that for all $T \ge t_2$, \begin{align*} d_{\mathrm{KL}}\left(\frac{\alpha_0^d -1 + r_{T-1}^d}{\alpha_0^d + \beta_0^d -1 + m_{T-1}^d}, y\right) \ge (1- \varepsilon) d_{\mathrm{KL}}(\theta^d,y), \end{align*} for all $y$ and all $d \in \{1, \ldots, k\}$. Thus, we get, \begin{align*} 1 - p_{T}^{d^{(1)}} & \ge \exp\left( -T N \max_{\bm w} \min_{d \neq d^{(1)}} \inf_{y \in I_{d, \varepsilon}^*}\left[ w_d d_{\mathrm{KL}}( \theta^d,y) + \frac{1}{2}d_{\mathrm{KL}}(\theta^{d^{(1)}},y) \right] \right) \end{align*} and thus, \begin{align*} \limsup_{T\to \infty} -\frac{1}{NT} \log \left(\sum_{d \neq d^{(1)}} p_T^d\right) \le \Lambda^*. \end{align*} This concludes the proof of the first part of Lemma (ref). Next, we show the second part of Lemma (ref). When $\lim_{T \to \infty}m_{T}^d/(NT) = \lambda^d$ for all $d \in \{1, \ldots, k\}$, we have that for each $d \in \{1, \ldots, k\}$, \begin{align*} & \lim_{T \to \infty} \inf_{y \in I_d}\Bigg[ \frac{\alpha_0^d + \beta_0^d -1 + m_{T-1}^d}{TN} d_{\mathrm{KL}}\left( \frac{\alpha_0^d -1 + r_{T-1}^d}{\alpha_0^d + \beta_0^d -1 + m_{T-1}^d},y\right)\\ &\ \ \ + \frac{\alpha_0^{d^{(1)}} + \beta_0^{d^{(1)}} -1 + m_{T-1}^{d^{(1)}}}{TN}d_{\mathrm{KL}}\left(\frac{\alpha_0^{d^{(1)}} -1 + r_{T-1}^{d^{(1)}}}{\alpha_0^{d^{(1)}} + \beta_0^{d^{(1)}} -1 + m_{T-1}^{d^{(1)}}},y\right)\Bigg] \\ & = \inf_{y \in \left[\theta^d, \theta^{d^{(1)}}\right]} \left[\lambda^d d_{\mathrm{KL}}(\theta^d,y) + \frac{1}{2} d_{\mathrm{KL}}(\theta^{d^{(1)}},y)\right] \\ & = \Lambda^*. \end{align*} Therefore, \begin{align*} 1 - p_{T}^{d^{(1)}} & \doteq \exp\left( -T N\max_{\bm w} \min_{d \neq d^{(1)}} \inf_{y \in I_{d, \varepsilon}^*}\left[ w_d d_{\mathrm{KL}}( \theta^d,y) + \frac{1}{2}d_{\mathrm{KL}}(\theta^{d^{(1)}},y)\right] \right) \\ & \doteq \exp(- TN \Lambda^*). \end{align*} Hence, we get \begin{align*} \lim_{T \to \infty} - \frac{1}{TN} \log \left( \sum_{d \neq d^{(1)}} p^d_T\right) = \Lambda^*. \end{align*} This concludes the proof. \end{proof} \section{Proof of Lemma (ref)} The proof is analogous to the proof of Lemma 28 in Shang2020. We extend the result from Beta-Bernoulli bandit model with the $\mathrm{Beta}(1, 1)$ prior to that with the $\mathrm{Beta}(\alpha_0^d,\beta_0^d)$ priors for each $d \in \{1, \ldots, k\}$, where the constants $\alpha_0^1, \ldots, \alpha_0^k, \beta_0^1, \ldots ,\beta_0^k>0$ can be arbitrary. \begin{proof} When $\overline{D}$ is empty, then $\mathrm{SW}_T(d) \xrightarrow{\mathrm{a.s.}} \theta^{d}$. The posterior variance $\sigma_{T, d}^2$ is \begin{align} \sigma_{T, d}^2 & = \frac{\alpha_T^d\beta_T^d}{\left(\alpha_T^d + \beta_T^d\right)^2\left(\alpha_T^d + \beta_T^d+1\right)} = \frac{\left(\alpha_0^d + r_{T-1}^d\right)\left(\beta_0^d + m_{T-1}^d- r_{T-1}^d\right)}{\left(\alpha_0^d + \beta_0^d + m_{T-1}^d\right)^2\left(\alpha_0^d + \beta_0^d + m_{T-1}^d + 1\right)}. \end{align} Therefore, under the event of $\overline{D} = \emptyset$, $\sigma_{T, d}^2 \xrightarrow{\mathrm{a.s.}} 0$ (posterior concentration). When $\overline{D}$ is not empty, then from (ref), we have that $\liminf_{T \to \infty}\sigma_{T, d}^2 >0$. Hence $\liminf_{T \to \infty}p_t^d > 0$. This concludes the proof. \end{proof}