Combinatorial Bandits

Losses $\langle a,y\rangle$ lie in $[0,m]$ rather than $[-1,1]$, so dividing by $m$ and applying Theorem 27.1 gives the factor $m$. For the second inequality: $\lvert\mathcal A\rvert\le\Phi_m(d) = \sum_{i\le m}\binom di\le(ed/m)^m$, so $\log\lvert\mathcal A\rvert\le m\log(ed/m)$.

∎

Step 1: by Theorem 28.10,

$$R_n\le\frac{\mathrm{diam}_F(\mathrm{co}\,\mathcal A)}\eta + \mathbb E\sum_t\Big(\langle\bar A_t - \bar A_{t+1},\hat Y_t\rangle - \frac1\eta D_F(\bar A_{t+1},\bar A_t)\Big) \tag{30.2}$$

Step 2: Diameter. On $\mathrm{co}(\mathcal A)\subseteq[0,1]^d$, $F\le0$ and $-F(a) = \sum_i(a_i + a_i\log\frac1{a_i})$. With $\sum_ia_i\le m$, Jensen puts the entropy term’s maximum at $a_i = m/d$, giving at most $m\log\frac dm$. So $\mathrm{diam}_F\le m(1 + \log(d/m))$.

Step 3: Keep only the coordinates that shrink. Let $\hat Y_{ti}' = \hat Y_{ti}\,\mathbb I\{\bar A_{t+1,i}\le\bar A_{ti}\}$. Since $\hat Y\ge0$, the dropped coordinates contribute $(\bar A_{ti} - \bar A_{t+1,i})\hat Y_{ti}\le0$, so replacing $\hat Y$ by $\hat Y'$ only increases the inner product.

Step 4: Local norm. By Theorem 26.13, with $Z_t$ on the chord and $(\nabla^2F(z))^{-1} = \mathrm{diag}(z)$. On the kept coordinates $Z_{ti}\le\bar A_{ti}$, so

$$\langle\bar A_t - \bar A_{t+1},\hat Y_t'\rangle - \frac1\eta D_F\le\frac\eta2\sum_i\bar A_{ti}\Big(\frac{A_{ti}y_{ti}}{\bar A_{ti}}\Big)^2\le\frac\eta2\sum_i\frac{A_{ti}}{\bar A_{ti}}$$

whose expectation is $\frac{\eta d}2$.

Step 5: $R_n\le\frac{m(1 + \log(d/m))}\eta + \frac{\eta nd}2$, then tune $\eta$.

∎

Step 1: Separate the bias. By linearity and Theorem 28.4 applied to the estimated losses,

$$R_n(a)\le\frac{\mathrm{diam}_F}\eta + \frac1\eta\mathbb E\sum_tD_F(\bar A_t,\bar A_{t+1}) + \mathbb E\sum_t\langle\bar A_t - a,y_t - \hat Y_t\rangle \tag{30.6}$$

Step 2: Diameter. With $x = 0$ in the dual definition, $F(a)\ge-\mathbb E\max_b\langle b,Z\rangle\ge-m\,\mathbb E\lVert Z\rVert_\infty = -m\sum_{i=1}^d\frac1i\ge-m(1 + \log d)$ (Hölder, $\lVert b\rVert_1\le m$, and the Laplace sup-norm identity below). By Jensen and centred $Z$, $\mathbb E\phi(x + Z)\ge\phi(x)\ge\langle a,x\rangle$ for $a\in\mathcal A$, so $F(a)\le0$. Hence $\mathrm{diam}_F\le m(1 + \log d)$ (30.8).

Step 3: Bregman via the dual Hessian. By Theorem 26.6(b) and Taylor, for some $\xi$ between $-\eta\hat L_{t-1}$ and $-\eta\hat L_t$, $D_F(\bar A_t,\bar A_{t+1}) = D_{F^*}(-\eta\hat L_t,-\eta\hat L_{t-1}) = \frac{\eta^2}2\lVert\hat Y_t\rVert^2_{\nabla^2F^*(\xi)}$ (30.9). A change of variables moves the gradient onto the density:

$$\nabla^2F^*(x) = \int a(x + z)\,\mathrm{sign}(z)^\top q(z)\,dz \tag{30.10}$$

Step 4: Entries are controlled by the marginals. Since $a(\cdot)\ge0$ and $q(u + v)\le e^{\lVert v\rVert_1}q(u)$,

$$\nabla^2F^*(\xi)_{ij}\le e^{\lVert\alpha\eta\hat Y_t\rVert_1}\int a(u - \eta\hat L_{t-1})_iq(u)\,du\le e^2P_{ti} \tag{30.11}$$

using $\lVert\eta\hat Y_t\rVert_1\le\eta m\beta\le\eta m\big(\frac1{\eta m} + 1\big)\le2$, which is where $\eta m\le1$ is needed.

Step 5: Expected stability. Since $\hat Y\ge0$, $\lVert\hat Y_t\rVert^2_{\nabla^2F^*(\xi)}\le e^2\sum_{i,j}P_{ti}\hat Y_{ti}\hat Y_{tj}\le e^2\sum_{i,j}P_{ti}K_{ti}A_{ti}K_{tj}A_{tj}$. Off the diagonal, $\mathbb E[K_{ti}K_{tj}\mid\mathcal F_t] = 1/(P_{ti}P_{tj})$, and $\mathbb E\sum_{i,j}A_{ti}A_{tj}/P_{tj}\le m\sum_j\mathbb E[A_{tj}]/P_{tj} = md$. So $\mathbb E[D_F]\lesssim\frac{e^2md\eta^2}2$.

Step 6: Bias. The bias is nonnegative and $a\ge0$, so $\mathbb E\langle\bar A_t - a,y_t - \hat Y_t\rangle\le\mathbb E\sum_iy_{ti}P_{ti}(1 - P_{ti})^\beta\le\frac d{2\beta}$ per round, using $x(1-x)^s\le xe^{-sx}\le\frac1{es}$. Over $n$ rounds this is at most $\frac{dnm\eta}2$.

Step 7: $R_n\le\frac{m(1 + \log d)}\eta + \frac{(1 + e^2)dnm\eta}2$, then tune $\eta$.

∎