C Proofs of results from Section 4

For \(u, w \in \mathbb {R}^K\), we use the notation \(\Vert u \Vert _{\omega } = \sqrt{\sum _{k=1}^K \omega _k u_k^2}\).

Lemma 3

For the Gaussian half-space identification problem, where arm \(k\) has variance \(\sigma _k^2 {\gt} 0\), with orthogonal vector \(u\) with \(\Vert u \cdot \sigma \Vert _1 = 1\), \(H_{\mathcal C^{sp}}(\lambda )^{-1} = \frac{1}{2}(\lambda ^\top u)^2\).

Proof ▼

We compute \(\sup _{\omega \in \triangle _K} \inf _{\nu \in \mathrm{Alt}(\lambda )} \sum _{k=1}^K \omega _k \mathrm{KL}(\nu _k, \lambda _k)\) for any \(\lambda \).

\begin{align*} \inf _{\nu \in \mathrm{Alt}(\lambda )} \sum _{k=1}^K \omega _k \mathrm{KL}(\nu _k, \lambda _k) & = \frac{1}{2}\inf _{\nu \in \mathrm{Alt}(\lambda )} \sum _{k=1}^K \omega _k \sigma _k^{-2} (\nu _k - \lambda _k)^2 = \frac{1}{2} \frac{(\lambda ^\top u)^2}{\Vert u \Vert _{\omega ^{-1} \cdot \sigma ^{2}}^2} \end{align*}

\begin{align*} \sup _{\omega \in \triangle _K} \inf _{\nu \in \mathrm{Alt}(\lambda )} \sum _{k=1}^K \omega _k \mathrm{KL}(\nu _k, \lambda _k) & = \sup _{\omega \in \triangle _K} \frac{1}{2} \frac{(\lambda ^\top u)^2}{\Vert u \Vert _{\omega ^{-1} \cdot \sigma ^{2}}^2} = \frac{1}{2} (\lambda ^\top u)^2 \: . \end{align*}

Lemma 4

For Gaussian half-space identification, \(\inf _{\mathcal A \in \mathcal C_\infty }\sup _{\lambda \in \mathcal D} R_{H_{\mathcal C^{sp}}, \infty }(\mathcal A, \lambda ) \ge 1\).

Proof ▼

For the proof, the vector orthogonal to the hyperplane is \(u\) with \(\Vert u \cdot \sigma \Vert _1 = 1\).

We show that for all \(\nu \), \(\max _{\omega \in \triangle _K} \inf _{\lambda \in \mathrm{Alt}(\nu )} H_{\mathcal C^{sp}}(\lambda ) \sum _{k=1}^K \omega _{k} \mathrm{KL}(\nu _k, \lambda _k) = 1\). The result then follows from an application of Theorem 3.

\begin{align*} \max _{\omega \in \triangle _K} \inf _{\lambda \in \mathrm{Alt}(\nu )} H_{\mathcal C^{sp}}(\lambda ) \sum _{k=1}^K \omega _{k} \mathrm{KL}(\nu _k, \lambda _k) & = \max _{\omega \in \triangle _K} \inf _{\lambda \in \mathrm{Alt}(\nu )} \frac{\sum _{k=1}^K \omega _{k} \sigma _k^{-2} (\nu _k - \lambda _k)^2}{(\lambda ^\top u)^2} \\ & = \max _{\omega \in \triangle _K} \inf _{a{\gt}0} \frac{1}{a}\inf _{\lambda \in \mathrm{Alt}(\nu ), (\lambda ^\top u)^2 = a} \sum _{k=1}^K \omega _{k} \sigma _k^{-2} (\nu _k - \lambda _k)^2 \\ & = \max _{\omega \in \triangle _K} \inf _{a{\gt}0} \frac{(\sqrt{a} + \vert u^\top \nu \vert )^2}{a \Vert u \Vert _{\omega ^{-1} \cdot \sigma ^{2}}^2} \\ & = \max _{\omega \in \triangle _K} \frac{1}{\Vert u \Vert _{\omega ^{-1} \cdot \sigma ^{2}}^2} \\ & = 1 \: . \end{align*}

