Proof of Theorem 1. By the definition of the lower \(\alpha\)-quantile, \(\mathbb{P}(R_T<r_{T,\alpha}) \le \alpha \le \mathbb{P}(R_T\le r_{T,\alpha}).\) The boundary randomization in 9 is chosen so that \(\mathbb{P}(\hat{a}_T=?) = \mathbb{P}(R_T<r_{T,\alpha}) + \theta_{T,\alpha}\mathbb{P}(R_T=r_{T,\alpha}) = \alpha.\) Thus \(\mathcal{A}_T({\textrm{\mathrm{\small PGWS}}}(\alpha))=\alpha\).

For the error probability, Lemma 1 gives \(\mathcal{E}_T({\textrm{\mathrm{\small PGWS}}}(\alpha)) \le (K-1)e^{-r_{T,\alpha}}.\) By Lemma 2, for every \(\varepsilon\in(0,1)\), all sufficiently small \(\alpha\), and all sufficiently large \(T\), \(r_{T,\alpha} \ge (1-\varepsilon) \frac{1}{8\kappa_\nu^2}\alpha^2T.\) Therefore \[\mathcal{E}_T({\textrm{\mathrm{\small PGWS}}}(\alpha)) \le (K-1) \exp \left\{ -(1-\varepsilon) \frac{1}{8\kappa_\nu^2}\alpha^2T \right\}.\] This then yields the final result in ?? . ◻

Proof. For each arm \(i \in [K]\), the event that arm \(i\) is the best and the top-two gap is at most \(\varepsilon\) is \(\left\{ \mu_i=\mu_{(1)},\; \mu_{(1)}-\mu_{(2)}\le \varepsilon \right\}.\) Conditional on \(\{\mu_i=x\}\), this event says that the means of all the other arms are at most \(x\) and at least one other arm is in \([x-\varepsilon,x]\). Hence \[\begin{align} \mathbb{P}(\Gamma\le \varepsilon) &= \sum_{i=1}^K \mathbb{P}(\mu_i=\mu_{(1)},\; \mu_{(1)}-\mu_{(2)}\le \varepsilon) =\sum_{i=1}^K \int_{\mathbb{R}} f_i(x) \left[ \prod_{k\neq i}F_k(x) - \prod_{k\neq i}F_k(x-\varepsilon) \right]\mathrm{d}x \end{align}\] Let \(G_i(x):=\prod_{k\neq i}F_k(x)\), then \(G_i'(x) = \sum_{j\neq i} \big( f_j(x)\prod_{k\neq i,j}F_k(x) \big)\). By the fundamental theorem of calculus, \(G_i(x)-G_i(x-\varepsilon) = \int_{x-\varepsilon}^x G_i'(u)\,\mathrm{d}u.\) Additionally, by the dominated convergence theorem, as \(\varepsilon \to 0\), \[\begin{align} \frac{\mathbb{P}(\Gamma\le \varepsilon)}{\varepsilon} &= \sum_{i=1}^K \int_{\mathbb{R}} f_i(x) \left[ \frac{G_i(x) - G_i(x-\varepsilon)}{\varepsilon} \right] \, \mathrm{d}x\to \sum^K_{i=1} \sum_{j\neq i} \int_{\mathbb{R}} f_i(x)f_j(x)\prod_{k\neq i,j}F_k(x)\,\mathrm{d}x. \end{align}\] It remains to simplify the product of the Gaussian densities. For \(i<j\), \[\begin{align} f_i(x)f_j(x) &= \frac{1}{2\pi\sigma_0^2} \exp\!\left( -\frac{(x-\nu_i)^2 + (x-\nu_j)^2}{2\sigma_0^2} \right) = \frac{1}{2\sqrt\pi\,\sigma_0} \exp\left( -\frac{(\nu_i-\nu_j)^2}{4\sigma_0^2} \right) g_{ij}(x), \end{align}\] where \(g_{ij}\) is the density of \(\mathcal{N}\!\left( \frac{\nu_i+\nu_j}{2}, \frac{\sigma_0^2}{2} \right)\). Therefore \[\begin{align} 2\int_{\mathbb{R}} f_i(x)f_j(x)\prod_{k\neq i,j}F_k(x)\,\mathrm{d}x &= \frac{1}{\sigma_0\sqrt\pi} \exp\!\left( -\frac{(\nu_i-\nu_j)^2}{4\sigma_0^2} \right) \int_{\mathbb{R}} g_{ij}(x)\prod_{k\neq i,j}F_k(x)\,\mathrm{d}x \\ &= \frac{1}{\sigma_0\sqrt\pi} \exp\!\left( -\frac{(\nu_i-\nu_j)^2}{4\sigma_0^2} \right) w_{ij}. \end{align}\] Summing over \(i<j\) proves the claim. ◻

Proof of Lemma 1. If the algorithm recommends \(\widehat b_T\), then conditional on \(\mathcal{F}_T\), \[\mathbb{P}(a^\star\neq \widehat b_T\mid \mathcal{F}_T) \le \sum_{j\neq \widehat b_T} \mathbb{P}(\mu_j\ge \mu_{\widehat b_T}\mid \mathcal{F}_T).\]

As usual, let \(\mu=(\mu_1,\dots,\mu_K)\). By the independent Gaussian prior and the arm-wise reward model, the posterior factorizes across arms even under adaptive sampling: \[p(\mu\mid\mathcal{F}_T) \propto \prod_{i=1}^K \left[ p(\mu_i) \prod_{s=1}^{N_i(T)} p(Y_{i,s}\mid \mu_i) \right].\] Consequently, the law of the means is \[\mathcal{L}(\mu_1,\dots,\mu_K\mid\mathcal{F}_T) = \bigotimes_{i=1}^K \mathcal{N}(M_i(T),V_i(T)),\] thus the arm means \(\mu_1,\dots,\mu_K\) are mutually independent conditional on \(\mathcal{F}_T\).

Furthermore, \(M_i(T)\) and \(V_i(T)\) are \(\mathcal{F}_T\)-measurable, and therefore \(\widehat b_T=\arg\max_i M_i(T)\) is also \(\mathcal{F}_T\)-measurable. Hence, conditional on \(\mathcal{F}_T\), the random index \(\widehat b_T\) is fixed. Thus, for each \(j\neq \widehat b_T\), \[\mu_{\widehat b_T}-\mu_j\mid\mathcal{F}_T \sim \mathcal{N}\!\left( M_{\widehat b_T}(T)-M_j(T), V_{\widehat b_T}(T)+V_j(T) \right).\] Therefore, using \(\Phi(-x)\le e^{-x^2/2}\) for \(x\ge0\), \[\mathbb{P}(\mu_j\ge\mu_{\widehat b_T}\mid\mathcal{F}_T) = \Phi\left( -\frac{M_{\widehat b_T}(T)-M_j(T)}{\sqrt{V_{\widehat b_T}(T)+V_j(T)}} \right) \le \exp\left( -\frac{ \bigl(M_{\widehat b_T}(T)-M_j(T)\bigr)^2 }{ 2\bigl(V_{\widehat b_T}(T)+V_j(T)\bigr) } \right).\] By definition of \(R_T\), on the event that the algorithm does not abstain we have \(R_T\ge r_{T,\alpha}\). Hence, on this event, \(\mathbb{P}(a^\star\neq \widehat b_T\mid\mathcal{F}_T) \le (K-1)e^{-R_T} \le (K-1)e^{-r_{T,\alpha}}.\)

Taking expectation gives \[\mathcal{E}_T = \mathbb{E}\!\left[ \mathbb{1}\{\hat{a}_T\neq ?\} \mathbb{P}(a^\star\neq \widehat b_T\mid\mathcal{F}_T) \right] \le (K-1)e^{-r_{T,\alpha}}.\] ◻

Proof. By definition, the normalized sampling proportions are: \[p_{b^\star}^\dagger=\frac{1}{W^\dagger(\mu)}, \quadand\quad p_j^\dagger = \frac{\Gamma^2/\Delta_j^2}{W^\dagger(\mu)}.\] We substitute these proportions into the pairwise error exponent for a specific challenger \(j\): \[\frac{ \Delta_j^2 }{ 2\left( 1/p_{b^\star}^\dagger+1/p_j^\dagger \right) } = \frac{ \Delta_j^2 }{ 2W^\dagger(\mu)\left(1+\Delta_j^2/\Gamma^2\right) }.\] To isolate the effect of the gap, we factor out \(\frac{\Gamma^2}{2W^\dagger(\mu)}\) and express the remainder as a function of the relative gap \(r_j := \Delta_j/\Gamma\): \[\frac{ \Delta_j^2 }{ 2\left( 1/p_{b^\star}^\dagger+1/p_j^\dagger \right) } = \frac{\Gamma^2}{2W^\dagger(\mu)} \left[ \frac{(\Delta_j/\Gamma)^2}{1+(\Delta_j/\Gamma)^2} \right] = \frac{\Gamma^2}{2W^\dagger(\mu)} \left( \frac{r_j^2}{1+r_j^2} \right).\]

Now, recall the limiting exponent \(C^\dagger(\mu)\) is defined as the minimum of this expression over all challengers \(j \neq b^\star\). Observe that the function \(f(r) = \frac{r^2}{1+r^2}\) is increasing on \([1,\infty)\). Since \(\Delta_j/\Gamma\ge1\) for all \(j\neq b^\star\), the minimum is attained by a second-best arm, for which \(\Delta_j=\Gamma\): \[C^\dagger(\mu) = \frac{\Gamma^2}{2W^\dagger(\mu)} \left( \frac{1^2}{1+1^2} \right) = \frac{\Gamma^2}{4W^\dagger(\mu)}.\] Also, because \(w_{b^\star}^\dagger=1\), the second-best arm has weight \(1\), and all other weights are at most \(1\), we have \(2\le W^\dagger(\mu)\le K\). Substituting back gives \[\frac{\Gamma^2}{4K} \le C^\dagger(\mu) \le \frac{\Gamma^2}{8}.\] ◻

Proof. First, recall that the algorithm’s forced-exploration samples arm \(i\) whenever \(N_i(t) < \sqrt{t+1}\), this guarantees that as \(t \to \infty\), \(N_i(t)\to\infty\) for every \(i\).

Second, conditional on a specific realization of the true mean \(\mu_i\), the reward sequence \((Y_{i,s})_{s\ge1}\) consists of mutually independent draws from \(\mathcal{N}(\mu_i,1)\). Therefore, by the Strong Law of Large Numbers, the conditional probability of the empirical average converging to \(\mu_i\) is \(1\). Integrating this over the prior of \(\mu_i\), we have \[\frac{1}{N_i(t)} \sum_{s=1}^{N_i(t)}Y_{i,s} \to \mu_i \qquad\text{almost surely}.\]

Finally, recall our algorithm’s update for the posterior mean: \[M_i(t) = \frac{ \sigma_0^{-2}\nu_i+\sum_{s=1}^{N_i(t)}Y_{i,s} }{ \sigma_0^{-2}+N_i(t) }.\] Combining the previous two displayed equations yields ?? . ◻

Proof. Fix an arm \(i\). We proceed in four steps:

Step 1: Forced exploration is negligible. Let \(F_i(T)\) be the number of forced-exploration pulls of arm \(i\) up to time \(T\). If the \(m\)-th forced pull of arm \(i\) occurs before time \(T\), then immediately before that pull, \(N_i(t)\ge m-1\). But a forced pull of arm \(i\) can occur only if \(N_i(t)<\sqrt{t+1}\le \sqrt{T+1}\). Hence \(m-1<\sqrt{T+1}\), and therefore \(F_i(T)\le \lceil \sqrt{T+1}\rceil+1\). Consequently, \[\frac{F_i(T)}{T}\to0.\] Let \(F(T)\) be the total number of forced-exploration rounds up to time \(T\). Since \(F(T)=\sum_{\ell=1}^K F_\ell(T)\), we also have \[\frac{F(T)}{T}\le \frac{K(\lceil\sqrt{T+1}\rceil+1)}{T} \to0.\]

Step 2: Martingale concentration on non-forced rounds. Let \(\mathcal{F}_t\) be the history before round \(t+1\), and define \(B_t := \mathbb{1}\{\text{round }t+1\text{ is non-forced}\}\). The event \(\{B_t=1\}\) is \(\mathcal{F}_t\)-measurable. On non-forced rounds, the algorithm samples arm \(i\) with conditional probability \(p_i(t)\).

Define \(D_{i,t+1} := B_t\bigl(\mathbb{1}\{A_{t+1}=i\}-p_i(t)\bigr)\). Then \(\mathbb{E}[D_{i,t+1}\mid \mathcal{F}_t]=0\), so \((D_{i,t+1})_{t\ge0}\) is a martingale difference sequence. Also, \(|D_{i,t+1}|\le1\).

Therefore, by Azuma’s inequality, for every \(\varepsilon>0\), \[\mathbb{P}\left( \bigg| \frac{1}{T}\sum_{t=0}^{T-1}D_{i,t+1} \bigg| \ge \varepsilon \right) \le 2\exp\left(-\frac{\varepsilon^2T}{2}\right).\] The right-hand side is summable in \(T\). Hence, by the Borel–Cantelli lemma, \[\frac{1}{T}\sum_{t=0}^{T-1}D_{i,t+1}\to0 \qquad\text{almost surely}.\]

Step 3: Decomposition of the empirical pull count. The total number of pulls of arm \(i\) can be decomposed as \[N_i(T) = F_i(T) + \sum_{t=0}^{T-1} B_t\mathbb{1}\{A_{t+1}=i\}.\] Using the definition of \(D_{i,t+1}\), we have \(B_t\mathbb{1}\{A_{t+1}=i\} = D_{i,t+1}+B_t p_i(t)\). Thus \[\frac{N_i(T)}{T} = \frac{F_i(T)}{T} + \frac{1}{T}\sum_{t=0}^{T-1}D_{i,t+1} + \frac{1}{T}\sum_{t=0}^{T-1}B_t p_i(t).\] By Steps 1 and 2, \[\frac{N_i(T)}{T} - \frac{1}{T}\sum_{t=0}^{T-1}B_t p_i(t) \to0 \qquad\text{almost surely}.\]

Step 4: Cesàro convergence of the target probabilities. By Lemma 5, \(M(t)\to \mu\) almost surely. Since the prior is continuous, the true best arm and true second-best arm are unique almost surely. On this probability-one event, the map \(m\mapsto p(m)\) is continuous at \(m=\mu\). Therefore, as \(t \to \infty\), \[p_i(t)\to p_i^\dagger(\mu) \qquad\text{almost surely}.\] Hence, the sequence \(\{p_i(t)\}\) is also Cesàro convergent, i.e., \[\frac{1}{T}\sum_{t=0}^{T-1}p_i(t) \to p_i^\dagger(\mu) \qquad\text{almost surely}.\]

Now write \[\frac{1}{T}\sum_{t=0}^{T-1}B_t p_i(t) = \frac{1}{T}\sum_{t=0}^{T-1}p_i(t) - \frac{1}{T}\sum_{t=0}^{T-1}(1-B_t)p_i(t).\] Since \(0\le p_i(t)\le1\), \[0\le \frac{1}{T}\sum_{t=0}^{T-1}(1-B_t)p_i(t) \le \frac{1}{T}\sum_{t=0}^{T-1}(1-B_t) = \frac{F(T)}{T} \to0.\] Hence \[\frac{1}{T}\sum_{t=0}^{T-1}B_t p_i(t) \to p_i^\dagger(\mu) \qquad\text{almost surely}.\] Combining this with Step 3 gives ?? . ◻

Proof. By Lemma 5, \(M_i(T)\to \mu_i\) for every \(i\). Since the true best arm is unique almost surely, \(\widehat b_T=b^\star\) for \(T\) large enough. So for every \(j\neq b^\star\), \(M_{b^\star}(T)-M_j(T)\to \Delta_j\).

Recall \(V_i(T)=\frac{1}{\sigma_0^{-2}+N_i(T)}\). Furthermore, by Lemma 6, \(\frac{N_i(T)}{T}\to p_i^\dagger(\mu)\).

Hence \[T\;V_i(T) = \frac{T}{\sigma_0^{-2}+N_i(T)} \to \frac{1}{p_i^\dagger(\mu)}.\] Therefore, for every \(j\neq b^\star\), \[\frac{1}{T} \frac{ \bigl(M_{b^\star}(T)-M_j(T)\bigr)^2 }{ 2\bigl(V_{b^\star}(T)+V_j(T)\bigr) } \to \frac{ \Delta_j^2 }{ 2\left( 1/p_{b^\star}^\dagger(\mu)+1/p_j^\dagger(\mu) \right) }.\] Taking the minimum over \(j\neq b^\star\) proves ?? as desired. ◻

Proof. For \(K=2\) the statement is trivial. Assume \(K\ge3\). If \(\Gamma_3\le \varepsilon\), then there exist three distinct arms \(i,j,k\) such that all three means lie within an interval of length \(\varepsilon\) around the largest of the three. By a union bound over ordered triples, \[\mathbb{P}(\Gamma_3\le \varepsilon) \le \sum_{i\neq j\neq k} \int_{\mathbb{R}} f_i(x) \left[ \int_{x-\varepsilon}^x f_j(y)\,\mathrm{d}y \right] \left[ \int_{x-\varepsilon}^x f_k(z)\,\mathrm{d}z \right]\mathrm{d}x.\] Gaussian densities are bounded uniformly by \((\sigma_0\sqrt{2\pi})^{-1}\), so each inner integral is \(O(\varepsilon)\) uniformly in \(x\). Since \(\int f_i(x)\,\mathrm{d}x=1\), the whole expression is \(O(\varepsilon^2)\). ◻

Proof. By Lemma 4, \(C^\dagger(\mu) = \frac{\Gamma^2}{4W^\dagger(\mu)} \le \frac{\Gamma^2}{8}\). Therefore \(\{\Gamma\le \sqrt{8x}\} \subseteq \{C^\dagger(\mu)\le x\}\).

Using Lemma 3, \[\mathbb{P}(C^\dagger(\mu)\le x) \ge \mathbb{P}(\Gamma\le \sqrt{8x}) = \kappa_\nu\sqrt{8x}+o(\sqrt x).\]

