Lower Bounds for Stochastic Linear Bandits

Step 1: Per-coordinate mistake events. Let $p_{\theta i} = \mathbb P_\theta\big(\sum_t\mathbb I\{\mathrm{sign}(A_{ti})\ne\mathrm{sign}(\theta_i)\}\ge n/2\big)$: the probability that coordinate $i$ has the wrong sign at least half the time.

Step 2: Neighbours are indistinguishable. Let $\theta'$ equal $\theta$ but with $\theta_i' = -\theta_i$. Then $\langle A_t,\theta - \theta'\rangle^2 = 4A_{ti}^2/n\le4/n$, so (24.1) gives $D\le2$. Bretagnolle–Huber, applied to that event:

$$p_{\theta i} + p_{\theta'i}\ge\tfrac12e^{-2} \tag{24.2}$$

Step 3: Averaging hammer. Pairing each $\theta$ with its $i$-flip, $\frac1{\lvert\Theta\rvert}\sum_\theta\sum_ip_{\theta i}\ge\frac d4e^{-2}$, so some $\theta$ has $\sum_ip_{\theta i}\ge\frac d4e^{-2}$.

Step 4: Mistakes cost regret. The optimal action is $a^* = \mathrm{sign}(\theta)$, and $(\mathrm{sign}(\theta_i) - A_{ti})\theta_i\ge\lvert\theta_i\rvert\,\mathbb I\{\mathrm{sign}(A_{ti})\ne\mathrm{sign}(\theta_i)\}$ (nonnegative always; at least $\lvert\theta_i\rvert$ when the signs disagree). With $\lvert\theta_i\rvert = n^{-1/2}$ and Markov’s inequality on the mistake count,

$$R_n\ge\frac1{\sqrt n}\sum_i\mathbb E_\theta[\#\text{mistakes}_i]\ge\frac{\sqrt n}2\sum_ip_{\theta i}\ge\frac{e^{-2}}8d\sqrt n$$

∎

Let $\Delta = \frac1{4\sqrt3}\sqrt{d/n}$, $\theta\in\{\pm\Delta\}^d$, and $\tau_i = n\wedge\min\{t : \sum_{s\le t}A_{si}^2\ge n/d\}$.

Step 1: Regret dominates a squared distance. The optimal action is $\mathrm{sign}(\theta)/\sqrt d$, so $R_n = \Delta\,\mathbb E\sum_t\sum_i\big(\frac1{\sqrt d} - A_{ti}\mathrm{sign}(\theta_i)\big)$. Expanding the square and using $\lVert A_t\rVert^2\le1$, $\sum_i\big(\frac1{\sqrt d} - A_is_i\big)\ge\frac{\sqrt d}2\sum_i\big(\frac1{\sqrt d} - A_is_i\big)^2$. Truncating each coordinate’s sum at $\tau_i$:

$$R_n\ge\frac{\Delta\sqrt d}2\sum_i\mathbb E_\theta\big[U_i(\mathrm{sign}\,\theta_i)\big],\qquad U_i(x) = \sum_{t\le\tau_i}\Big(\frac1{\sqrt d} - A_{ti}x\Big)^2$$

Step 2: Flipping $\theta_i$ barely changes the law of $U_i$. $U_i\in[0, 4n/d + 2]$. By Pinsker and Exercise 14.4, $\lvert\mathbb E_\theta U_i - \mathbb E_{\theta'}U_i\rvert\le(4n/d + 2)\sqrt{D/2}$. The stopped chain rule (Exercise 15.7) bounds $D$ by the KL accumulated up to $\tau_i$, which is of order $\Delta^2\mathbb E\sum_{t\le\tau_i}A_{ti}^2\le\Delta^2(n/d + 1)$: the stopping time caps the information. With $d\le2n$, this gives (24.5): $\mathbb E_\theta U_i(1)\ge\mathbb E_{\theta'}U_i(1) - \frac{4\sqrt3\Delta n}d\sqrt{\frac nd}$.

Step 3: The two guesses together are expensive. $(\frac1{\sqrt d} - A)^2 + (\frac1{\sqrt d} + A)^2 = \frac2d + 2A^2$, and by the definition of $\tau_i$, $\frac{\tau_i}d + \sum_{t\le\tau_i}A_{ti}^2\ge\frac nd$ (either the energy budget was reached or $\tau_i = n$). So

$$\mathbb E_\theta U_i(1) + \mathbb E_{\theta'}U_i(-1)\ge\frac{2n}d - \frac{4\sqrt3n\Delta}d\sqrt{\frac nd} = \frac nd$$

Step 4: Randomisation hammer. Summing over all $2^d$ sign vectors, paired by the flip in each coordinate, $\sum_\theta R_n(\mathcal A,\theta)\ge2^{d-2}n\Delta\sqrt d$, so some $\theta$ has $R_n\ge\frac{n\Delta\sqrt d}4 = \frac{d\sqrt n}{16\sqrt3}$.

∎

Each block $\theta^{(i)}\in\{\Delta e_j : j\in[k]\}$, so $\theta$ is $p$-sparse. With $B_t = VA_t\in[k]^p$ the “base” arms chosen, $R_n = \sum_{i=1}^p\Delta\,\mathbb E\sum_t\mathbb I\{B_{ti}\ne b_i^*\}$. Averaging over $\Theta^p$ and fixing the other blocks, block $i$ is a $k$-armed bandit. Its information comes only through the shared summed observation, which is no more informative about block $i$ than a dedicated observation would be. The Assouad-style argument of Exercise 15.2, with $\Delta\approx\sqrt{k/n}$, gives at least $\frac18\sqrt{kn}$ per block. Total: $\frac p8\sqrt{kn} = \frac18\sqrt{pdn}$.

∎

Step 1: take $\mu\in\Theta$ with $\mu_1 = \Delta = (k-1)/V\le\frac12$. Then $\Delta\sum_{i>1}\mathbb E_\mu[T_i(n)]\le V$, so by pigeonhole some $i > 1$ has $\mathbb E_\mu[T_i(n)]\le\frac V{(k-1)\Delta} = \frac1{\Delta^2}$.

Step 2: $\mu'$: $\mu_1' = \Delta$, $\mu_i' = 2\Delta$, others 0. Then $D(\mathbb P_\mu,\mathbb P_{\mu'}) = 2\Delta^2\mathbb E_\mu[T_i(n)]\le2$. Bretagnolle–Huber with $A = \{T_1(n)\le n/2\}$: $R_n(\mu) + R_n(\mu')\ge\frac{n\Delta}4e^{-2} = \frac{n(k-1)}{4V}e^{-2}$.

Step 3: $R_n(\mu)\le V\le\frac{n(k-1)e^{-2}}{8V}$ by the assumed upper limit on $V$, so $R_n(\mu')\ge\frac{n(k-1)}{8V}e^{-2}$.

∎

Step 1: KL in matrix form. For any alternative $\theta'$ and event $E$, by Bretagnolle–Huber and (24.1), $\frac12\lVert\theta - \theta'\rVert^2_{\bar G_n}\ge\log\frac1{2\mathbb P(E) + 2\mathbb P'(E^c)}$ (25.2).

Step 2: An alternative where $a^*$ is no longer optimal. For $\varepsilon\in(0,\Delta_{\min})$ and $H\succ0$, set

$$\theta' = \theta + \frac{\Delta_a + \varepsilon}{\lVert a - a^*\rVert^2_H}H(a - a^*)$$

so $\langle a - a^*,\theta'\rangle = \varepsilon$: $a^*$ is $\varepsilon$-suboptimal under $\theta'$. With $E = \{T_{a^*}(n) < n/2\}$, $\mathbb P(E) + \mathbb P'(E^c)\le\frac2{n\varepsilon}(R_n + R_n')$ (25.3).

Step 3: Rewrite the KL. $\frac12\lVert\theta - \theta'\rVert^2_{\bar G_n} = \frac{(\Delta_a + \varepsilon)^2}{2\lVert a - a^*\rVert^2_{\bar G_n^{-1}}}\rho_n(H)$, with $\rho_n(H) = \frac{\lVert a - a^*\rVert^2_{\bar G_n^{-1}}\lVert a - a^*\rVert^2_{H\bar G_nH}}{\lVert a - a^*\rVert^4_H}$, which is at least 1 by Cauchy–Schwarz and equals 1 when $H\propto\bar G_n^{-1}$. Consistency makes $\log(R_n + R_n')/\log n\to0$, so letting $\varepsilon\to0$,

$$\liminf_n\frac{\rho_n(H)}{\log(n)\lVert a - a^*\rVert^2_{\bar G_n^{-1}}}\ge\frac2{\Delta_a^2} \tag{25.4}$$

Step 4: Contradiction. If $\limsup_n\log(n)\lVert a - a^*\rVert^2_{\bar G_n^{-1}} > \Delta_a^2/2$, then along some subsequence $S$, $\liminf_{S}\rho_n(H) > 1$ for every valid $H$. Take $H$ a cluster point of $\bar G_n^{-1}/\lVert\bar G_n^{-1}\rVert$ on $S$ (the unit-norm matrices form a compact set; the first part ensures $\lVert a - a^*\rVert_H > 0$). Along that sub-subsequence $\rho_n(H)\to1$, which is a contradiction. Since $a^*$ is played linearly often, $\lVert a - a^*\rVert_{\bar G_n^{-1}}/\lVert a\rVert_{\bar G_n^{-1}}\to1$, which gives the stated form. (The first part, that $\lambda_{\min}(\bar G_n)$ grows like $\log n$, is omitted: Exercise 25.2.)

∎

The optimal arm’s index is at least $\langle a_1,\theta\rangle = 1$. Once $T_{a_2}(t-1) > 4c^2\log n$,

$$\max_{\tilde\theta\in\mathcal C_t}\langle a_2,\tilde\theta\rangle = \max\langle a_2,\tilde\theta - \theta\rangle\le2c\sqrt{\lVert a_2\rVert^2_{V_t^{-1}}\log n}\le2c\sqrt{\frac{\log n}{T_{a_2}(t-1)}} < 1$$

so $a_2$ is played at most $1 + 4c^2\log n$ times. Then $\alpha(a_2)\lesssim4c^2$, and with $\gamma^2\gg c^2$ the certification constraint $\alpha(a_3)\varepsilon^2\gamma^2 + \alpha(a_2)\ge2\gamma^2$ forces $\alpha(a_3) = \Omega(1/\varepsilon^2)$: $a_3$ is played $\Omega(\log n/\varepsilon^2)$ times at cost $\varepsilon$ each, i.e. $\Omega(\log n/\varepsilon)$ regret.

∎