We suppose in the remainder of this section that the distributions of the arms are Gaussian, where arm \(k\) has variance \(\sigma _k^2 {\gt} 0\). The Kullback-Leibler divergence is \((x,y) \mapsto \frac{1}{2 \sigma _k^2}(x - y)^2\). Suppose that there is a ball \(B(\eta , r)\) in the norm \(\Vert \cdot \Vert _{\sigma ^{-2}}\) with center \(\eta \in \mathcal D\) and radius \(r {\gt} 0\) such that \(i^\star \) takes only two values in \(B(\eta , r)\), say \(i\) and \(j\), and the boundary between \(B(\eta , r) \cap \{ \mu \mid i^\star (\mu ) = i\} \) and \(B(\eta , r) \cap \{ \mu \mid i^\star (\mu ) = j\} \) is the restriction of a hyperplane passing through \(\eta \). Let \(u\) be a vector orthogonal to the hyperplane with \(\Vert u \cdot \sigma \Vert _1 = 1\).

Lemma 5

For \(\mu \in B(\eta , r/(\sqrt{K}+1))\) with \(\mu ^\top u {\lt} \eta ^\top u\),

\begin{align*} \max _{\omega \in \triangle _K} \inf _{\lambda \in \mathrm{Alt}(\mu ) \cap B(\eta , r)} \sum _{k=1}^K \omega _k (\lambda _k - \mu _k)^2 & = \max _{\omega \in \triangle _K} \inf _{\lambda : (\lambda - \eta )^\top u \ge 0} \sum _{k=1}^K \omega _k (\lambda _k - \mu _k)^2 = ((\mu - \eta )^\top u)^2 \: . \end{align*}

Proof ▼

Let \(\mu \in B(\eta , r/(\sqrt{K}+1))\) be such that \(u^\top \mu {\lt} u^\top \eta \). For the full half-space alternative, we have

\begin{align*} \max _{\omega \in \triangle _K} \inf _{\lambda : (\lambda - \eta )^\top u \ge 0} \sum _{k=1}^K \omega _k \sigma _k^{-2} (\lambda _k - \mu _k)^2 = ((\mu - \eta )^\top u)^2 \end{align*}

Let \(\lambda _u(\mu ) = \mu - ((\mu - \eta )^\top u) \sigma \). We now prove that that point belongs to the ball \(B(\eta , r)\). We will use the fact that \(\Vert u \Vert _{\sigma ^2}^2 = \sum _{k=1}^K u_k^2 \sigma _k^2 \le \sum _{k=1}^K u_k \sigma _k = 1\) (since \(\Vert u \cdot \sigma \Vert _1 = 1)\).

\begin{align*} \Vert \lambda _{u}(\mu ) - \eta \Vert _{\sigma ^{-2}}^2 & = \Vert \mu _k - \eta _k - ((\mu - \eta )^\top u) \sigma \Vert _{\sigma ^{-2}}^2 \\ & \le \left( \Vert \mu - \eta \Vert _{\sigma ^{-2}} + \sqrt{K} \vert (\mu - \eta )^\top u \vert \right)^2 \\ & \le \left( \Vert \mu - \eta \Vert _{\sigma ^{-2}} + \sqrt{K} \Vert \mu - \eta \Vert _{\sigma ^{-2}} \Vert u \Vert _{\sigma ^{2}} \right)^2 \\ & \le (\sqrt{K} + 1)^2 \Vert \mu - \eta \Vert _{\sigma ^{-2}}^2 \\ & \le r^2 \: . \end{align*}

For the problem restricted to the ball,

\begin{align*} \max _{\omega \in \triangle _K} \inf _{\lambda \in \mathrm{Alt}(\mu ) \cap B(\eta , r)} \sum _{k=1}^K \omega _k \sigma _k^{-2} (\lambda _k - \mu _k)^2 & \le \max _{\omega \in \triangle _K} \sum _{k=1}^K \omega _k \sigma _k^{-2} (\lambda _{u,k}(\mu ) - \mu _k)^2 = ((\mu - \eta )^\top u)^2 \; , \\ \text{and } \max _{\omega \in \triangle _K} \inf _{\lambda \in \mathrm{Alt}(\mu ) \cap B(\eta , r)} \sum _{k=1}^K \omega _k \sigma _k^{-2} (\lambda _k - \mu _k)^2 & \ge \max _{\omega \in \triangle _K} \inf _{\lambda : (\lambda - \eta )^\top u \ge 0} \sum _{k=1}^K \omega _k \sigma _k^{-2} (\lambda _k - \mu _k)^2 = ((\mu - \eta )^\top u)^2 \: . \end{align*}

The last inequality comes from \(\mathrm{Alt}(\mu ) \cap B(\eta , r) \subseteq \{ \lambda \mid (\lambda - \eta )^\top u \ge 0\} \). We have proved the equality.