On the other hand, to derive an upper bound, set \(\delta_x:=x^{3/8}\). On the event \(\{C^\dagger(\mu)\le x\}\), Lemma 4 yields \(\Gamma^2\le 4Kx\), because \(W^\dagger(\mu)\le K\). On the additional event \(\{\Gamma_3>\delta_x\}\), every arm other than the top two has gap at least \(\delta_x\) from the best arm. Hence, for every such arm \(k\), \[\left(\frac{\Gamma}{\Delta_k}\right)^2 \le \frac{4Kx}{\delta_x^2} = 4Kx^{1/4} =o(1)\quad \text{ as } x \downarrow 0.\] Thus, on \(\{C^\dagger(\mu)\le x,\;\Gamma_3>\delta_x\}\), we have \[W^\dagger(\mu) =\sum_{\ell=1}^K w_\ell^\dagger(\mu) = 1+\sum_{j\neq b^\star} \left( \frac{\Gamma}{\Delta_j} \right)^2= 2+o(1),\] uniformly as \(x\downarrow0\). Therefore, for every fixed \(\eta>0\) and all sufficiently small \(x\), \[C^\dagger(\mu)\le x,\;\Gamma_3>\delta_x \quad\Longrightarrow\quad \Gamma = 2 \sqrt{C^\dagger(\mu) W^\dagger(\mu)} \le (1+\eta)\sqrt{8x}.\] Consequently, \[\mathbb{P}(C^\dagger(\mu)\le x) \le \mathbb{P}\bigl(\Gamma\le(1+\eta)\sqrt{8x}\bigr) + \mathbb{P}(\Gamma_3\le\delta_x).\] By Lemma 3, \[\mathbb{P}\bigl(\Gamma\le(1+\eta)\sqrt{8x}\bigr) = (1+\eta)\kappa_\nu\sqrt{8x}+o(\sqrt x).\] By Lemma 8, \[\mathbb{P}(\Gamma_3\le\delta_x) = O(\delta_x^2) = O(x^{3/4}) = o(\sqrt x).\] Thus \[\limsup_{x\downarrow0} \frac{\mathbb{P}(C^\dagger(\mu)\le x)}{\sqrt x} \le (1+\eta)\kappa_\nu\sqrt8.\] Letting \(\eta\downarrow0\) gives the matching upper bound, and hence we obtain ?? . ◻

Proof of Lemma 2. Fix \(\varepsilon\in(0,1)\) and set \(x_{\alpha,\varepsilon} := (1-\varepsilon) \frac{1}{8\kappa_\nu^2} \alpha^2\). By Lemma 9, \[\mathbb{P}(C^\dagger(\mu)\le x_{\alpha,\varepsilon}) = \kappa_\nu \sqrt{8(1-\varepsilon) \frac{1}{8\kappa_\nu^2} }\,\alpha + o(\alpha) = \sqrt{1-\varepsilon}\,\alpha + o(\alpha).\] Hence, for sufficiently small \(\alpha\), \(\mathbb{P}(C^\dagger(\mu)\le x_{\alpha,\varepsilon}) < \alpha\).

Additionally, by Lemma 7, \(\frac{R_T}{T}\to C^\dagger(\mu)\) almost surely. Therefore we also have convergence in distribution. By the Portmanteau theorem applied to the closed set \((-\infty,x_{\alpha,\varepsilon}]\), \[\limsup_{T\to\infty} \mathbb{P}\left(\frac{R_T}{T}\le x_{\alpha,\varepsilon}\right) \le \mathbb{P}(C^\dagger(\mu)\le x_{\alpha,\varepsilon}) < \alpha.\] Hence for all sufficiently large \(T\), \[\mathbb{P}(R_T\le x_{\alpha,\varepsilon}T)<\alpha.\] By the definition of \(r_{T,\alpha}\) as the lower \(\alpha\)-quantile of \(R_T\), this implies \[r_{T,\alpha} \ge x_{\alpha,\varepsilon}T = (1-\varepsilon) \frac{1}{8\kappa_\nu^2} \alpha^2T.\] ◻

Proof. For each \((i,j)\), because \(\mathcal{C}_{ij}(\ell, M)\) is compact, the Gaussian densities defined on \(\mathcal{C}_{ij}(\ell, M)\) are (strictly) positive and uniformly continuous. Because \(\ell > 0\) separates the top pair of arms \(i,j\) from the other arms \(k \ne i,j\), we can choose a sufficiently small \(\delta_\rho < 2\ell\) such that the continuity of \(f_i\) and \(f_j\) guarantees the multiplicative bound over the interval \([0,\delta_\rho]\). Since there are finitely many pairs, taking minimum of the pair-specific values of \(\delta_\rho\) yields the desired result. ◻

Proof. For each \(i<j\), let \(\mathcal{S}_{ij} := \left\{ \mu(\xi,\delta,h): \xi\in\mathcal{C}_{ij}(\ell,M),\; \delta\in[0,\delta_\rho],\; h\in\{+1,-1\} \right\},\) and let \(\mathcal{S}:=\bigcup_{i<j}\mathcal{S}_{ij}\). For any Borel set \(E\subseteq\mathbb{R}^K\), substituting the definition of \(\Lambda_\rho\) in 13 into 14 gives \[Q_\rho(E) = \sum_{i<j}\sum_{h\in\{+1,-1\}} \int_{\mathcal{C}_{ij}(\ell,M)} \int_0^{\delta_\rho} \mathbb{1}_E\!\bigl(\mu(\xi,\delta,h)\bigr) (1-\rho)f_i(x)f_j(x) \prod_{k\neq i,j}f_k(\zeta_k) \,\mathrm{d}\delta\,\mathrm{d}x\,\mathrm{d}\zeta_{-ij}.\] For each fixed \(i<j\) and \(h\), the Jacobian determinant of the coordinate transformation in ?? has absolute value \(1\). Moreover, except on the null set \(\{\delta=0\}\), the sign \(h\) is uniquely determined by \(\mu_i-\mu_j\), and the top-two pair \(\{i,j\}\) is uniquely determined on \(\mathcal{S}\). Hence \(Q_\rho\) has Lebesgue density \[q_\rho\bigl(\mu(\xi,\delta,h)\bigr) = (1-\rho)f_i(x)f_j(x) \prod_{k\neq i,j}f_k(\zeta_k)\] for Lebesgue-almost every \(\mu(\xi,\delta,h)\in\mathcal{S}_{ij}\). Per the definition in 14 , \(Q_\rho\) is supported on \(\mathcal{S}\), hence we also have \(q_\rho(\mu)=0\) for Lebesgue-almost every \(\mu\notin\mathcal{S}\).

For \(\mu=\mu(\xi,\delta,h)\in\mathcal{S}_{ij}\), the true prior density is \[p_\nu(\mu) = f_i\left(x+h\frac{\delta}{2}\right) f_j\left(x-h\frac{\delta}{2}\right) \prod_{k\neq i,j}f_k(\zeta_k).\] Lemma 10 therefore gives \(q_\rho(\mu)\le p_\nu(\mu)\) for Lebesgue-almost every \(\mu\in\mathcal{S}\). The same inequality holds outside \(\mathcal{S}\) because \(q_\rho=0\) there. Consequently, for every Borel set \(E\subseteq\mathbb{R}^K\), \[Q_\rho(E) = \int_E q_\rho(\mu)\,\mathrm{d}\mu \le \int_E p_\nu(\mu)\,\mathrm{d}\mu = P_\nu(E).\] Hence \(Q_\rho\le P_\nu\). ◻

Proof. By the definition of \(Q_\rho\), the measure on the product space \(\mathcal{C}_\rho \times [0, \delta_\rho] \times \{+1, -1\}\) factors as \(\Lambda_\rho(\mathrm{d}\xi) \otimes \mathrm{d}\delta \otimes \mathbb{1}_{\{h\}}\). Because this is a product measure that does not depend on \(h\), the sign \(H\) occurs with equal probability \(1/2\) regardless of \(\Xi\) or \(\Delta\). Furthermore, integrating out \(\Xi\) and \(H\) leaves the measure of the gap \(\Delta\) as \(2\Lambda_\rho(\mathcal{C}_\rho)\, \mathrm{d}\delta = c_\rho \,\mathrm{d}\delta\), proving the flat gap property. ◻

Proof. This follows directly from Lemma 11. ◻