Lemma 6

Let \(\delta {\gt} 0\), \(\varepsilon {\gt} 0\), \(r' = r / (\sqrt{K} + 1)\) and \(r'' = \frac{1}{2} r' \frac{\delta \varepsilon }{(1 + \delta ) (1 + \varepsilon )}\). Let \(\mu \in B(\eta , r'')\) with \((\mu - \eta )^\top u {\gt} 0\) and let \(D_{\varepsilon , \delta }(\mu ) = \mathrm{Alt}(\mu )\cap B(\eta , r')\). Then

\begin{align*} \max _{\omega \in \triangle _K} \inf _{\lambda \in D_{\varepsilon , \delta }(\mu )} \sum _{k=1}^K \omega _k \mathrm{KL}(\lambda _k, \mu _k) \le (1 + \varepsilon ) (1 + \delta )^2 \: . \end{align*}

This bound is then used in Theorem 3 to get a lower bound on the difficulty ratio. Taking the limit as \(\varepsilon \to 0\) and \(\delta \to 0\), we prove Theorem 6.

Proof ▼

For all \(\lambda \in \mathrm{Alt}(\mu ) \cap B(\eta , r')\), Lemma 5 gives \(H_{\mathcal C^{sp}}(\lambda ) = 2 ((\lambda - \eta )^\top u)^{-2}\).

\begin{align*} \max _{\omega \in \triangle _K} \inf _{\lambda \in \mathrm{Alt}(\mu ) \cap B(\eta , r')} H_{\mathcal C^{sp}}(\lambda ) \sum _{k=1}^K \omega _{k} \mathrm{KL}(\mu _k, \lambda _k) & = \max _{\omega \in \triangle _K} \inf _{\lambda \in \mathrm{Alt}(\mu ) \cap B(\eta , r')} \frac{\sum _{k=1}^K \omega _{k} \sigma _k^{-2} (\mu _k - \lambda _k)^2}{((\lambda - \eta )^\top u)^2} \\ & = \max _{\omega \in \triangle _K} \inf _{\lambda \in \cap B(\eta , r'), (\lambda - \eta )^\top u \le 0} \frac{\sum _{k=1}^K \omega _{k} \sigma _k^{-2} (\mu _k - \lambda _k)^2}{((\lambda - \eta )^\top u)^2} \: . \end{align*}

If we did not restrict \(\lambda \) to the ball \(B(\eta , r')\), then that quantity would be equal to 1 as shown in Lemma 4. We now argue that if \(\mu \) is sufficiently close to \(\eta \), it approaches 1 even with the restriction to the ball.

For \(\omega \in \triangle _K\), let \(\omega ^\varepsilon \in \triangle _K^0\) be such that \(\omega _k^\varepsilon = \frac{\omega _k + \varepsilon }{1 + \varepsilon }\).

Let \(x = \frac{1}{2}r' \frac{\varepsilon }{(1 + \delta ) (1 + \varepsilon )}\). Let \(\lambda _{\omega ^\varepsilon }(\mu )\) be the vector with coordinates \(\lambda _{\omega ^\varepsilon ,k}(\mu ) = \mu _k - \frac{(\mu - \eta )^\top u + x}{\Vert u \Vert ^2_{(\omega ^\varepsilon )^{-1} \cdot \sigma ^{2}}} \frac{u_k}{\omega _k^\varepsilon } \sigma _k^2\). We show that it belongs to the ball \(B(\eta , r')\). This is possible only thanks to the lower bound on any coordinate of \(\omega ^\varepsilon \), and is the reason for introducing that modification of \(\omega \).

\begin{align*} \Vert \lambda _{\omega ^\varepsilon }(\mu ) - \eta \Vert _{\sigma ^{-2}} & = \Vert \mu - \eta - \frac{(\mu - \eta )^\top u + x}{\Vert u \Vert ^2_{(\omega ^\varepsilon )^{-1} \cdot \sigma ^{2}}} (\frac{u_k}{\omega _k^\varepsilon } \sigma _k^2)_{k\in [K]} \Vert _{\sigma ^{-2}} \\ & \le \Vert \mu - \eta \Vert _{\sigma ^{-2}} + \frac{(\mu - \eta )^\top u + x}{\Vert u \Vert ^2_{(\omega ^\varepsilon )^{-1} \cdot \sigma ^{2}}} \Vert \frac{u}{\omega ^{\varepsilon }} \sigma ^2 \Vert _{\sigma ^{-2}} \\ & \le \Vert \mu - \eta \Vert _{\sigma ^{-2}} + \frac{\Vert \mu - \eta \Vert _{\sigma ^{-2}} + x}{\Vert u \Vert ^2_{(\omega ^\varepsilon )^{-1} \cdot \sigma ^{2}}} \Vert \frac{u}{\omega ^{\varepsilon }} \sigma ^2 \Vert _{\sigma ^{-2}} \\ & \le \Vert \mu - \eta \Vert _{\sigma ^{-2}} + (\Vert \mu - \eta \Vert _{\sigma ^{-2}} + x) \Vert \frac{u}{\omega ^{\varepsilon }} \sigma ^2 \Vert _{\sigma ^{-2}} \\ & \le \Vert \mu - \eta \Vert _{\sigma ^{-2}} + (\Vert \mu - \eta \Vert _{\sigma ^{-2}} + x)\frac{1 + \varepsilon }{\varepsilon } \\ & \le r” + (r” + x)\frac{1 + \varepsilon }{\varepsilon } \\ & = x (\delta + (1 + \delta )\frac{1 + \varepsilon }{\varepsilon }) \le 2 x(1 + \delta )\frac{1 + \varepsilon }{\varepsilon } = r’ \: . \end{align*}

Now since \(\lambda _{\omega ^\varepsilon }(\mu ) \in \mathrm{Alt}(\mu ) \cap B(\eta , r')\), we get

\begin{align*} & \max _{\omega \in \triangle _K} \inf _{\lambda \in \cap B(\eta , r'), (\lambda - \eta )^\top u \le 0} \frac{\sum _{k=1}^K \omega _{k} \sigma _k^{-2} (\mu _k - \lambda _k)^2}{((\lambda - \eta )^\top u)^2} \\ & \le (1 + \varepsilon ) \max _{\omega \in \triangle _K} \inf _{\lambda \in \cap B(\eta , r'), (\lambda - \eta )^\top u \le 0} \frac{\sum _{k=1}^K \omega _{k}^\varepsilon \sigma _k^{-2} (\mu _k - \lambda _k)^2}{((\lambda - \eta )^\top u)^2} \\ & \le (1 + \varepsilon ) \max _{\omega \in \triangle _K} \frac{\sum _{k=1}^K \omega _{k}^\varepsilon \sigma _k^{-2} (\mu _k - \lambda _{\omega ^\varepsilon ,k}(\mu ))^2}{((\lambda _{\omega ^\varepsilon }(\mu ) - \eta )^\top u)^2} \: . \end{align*}

We can compute explicitly both terms in the ratio:

\begin{align*} \sum _{k=1}^K \omega _{k}^\varepsilon \sigma _k^{-2} (\mu _k - \lambda _{\omega ^\varepsilon ,k}(\mu ))^2 & = \frac{((\mu - \eta )^\top u + x)^2}{\Vert u \Vert ^2_{(\omega ^\varepsilon )^{-1} \cdot \sigma ^{2}}} \: , & (\lambda _{\omega ^\varepsilon }(\mu ) - \eta )^\top u & = -x \: . \end{align*}

Finally,

\begin{align*} & \max _{\omega \in \triangle _K} \inf _{\lambda \in \cap B(\eta , r'), (\lambda - \eta )^\top u \le 0} \frac{\sum _{k=1}^K \omega _{k} (\mu _k - \lambda _k)^2}{((\lambda - \eta )^\top u)^2} \\ & \le (1 + \varepsilon ) \max _{\omega \in \triangle _K} \inf _{\lambda \in \cap B(\eta , r'), (\lambda - \eta )^\top u \le 0} \frac{\sum _{k=1}^K \omega _{k}^\varepsilon (\mu _k - \lambda _k)^2}{((\lambda - \eta )^\top u)^2} \\ & \le (1 + \varepsilon ) \max _{\omega \in \triangle _K} \frac{((\mu - \eta )^\top u + x)^2}{x^2 \Vert u \Vert ^2_{(\omega ^\varepsilon )^{-1} \cdot \sigma ^{2}}} \\ & \le (1 + \varepsilon ) (\frac{(\mu - \eta )^\top u}{x} + 1)^2 \\ & \le (1 + \varepsilon ) (\frac{r''}{x} + 1)^2 \\ & = (1 + \varepsilon ) (1 + \delta )^2 \: . \end{align*}