Proof. Fix \(\xi = (i, j, x, \zeta_{-ij})\). We construct a modified strategy \(\pi'\) from \(\pi\) that possesses the desired properties in ?? .

When \(\pi\) samples from an arm \(k \in \{i, j\}\), \(\pi'\) queries that same arm and feeds the observed reward back to \(\pi\). Whenever \(\pi\) chooses to sample from an arm \(k \notin \{i,j\}\), \(\pi'\) instead queries arm \(i\), discards the true reward, and feeds \(\pi\) an independent simulated reward drawn from \(\mathcal{N}(\zeta_k, 1)\).

Because \(\Xi = \xi\) is known, \(\zeta_k\) is the true mean of arm \(k\). Furthermore, for \(k\ne i,j\), the reward distributions of arm \(k\) are independent of the unknown signed gap \(\Theta\). Therefore, the simulated reward from \(\pi'\) matches that from the true distribution of arm \(k\). By induction, the internal history observed by \(\pi\) under \(\pi'\) is identically distributed to the true history in the original experiment. Consequently, the terminal distribution of \(\pi\) is preserved for every \(\theta\).

When \(\pi\) stops and outputs a recommendation \(\hat{a}_T\), \(\pi'\) maps this to a sign decision \(\hat{a}'_T \in \{+,-,?\}\) as follows: \(i \mapsto +\), \(j \mapsto -\), \(? \mapsto ?\), and any \(k \notin \{i, j, ?\}\) is mapped arbitrarily to \(+\). This map preserves the abstention probability. For the undetected error, recall that on the support of \(Q_\rho\), arms \(i\) and \(j\) are strictly the top two arms. Thus, any original output \(k \notin \{i, j, ?\}\) is an error. If \(h = -\), mapping \(k\) to \(+\) yields \(\hat{a}'_T = +\), which is an incorrect sign, thereby preserving the error probability. If \(h = +\), mapping \(k\) to \(+\) converts an original error into a correct guess, reducing the error probability. Thus, across all cases, the probability of an incorrect sign under \(\pi'\) is less than or equal to the probability of an undetected error under \(\pi\), showing ?? . ◻

Proof. If \(A_t=i\), the true observation follows \(X_t \mid \mathcal{H}_{t-1}^{\xi},A_t=i,\Theta=\theta,\Xi=\xi \sim \mathcal{N}\!\left(x+\frac{\theta}{2},1\right).\) Applying the transformation \(Z_t=X_t-x\) yields ?? . While if \(A_t=j\), the true observation follows \(X_t \mid \mathcal{H}_{t-1}^{\xi},A_t=j,\Theta=\theta,\Xi=\xi \sim \mathcal{N}\!\left(x-\frac{\theta}{2},1\right)\). Similarly, applying the transformation yields ?? . Thus, the conditional law of \(Z_t\) is \(\mathcal{N}(\theta/2,1)\) regardless of which of the two arms is chosen.

Next we prove independence. Let \(\gamma_\theta\) denote the measure corresponding to \(\mathcal{N}(\theta/2,1)\). For any Borel set \(B\), we have: \[\mathbb{P}_\theta^{\xi}(Z_t\in B\mid \mathcal{H}_{t-1}^{\xi},A_t)=\gamma_\theta(B).\] Iterating this identity using the tower property shows that for any sequence of Borel sets \(B_1,\dots,B_T\): \[\mathbb{P}_\theta^{\xi}(Z_1\in B_1,\dots,Z_T\in B_T)=\prod_{t=1}^T\gamma_\theta(B_t).\] Hence, given \(\xi\) and \(\theta\), \(Z_1,\dots,Z_T\) are i.i.d.over the transformed history. ◻

Proof. Let \(h_T=(\xi,a_1,z_1,\dots,a_T,z_T)\) be the realized transformed oracle history, and let \(\phi\) be the standard normal density as usual. Under \(\mathbb{P}_\theta^{\xi}\), the density of \(h_T\) factors as: \[p_\theta^{\xi}(h_T)=\left[\prod_{t=1}^T\pi_t(a_t\mid \xi,a_1,z_1,\dots,a_{t-1},z_{t-1})\right]\prod_{t=1}^T\phi\!\left(z_t-\frac{\theta}{2}\right),\] where \(\pi_t\) is the strategy’s sampling kernel at time \(t\). Because the action probabilities are identical functions of the realized history under both \(\mathbb{P}_\theta^{\xi}\) and \(\mathbb{P}_0^{\xi}\), they cancel in the likelihood ratio, i.e., \[\frac{p_\theta^{\xi}(h_T)}{p_0^{\xi}(h_T)}=\prod_{t=1}^T\frac{\phi(z_t-\theta/2)}{\phi(z_t)}=\prod_{t=1}^T\exp\!\left(\frac{\theta}{2}z_t-\frac{\theta^2}{8}\right).\] Aggregating the sum inside the exponential yields: \[\frac{p_\theta^{\xi}(h_T)}{p_0^{\xi}(h_T)}=\exp\!\left(\frac{\theta}{2}\sum_{t=1}^T z_t-\frac{T\theta^2}{8}\right)=\exp\!\left(\frac{\theta}{2}W-\frac{T\theta^2}{8}\right).\] ◻

Proof. By Lemma 16, the likelihood ratio \(\mathrm{d}\mathbb{P}_\theta^{\xi}/\mathrm{d}\mathbb{P}_0^{\xi}\) is \(\sigma(W)\)-measurable. Since \(\sigma(V)=\sigma(W)\), it is also \(\sigma(V)\)-measurable.

Let \(\tilde{\psi}_d^\xi(h_T)\) denote the probability that the original terminal rule outputs decision \(d\in\{+,-,?\}\) after observing transformed history \(h_T\). Let \(\mathbb{Q}^{\xi}(v,\mathrm{d}h_T)\) be a regular conditional distribution of \(\mathcal{H}_T^{\xi}\) given \(V=v\) under \(\mathbb{P}_0^{\xi}\). i.e., \(\mathbb{Q}^{\xi}(V,B)\) is a version of \(\mathbb{P}_0^{\xi}\left( \mathcal{H}_T^{\xi} \in B \mid V \right)\).

By Lemma 16, \(\mathbb{P}^\xi_{\theta}(V \in dv) =\exp\!\left(\frac{\theta\sqrt{T}}{2}v-\frac{T\theta^2}{8}\right) \mathbb{P}^\xi_{0}(V \in dv)\). Therefore, for every measurable set \(B\) and \(C \in \mathcal{B}(\mathbb{R})\), \[\begin{align} \mathbb{P}_\theta^{\xi}\left(\mathcal{H}_T^{\xi} \in B , V \in C \right) &= \mathbb{E}^\xi_0 \left[ \exp\!\left(\frac{\theta\sqrt{T}}{2}V-\frac{T\theta^2}{8}\right) \mathbb{1}_{\{\mathcal{H}_T^{\xi} \in B\}} \mathbb{1}_{\{V \in C\}} \right] \\ &= \int_C \exp\!\left(\frac{\theta\sqrt{T}}{2}v-\frac{T\theta^2}{8}\right) Q^\xi(v,B) \mathbb{P}^\xi_{0}(V \in \mathrm{d}v) \\ &= \int_C Q^\xi(v,B) \mathbb{P}^\xi_{\theta}(V \in \mathrm{d}v). \end{align}\] This implies that the kernel \(\mathbb{Q}^{\xi}(v,\mathrm{d}h_T)\) is a conditional law under \(\mathbb{P}_\theta^{\xi}\). Hence, for every bounded measurable \(f\), \[\label{RCD95Q95xi} \mathbb{E}^\xi_\theta \big[ f(\mathcal{H}^\xi_T) \mid V \big] = \int f(h_T) Q^\xi(V,\mathrm{d}h_T) \quad \mathbb{P}^\xi_\theta\text{-a.s.,}\tag{15}\]

Define the terminal rule \(\psi^\xi = (\psi_+^\xi, \psi_-^\xi, \psi_?^\xi)\) via the kernel \(\mathbb{Q}^{\xi}(v,\mathrm{d}h_T)\) as follows: \[\psi_d^\xi(v) := \int \tilde{\psi}_d^\xi(h_T)\,\mathbb{Q}^{\xi}(v,\mathrm{d}h_T), \qquad d\in\{+,-,?\}.\] By definition, \(\psi_{(\cdot)}^\xi(v)\) is a probability distribution on \(\{+,-,?\}\). For every signed-gap realization \(\theta\) and every decision \(d \in\{+,-,?\}\), taking \(f=\tilde{\psi}_d^\xi\) in 15 , the tower property guarantees: \[\mathbb{P}_\theta^{\xi}(\hat{a}^V=d) = \mathbb{E}_\theta^{\xi}[\psi_d^\xi(V)] = \mathbb{E}_\theta^{\xi}\big[\mathbb{E}_\theta^{\xi}[\tilde{\psi}_d^\xi(\mathcal{H}_T^{\xi})\mid V]\big] = \mathbb{E}_\theta^{\xi}[\tilde{\psi}_d^\xi(\mathcal{H}_T^{\xi})] = \mathbb{P}_\theta^{\xi}(\hat{a}=d).\] Thus, the \(V\)-based rule preserves all probabilities under every realization of the signed-gap \(\theta\). ◻

Proof. Fix \((\xi,v)\). Since \(\psi_+^{\xi}(v)+\psi_-^{\xi}(v)=1-\psi_?^{\xi}(v)\), and both \(\psi_+^{\xi}(v)\) and \(\psi_-^{\xi}(v)\) are non-negative, \[\psi_-^{\xi}(v)A_T(v)+\psi_+^{\xi}(v)B_T(v) \ge \bigl(\psi_-^{\xi}(v)+\psi_+^{\xi}(v)\bigr)\min\{A_T(v),B_T(v)\} = \bigl(1-\psi_?^{\xi}(v)\bigr)\min\{A_T(v),B_T(v)\}.\] Integrating over \(v\) and \(\xi\) proves the claim. ◻

Proof. First, evaluating the integrals of the standard normal density \(\phi\) yields: \[A_T(v) = \int_0^{L_T}\phi(v-g)\,\mathrm{d}g = \Phi(v) - \Phi(v-L_T),\;\;and\;\; B_T(v) = \int_0^{L_T}\phi(v+g)\,\mathrm{d}g = \Phi(v+L_T) - \Phi(v).\] Adding these yields: \[A_T(v) + B_T(v) = \Phi(v+L_T) - \Phi(v-L_T).\] For \(|v| \le L_T/2\), this domain restriction implies \(v+L_T \ge L_T/2\) and \(v-L_T \le -L_T/2\). Since \(\Phi\) is strictly increasing, we can lower bound the sum by evaluating it at these extremes: \[A_T(v) + B_T(v) \ge \Phi(L_T/2) - \Phi(-L_T/2) = 1 - 2\Phi(-L_T/2).\] As \(T \to \infty\), \(L_T \to \infty\), so \(1 - 2\Phi(-L_T/2) \to 1\). Thus, for sufficiently large \(T\), the sum is bounded below by \(1-\eta\).

For the second inequality, observe that \(\phi\) is symmetric and strictly decreasing away from zero. Thus, the relationship between \(A_T(v)\) and \(B_T(v)\) depends only on the sign of \(v\). For \(v \ge 0\), the integration interval for \(A_T(v)\) is \([v-L_T, v]\), which is closer to the origin than the interval \([v, v+L_T]\) for \(B_T(v)\). Hence, \(A_T(v) \ge B_T(v)\), yielding: \[\min\{A_T(v), B_T(v)\} = B_T(v) = \Phi(v+L_T) - \Phi(v) = \Phi(-v) - \Phi(-(v+L_T))\] since \(\Phi(x) = 1 - \Phi(-x)\). By identical symmetric reasoning for \(v < 0\), we find \(\min\{A_T(v), B_T(v)\} = A_T(v)\). Consolidating both cases yields a single identity for all \(v\): \[\label{eq:min95AB95with95Phi} \min\{A_T(v), B_T(v)\} = \Phi(-|v|) - \Phi(-(|v|+L_T)).\tag{17}\] We wish to show that \(\Phi(-|v|) - \Phi(-(|v|+L_T)) \ge (1-\eta)\Phi(-|v|)\), which is equivalent to bounding the ratio: \[\frac{\Phi(-(|v|+L_T))}{\Phi(-|v|)} \le \eta.\] Since \(0 \le |v| \le L_T/2\), the numerator is bounded above by \(\Phi(-L_T)\) and the denominator is bounded below by \(\Phi(-L_T/2)\). Therefore: \[\frac{\Phi(-(|v|+L_T))}{\Phi(-|v|)} \le \frac{\Phi(-L_T)}{\Phi(-L_T/2)} \to 0\] uniformly as \(T \to \infty\). Thus, the bound holds for sufficiently large \(T\). ◻

Proof. Define the central cylinder set \(C:=\mathcal{O}\times\{v:|v|<a\}\). The measure of \(C\) is \(2a\,\Lambda(\mathcal{O})\). Because \(w(v)\) is non-increasing in \(|v|\), we have \(w(v)\ge w(a)\) on \(C\) and \(w(v)\le w(a)\) on \(C^c\). Thus, the integrand \(\bigl(\mathbb{1}_C(\xi,v)-r(\xi,v)\bigr)\bigl(w(v)-w(a)\bigr)\) is non-negative everywhere. Consequently: \[0 \le \int_{ \mathcal{O}\times (-B,B) } \bigl(\mathbb{1}_C-r\bigr)\bigl(w-w(a)\bigr).\] Expanding this inequality gives: \[\int_{ \mathcal{O}\times (-B,B) } r w \le \int_C w - w(a)\left( \int_C 1 - \int_{ \mathcal{O}\times (-B,B) } r \right) \le \int_C w,\] where the final step follows because the assumption \(\int_{ \mathcal{O}\times (-B,B) } r \le 2a\,\Lambda(\mathcal{O}) = \int_C 1\) forces the bracketed term to be non-negative. Therefore: \[\int_{ \mathcal{O}\times (-B,B) } (1-r)w \ge \int_{ \mathcal{O}\times (-B,B) } w - \int_C w = \int_{C^c} w = 2\;\Lambda(\mathcal{O})\;\int_a^B w(u)\,\mathrm{d}u.\] ◻

Proof. By Lemma 19, for all sufficiently large \(T\), \(A_T(v)+B_T(v)\ge 1-\eta\) on the interval \(|v|\le L_T/2\). Given the abstention constraint \(\mathcal{A}_T^{Q_\rho}(\psi) \le \alpha\), we can further restrict the integration domain to this interval \([-L_T/2,L_T/2]\) to obtain: \[\frac{2}{\sqrt{T}} \int_{\mathcal{C}_\rho} \int_{|v|\le L_T/2} \psi_?^\xi(v) \bigl[A_T(v)+B_T(v)\bigr] \,\mathrm{d}v\,\Lambda_\rho(\mathrm{d}\xi) \le \alpha.\] Substituting the uniform central bound (first bound in Lemma 19) yields: \[\int_{\mathcal{C}_\rho} \int_{|v|\le L_T/2} \psi_?^\xi(v) \,\mathrm{d}v\,\Lambda_\rho(\mathrm{d}\xi) \le \frac{\alpha\sqrt{T}}{2(1-\eta)}.\] Because \(\Lambda_\rho(\mathcal{C}_\rho) = c_\rho/2\), the right-hand side is \(2a_{T,\eta}\,\Lambda_\rho(\mathcal{C}_\rho)\).

Next, we evaluate the undetected error mass. Discarding the non-negative contribution from \(|v|>L_T/2\) and applying Lemma 18 and the second bound of Lemma 19, we obtain: \[\mathcal{E}_T^{Q_\rho}(\psi) \ge \frac{2(1-\eta)}{\sqrt{T}} \int_{\mathcal{C}_\rho} \int_{|v|\le L_T/2} \bigl(1-\psi_?^\xi(v)\bigr)\Phi(-|v|) \,\mathrm{d}v\,\Lambda_\rho(\mathrm{d}\xi).\] We now apply the abstention rearrangement result from Lemma 20 with \(B=L_T/2\), \(w(v)=\Phi(-|v|)\), and \(r(\xi,v)=\psi_?^{\xi}(v)\). Our assumption on \(\alpha\) ensures that \(a_{T,\eta} < L_T/4 < L_T/2\). This allows the rearrangement to yield: \[\int_{\mathcal{C}_\rho} \int_{|v|\le L_T/2} \bigl(1-\psi_?^\xi(v)\bigr)\Phi(-|v|) \,\mathrm{d}v\,\Lambda_\rho(\mathrm{d}\xi) \ge \Lambda_\rho(\mathcal{C}_\rho) \,2\int_{a_{T,\eta}}^{L_T/2}\Phi(-u)\,\mathrm{d}u.\] Substituting \(\Lambda_\rho(\mathcal{C}_\rho)=c_\rho/2\): \[\mathcal{E}_T^{Q_\rho}(\psi) \ge \frac{2(1-\eta)c_\rho}{\sqrt{T}} \int_{a_{T,\eta}}^{L_T/2}\Phi(-u)\,\mathrm{d}u.\] Finally, because \(a_{T,\eta} < L_T/4\), the omitted tail \(\int_{L_T/2}^\infty \Phi(-u)\,\mathrm{d}u\) decays exponentially faster than \(\int_{a_{T,\eta}}^\infty \Phi(-u)\,\mathrm{d}u\). Thus \[\int_{a_{T,\eta}}^{L_T/2}\Phi(-u)\,\mathrm{d}u = (1-o_T(1)) \int_{a_{T,\eta}}^\infty \Phi(-u)\,\mathrm{d}u,\] which concludes the proof. ◻

Proof of Theorem 2.

Let \(\pi\) be any policy satisfying the global abstention budget \(\mathcal{A}_T(\pi) \le \alpha\). By Lemma 13, the abstention and undetected error mass of this strategy under the local subprior \(Q_\rho\) are bounded above by their true global counterparts, i.e., \[\mathcal{A}_T^{Q_\rho}(\pi) \le \mathcal{A}_T(\pi) \le \alpha, \quad and \quad \mathcal{E}_T^{Q_\rho}(\pi)\le \mathcal{E}_T(\pi).\]

By Lemma 14 and Lemma 17, the original strategy \(\pi\) induces a \(V\)-based terminal rule \(\psi^\xi\) in the experiment with background oracle revealed. This reduction preserves the abstention probability and ensures the induced sign-rule error is no larger than the original undetected error. Therefore \[\mathcal{A}_T^{Q_\rho}(\psi^\xi) \le \alpha.\] Because the abstention constraint is satisfied, we may apply Lemma 21. This yields: \[\mathcal{E}_T(\pi) \ge \mathcal{E}_T^{Q_\rho}(\psi^\xi) \ge (1-o_T(1)) \frac{2(1-\eta)c_\rho}{\sqrt{T}} \int_{a_{T,\eta}}^\infty \Phi(-u)\,\mathrm{d}u,\] where the lower limit of the integral \(a_{T,\eta}\) is defined in ?? .

Fix \(\rho \in (0,1)\) and \(\eta \in (0,1)\). The construction of the local subprior gives constants \(c_\rho > 0\) and \(\delta_{\rho} > 0\). We define the critical abstention threshold \(\alpha_0(\rho,\eta) := \frac{(1-\eta)c_\rho\delta_{\rho}}{4}.\) For every fixed \(\alpha \in (0, \alpha_0(\rho,\eta))\), Lemma 21 applies. Furthermore, as \(T \to \infty\), \(a_{T,\eta} = \frac{\alpha\sqrt{T}}{2(1-\eta)c_\rho} \to \infty.\)

Using \(\int_a^\infty \Phi(-u)\,\mathrm{d}u = \phi(a)-a\Phi(-a)\) and the standard Gaussian tail asymptotics: \[\log\left(\int_a^\infty \Phi(-u)\,\mathrm{d}u\right) = -\frac{a^2}{2} + O(\log a) \qquad \text{as } a \to \infty,\] we extract the exponential decay rate for any feasible strategy \(\pi\): \[\liminf_{T\to\infty} \frac{1}{\alpha^2 T} \log \mathcal{E}_T(\pi) \ge -\frac{1}{8(1-\eta)^2 c_\rho^2}.\] Taking the infimum over all feasible strategies yields the lower bound on the optimal undetected error probability \(\mathfrak{E}_{T}(\alpha)\). Since this bound holds for all \(\alpha \in (0, \alpha_0(\rho,\eta))\), taking the limit as \(\alpha \downarrow 0\): \[\liminf_{\alpha\downarrow 0} \liminf_{T\to\infty} \frac{1}{\alpha^2 T} \log \mathfrak{E}_{T}(\alpha) \ge -\frac{1}{8(1-\eta)^2 c_\rho^2} \ge -\frac{1}{8(1-\eta)^2 (1-\rho)^4 \kappa_\nu^2}, \label{eqn:lowerbd}\tag{18}\] where the second inequality follows because our definition of the restricted set \(\mathcal{C}_{ij}\) ensures that the constant satisfies \(c_\rho \ge (1-\rho)^2 \kappa_\nu\). Because 18 holds for arbitrary \(\eta \in (0,1)\) and \(\rho \in (0,1)\), we may take \(\eta \downarrow 0\) and then \(\rho \downarrow 0\) to obtain the desired lower bound. ◻

Proof. Fix any strategy \(\pi\in\Pi_T^{\rm freq}(\alpha)\). The proof uses the midpoint instance \(\mu^0:=(x,x)\) as a change-of-measure reference. Since the abstention constraint is uniform over all two-arm Gaussian instances, \[\label{eq:freq-abst-midpoint} \mathbb{P}_{\mu^0}^\pi(\hat{a}_T=?)\le \alpha .\tag{22}\] For \(\theta\in\{-1,0,+1\}\), define \[\mu^\theta := \left( x+\theta\frac{\Delta}{2}, x-\theta\frac{\Delta}{2} \right).\] Thus \(\mu^0=(x,x)\). Let \[S_t:=\mathbb{1}\{A_t=1\}-\mathbb{1}\{A_t=2\}\in\{+1,-1\},\] and define the centered signed observation \(Z_t:=S_t(X_t-x)\). Finally, set \(W:=\sum_{t=1}^T Z_t\), \(V:=\frac{W}{\sqrt T}\) and \(m:=\frac{\Delta\sqrt T}{2}\).

We first reduce the adaptive experiment to a one-dimensional Gaussian shift experiment. Under \(\mu^\theta\), conditionally on the past and on the chosen arm \(A_t\), the transformed observation satisfies \(Z_t\sim \mathcal{N}\!\left(\theta\frac{\Delta}{2},1\right)\). The conditional law of \(Z_t\) is therefore independent of both the past and the chosen arm. Hence \(Z_1,\ldots,Z_T \overset{\mathrm{i.i.d.}}{\sim} \mathcal{N}\!\left(\theta\frac{\Delta}{2},1\right)\), and consequently \[V\sim \begin{cases} \mathcal{N}(m,1), & \theta=+1,\\ \mathcal{N}(0,1), & \theta=0,\\ \mathcal{N}(-m,1), & \theta=-1. \end{cases}\]

The same argument as in Lemma 17 applies here, with the background oracle consisting only of the two arms and their midpoint \(x\). Therefore, for the three instances \(\mu^0,\mu^+,\mu^-\), the terminal decision rule may be represented by measurable functions \(\psi = (\psi_+, \psi_-,\psi_?)\), where \(\psi_+(v)\) is the probability of recommending arm \(1\) after observing \(V=v\), \(\psi_-(v)\) is the probability of recommending arm \(2\), and \(\psi_?(v)\) is the probability of abstaining. These functions satisfy, for every \(v\), \[\psi_+(v)+\psi_-(v)+\psi_?(v)=1, \qquad \psi_+(v),\psi_-(v),\psi_?(v)\in[0,1].\]

Let \(\phi\) denote the standard normal density. Under the midpoint instance \(\mu^0\), we have \(V\sim\mathcal{N}(0,1)\), so 22 means \[\label{eq:freq-psi-abstention} \int_{\mathbb{R}}\psi_?(v)\phi(v)\,\mathrm{d}v\le \alpha .\tag{23}\] Under \(\mu^+\), arm \(1\) is uniquely optimal and \(V\sim\mathcal{N}(m,1)\). Therefore \[\label{eq:freq-error-plus-psi} \mathcal{E}_{T,\mu^+}(\pi) = \mathbb{P}_{\mu^+}^\pi(\hat{a}_T=2) = \int_{\mathbb{R}}\psi_-(v)\phi(v-m)\,\mathrm{d}v .\tag{24}\] Similarly, under \(\mu^-\), arm \(2\) is uniquely optimal and \(V\sim\mathcal{N}(-m,1)\), so \[\label{eq:freq-error-minus-psi} \mathcal{E}_{T,\mu^-}(\pi) = \mathbb{P}_{\mu^-}^\pi(\hat{a}_T=1) = \int_{\mathbb{R}}\psi_+(v)\phi(v+m)\,\mathrm{d}v .\tag{25}\] We next lower bound the average of the two mirror-instance errors. Define \[p_+(v):=\phi(v-m), \qquad p_-(v):=\phi(v+m).\] By 24 and 25 , \[\begin{align} \overline{\mathcal{E}} := \frac{1}{2}\mathcal{E}_{T,\mu^+}(\pi) + \frac{1}{2}\mathcal{E}_{T,\mu^-}(\pi) &= \frac{1}{2} \int_{\mathbb{R}} \left[ \psi_-(v)p_+(v) + \psi_+(v)p_-(v) \right]\,\mathrm{d}v \\ &\ge \frac{1}{2} \int_{\mathbb{R}} \bigl(1-\psi_?(v)\bigr) \min\{p_+(v),p_-(v)\}\,\mathrm{d}v . \end{align}\] Note that \(\min\{p_+(v),p_-(v)\} = \phi(|v|+m)\). Hence \[\label{eq:freq-average-error-phi} \overline{\mathcal{E}} \ge \frac{1}{2} \int_{\mathbb{R}} \bigl(1-\psi_?(v)\bigr)\phi(|v|+m)\,\mathrm{d}v .\tag{26}\]

It remains to identify the least possible value of the right-hand side subject to the midpoint abstention constraint 23 . Let \(r(v):=\psi_?(v)\). Then \(0\le r(v)\le1\) and \[\int_{\mathbb{R}}r(v)\phi(v)\,\mathrm{d}v\le\alpha .\] Write \[\phi(|v|+m) = q_m(v)\phi(v), \qquad q_m(v):= \exp\!\left(-m|v|-\frac{m^2}{2}\right).\] The function \(q_m\) is even and nonincreasing in \(|v|\). Let \(C_\alpha:=[-z_\alpha,z_\alpha]\). By the definition of \(z_\alpha\), \[\int_{C_\alpha}\phi(v)\,\mathrm{d}v=\alpha .\] Since \(q_m(v)\ge q_m(z_\alpha)\) on \(C_\alpha\) and \(q_m(v)\le q_m(z_\alpha)\) on \(C_\alpha^c\), we have pointwise \[\bigl(r(v)-\mathbb{1}_{C_\alpha}(v)\bigr) \bigl(q_m(v)-q_m(z_\alpha)\bigr) \le 0 .\] Integrating with respect to \(\phi(v)\,\mathrm{d}v\) gives \[\int_{\mathbb{R}} r(v)q_m(v)\phi(v)\,\mathrm{d}v \le \int_{C_\alpha}q_m(v)\phi(v)\,\mathrm{d}v + q_m(z_\alpha) \left[ \int_{\mathbb{R}}r(v)\phi(v)\,\mathrm{d}v - \int_{C_\alpha}\phi(v)\,\mathrm{d}v \right].\] The bracketed term is nonpositive by 23 , and hence \[\int_{\mathbb{R}} r(v)q_m(v)\phi(v)\,\mathrm{d}v \le \int_{C_\alpha}q_m(v)\phi(v)\,\mathrm{d}v .\] Equivalently, \[\label{eq:freq-rearrangement} \int_{\mathbb{R}} \bigl(1-r(v)\bigr)\phi(|v|+m)\,\mathrm{d}v \ge \int_{\mathbb{R}\setminus C_\alpha}\phi(|v|+m)\,\mathrm{d}v .\tag{27}\] By symmetry, \[\int_{\mathbb{R}\setminus C_\alpha}\phi(|v|+m)\,\mathrm{d}v = 2\int_{z_\alpha}^{\infty}\phi(v+m)\,\mathrm{d}v = 2\Phi(-m-z_\alpha).\] Combining this identity with 26 and 27 yields \(\overline{\mathcal{E}} \ge \Phi(-m-z_\alpha)\). Finally, \[\max\left\{ \mathcal{E}_{T,\mu^+}(\pi), \mathcal{E}_{T,\mu^-}(\pi) \right\} \ge \overline{\mathcal{E}} \ge \Phi(-m-z_\alpha) =\Phi\!\left( -\frac{\Delta\sqrt T}{2}-z_\alpha \right).\] ◻

Proof. For \(\xi=(i,j,u,\zeta_{-ij})\in\mathcal{C}_{\rho,ij}\), define \[R_{ijh}(\xi,\delta) := \frac{ \bar f_i\bigl(\eta_i(\xi,\delta,h)\bigr) \bar f_j\bigl(\eta_j(\xi,\delta,h)\bigr) J_{ijh}(u,\delta) }{ \bar f_i(u)\bar f_j(u) }.\] Since \(\mathcal{C}_\rho\) is compact and the prior densities are continuous and strictly positive, the denominator is uniformly bounded away from zero on \(\mathcal{C}_\rho\).

At \(\delta=0\), we have \(\eta_i(\xi,0,h)=\eta_j(\xi,0,h)=u\) and \(J_{ijh}(u,0)=1\). Hence \(R_{ijh}(\xi,0)=1\).

The coordinate maps, \(J_{ijh}\), and \(R_{ijh}\) are continuous in a neighborhood of \(\mathcal{C}_\rho\times\{0\}\times\{+1,-1\}\). Since \(\mathcal{C}_\rho\) is compact and there are finitely many pairs and signs, there exists \(\delta_\rho>0\) such that, uniformly over all admissible \(\xi\), \(h\), and \(\delta\in[0,\delta_\rho]\), \[\eta_i(\xi,\delta,h), \eta_j(\xi,\delta,h) \in (u-\ell_\rho,u+\ell_\rho), \qquad J_{ijh}(u,\delta)>0,\] and \(R_{ijh}(\xi,\delta)\ge1-\rho\). The latter inequality is ?? .

Finally, by 30 , \[\begin{align} \min\{ \eta_i(\xi,\delta,h), \eta_j(\xi,\delta,h) \} &> u-\ell_\rho\\ &> u-2\ell_\rho\\ &\ge \zeta_k = \eta_k(\xi,\delta,h), \qquad k\neq i,j. \end{align}\] Thus \(i\) and \(j\) are the unique top-two arms. ◻

Proof. Let \(s(\mu) := \bigl(s(\mu_1),\ldots,s(\mu_K)\bigr)\). Define the measures in the information coordinate as \[\bar P(B) := P\bigl(s^{-1}(B)\bigr), \qquad \bar Q_{\rho,\bar\delta}(B) := Q_{\rho,\bar\delta}\bigl(s^{-1}(B)\bigr).\] Note \(\bar P\) has Lebesgue density \(\bar p(\eta) = \prod_{k=1}^K\bar f_k(\eta_k)\).

For each pair \(i<j\), define \[\mathcal{S}_{i,j}^{\bar\delta} := \left\{ \eta(\xi,\delta,h): \xi\in\mathcal{C}_{\rho,ij},\; 0\le\delta\le\bar\delta,\; h\in\{+1,-1\} \right\},\] and set \(\mathcal{S}_\rho^{\bar\delta}:= \bigcup_{i<j}\mathcal{S}_{i,j}^{\bar\delta}\).

By Lemma 22, arms \(i\) and \(j\) are the unique strict top-two arms on \(\mathcal{S}_{i,j}^{\bar\delta}\). Consequently, the sets \(\mathcal{S}_{i,j}^{\bar\delta}\) are pairwise disjoint. Moreover, when \(\delta>0\), the sign is uniquely determined by \(h=\operatorname{sign}(\eta_i-\eta_j)\). The two sign representations overlap only when \(\delta=0\), which is a \(Q_{\rho,\bar\delta}\)-null set.

For any Borel set \(B\subseteq\mathcal{H}^K\), substituting the definition of \(\Lambda_\rho\) in 31 into ?? gives \[\begin{align} \bar Q_{\rho,\bar\delta}(B) = \sum_{i<j}\sum_{h\in\{+1,-1\}} \int_{\mathcal{C}_{\rho,ij}} \int_0^{\bar\delta} \mathbb{1}_B\bigl(\eta(\xi,\delta,h)\bigr) (1-\rho)\bar f_i(u)\bar f_j(u) \prod_{k\neq i,j}\bar f_k(\zeta_k) \,\mathrm{d}\delta\,\mathrm{d}u\,\mathrm{d}\zeta_{-ij}. \end{align}\]

For each fixed pair and sign, apply change-of-variables with \((u,\delta,\zeta_{-ij}) \longmapsto \eta(\xi,\delta,h)\). The absolute Jacobian determinant is \(J_{ijh}(u,\delta)\). It follows that \(\bar Q_{\rho,\bar\delta}\) has Lebesgue density \(\bar q_{\rho,\bar\delta}\) satisfying \[\bar q_{\rho,\bar\delta} \bigl(\eta(\xi,\delta,h)\bigr) = \frac{ (1-\rho)\bar f_i(u)\bar f_j(u) \displaystyle\prod_{k\neq i,j}\bar f_k(\zeta_k) }{ J_{ijh}(u,\delta) }\] for Lebesgue-almost every \(\eta(\xi,\delta,h)\in\mathcal{S}_{i,j}^{\bar\delta}\).

Furthermore, the definition ?? implies \(\bar Q_{\rho,\bar\delta} \bigl( \mathcal{H}^K\setminus \mathcal{S}_\rho^{\bar\delta} \bigr) = 0\). Hence \(\bar q_{\rho,\bar\delta}(\eta)=0\) for Lebesgue-almost every \(\eta\notin\mathcal{S}_\rho^{\bar\delta}\).

For \(\eta=\eta(\xi,\delta,h)\in\mathcal{S}_{i,j}^{\bar\delta}\), Lemma 22 gives \[(1-\rho)\bar f_i(u)\bar f_j(u) \le \bar f_i(\eta_i)\bar f_j(\eta_j) J_{ijh}(u,\delta).\] Since \(J_{ijh}(u,\delta)>0\) and \(\eta_k=\zeta_k\) for \(k\neq i,j\), \[\begin{align} \bar q_{\rho,\bar\delta}(\eta) \le \bar f_i(\eta_i)\bar f_j(\eta_j) \prod_{k\neq i,j}\bar f_k(\eta_k) = \bar p(\eta). \end{align}\] The same inequality holds outside \(\mathcal{S}_\rho^{\bar\delta}\) because \(\bar q_{\rho,\bar\delta}=0\) there. Thus \(\bar q_{\rho,\bar\delta}\le\bar p\) Lebesgue-almost everywhere on \(\mathcal{H}^K\).

Consequently, for every Borel set \(B\subseteq\mathcal{H}^K\), \[\bar Q_{\rho,\bar\delta}(B) = \int_B\bar q_{\rho,\bar\delta}(\eta)\,\mathrm{d}\eta \le \int_B\bar p(\eta)\,\mathrm{d}\eta = \bar P(B).\] Finally, for every Borel set \(E\subseteq(\mathcal{I})^K\), \[\begin{align} Q_{\rho,\bar\delta}(E) = \bar Q_{\rho,\bar\delta}\bigl(s(E)\bigr) \le \bar P\bigl(s(E)\bigr) = P(E). \end{align}\] Hence \(Q_{\rho,\bar\delta}\le P\). ◻

Proof. The uniqueness of the pair follows from the strict top-two property in Lemma 22. When \(\delta>0\), the sign is determined by \(h=\operatorname{sign}(\eta_i-\eta_j)\), and the center and remaining coordinates are recovered from the inverse transformation given above. The two sign representations coincide only when \(\delta=0\), which is a \(Q_{\rho,\bar\delta}\)-null set. Define the coordinates arbitrarily on this null set.

For Borel sets \(C\subseteq\mathcal{C}_\rho\) and \(D\subseteq[0,\bar\delta]\), the definition ?? gives \[\begin{align} Q_{\rho,\bar\delta} \bigl( \Xi\in C,\, \Delta\in D,\, H=h \bigr) = \int_C\int_D \mathrm{d}\delta\,\Lambda_\rho(\mathrm{d}\xi) = \Lambda_\rho(C)\operatorname{Leb}(D). \end{align}\] This proves ?? . Since the two signs have the same mass conditional on \((\Xi,\Delta)\), integrating over \(\xi\) and summing over the two signs gives \[Q_{\rho,\bar\delta}(\Delta\in\mathrm{d}\delta) = 2\Lambda_\rho(\mathcal{C}_\rho)\,\mathrm{d}\delta = c_\rho\,\mathrm{d}\delta.\] ◻

Proof. Follows directly from \(Q_{\rho,\bar\delta}\le P\). ◻

Proof. Fix \(\xi=(i,j,u,\zeta_{-ij})\in\mathcal{C}_\rho\). We construct the modified strategy \(\pi'\) that satisfies ?? by internally simulating \(\pi\).

Whenever the internal copy of \(\pi\) samples arm \(k\in\{i,j\}\), the strategy \(\pi'\) samples the same arm and feeds the observed reward to the internal copy. Whenever the internal copy samples an arm \(k\notin\{i,j\}\), the strategy \(\pi'\) instead samples arm \(i\), discards the resulting reward, and feeds the internal copy an independent simulated reward drawn from \(P_{s^{-1}(\zeta_k)}\). Conditional on \(\Xi=\xi\), the quality parameter of every background arm \(k\notin\{i,j\}\) is known to be \(s^{-1}(\zeta_k)\), and its reward distribution is independent of \((H,\Delta)\). Therefore, for every fixed \((h,\delta)\), the simulated reward has the same distribution as the reward that \(\pi\) would have observed by sampling arm \(k\) in the original experiment.

It follows inductively over the sampling rounds that the internal history observed by \(\pi\) under \(\pi'\) has the same distribution as the history observed by \(\pi\) under \(\mathbb{P}_{h,\delta}^{\xi,\pi}\). Consequently, the terminal output of the internal copy has the same distribution as \(\hat{a}_T\) under the original strategy.

At time \(T\), the strategy \(\pi'\) maps the terminal output of the internal copy according to \[i\mapsto +,\qquad j\mapsto -,\qquad ?\mapsto ?,\] and maps every recommendation \(k\notin\{i,j\}\) arbitrarily to one of the two signs, say \(+\). This mapping preserves the abstention event, and hence \[\mathbb{P}_{h,\delta}^{\xi,\pi'}(\hat{a}'_T=?) = \mathbb{P}_{h,\delta}^{\xi,\pi}(\hat{a}_T=?).\]

Moreover, on the support of \(Q_{\rho,\bar\delta}\), arms \(i\) and \(j\) are the unique top-two arms, with \(a^\star(+)=i\) and \(a^\star(-)=j\). Therefore, any original recommendation \(k\notin\{i,j\}\) is already an undetected error. Mapping such a recommendation to a sign either preserves that error or converts it into a correct sign decision. Since the recommendations \(i\) and \(j\) are mapped to their corresponding signs, the mapping cannot turn a correct original recommendation into an incorrect sign decision. Thus \(\left\{\hat{a}'_T=-h\right\} \subseteq \left\{ \hat{a}_T\notin\{a^\star(h),?\} \right\}\) under the coupled construction, and consequently \[\mathbb{P}_{h,\delta}^{\xi,\pi'}(\hat{a}'_T=-h) \le \mathbb{P}_{h,\delta}^{\xi,\pi} \bigl(\hat{a}_T\notin\{a^\star(h),?\}\bigr).\] This proves ?? . ◻

Proof. Let \(\pi_t(a_t\mid\xi,\omega_{t-1})\) denote the sampling kernel used by the strategy at time \(t\), evaluated at the realized history \(\omega_{t-1}\). This kernel is fixed by the strategy and is the same measurable function of the realized past under every value of \((h,\delta)\).

For a natural parameter \(\theta\in\Theta\), write \[p_\theta(x) := h(x)\exp\{\theta t(x)-A(\theta)\}.\] Under \(\mathbb{P}_{h,\delta}^{\xi}\), where \(r=h\delta\sqrt T/2\), the density of the realized history \(\omega\) is \[\begin{align} p_{h,\delta}^\xi(\omega) = \prod_{t=1}^T \pi_t(a_t\mid\xi,\omega_{t-1}) \prod_{t=1}^T p_{\theta_0+S_t(\omega)r/\sqrt{Ta_0}}(x_t). \end{align}\] Under the tie law (where \(\delta=0\)), \[p_0^\xi(\omega) = \prod_{t=1}^T \pi_t(a_t\mid\xi,\omega_{t-1}) \prod_{t=1}^T p_{\theta_0}(x_t).\] The sampling kernels \(\pi_t\) and carrier densities \(h\) cancel in the likelihood ratio. Therefore, \[\begin{align} \log \frac{ p_{h,\delta}^\xi(\omega) }{ p_0^\xi(\omega) } = \sum_{t=1}^T \left[ \frac{S_t(\omega)r}{\sqrt{Ta_0}}t(x_t) - A\left( \theta_0+ \frac{S_t(\omega)r}{\sqrt{Ta_0}} \right) + A(\theta_0) \right], \end{align}\] which proves ?? . ◻

Proof. For fixed \((\xi,\delta,h)\), the conditional abstention probability induced by \(\psi^\xi\) is \[\label{integral95of95abs} \mathbb{P}_{h,\delta}^{\xi}(\hat{a}_T=?) = \int_{\mathcal{H}_T^\xi} \psi_?^\xi(\omega) \,\mathbb{P}_{h,\delta}^{\xi}(\mathrm{d}\omega).\tag{40}\] Hence we can write \[\begin{align} \mathcal{A}_T^{Q_{\rho,\bar\delta_\alpha}}(\psi) &= \int_{(\mathcal{I})^K} \mathbb{P}_\mu(\hat{a}_T =?) Q_{\rho, \bar\delta_\alpha}(\mathrm{d}\mu) \\ &\stackrel{(a)}{=} \sum_{h\in\{+1,-1\}} \int_{\mathcal{C}_\rho} \int_0^{\bar\delta_\alpha} \mathbb{P}_{h,\delta}^{\xi} (\hat{a}_T=?) \,\mathrm{d}\delta\, \Lambda_\rho(\mathrm{d}\xi)\\ &\stackrel{(b)}{=} \sum_{h\in\{+1,-1\}} \int_{\mathcal{C}_\rho} \int_0^{\bar\delta_\alpha} \int_{\mathcal{H}_T^\xi} \psi_?^\xi(\omega) \,\mathbb{P}_{h,\delta}^{\xi}(\mathrm{d}\omega) \,\mathrm{d}\delta\, \Lambda_\rho(\mathrm{d}\xi).\\ &\stackrel{(c)}{=} \frac{2}{\sqrt T} \int_{\mathcal{C}_\rho} \int_0^{L_T} \int_{\mathcal{H}_T^\xi} \psi_?^\xi(\omega) \,\mathbb{P}_{+1,\,2g/\sqrt T}^{\xi}(\mathrm{d}\omega) \,\mathrm{d}g\, \Lambda_\rho(\mathrm{d}\xi)\\ &\quad+ \frac{2}{\sqrt T} \int_{\mathcal{C}_\rho} \int_0^{L_T} \int_{\mathcal{H}_T^\xi} \psi_?^\xi(\omega) \,\mathbb{P}_{-1,\,2g/\sqrt T}^{\xi}(\mathrm{d}\omega) \,\mathrm{d}g\, \Lambda_\rho(\mathrm{d}\xi). \end{align}\] where \((a)\) is due to the coordinate factorization of \(Q_{\rho, \bar\delta_\alpha}\) ?? , \((b)\) is due to 40 and \((c)\) is due to the change of variable with \(g=\delta\sqrt T/2\) separately for the two signs. Hence by the definitions of \(\mathbb{M}_{T,\xi}\), this is ?? .

An undetected sign error occurs when the rule recommends \(-\) under \(H=+1\), or recommends \(+\) under \(H=-1\). Repeating similar arguments as for ?? with the two error events gives ?? . Note the tie case \(\delta=0\) does not affect the calculation because it is null with respect to the \(\delta\)-integration.

To prove the lower bound, write \(a_{T,\xi} := \frac{\mathrm{d}\mathbb{A}_{T,\xi}}{\mathrm{d}\mathbb{M}_{T,\xi}}\), and \(b_{T,\xi} := \frac{\mathrm{d}\mathbb{B}_{T,\xi}}{\mathrm{d}\mathbb{M}_{T,\xi}}\). Since \(\mathbb{M}_{T,\xi}=\mathbb{A}_{T,\xi}+\mathbb{B}_{T,\xi}\), \[a_{T,\xi}(\omega)+b_{T,\xi}(\omega) = 1 \qquad \mathbb{M}_{T,\xi}\text{-a.e.}\] For \(\mathbb{M}_{T,\xi}\)-almost every \(\omega\), \[\begin{align} \psi_-^\xi(\omega)a_{T,\xi}(\omega) + \psi_+^\xi(\omega)b_{T,\xi}(\omega) &\ge \bigl( \psi_-^\xi(\omega) + \psi_+^\xi(\omega) \bigr) \min\{ a_{T,\xi}(\omega), b_{T,\xi}(\omega) \}\\ &= \bigl( 1-\psi_?^\xi(\omega) \bigr) \frac{\mathrm{d}\mathbb{N}_{T,\xi}}{\mathrm{d}\mathbb{M}_{T,\xi}}(\omega). \end{align}\] Integrating with respect to \(\mathbb{M}_{T,\xi}\), and then with respect to \(\Lambda_\rho\), proves ?? . ◻

Proof. Fix \(\xi=(i,j,u,\zeta_{-ij})\in\mathcal{C}_\rho\), and recall that \(\theta_0=\beta(u)\) and \(a_0=A''(\theta_0)\). By 36 , \[-\ell_{T,\xi}''(r;\omega) = \frac{1}{Ta_0} \sum_{t=1}^T A''\left( \theta_0+ \frac{S_t(\omega)r}{\sqrt{Ta_0}} \right).\]

Because \(\mathcal{C}_\rho\) is compact, the centers \(\theta_0=\beta(u)\) range over a compact subset of \(\Theta\), and \(\inf_{\xi\in\mathcal{C}_\rho}a_0>0\). Moreover, for \(|r|\le L_T\), \(\left| \frac{r}{\sqrt{Ta_0}} \right| \le C_D\alpha\) uniformly over \(\xi\in\mathcal{C}_\rho\). Thus, for all sufficiently small \(\alpha\), every perturbed natural parameter \(\theta_0+\frac{S_t(\omega)r}{\sqrt{Ta_0}}\) belongs to a common compact subset of \(\Theta\). Since \(A''\) is locally Lipschitz on this compact set, there exists \(C<\infty\) such that \[\left| \frac{ A''\left( \theta_0+ \frac{S_t(\omega)r}{\sqrt{Ta_0}} \right) }{ A''(\theta_0) } -1 \right| \le C\alpha.\] Averaging over \(t\) proves ?? . By decreasing \(\alpha_0\) if necessary, we may assume \(C\alpha_0<1\), so the likelihood is strictly concave.

We next prove ?? . Fix \(r\in[-L_T/2,L_T/2]\) and consider the experiment under \(\mathbb{P}_{\mathrm{sgn}(r),\,\delta_T(r)}^\xi\). Define the score at the true signed parameter by \[U_{T,\xi}(r) := \ell_{T,\xi}'(r) = \sum_{t=1}^T D_t(r),\] where \[D_t(r) := \frac{S_t}{\sqrt{Ta_0}} \left[ t(X_t) - A'\left( \theta_0+ \frac{S_t r}{\sqrt{Ta_0}} \right) \right].\] Let \(\mathcal{G}_t^\xi := \sigma\bigl( \xi,A_1,X_1,\ldots,A_{t-1},X_{t-1},A_t \bigr)\) denote the information available after choosing \(A_t\) but before observing \(X_t\). Conditional on \(\mathcal{G}_t^\xi\), the reward has natural parameter \[\theta_0+\frac{S_t r}{\sqrt{Ta_0}}.\] Therefore, \[\mathbb{E}_{\mathrm{sgn}(r),\,\delta_T(r)}^\xi \left[ D_t(r)\mid\mathcal{G}_t^\xi \right] = 0\] and \[\mathbb{E}_{\mathrm{sgn}(r),\,\delta_T(r)}^\xi \left[ D_t(r)^2\mid\mathcal{G}_t^\xi \right] = \frac{ A''\left( \theta_0+ \frac{S_t r}{\sqrt{Ta_0}} \right) }{ Ta_0 }.\] Moreover, for \(s<t\), the variable \(D_s(r)\) is \(\mathcal{G}_t^\xi\)-measurable. Hence \[\begin{align} \mathbb{E}_{\mathrm{sgn}(r),\,\delta_T(r)}^\xi \left[ D_s(r)D_t(r) \right] &= \mathbb{E}_{\mathrm{sgn}(r),\,\delta_T(r)}^\xi \left[ D_s(r) \mathbb{E}_{\mathrm{sgn}(r),\,\delta_T(r)}^\xi \left[ D_t(r)\mid\mathcal{G}_t^\xi \right] \right]\\ &=0. \end{align}\] Thus the martingale increments are orthogonal in \(L^2\), and therefore \[\begin{align} \mathbb{E}_{\mathrm{sgn}(r),\,\delta_T(r)}^\xi \left[ U_{T,\xi}(r)^2 \right] &= \sum_{t=1}^T \mathbb{E}_{\mathrm{sgn}(r),\,\delta_T(r)}^\xi \left[ D_t(r)^2 \right]\\ &= \mathbb{E}_{\mathrm{sgn}(r),\,\delta_T(r)}^\xi \left[ \sum_{t=1}^T \mathbb{E}_{\mathrm{sgn}(r),\,\delta_T(r)}^\xi \left[ D_t(r)^2\mid\mathcal{G}_t^\xi \right] \right]\\ &= \mathbb{E}_{\mathrm{sgn}(r),\,\delta_T(r)}^\xi \left[ \frac{1}{Ta_0} \sum_{t=1}^T A''\left( \theta_0+ \frac{S_t r}{\sqrt{Ta_0}} \right) \right]\\ &\stackrel{(a)}{=} \mathbb{E}_{\mathrm{sgn}(r),\,\delta_T(r)}^\xi \left[ -\ell_{T,\xi}''(r) \right]\\ &\stackrel{(b)}{\le} 1+C\alpha, \end{align}\] where \((a)\) follows from 36 , and \((b)\) follows from ?? .

Let \(R\le L_T/2\). If \(V_{T,\xi}\ge r+R\), then concavity implies \(\ell_{T,\xi}'(r+R)\ge0\). Hence, \[\begin{align} 0 &\le \ell_{T,\xi}'(r+R)\\ &= \ell_{T,\xi}'(r) + \int_r^{r+R} \ell_{T,\xi}''(v) \,\mathrm{d}v\\ &\le U_{T,\xi}(r) - (1-C\alpha)R, \end{align}\] so that \[U_{T,\xi}(r) \ge (1-C\alpha)R.\] Similarly, \[V_{T,\xi}\le r-R \quad\Longrightarrow\quad U_{T,\xi}(r) \le -(1-C\alpha)R.\] Consequently, \[|V_{T,\xi}-r|>R \quad\Longrightarrow\quad |U_{T,\xi}(r)| \ge (1-C\alpha)R.\] Chebyshev’s inequality gives \[\begin{align} \mathbb{P}_{\mathrm{sgn}(r),\,\delta_T(r)}^\xi \left( |V_{T,\xi}-r|>R \right) &\le \frac{ 1+C\alpha }{ (1-C\alpha)^2R^2 }. \end{align}\] Since \(\alpha\le\alpha_0\), the right-hand side is at most \(C_1/R^2\) for a constant \(C_1<\infty\) independent of \(\xi\), \(T\), \(r\), and the sampling strategy. ◻

Proof. Recall we have established that, for every measurable (history event) \(E \in \mathscr H^\xi_T\), \[\label{eq:M-signed-mixture-transfer-lower} \begin{align} \mathbb{M}_{T,\xi}(E) &= \int_0^{L_T} \mathbb{P}_{+1,\,2g/\sqrt T}^{\xi}(E) \,\mathrm{d}g + \int_0^{L_T} \mathbb{P}_{-1,\,2g/\sqrt T}^{\xi}(E) \,\mathrm{d}g\\ &= \int_{-L_T}^{L_T} \mathbb{P}_{\mathrm{sgn}(r),\,\delta_T(r)}^\xi(E) \,\mathrm{d}r. \end{align}\tag{42}\]

Choose \(R>0\) sufficiently large that \(\frac{C_1}{R^2} \le \frac{\varepsilon}{4}\), where \(C_1\) is the constant in Lemma 29. For all sufficiently large \(T\), we have \(R<a_T\) and \(R<L_T/2\). Also recall \(L_T>4a_T\), hence \([-a_T+R,a_T-R] \subset [-L_T,L_T]\). And on this interval \(|r|\le a_T-R\), hence \(\{ |V_{T,\xi}-r|\le R \} \subset \{ |V_{T,\xi}|\le a_T \}\). Therefore, \[\begin{align} \mathbb{M}_{T,\xi} \left( |V_{T,\xi}|\le a_T \right) &= \int_{-L_T}^{L_T} \mathbb{P}_{\mathrm{sgn}(r),\,\delta_T(r)}^\xi \left( |V_{T,\xi}|\le a_T \right) \,\mathrm{d}r\\ &\ge \int_{-a_T+R}^{a_T-R} \mathbb{P}_{\mathrm{sgn}(r),\,\delta_T(r)}^\xi \left( |V_{T,\xi}-r|\le R \right) \,\mathrm{d}r\\ &\ge (2a_T-2R) \left( 1-\frac{\varepsilon}{4} \right). \end{align}\] Since \(a_T\to\infty\) for every fixed \(\alpha>0\), the final expression is at least \(2(1-\varepsilon)a_T\) for all sufficiently large \(T\). This proves ?? .

For the second (weighted) bound, suppose first that \(|V_{T,\xi}-r|\le R\) and \(r\in \left[ a_T+2R,\, \frac{L_T}{2}-R \right]\). Then \(a_T<V_{T,\xi}\le\frac{L_T}{2}\), and hence \(\Phi(-|V_{T,\xi}|) \ge \Phi(-(r+R))\). Similarly, if \(|V_{T,\xi}-r|\le R\) and \(r\in \left[ -\frac{L_T}{2}+R,\, -a_T-2R \right]\), then \(a_T<|V_{T,\xi}|\le\frac{L_T}{2}\), and \(\Phi(-|V_{T,\xi}|) \ge \Phi(-(|r|+R))\). Using 42 , we have \[\begin{align} &\int_{\{a_T<|V_{T,\xi}|\le L_T/2\}} \Phi\bigl(-|V_{T,\xi}(\omega)|\bigr) \,\mathbb{M}_{T,\xi}(\mathrm{d}\omega)\\ &= \int_{\mathcal{H}^\xi_T} \mathbb{1} \left\{ a_T<|V_{T,\xi}(\omega)| \le \frac{L_T}{2} \right\} \Phi\bigl(-|V_{T,\xi}(\omega)|\bigr) \int_{-L_T}^{L_T} \mathrm{d}r \,\mathbb{P}_{\mathrm{sgn}(r),\,\delta_T(r)}^\xi(\mathrm{d}\omega) \\ &= \int_{-L_T}^{L_T} \int_{\mathcal{H}^\xi_T} \mathbb{1} \left\{ a_T<|V_{T,\xi}(\omega)| \le \frac{L_T}{2} \right\} \Phi\bigl(-|V_{T,\xi}(\omega)|\bigr) \,\mathbb{P}_{\mathrm{sgn}(r),\,\delta_T(r)}^\xi(\mathrm{d}\omega) \,\mathrm{d}r\\ &\ge \int_{a_T+2R}^{L_T/2-R} \int_{\mathcal{H}^\xi_T} \mathbb{1} \left\{ |V_{T,\xi}(\omega)-r|\le R \right\} \Phi(-(r+R)) \,\mathbb{P}_{\mathrm{sgn}(r),\,\delta_T(r)}^\xi(\mathrm{d}\omega) \,\mathrm{d}r\\ &\quad+ \int_{-L_T/2+R}^{-a_T-2R} \int_{\mathcal{H}^\xi_T} \mathbb{1} \left\{ |V_{T,\xi}(\omega)-r|\le R \right\} \Phi(-(|r|+R)) \,\mathbb{P}_{\mathrm{sgn}(r),\,\delta_T(r)}^\xi(\mathrm{d}\omega) \,\mathrm{d}r\\ &= \int_{a_T+2R}^{L_T/2-R} \Phi(-(r+R)) \mathbb{P}_{\mathrm{sgn}(r),\,\delta_T(r)}^\xi \left( |V_{T,\xi}-r|\le R \right) \,\mathrm{d}r\\ &\quad+ \int_{-L_T/2+R}^{-a_T-2R} \Phi(-(|r|+R)) \mathbb{P}_{\mathrm{sgn}(r),\,\delta_T(r)}^\xi \left( |V_{T,\xi}-r|\le R \right) \,\mathrm{d}r. \end{align}\]

By ?? , \[\mathbb{P}_{\mathrm{sgn}(r),\,\delta_T(r)}^\xi \left( |V_{T,\xi}-r|\le R \right) \ge 1-\frac{\varepsilon}{4}\] throughout both integration intervals. Then, with the change of variables \(u=-r\), we get \[\begin{align} \int_{\{a_T<|V_{T,\xi}|\le L_T/2\}} \Phi\bigl(-|V_{T,\xi}(\omega)|\bigr) \,\mathbb{M}_{T,\xi}(\mathrm{d}\omega) &\ge 2\left(1-\frac{\varepsilon}{4}\right) \int_{a_T+2R}^{L_T/2-R} \Phi(-(r+R)) \,\mathrm{d}r\\ &= 2\left(1-\frac{\varepsilon}{4}\right) \int_{a_T+3R}^{L_T/2} \Phi(-u) \,\mathrm{d}u. \end{align}\]

Since \(R\) is fixed, \(a_T\asymp\alpha\sqrt T\), and \(L_T/2>2a_T\), Gaussian tail asymptotics (\(\Phi(-x)=\frac{\phi(x)}{x}(1+O(x^{-2)})\) and \(\int^\infty_x \Phi(-u) \mathrm{d}u=\phi(x)-x\Phi(-x)\)) imply \[\log \frac{ \displaystyle \int_{a_T+3R}^{L_T/2} \Phi(-u)\,\mathrm{d}u }{ \displaystyle \int_{a_T}^{L_T/2} \Phi(-u)\,\mathrm{d}u } = -3Ra_T+O(1+\log a_T) = -o_T(\alpha^2T)\] for every fixed \(\alpha>0\). Therefore, \[\begin{align} &\int_{\{a_T<|V_{T,\xi}|\le L_T/2\}} \Phi\bigl(-|V_{T,\xi}(\omega)|\bigr) \,\mathbb{M}_{T,\xi}(\mathrm{d}\omega) \ge \exp\{-o_T(\alpha^2T)\} 2(1-\varepsilon) \int_{a_T}^{L_T/2} \Phi(-u) \,\mathrm{d}u, \end{align}\] which proves ?? .

It remains to prove the third overlap bound. Fix a history realization \(\omega\), and for ease of notation define \(v:=V_{T,\xi}(\omega)\). Assume \(|v|\le L_T/2\). Since \(v\) is an interior maximizer, \[\ell_{T,\xi}'(v;\omega)=0.\] By ?? in Lemma 29, for every \(r\in[-L_T,L_T]\), \[\label{eq:quadratic-likelihood-comparison-transfer-lower} \begin{align} \ell_{T,\xi}(v;\omega) - \frac{1+C\alpha}{2}(r-v)^2 &\le \ell_{T,\xi}(r;\omega)\\ &\le \ell_{T,\xi}(v;\omega) - \frac{1-C\alpha}{2}(r-v)^2. \end{align}\tag{43}\] Recall from 39 that \[\begin{align} \frac{\mathrm{d}\mathbb{N}_{T,\xi}}{\mathrm{d}\mathbb{M}_{T,\xi}}(\omega) = \frac{ \min\left\{ \displaystyle \int_0^{L_T} e^{\ell_{T,\xi}(r;\omega)} \,\mathrm{d}r,\, \displaystyle \int_{-L_T}^{0} e^{\ell_{T,\xi}(r;\omega)} \,\mathrm{d}r \right\} }{ \displaystyle \int_{-L_T}^{L_T} e^{\ell_{T,\xi}(r;\omega)} \,\mathrm{d}r }. \end{align}\]

Suppose first that \(v\ge0\). By the lower bound in 43 , \[\begin{align} &\min\left\{ \int_0^{L_T} e^{\ell_{T,\xi}(r;\omega)} \,\mathrm{d}r,\, \int_{-L_T}^{0} e^{\ell_{T,\xi}(r;\omega)} \,\mathrm{d}r \right\} \\ &\quad\ge e^{\ell_{T,\xi}(v;\omega)}\min\left\{ \int_0^{L_T} e^{-(1+C\alpha)(r-v)^2/2} \,\mathrm{d}r,\, \int_{-L_T}^{0} e^{-(1+C\alpha)(r-v)^2/2} \,\mathrm{d}r \right\} \\ &\quad\ge e^{\ell_{T,\xi}(v;\omega)} \int_{-L_T}^{0} \exp\left\{ -\frac{1+C\alpha}{2}(r-v)^2 \right\} \,\mathrm{d}r. \end{align}\] By the upper bound in 43 , \[\begin{align} \int_{-L_T}^{L_T} e^{\ell_{T,\xi}(r;\omega)} \,\mathrm{d}r &\le e^{\ell_{T,\xi}(v;\omega)} \int_{-\infty}^{\infty} \exp\left\{ -\frac{1-C\alpha}{2}(r-v)^2 \right\} \,\mathrm{d}r\\ &= e^{\ell_{T,\xi}(v;\omega)} \sqrt{\frac{2\pi}{1-C\alpha}}. \end{align}\] Thus \[\begin{align} \frac{\mathrm{d}\mathbb{N}_{T,\xi}}{\mathrm{d}\mathbb{M}_{T,\xi}}(\omega) &\ge \sqrt{ \frac{1-C\alpha}{1+C\alpha} } \left[ \Phi\left( -\sqrt{1+C\alpha}\,v \right) - \Phi\left( -\sqrt{1+C\alpha}\,(L_T+v) \right) \right]. \end{align}\] The case \(v\le0\) is symmetric and yields the same bound with \(|v|\) in place of \(v\).

Since \(\Phi(-x)\) is decreasing, uniformly over \(|v|\le L_T/2\), \[\frac{ \Phi\left( -\sqrt{1+C\alpha}(L_T+|v|) \right) }{ \Phi\left( -\sqrt{1+C\alpha}|v| \right) } \leq \frac{\Phi\left(-\sqrt{1+C\alpha} L_T\right)}{ \Phi\left(-\sqrt{1+C\alpha}L_T/2\right)} = o_T(1).\] Moreover, note \(\frac{\mathrm{d}}{\mathrm{d}t} \log \Phi(-t) = -\frac{\phi(t)}{\Phi(-t)}\). By Mills ratio bound \(\Phi(-t)\geq \frac{t}{1+t^2}\phi(t)\), we have \[\begin{align} \log \frac{\Phi\left(-\sqrt{1+C\alpha}\,v\right)}{\Phi\left(-v\right)} &= -\int^{\sqrt{1+C\alpha}\,v}_v \frac{\phi(t)}{\Phi(-t)} \mathrm{d}t \\ &\geq -\int^{\sqrt{1+C\alpha}\,v}_v (t+\frac{1}{t}) \mathrm{d}t \\ &= -\frac{1+C\alpha-1}{2}v^2 - \log\left(\sqrt{1+C\alpha}\right) \end{align}\] And note \((1+C\alpha)^{-1/2}\geq 1-\frac{C}{2}\alpha\). Hence there exists \(C_2=C/2<\infty\) such that, for all sufficiently small \(\alpha\) and all \(v>0\), \[\Phi\left( -\sqrt{1+C\alpha}\,v \right) \ge (1-C_2\alpha) \exp\{-C_2\alpha v^2\} \Phi(-v).\]

Finally, uniformly over \(|v|\le L_T/2\), \[\begin{align} \frac{\mathrm{d}\mathbb{N}_{T,\xi}}{\mathrm{d}\mathbb{M}_{T,\xi}}(\omega) &\ge \sqrt{ \frac{1-C\alpha}{1+C\alpha} } \left[ \Phi\left( -\sqrt{1+C\alpha}\,|v| \right) - \Phi\left( -\sqrt{1+C\alpha}\,(L_T+|v|) \right) \right] \\ &= \sqrt{ \frac{1-C\alpha}{1+C\alpha} } \Phi\left( -\sqrt{1+C\alpha}\,|v| \right) \left[ 1 - \frac{\Phi\left( -\sqrt{1+C\alpha}\,(L_T+|v|) \right)}{\Phi\left( -\sqrt{1+C\alpha}\,|v| \right)}\right] \\ &\geq \left( 1- o_T(1) \right) \sqrt{ \frac{1-C\alpha}{1+C\alpha} } (1-C_2\alpha) \exp\{-C_2\alpha v^2\} \Phi(-|v|). \end{align}\] Moreover, for all sufficiently small \(\alpha\), there exists \(C_3<\infty\) such that \(\sqrt{\frac{1-C\alpha}{1+C\alpha}} \ge 1-C_3\alpha\). Consequently, \[\begin{align} \frac{\mathrm{d}\mathbb{N}_{T,\xi}}{\mathrm{d}\mathbb{M}_{T,\xi}}(\omega) &\ge (1-o_T(1)) (1-C_2\alpha)(1-C_3\alpha) \exp\left\{ -C_2\alpha v^2 \right\} \Phi\left( -|v| \right). \end{align}\] Since \(|v| \le \frac{L_T}{2} = \frac{D\alpha\sqrt T}{4}\), there exists \(C_4<\infty\) such that \(C_2\alpha v^2 \le C_4D^2\alpha^3T\). Choose \(\alpha\) sufficiently small such that \(C_4D^2\alpha \le \varepsilon\). Then \[\exp\{ -C_2\alpha v^2 \} \ge \exp\left\{ -\varepsilon\alpha^2T \right\}.\] Shrinking \(\alpha\) further and then taking \(T\) sufficiently large to obtain \((1-o_T(1)) (1-C_2\alpha)(1-C_3\alpha)>(1-\varepsilon)\). This proves ?? . ◻

Proof. Let \[C:=\{|V|\le a\}, \qquad D:=\{|V|\le B\}.\] Since \(w(V)\le w(a)\) on \(D\setminus C\), \[\begin{align} \int_D\varphi w(V)\,\mathrm{d}\mathfrak m &\le \int_C\varphi w(V)\,\mathrm{d}\mathfrak m + w(a) \int_{D\setminus C}\varphi\,\mathrm{d}\mathfrak m. \end{align}\] The budget and central-mass assumptions imply \[\begin{align} \int_{D\setminus C}\varphi\,\mathrm{d}\mathfrak m &\le \int_{C^c}\varphi\,\mathrm{d}\mathfrak m\\ &\le \mathfrak m(C) - \int_C\varphi\,\mathrm{d}\mathfrak m\\ &= \int_C(1-\varphi)\,\mathrm{d}\mathfrak m. \end{align}\] Since \(w(V)\ge w(a)\) on \(C\), \[w(a) \int_C(1-\varphi)\,\mathrm{d}\mathfrak m \le \int_C (1-\varphi)w(V) \,\mathrm{d}\mathfrak m.\] Therefore, \[\begin{align} \int_D\varphi w(V)\,\mathrm{d}\mathfrak m &\le \int_C\varphi w(V)\,\mathrm{d}\mathfrak m + \int_C(1-\varphi)w(V)\,\mathrm{d}\mathfrak m\\ &= \int_Cw(V)\,\mathrm{d}\mathfrak m. \end{align}\] Consequently, \[\begin{align} \int_D(1-\varphi)w(V)\,\mathrm{d}\mathfrak m &= \int_Dw(V)\,\mathrm{d}\mathfrak m - \int_D\varphi w(V)\,\mathrm{d}\mathfrak m\\ &\ge \int_Dw(V)\,\mathrm{d}\mathfrak m - \int_Cw(V)\,\mathrm{d}\mathfrak m\\ &= \int_{D\setminus C} w(V) \,\mathrm{d}\mathfrak m, \end{align}\] which proves ?? . ◻

Proof. Define a finite measure \(\mathfrak m_T\) by \[\begin{align} \int F(\xi,\omega)\, \mathfrak m_T(\mathrm{d}\xi,\mathrm{d}\omega) &:= \int_{\mathcal{C}_\rho} \int_{\mathcal{H}_T^\xi} F(\xi,\omega) \,\mathbb{M}_{T,\xi}(\mathrm{d}\omega)\, \Lambda_\rho(\mathrm{d}\xi) \end{align}\] for every nonnegative measurable function \(F\). Let \[V(\xi,\omega) := V_{T,\xi}(\omega), \qquad \varphi(\xi,\omega) := \psi_?^\xi(\omega).\]

By the abstention representation ?? , the constraint \(\mathcal{A}_T^{Q_{\rho,\bar\delta_\alpha}}(\psi)\le\alpha\) implies \[\int \varphi \,\mathrm{d}\mathfrak m_T \le \frac{\alpha\sqrt T}{2}.\] On the other hand, by ?? and \(\Lambda_\rho(\mathcal{C}_\rho)=c_\rho/2\), \[\begin{align} \mathfrak m_T(|V|\le a_T) &= \int_{\mathcal{C}_\rho} \mathbb{M}_{T,\xi} \left( |V_{T,\xi}|\le a_T \right) \,\Lambda_\rho(\mathrm{d}\xi)\\ &\ge 2(1-\varepsilon)a_T \Lambda_\rho(\mathcal{C}_\rho)\\ &= (1-\varepsilon)c_\rho a_T\\ &= \frac{1-\varepsilon}{1-3\varepsilon} \frac{\alpha\sqrt T}{2}\\ &> \frac{\alpha\sqrt T}{2}. \end{align}\] Intuitively, this means the central set \(\{|V|\le a_T\}\) has enough \(\mathfrak m_T\)-mass to contain the entire abstention budget.

By the overlap lower bound ?? , \[\begin{align} \mathcal{E}_T^{Q_{\rho,\bar\delta_\alpha}}(\psi) &\ge \frac{2}{\sqrt T} \int_{\mathcal{C}_\rho} \int_{\mathcal{H}_T^\xi} \bigl(1-\psi_?^\xi(\omega)\bigr) \,\mathbb{N}_{T,\xi}(\mathrm{d}\omega)\, \Lambda_\rho(\mathrm{d}\xi). \end{align}\] Restricting the integral to \(\{|V_{T,\xi}|\le L_T/2\}\) and applying ?? yields \[\begin{align} \mathcal{E}_T^{Q_{\rho,\bar\delta_\alpha}}(\psi) &\ge \frac{2}{\sqrt T} \int_{\mathcal{C}_\rho} \int_{\{|V_{T,\xi}|\le L_T/2\}} \bigl(1-\psi_?^\xi(\omega)\bigr) \,\mathbb{N}_{T,\xi}(\mathrm{d}\omega)\, \Lambda_\rho(\mathrm{d}\xi) \\ &= \frac{2}{\sqrt T} \int_{\mathcal{C}_\rho} \int_{\{|V_{T,\xi}|\le L_T/2\}} \bigl(1-\psi_?^\xi(\omega)\bigr) \,\frac{\mathrm{d}\mathbb{N}_{T,\xi}}{\mathrm{d}\mathbb{M}_{T,\xi}}\mathbb{M}_{T,\xi}(\mathrm{d}\omega)\, \Lambda_\rho(\mathrm{d}\xi) \\ &\ge \frac{2(1-\varepsilon)}{\sqrt T} \exp\{ -\varepsilon\alpha^2T -o_T(\alpha^2T) \} \int_{\{|V|\le L_T/2\}} (1-\varphi) \Phi(-|V|) \,\mathrm{d}\mathfrak m_T. \end{align}\]

Apply Lemma 31 with \[w(v):=\Phi(-|v|), \qquad a=a_T, \qquad B=L_T/2, \qquad b=\frac{\alpha\sqrt T}{2}.\] The budget and central-mass conditions were verified above. Therefore, \[\begin{align} \int_{\{|V|\le L_T/2\}} (1-\varphi) \Phi(-|V|) \,\mathrm{d}\mathfrak m_T &\ge \int_{\{a_T<|V|\le L_T/2\}} \Phi(-|V|) \,\mathrm{d}\mathfrak m_T\\ &= \int_{\mathcal{C}_\rho} \int_{\{a_T<|V_{T,\xi}|\le L_T/2\}} \Phi\bigl(-|V_{T,\xi}(\omega)|\bigr) \,\mathbb{M}_{T,\xi}(\mathrm{d}\omega)\, \Lambda_\rho(\mathrm{d}\xi) \\ &\stackrel{(a)}{\geq} \exp\{-o_T(\alpha^2T)\} 2(1-\varepsilon) \Lambda_\rho(\mathcal{C}_\rho) \int_{a_T}^{L_T/2} \Phi(-u) \,\mathrm{d}u\\ &= \exp\{-o_T(\alpha^2T)\} (1-\varepsilon)c_\rho \int_{a_T}^{L_T/2} \Phi(-u) \,\mathrm{d}u. \end{align}\] where \((a)\) is by ?? and \(\Lambda_\rho(\mathcal{C}_\rho)=c_\rho/2\). Consequently, \[\begin{align} \mathcal{E}_T^{Q_{\rho,\bar\delta_\alpha}}(\psi) &\ge \exp\{ -\varepsilon\alpha^2T -o_T(\alpha^2T) \} \frac{ 2(1-\varepsilon)^2c_\rho }{ \sqrt T } \int_{a_T}^{L_T/2} \Phi(-u) \,\mathrm{d}u. \end{align}\]

Finally, the choice of \(D\) implies \(\frac{L_T}{2}>2a_T\). Since \(a_T\to\infty\) for every fixed \(\alpha>0\), Gaussian tail asymptotics give \[\int_{a_T}^{L_T/2} \Phi(-u) \,\mathrm{d}u = (1-o_T(1)) \int_{a_T}^{\infty} \Phi(-u) \,\mathrm{d}u.\] Absorbing the factor \(1-o_T(1)\) into \(\exp\{-o_T(\alpha^2T)\}\) proves ?? . ◻

Proof. Condition on the terminal history \(\mathcal{F}_T\). If the algorithm recommends \(\widehat b_T\), then \[\mathbb{P}(a^\star\neq \widehat b_T\mid\mathcal{F}_T) \le \sum_{j\neq \widehat b_T} \varPi_T(\mu_j\ge \mu_{\widehat b_T}).\] By the definition of \(R_T\), \[\max_{j\neq\widehat b_T} \varPi_T(\mu_j\ge \mu_{\widehat b_T}) = e^{-R_T}.\] Therefore \[\mathbb{P}(a^\star\neq \widehat b_T\mid\mathcal{F}_T) \le (K-1)e^{-R_T}.\] On the event that the algorithm does not abstain, the terminal quantile rule implies \(R_T\ge r_{T,\alpha}\). Hence \[\begin{align} \mathcal{E}_T(\mathrm{\small IC-PGWS}(\alpha)) = \mathbb{E}\!\left[ \mathbb{1}\{\widehat a_T\neq ?\} \mathbb{P}(a^\star\neq \widehat b_T\mid\mathcal{F}_T) \right] \le (K-1)e^{-r_{T,\alpha}}. \end{align}\] ◻

Proof. The forced-exploration rule implies \[N_i(t)\to\infty \qquad\text{a.s. for every }i.\] Conditional on \(\mu_i\), the observations from arm \(i\) are i.i.d. from \(P_{\mu_i}\). Since the log-partition function is finite on an open natural-parameter space, the natural statistic has finite mean under \(P_{\mu_i}\), and \[\mathbb{E}_{\mu_i}[t(X)] = A'(\theta(\mu_i)).\] Therefore, by the strong law of large numbers, \[\widehat{t}_i(t) = \frac{1}{N_i(t)} \sum_{r\le t:A_r=i}t(X_r) \to A'(\theta(\mu_i)) \qquad\text{a.s.}\] Because \(\theta(\mu_i)\in\Theta\) and \(\Theta\) is open, \(A'(\theta(\mu_i))\in A'(\Theta)\). Hence \(\widehat{t}_i(t)\in A'(\Theta)\) eventually almost surely. On this eventual event, \[\widehat\theta_i(t) = (A')^{-1}\!\left(\widehat{t}_i(t)\right) \to \theta(\mu_i),\] since \(A''>0\) implies that \(A'\) is strictly increasing and continuous. Thus \[\widehat \eta_i(t) = \beta^{-1}(\widehat\theta_i(t)) \to \beta^{-1}(\theta(\mu_i)) = s(\mu_i) = \eta_i.\] Continuity of \(s^{-1}\) gives \[\widehat \mu_i(t)=s^{-1}(\widehat \eta_i(t))\to \mu_i.\] ◻

Proof. By Lemma 34, \[\widehat \eta_i(t)\to \eta_i \qquad\text{for every }i.\] Since the prior densities are continuous, ties have probability zero. Thus the best arm and the second-best arm are unique almost surely. On this probability-one event, \(\widehat b_t=b^\star\) eventually, and \[\widehat\Delta_{j,s}(t)\to\Delta_{j,s}, \qquad \widehat\Gamma_{s,t}\to\Gamma_s.\] Therefore \[w_i(t)\to w_i^\dagger(\eta), \qquad p_i(t)\to p_i^\dagger(\eta) \qquad\text{a.s. for every }i.\]

Now fix an arm \(i\). We take four steps:

Step 1: Forced exploration is negligible. Let \(F_i(T)\) be the number of forced-exploration pulls of arm \(i\) up to time \(T\). If the \(m\)-th forced pull of arm \(i\) occurs before time \(T\), then immediately before that pull, \(N_i(t)\ge m-1\). But a forced pull of arm \(i\) can occur only if \(N_i(t)<\sqrt{t+1}\le \sqrt{T+1}\). Hence \(m-1<\sqrt{T+1}\), and therefore \(F_i(T)\le \lceil \sqrt{T+1}\rceil+1\). Consequently, \[\frac{F_i(T)}{T}\to0.\] Let \(F(T)\) be the total number of forced-exploration rounds up to time \(T\). Since \(F(T)=\sum_{\ell=1}^K F_\ell(T)\), we also have \[\frac{F(T)}{T}\le \frac{K(\lceil\sqrt{T+1}\rceil+1)}{T} \to0.\]

Step 2: Martingale concentration on non-forced rounds. Let \(\mathcal{F}_t\) be the history before round \(t+1\), and define \(B_t := \mathbb{1}\{\text{round }t+1\text{ is non-forced}\}\). The event \(\{B_t=1\}\) is \(\mathcal{F}_t\)-measurable. On non-forced rounds, the algorithm samples arm \(i\) with conditional probability \(p_i(t)\).

Define \(D_{i,t+1} := B_t\Bigl(\mathbb{1}\{A_{t+1}=i\}-p_i(t)\Bigr)\). Then \(\mathbb{E}[D_{i,t+1}\mid \mathcal{F}_t]=0\), so \((D_{i,t+1})_{t\ge0}\) is a martingale difference sequence. Also, \(|D_{i,t+1}|\le1\).

Therefore, by Azuma’s inequality, for every \(\varepsilon>0\), \[\mathbb{P}\left( \left| \frac{1}{T}\sum_{t=0}^{T-1}D_{i,t+1} \right| \ge \varepsilon \right) \le 2\exp\left(-\frac{\varepsilon^2T}{2}\right).\] The right-hand side is summable in \(T\). Hence, by the Borel–Cantelli lemma, \[\frac{1}{T}\sum_{t=0}^{T-1}D_{i,t+1}\to0 \qquad\text{almost surely}.\]

Step 3: Decomposition of the empirical pull count. The total number of pulls of arm \(i\) can be decomposed as \[N_i(T) = F_i(T) + \sum_{t=0}^{T-1} B_t\mathbb{1}\{A_{t+1}=i\}.\] Using the definition of \(D_{i,t+1}\), we have \(B_t\mathbb{1}\{A_{t+1}=i\} = D_{i,t+1}+B_t p_i(t)\). Thus \[\frac{N_i(T)}{T} = \frac{F_i(T)}{T} + \frac{1}{T}\sum_{t=0}^{T-1}D_{i,t+1} + \frac{1}{T}\sum_{t=0}^{T-1}B_t p_i(t).\] By Steps 1 and 2, \[\frac{N_i(T)}{T} - \frac{1}{T}\sum_{t=0}^{T-1}B_t p_i(t) \to0 \qquad\text{almost surely}.\]

Step 4: Cesàro convergence of the target probabilities. Since \[p_i(t)\to p_i^\dagger(\eta) \qquad\text{almost surely},\] the sequence \(\{p_i(t)\}\) is Cesàro convergent, i.e., \[\frac{1}{T}\sum_{t=0}^{T-1}p_i(t) \to p_i^\dagger(\eta) \qquad\text{almost surely}.\]

Now write \[\frac{1}{T}\sum_{t=0}^{T-1}B_t p_i(t) = \frac{1}{T}\sum_{t=0}^{T-1}p_i(t) - \frac{1}{T}\sum_{t=0}^{T-1}(1-B_t)p_i(t).\] Since \(0\le p_i(t)\le1\), \[0\le \frac{1}{T}\sum_{t=0}^{T-1}(1-B_t)p_i(t) \le \frac{1}{T}\sum_{t=0}^{T-1}(1-B_t) = \frac{F(T)}{T} \to0.\] Hence \[\frac{1}{T}\sum_{t=0}^{T-1}B_t p_i(t) \to p_i^\dagger(\eta) \qquad\text{almost surely}.\] Combining this with Step 3 gives the desired result. ◻

Proof. Set \[\eta_i=s(\mu_i), \qquad \theta_i:=\theta(\mu_i)=\beta(\eta_i), \qquad m_i:=A'(\theta_i),\] and write \[\bar m_n:=\frac{1}{n}\sum_{r=1}^nt(X_{i,r}).\]

For \(\eta\in\mathcal{H}\), write \[p_\eta(w) := \frac{\mathrm{d}P_{s^{-1}(\eta)}}{\mathrm{d}\lambda}(w) = \exp\{\beta(\eta)t(w)-A(\beta(\eta))\}h(w).\] Consider a realized full adaptive history \(h_t=(a_1,x_1,\ldots,a_t,x_t)\), For a candidate parameter vector \(\boldsymbol{\eta}=(\eta_1,\ldots,\eta_K)\in\mathcal{H}^K\), the density of this realized history under the policy \(\pi\), with respect to counting measure on actions and \(\lambda^{\otimes t}\) on rewards, is \[L_t^\pi(\boldsymbol{\eta};h_t) = \prod_{r=1}^t \pi_r(a_r\mid h_{r-1}) \prod_{r=1}^t p_{\eta_{a_r}}(x_r).\] Here \(\pi_r(a_r\mid h_{r-1})\) is the sampling probability assigned by the policy to the realized action \(a_r\) after the realized past \(h_{r-1}\).

Using the product prior in information coordinates, the posterior density of \(\boldsymbol{\eta}\) is therefore proportional to \[\prod_{\ell=1}^K \bar f_\ell(\eta_\ell) \prod_{r:a_r=\ell} p_{\eta_\ell}(x_r).\] Thus the posterior factorizes arm by arm. In particular, the marginal posterior of arm \(i\) depends only on the rewards observed from arm \(i\). If these rewards are denoted \(X_{i,1},\ldots,X_{i,n}\), then, for every measurable set \(B\subseteq\mathcal{H}\), \[\varPi_{i,n}(B) = \frac{ \int_B \bar f_i(\eta) \prod_{r=1}^n p_\eta(X_{i,r}) \,\mathrm{d}\eta }{ \int_{\mathcal{H}} \bar f_i(\eta) \prod_{r=1}^n p_\eta(X_{i,r}) \,\mathrm{d}\eta }.\] Substituting the exponential-family density gives \[\prod_{r=1}^n p_\eta(X_{i,r}) = \exp\left\{ \beta(\eta)\sum_{r=1}^nt(X_{i,r}) - nA(\beta(\eta)) \right\} \prod_{r=1}^n h(X_{i,r}).\] \(\prod_{r=1}^n h(X_{i,r})\) does not depend on \(\eta\), so it also cancels between numerator and denominator. Bayes’ rule gives \[\varPi_{i,n}(B) = \frac{ \int_B \bar f_i(\eta) \exp\{n[\beta(\eta)\bar m_n-A(\beta(\eta))]\} \,\mathrm{d}\eta }{ \int_{\mathcal{H}} \bar f_i(\eta) \exp\{n[\beta(\eta)\bar m_n-A(\beta(\eta))]\} \,\mathrm{d}\eta }.\] Multiplying both numerator and denominator by \[\exp\{-n[\beta(\eta_i)\bar m_n-A(\beta(\eta_i))]\}\] allows us to write \[\varPi_{i,n}(B) = \frac{ \int_B \bar f_i(\eta)e^{nL_n(\eta)}\,\mathrm{d}\eta }{ Z_n },\] where \[L_n(\eta) := (\beta(\eta)-\beta(\eta_i))\bar m_n - A(\beta(\eta)) + A(\beta(\eta_i))\] and \[Z_n := \int_{\mathcal{H}}\bar f_i(\eta)e^{nL_n(\eta)}\,\mathrm{d}\eta.\] Note \(L_n(\eta_i)=0\) and \[L_n(\eta)\to (\beta(\eta)-\beta(\eta_i))A'(\beta(\eta_i)) - A(\beta(\eta))+A(\beta(\eta_i)) = -D(\mu_i,s^{-1}(\eta))=-I_i(\eta)\] on compact subsets of \(\mathcal{H}\).

We first prove that \[\label{eq:one-arm-denominator-rate-simple-upper} \frac{1}{n}\log Z_n\to0.\tag{58}\]

For the lower bound on \(Z_n\), fix \(\tau>0\). Since \(\bar m_n\to m_i\), \(L_n(\eta)\to -I_i(\eta)\) uniformly on compact neighborhoods of \(\eta_i\).

Since \(I_i(\eta_i)=0\), choose a compact interval \(J_\tau\Subset\mathcal{H}\) containing \(\eta_i\) such that, for all sufficiently large \(n\), \(\inf_{\eta\in J_\tau}L_n(\eta)\ge -\tau\).

By continuity and strict positivity of \(\bar f_i\), \[\int_{J_\tau}\bar f_i(\eta)\,\mathrm{d}\eta>0.\] Therefore \[Z_n \ge \int_{J_\tau}\bar f_i(\eta)e^{nL_n(\eta)}\,\mathrm{d}\eta \ge e^{-n\tau}\int_{J_\tau}\bar f_i(\eta)\,\mathrm{d}\eta.\] Thus \[\liminf_{n\to\infty}\frac{1}{n}\log Z_n\ge -\tau.\] Letting \(\tau\downarrow0\) gives \[\liminf_{n\to\infty}\frac{1}{n}\log Z_n\ge0.\]

For the upper bound on \(Z_n\), for all large \(n\) we have \(\bar m_n\in A'(\Theta)\). Define the pseudo-MLE \[\theta_n:=(A')^{-1}(\bar m_n), \qquad \eta_n:=\beta^{-1}(\theta_n).\] Then \(\theta_n\to\theta_i\) and \(\eta_n\to \eta_i\). Moreover, using \(\bar m_n=A'(\theta_n)\), \[\begin{align} L_n(\eta_n)-L_n(\eta) &= (\theta_n-\beta(\eta))A'(\theta_n) - A(\theta_n) + A(\beta(\eta)) \\ &= D(s^{-1}(\eta_n),s^{-1}(\eta)). \end{align}\] Therefore, by assumption 44 , \[L_n(\eta) \le L_n(\eta_n)-\widetilde{c}\,(\eta-\eta_n)^2.\] Since \[L_n(\eta_n) = D(s^{-1}(\eta_n),\mu_i) \to0,\] boundedness of \(\bar f_i\) gives \[\begin{align} Z_n &\le \|\bar f_i\|_\infty e^{nL_n(\eta_n)} \int_{\mathcal{H}}e^{-n\widetilde{c} (\eta-\eta_n)^2}\,\mathrm{d}\eta \\ &\le \|\bar f_i\|_\infty e^{nL_n(\eta_n)} \sqrt{\frac{\pi}{n\widetilde{c}}}. \end{align}\] Hence \[\limsup_{n\to\infty}\frac{1}{n}\log Z_n\le0.\] This proves 58 .

Now fix a compact interval \(K\Subset\mathcal{H}\). Since \(\bar m_n\to m_i\), \[L_n(\eta)\to -D(\mu_i,s^{-1}(\eta))=-I_i(\eta)\] uniformly on \(K\). Hence \[\begin{align} \limsup_{n\to\infty} \frac{1}{n}\log \int_K \bar f_i(\eta)e^{nL_n(\eta)}\,\mathrm{d}\eta &\le -\inf_{\eta\in K}I_i(\eta). \end{align}\] Combining this numerator bound with 58 gives the compact-interval upper bound.

Next let \(G\subseteq\mathcal{H}\) be a nonempty open interval. Choose \(\eta_0\in G\) such that \[I_i(\eta_0)\le \inf_{\eta\in G}I_i(\eta)+\tau.\] Choose a compact interval \(J\Subset G\) containing \(\eta_0\) and small enough that \[\sup_{\eta\in J}I_i(\eta)\le I_i(\eta_0)+\tau.\] By uniform convergence of \(L_n\) on \(J\) and strict positivity of \(\bar f_i\) on \(J\), \[\begin{align} \liminf_{n\to\infty} \frac{1}{n}\log \int_G \bar f_i(\eta)e^{nL_n(\eta)}\,\mathrm{d}\eta &\ge \liminf_{n\to\infty} \frac{1}{n}\log \int_J \bar f_i(\eta)e^{nL_n(\eta)}\,\mathrm{d}\eta \\ &\ge -\sup_{\eta\in J}I_i(\eta) \ge -\inf_{\eta\in G}I_i(\eta)-2\tau. \end{align}\] Using again the denominator rate 58 , and then letting \(\tau\downarrow0\), gives the open-interval lower bound.

It remains to prove the one-sided estimates. Consider \(a<\eta_i\). Since \(\eta_n\to \eta_i\), eventually \(a<\eta_n\). The function \(\theta\mapsto \theta\bar m_n-A(\theta)\) is strictly concave and maximized at \(\theta_n\). Since \(\beta\) is strictly increasing, \(L_n(\eta)\) is increasing on \(\{\eta<\eta_n\}\). Therefore, for all large \(n\), \[\sup_{\eta\le a}L_n(\eta)=L_n(a).\] Thus \[\varPi_{i,n}(\eta\le a) \le \frac{e^{nL_n(a)}}{Z_n},\] because \(\int_{\{\eta\le a\}}\bar f_i(\eta)\,\mathrm{d}\eta\le1\). Since \(L_n(a)\to -I_i(a)\) and \(n^{-1}\log Z_n\to0\), we obtain \[\limsup_{n\to\infty} \frac{1}{n}\log\varPi_{i,n}(\eta\le a) \le -I_i(a).\] The proof for \(b>\eta_i\) is identical: eventually \(b>\eta_n\), \(L_n\) is decreasing on \(\{\eta>\eta_n\}\), and hence \[\sup_{\eta\ge b}L_n(\eta)=L_n(b).\] This gives the upper-tail estimate. ◻

Proof. Write \[\eta_i=s(\mu_i), \qquad \eta_j=s(\mu_j), \qquad \eta_i>\eta_j.\] Recall from the proof of Lemma 36 that, conditional on the realized history, the arm-wise posterior of \(\eta_i=s(\mu_i)\) is \[\varPi_{i,T}(\mathrm{d}\eta) = \frac{ \bar f_i(\eta) \exp\{\beta(\eta)S_i(T)-N_i(T)A(\beta(\eta))\} }{ Z_{i,T} }\,\mathrm{d}\eta,\] where \[Z_{i,T} := \int_{\mathcal{H}} \bar f_i(u) \exp\{\beta(u)S_i(T)-N_i(T)A(\beta(u))\} \,\mathrm{d}u .\] Because the prior is a product prior and the likelihood factors arm by arm, the full posterior factorizes: \[\varPi_T(\mathrm{d}\eta_1,\ldots,\mathrm{d}\eta_K) = \bigotimes_{\ell=1}^K \varPi_{\ell,T}(\mathrm{d}\eta_\ell).\] Consequently, let \(U\sim\varPi_{i,T}\) and \(V\sim\varPi_{j,T}\) denote the posterior information coordinate qualities (arm parameter) of arms \(i\) and \(j\), then \(U\) and \(V\) are independent under the posterior, and for Borel sets \(B,C\subseteq\mathcal{H}\), \[\varPi_T(U\in B,\;V\in C) = \varPi_{i,T}(B)\varPi_{j,T}(C).\] In particular, \[\varPi_T(\mu_j\ge \mu_i) = \varPi_T(\eta_j\ge \eta_i) = \varPi_T(V\ge U).\] Define \[I_i(u):=D(\mu_i,s^{-1}(u)), \qquad I_j(v):=D(\mu_j,s^{-1}(v)),\] and \[C_{ij} := \inf_{w\in[\eta_j,\eta_i]} \{q_iI_i(w)+q_jI_j(w)\}.\] The one-arm bounds on \(\log \varPi_{i,n}\) of Lemma 36 hold along every subsequence \(n\to\infty\) on the arm-wise strong-law event. Therefore they also hold along the random subsequences \(N_i(T)\) and \(N_j(T)\). Multiplying the one-arm exponents by \(N_i(T)/T\to q_i\) and \(N_j(T)/T\to q_j\) gives the corresponding \(T\)-speed bounds: For intervals \(B,C\), \[\limsup_{T\to\infty} \frac{1}{T}\log\{\varPi_{i,T}(B)\varPi_{j,T}(C)\} \le -q_i\inf_{u\in B}I_i(u)-q_j\inf_{v\in C}I_j(v)\] when \(B,C\) are compact, and the corresponding lower bound when \(B,C\) are open.

We first prove the lower bound for ?? . Let \(w^\star\in[\eta_j,\eta_i]\) be a minimizer of \[w\mapsto q_iI_i(w)+q_jI_j(w).\] If \(w^\star\in(\eta_j,\eta_i)\), choose \(\delta>0\) so small that \[(w^\star-\delta,w^\star) \times (w^\star,w^\star+\delta) \subseteq \{(u,v):v\ge u\}.\] Then, by posterior product decomposition and the open-interval lower bounds in Lemma 36, \[\begin{align} \liminf_{T\to\infty} \frac{1}{T}\log \varPi_T(V\ge U) &\ge -q_i\inf_{u\in(w^\star-\delta,w^\star)}I_i(u) -q_j\inf_{v\in(w^\star,w^\star+\delta)}I_j(v). \end{align}\] Letting \(\delta\downarrow0\) gives \[\liminf_{T\to\infty} \frac{1}{T}\log \varPi_T(V\ge U) \ge -C_{ij}.\] If \(w^\star=\eta_j\), use instead the rectangle \(U\in(\eta_j-\delta,\eta_j)\) and \(V\in(\eta_j,\eta_j+\delta)\). Since \[\inf_{u\in(\eta_j-\delta,\eta_j)} I_i(u)\to I_i(\eta_j), \qquad \inf_{v\in(\eta_j,\eta_j+\delta)} I_j(v)\to I_j(\eta_j)=0,\] the same lower bound follows.

Similarly if \(w^\star=\eta_i\), use \(U\in(\eta_i-\delta,\eta_i)\) and \(V\in(\eta_i,\eta_i+\delta)\). Then \[\inf_{u\in(\eta_i-\delta,\eta_i)} I_i(u)\to I_i(\eta_i)=0, \qquad \inf_{v\in(\eta_i,\eta_i+\delta)} I_j(v)\to I_j(\eta_i),\] and the same lower bound again follows. Thus \[\liminf_{T\to\infty} \frac{1}{T}\log \varPi_T(V\ge U) \ge -C_{ij}.\]

For the upper bound, decompose \[\{V\ge U\} \subseteq E_-\cup E_0\cup E_+,\] where \(E_-:=\{U\le \eta_j\}\), \(E_+:=\{V\ge \eta_i\}\) and \(E_0:=\{\eta_j\le U\le V\le \eta_i\}\).

The one-sided estimates in Lemma 36 give \[\limsup_{T\to\infty} \frac{1}{T}\log\varPi_T(E_-) \le -q_i I_i(\eta_j) = -q_iD(\mu_i,\mu_j),\] and \[\limsup_{T\to\infty} \frac{1}{T}\log\varPi_T(E_+) \le -q_j I_j(\eta_i) = -q_jD(\mu_j,\mu_i).\] Since \(C_{ij}\le q_iD(\mu_i,\mu_j)\), by taking \(w=\eta_j\), and \(C_{ij}\le q_jD(\mu_j,\mu_i)\), by taking \(w=\eta_i\), both endpoint events have exponent at least \(C_{ij}\).

It remains to control \(E_0\). The set \(K_0:=\{(u,v):\eta_j\le u\le v\le \eta_i\}\) is compact. Fix \(\tau>0\). By continuity of \((u,v)\mapsto q_iI_i(u)+q_jI_j(v)\) on the compact square \([\eta_j,\eta_i]^2\), there exist finitely many compact rectangles \[R_m=I_m\times J_m,\qquad m=1,\ldots,M,\] whose union covers \(K_0\), such that each \(R_m\subseteq[\eta_j,\eta_i]^2\) and \[\inf_{(u,v)\in R_m} \{q_iI_i(u)+q_jI_j(v)\} \ge \inf_{(u,v)\in K_0} \{q_iI_i(u)+q_jI_j(v)\} -\tau .\] By posterior product decomposition, \[\varPi_T(E_0) \le \sum_{m=1}^M \varPi_{i,T}(I_m)\varPi_{j,T}(J_m),\] where \(\varPi_{i,T}\) and \(\varPi_{j,T}\) are the corresponding arm-wise posterior marginals. Applying the compact-interval upper bound from Lemma 36 along the subsequences \(N_i(T)\) and \(N_j(T)\), we get, for each \(m\), \[\begin{align} \limsup_{T\to\infty} \frac{1}{T}\log\{\varPi_{i,T}(I_m)\varPi_{j,T}(J_m)\} &\le -q_i\inf_{u\in I_m}I_i(u) -q_j\inf_{v\in J_m}I_j(v) \\ &= -\inf_{(u,v)\in R_m} \{q_iI_i(u)+q_jI_j(v)\}. \end{align}\] Since the cover is finite, the union bound yields \[\begin{align} \limsup_{T\to\infty} \frac{1}{T}\log\varPi_T(E_0) &\le - \inf_{(u,v)\in K_0} \{q_iI_i(u)+q_jI_j(v)\} +\tau . \end{align}\] Letting \(\tau\downarrow0\), we obtain \[\limsup_{T\to\infty} \frac{1}{T}\log\varPi_T(E_0) \le - \inf_{\eta_j\le u\le v\le \eta_i} \{q_iI_i(u)+q_jI_j(v)\}.\]

We now reduce this infimum to the diagonal (\(u=v\)). Note the derivative \[\frac{\partial }{\partial z} D(\mu,z) = \theta'(z)\left[ A'(\theta(z))-A'(\theta(\mu)) \right],\] is negative for \(z<\mu\) and positive for \(z>\mu\). Hence, on the interval \([\eta_j,\eta_i]\), the map \(u\mapsto I_i(u)\) is non-increasing whereas \(v\mapsto I_j(v)\) is non-decreasing. Therefore, if \(u\le v\), then for every \(w\in[u,v]\), \(I_i(w)\le I_i(u)\) and \(I_j(w)\le I_j(v)\).

Thus every feasible off-diagonal point can be moved to a diagonal point with no larger objective. Hence \[\inf_{\eta_j\le u\le v\le \eta_i} \{q_iI_i(u)+q_jI_j(v)\} = \inf_{w\in[\eta_j,\eta_i]} \{q_iI_i(w)+q_jI_j(w)\} = C_{ij}.\] Combining the bounds for \(E_-\), \(E_0\), and \(E_+\) by a union bound gives \[\limsup_{T\to\infty} \frac{1}{T}\log \varPi_T(V\ge U) \le -C_{ij}.\] Together with the lower bound, \[-\frac{1}{T}\log\varPi_T(V\ge U)\to C_{ij}.\] Returning to \(z=s^{-1}(w)\) proves the claimed formula. ◻

Proof. By Lemma 34, \(\widehat b_T=b^\star\) eventually almost surely. By Lemma 35, \[\frac{N_i(T)}{T}\to p_i^\dagger(\eta) \qquad\text{for every }i.\] Since \(p_i^\dagger(\eta)>0\) for every arm, applying Lemma 37 with \(i=b^\star\) and each \(j\neq b^\star\) gives \[-\frac{1}{T} \log \varPi_T(\mu_j\ge \mu_{b^\star}) \to \inf_{z\in[\mu_j,\mu_{b^\star}]} \left\{ p_{b^\star}^\dagger(\eta) D(\mu_{b^\star},z) + p_j^\dagger(\eta) D(\mu_j,z) \right\}.\] Taking the minimum over the finite set \(j\neq b^\star\) yields \[\frac{R_T}{T} = \min_{j\neq b^\star} \left\{ -\frac{1}{T}\log \varPi_T(\mu_j\ge \mu_{b^\star}) \right\} \to C^\dagger(\mu).\] ◻

Proof. For the top-two gap expansion, condition on arm \(i\) having information coordinate value \(u\). The event that arm \(i\) is best and that the top-two gap is at most \(\varepsilon\) has conditional probability \[\prod_{k\neq i}\bar F_k(u) - \prod_{k\neq i}\bar F_k(u-\varepsilon),\] where \(\bar F_k(t)\) is understood to be \(0\) below the left endpoint of \(\mathcal{H}\) and \(1\) above the right endpoint. Hence \[\mathbb{P}(\Gamma_s\le\varepsilon) = \sum_{i=1}^K \int_{\mathcal{H}} \bar f_i(u) \left[ \prod_{k\neq i}\bar F_k(u) - \prod_{k\neq i}\bar F_k(u-\varepsilon) \right]\mathrm{d}u.\] Let \[G_i(u):=\prod_{k\neq i}\bar F_k(u).\] Then \[G_i'(u) = \sum_{j\neq i} \bar f_j(u)\prod_{k\neq i,j}\bar F_k(u)\] where the derivative exists, and \(G_i\) is Lipschitz because the densities are bounded. Therefore \[\frac{G_i(u)-G_i(u-\varepsilon)}{\varepsilon} \to G_i'(u)\] for almost every \(u\), and the quotient is uniformly bounded. Dominated convergence gives \[\begin{align} \frac{\mathbb{P}(\Gamma_s\le\varepsilon)}{\varepsilon} \to \sum_{i=1}^K \sum_{j\neq i} \int_{\mathcal{H}} \bar f_i(u)\bar f_j(u) \prod_{k\neq i,j}\bar F_k(u)\,\mathrm{d}u =\kappa . \end{align}\]

For the triple-gap bound, the case \(K=2\) is trivial. Assume \(K\ge3\), and let \[M_{\bar{f}}:=\max_{i\in[K]}\|\bar f_i\|_\infty<\infty.\] If \(\Gamma_{3,s}\le\varepsilon\), then there exist three distinct arms \(i,j,k\) whose information coordinate values all lie in an interval of length \(\varepsilon\) below the largest of the three. Hence, by a union bound over ordered triples, \[\begin{align} \mathbb{P}(\Gamma_{3,s}\le\varepsilon) &\le \sum_{i,j,k\;{\rm distinct}} \int_{\mathcal{H}} \bar f_i(u) \left[ \int_{u-\varepsilon}^{u}\bar f_j(v)\,\mathrm{d}v \right] \left[ \int_{u-\varepsilon}^{u}\bar f_k(w)\,\mathrm{d}w \right]\mathrm{d}u \\ &\le K(K-1)(K-2)M_{\bar{f}}^2\varepsilon^2. \end{align}\] ◻

Proof. Since \(\mathcal{T}^\uparrow\) is a finite disjoint union of open subsets of Euclidean spaces and \(\lambda\) is a finite Borel measure with density with respect to Lebesgue measure on each component, \(\lambda\) is a finite Radon measure. In particular, it is inner regular. Choose a compact set \(\mathcal{K}_\rho\subset\mathcal{T}^\uparrow\) such that \(\lambda(\mathcal{K}_\rho)\ge \kappa-\rho\).

Because \(\mathcal{K}_\rho\) is compact and lies inside the open ordered tie manifold, there exists \(\ell_\rho>0\) such that, for every \((i,j,u,\zeta_{-ij})\in\mathcal{K}_\rho\), \(\zeta_k\le u-\ell_\rho\) for all \(k\neq i,j\).

For all sufficiently small \(\varepsilon\), uniformly over \(0\le r\le R\varepsilon\), the second-arm value \(u-r\) remains above all background values on \(\mathcal{K}_\rho\). Hence, restricted to \(\mathcal{K}_\rho\), \[\begin{align} &\mathbb{P}\{\Gamma_s\le R\varepsilon,\, \xi^\uparrow(\eta)\in\mathcal{K}_\rho\} \\ &\quad= \sum_{i\neq j} \int \mathbb{1}_{\{(i,j,u,\zeta_{-ij})\in\mathcal{K}_\rho\}} \bar f_i(u) \prod_{k\neq i,j}\bar f_k(\zeta_k) \left[ \int_{u-R\varepsilon}^{u}\bar f_j(v)\,\mathrm{d}v \right] \mathrm{d}u\,\mathrm{d}\zeta_{-ij}. \end{align}\] By continuity of \(\bar f_j\) on the compact projection of \(\mathcal{K}_\rho\), \[\int_{u-R\varepsilon}^{u}\bar f_j(v)\,\mathrm{d}v = R\varepsilon\,\bar f_j(u)+o(\varepsilon)\] uniformly over \(\mathcal{K}_\rho\). Therefore \[\mathbb{P}\{\Gamma_s\le R\varepsilon,\, \xi^\uparrow(\eta)\in\mathcal{K}_\rho\} = R\varepsilon\,\lambda(\mathcal{K}_\rho)+o(\varepsilon) \ge (\kappa-\rho)R\varepsilon+o(\varepsilon).\] The complement bound follows by subtracting this lower bound from the total top-two gap expansion: \[\mathbb{P}(\Gamma_s\le R\varepsilon) = \kappa R\varepsilon+o(\varepsilon).\] ◻

Proof. Fix \(j\neq b^\star\), write \(\Delta:=\Delta_{j,s}=\eta_{b^\star}-\eta_j\), and \(a:=w_j^\dagger(\eta)\). For \(z\in[\mu_j,\mu_{b^\star}]\), write \(r:=s(z)-\eta_j\in[0,\Delta]\). By 44 , \[\begin{align} D(\mu_{b^\star},z)+aD(\mu_j,z) &\ge \widetilde{c}\{(\Delta-r)^2+a r^2\}. \end{align}\] If \(a=1\), then \[\inf_{0\le r\le\Delta} \widetilde{c}\{(\Delta-r)^2+r^2\} = \frac{\widetilde{c}}{2}\Delta^2 \ge \frac{\widetilde{c}}{2}\Gamma_s^2.\] If \(a<1\), then by 55 , \(a=\frac{\Gamma_s^2}{4\widetilde{c}\,\Delta^2}\). Thus \[\begin{align} \inf_{0\le r\le\Delta} \widetilde{c}\{(\Delta-r)^2+a r^2\} = \widetilde{c}\frac{a}{1+a}\Delta^2 \ge \frac{\widetilde{c} a}{2}\Delta^2 = \frac{\Gamma_s^2}{8}, \end{align}\] where we used \(a<1\). Therefore, for every challenger \(j\), \[\inf_{z\in[\mu_j,\mu_{b^\star}]} \{D(\mu_{b^\star},z)+w_j^\dagger(\eta) D(\mu_j,z)\} \ge c_{\rm gap}\Gamma_s^2,\] where \(c_{\rm gap}:= \min\left\{\frac{\widetilde{c}}{2},\frac{1}{8}\right\}>0\).

Since \(W^\dagger(\eta)\le K\), 57 gives \(C^\dagger(\mu) \ge \frac{c_{\rm gap}}{K}\Gamma_s^2\). Hence \(C^\dagger(\mu)\le u\) implies \[\Gamma_s\le \sqrt{\frac{K}{c_{\rm gap}}}\sqrt u.\] Taking \(R^\star:=\sqrt{K/c_{\rm gap}}\) gives the desired result. ◻

Proof. Let \(b^\star_2\) denote the second-best arm and put \(\gamma:=\Gamma_s\).

Because \(\mathcal{K}\) is compactly contained in \(\mathcal{T}^\uparrow\), there exists \(\ell>0\) such that, whenever \(\xi^\uparrow(\eta)\in\mathcal{K}\), \[\eta_{b^\star}-\eta_k\ge \ell, \qquad k\notin\{b^\star,b^\star_2\},\] for all sufficiently small \(\gamma\). Also, all relevant information coordinate values remain in a compact subset of \(\mathcal{H}\).

The KL divergence has the uniform local Fisher coordinate expansion \[\label{eq:local-kl-simple-upper} D(s^{-1}(\eta),s^{-1}(v)) = \frac{1}{2}(\eta-v)^2+O(|\eta-v|^3),\tag{59}\] for \(\eta,v\) in any compact subset of \(\mathcal{H}\). This follows from a Taylor expansion of the KL divergence and the definition of \(s\).

For the top two arms, \(w_{b^\star}^\dagger(\eta)=1\) and \(w_{b^\star_2}^\dagger(\eta) = \min\left\{ 1,\frac{\gamma^2}{4\widetilde{c}\,\gamma^2} \right\} = 1,\) Hence using 59 , \[\begin{align} &\inf_{z\in[\mu_{b^\star_2},\mu_{b^\star}]} \{D(\mu_{b^\star},z)+D(\mu_{b^\star_2},z)\} \\ &\qquad= \inf_{w\in[\eta_{b^\star}-\gamma,\eta_{b^\star}]} \left\{ \frac{1}{2}(\eta_{b^\star}-w)^2 + \frac{1}{2}(w-\eta_{b^\star}+\gamma)^2 \right\} + o(\gamma^2) \\ &\qquad= \frac{\gamma^2}{4}+o(\gamma^2). \end{align}\]

For any other challenger \(k\notin\{b^\star,b^\star_2\}\), its information gap \(\Delta_{k,s}:=\eta_{b^\star}-\eta_k\) is bounded below by \(\ell\). Therefore \(w_k^\dagger(\eta) = \frac{\gamma^2}{4\widetilde{c}\,\Delta_{k,s}^2} = O(\gamma^2)\), for all sufficiently small \(\gamma\). Hence \[W^\dagger(\eta) = 1+w_{b^\star_2}^\dagger(\eta)+\sum_{k\notin\{b^\star,b^\star_2\}}w_k^\dagger(\eta) = 2+O(\gamma^2).\] Furthermore, by the same coercivity calculation as in Lemma 41, \[\begin{align} \inf_{z\in[\mu_k,\mu_{b^\star}]} \{D(\mu_{b^\star},z)+w_k^\dagger(\eta) D(\mu_k,z)\} \ge \widetilde{c} \frac{w_k^\dagger(\eta)}{1+w_k^\dagger(\eta)} \Delta_{k,s}^2 = \frac{\gamma^2}{4}\{1+o(1)\}. \end{align}\] Thus \[\min_{j\neq b^\star} \inf_{z\in[\mu_j,\mu_{b^\star}]} \{D(\mu_{b^\star},z)+w_j^\dagger(\eta) D(\mu_j,z)\} = \frac{\gamma^2}{4}\{1+o(1)\}.\] Combining this with \(W^\dagger(\eta)=2+o(1)\) in 57 gives \[C^\dagger(\mu) = \frac{\gamma^2}{8}\{1+o(1)\}.\] The preceding estimates are uniform on \(\mathcal{K}\), so the proof is complete. ◻

Proof. We prove matching lower and upper bounds.

For the lower bound, fix \(\rho>0\) and \(\tau\in(0,1)\). Choose \(\mathcal{K}_\rho\) as in Lemma 40. By the uniform local expansion in Lemma 42, for all sufficiently small \(u\), \[\left\{ \Gamma_s\le (1-\tau)\sqrt{8u}, \;\xi^\uparrow(\eta)\in\mathcal{K}_\rho \right\} \subseteq \{C^\dagger(\mu)\le u\}.\] Indeed, on \(\mathcal{K}_\rho\), \[C^\dagger(\mu) = \frac{\Gamma_s^2}{8}\{1+o(1)\},\] uniformly as \(\Gamma_s\downarrow0\), and the factor \((1-\tau)^2\) leaves enough slack. Therefore, using Lemma 40 with \(\varepsilon=\sqrt u\) and \(R=(1-\tau)\sqrt8\), \[\begin{align} \mathbb{P}(C^\dagger(\mu)\le u) &\ge \mathbb{P}\left( \Gamma_s\le (1-\tau)\sqrt{8u}, \;\xi^\uparrow(\eta)\in\mathcal{K}_\rho \right) \\ &\ge (\kappa-\rho)(1-\tau)\sqrt{8u} + o(\sqrt u). \end{align}\] Letting \(\rho\downarrow0\) and then \(\tau\downarrow0\) yields \[\liminf_{u\downarrow0} \frac{\mathbb{P}(C^\dagger(\mu)\le u)}{\sqrt u} \ge \kappa\sqrt8.\]

For the upper bound, Lemma 41 gives \[\{C^\dagger(\mu)\le u\} \subseteq \{\Gamma_s\le R^\star\sqrt u\}.\] Fix \(\rho>0\), and again use the compact set \(\mathcal{K}_\rho\). On \[\{C^\dagger(\mu)\le u,\;\xi^\uparrow(\eta)\in\mathcal{K}_\rho\},\] Lemma 41 implies \(\Gamma_s\to0\) uniformly as \(u\downarrow0\). Hence the uniform local expansion gives, for all sufficiently small \(u\), \[C^\dagger(\mu) \ge (1-\tau)\frac{\Gamma_s^2}{8}.\] Consequently, on the same event, \[\Gamma_s \le \sqrt{\frac{8u}{1-\tau}} \le (1+\tau)\sqrt{8u},\] after decreasing \(u\) if necessary and replacing \(\tau\) by a smaller slack constant. Therefore \[\begin{align} \mathbb{P}(C^\dagger(\mu)\le u) \le \mathbb{P}\{\Gamma_s\le (1+\tau)\sqrt{8u}\} + \mathbb{P}\{\Gamma_s\le R^\star\sqrt u,\, \xi^\uparrow(\eta)\notin\mathcal{K}_\rho\}. \end{align}\] By Lemmas 39 and 40, \[\mathbb{P}(C^\dagger(\mu)\le u) \le \kappa(1+\tau)\sqrt{8u} + \rho R^\star\sqrt u + o(\sqrt u).\] Letting \(u\downarrow0\), then \(\rho\downarrow0\), and finally \(\tau\downarrow0\), gives \[\limsup_{u\downarrow0} \frac{\mathbb{P}(C^\dagger(\mu)\le u)}{\sqrt u} \le \kappa\sqrt8.\] Combining the two bounds proves the claim. ◻

Proof. Set \(c:=\frac{1}{8\kappa^2}\) and \(u_{\alpha,\varepsilon}:=(1-\varepsilon)c\alpha^2\). By Lemma 43, \[\begin{align} \mathbb{P}(C^\dagger(\mu)\le u_{\alpha,\varepsilon}) &= \kappa\sqrt{8(1-\varepsilon)c}\,\alpha+o(\alpha) \\ &= \sqrt{1-\varepsilon}\,\alpha+o(\alpha). \end{align}\] Therefore, for all sufficiently small \(\alpha\), \(\mathbb{P}(C^\dagger(\mu)\le u_{\alpha,\varepsilon})<\alpha\). By Lemma 38, \[\frac{R_T}{T}\to C^\dagger(\mu) \qquad\text{a.s.}\] Thus \(R_T/T\) converges to \(C^\dagger(\mu)\) in distribution. Applying the Portmanteau theorem to the closed set \((-\infty,u_{\alpha,\varepsilon}]\) gives \[\limsup_{T\to\infty} \mathbb{P}\left( \frac{R_T}{T}\le u_{\alpha,\varepsilon} \right) \le \mathbb{P}(C^\dagger(\mu)\le u_{\alpha,\varepsilon}) < \alpha.\] Hence, for all sufficiently large \(T\), \(\mathbb{P}(R_T\le u_{\alpha,\varepsilon}T)<\alpha\). By the definition of \(r_{T,\alpha}\) as the lower \(\alpha\)-quantile of \(R_T\), \[r_{T,\alpha} \ge u_{\alpha,\varepsilon}T = (1-\varepsilon)\frac{\alpha^2T}{8\kappa^2}.\] ◻

Proof. We first prove abstention calibration. By the definition of the lower \(\alpha\)-quantile, \[\mathbb{P}(R_T<r_{T,\alpha}) \le \alpha \le \mathbb{P}(R_T\le r_{T,\alpha}).\] If \(\mathbb{P}(R_T=r_{T,\alpha})>0\), the boundary randomization in 54 gives \[\begin{align} \mathbb{P}(\widehat a_T=?) = \mathbb{P}(R_T<r_{T,\alpha}) + \theta_{T,\alpha} \mathbb{P}(R_T=r_{T,\alpha}) = \alpha. \end{align}\] If \(\mathbb{P}(R_T=r_{T,\alpha})=0\), then \[\mathbb{P}(R_T<r_{T,\alpha}) = \mathbb{P}(R_T\le r_{T,\alpha}) = \alpha,\] by the defining property of the lower quantile and the absence of an atom at the quantile. Since \(\theta_{T,\alpha}=0\) in this case, the same conclusion holds. Therefore \[\mathcal{A}_T (\mathrm{\small IC-PGWS}(\alpha))=\alpha.\]

For the undetected error probability, Lemma 33 gives \[\mathcal{E}_T (\mathrm{\small IC-PGWS}(\alpha)) \le (K-1)e^{-r_{T,\alpha}}.\] By Lemma 44, for every \(\varepsilon\in(0,1)\), all sufficiently small \(\alpha\), and all sufficiently large \(T\), \[r_{T,\alpha} \ge (1-\varepsilon)\frac{\alpha^2T}{8\kappa^2}.\] Hence \[\mathcal{E}_T(\mathrm{\small IC-PGWS}(\alpha)) \le (K-1) \exp\left\{ -(1-\varepsilon)\frac{\alpha^2T}{8\kappa^2} \right\}.\] Taking logarithms, dividing by \(\alpha^2T\), taking \(T\to\infty\), then \(\alpha\downarrow0\), and finally \(\varepsilon\downarrow0\), yields \[\limsup_{\alpha\downarrow0} \limsup_{T\to\infty} \frac{1}{\alpha^2T} \log \mathcal{E}_T(\mathrm{\small IC-PGWS}(\alpha)) \le -\frac{1}{8\kappa^2}.\] ◻