Thompson Sampling

Step 1: Insert a UCB. Let $U_t(i) = \mathrm{clip}_{[0,1]}\big(\hat\mu_i(t-1) + \sqrt{2\log(1/\delta)/(1\vee T_i(t-1))}\big)$, which is $\mathcal F_{t-1}$-measurable. By (36.1),

$$\mathbb E[\mu_{A^*} - \mu_{A_t}\mid\mathcal F_{t-1}] = \mathbb E[\mu_{A^*} - U_t(A^*)\mid\mathcal F_{t-1}] + \mathbb E[U_t(A_t) - \mu_{A_t}\mid\mathcal F_{t-1}]$$

so $\mathrm{BR}_n = \mathbb E\big[\sum_t(\mu_{A^*} - U_t(A^*)) + \sum_t(U_t(A_t) - \mu_{A_t})\big]$ (36.2).

Step 2: The good event. $E$ is the event that every confidence interval holds, with $\mathbb P(E^c)\le2nk\delta$ (Exercise 36.2). On $E$:

• optimism: the first sum is at most 0, since $U_t(i)\ge\mu_i$;
• width: $U_t(i) - \mu_i\le\sqrt{8\log(1/\delta)/(1\vee T_i(t-1))}$, so $$\sum_t(U_t(A_t) - \mu_{A_t})\le\sum_i\int_0^{T_i(n)}\sqrt{\frac{8\log(1/\delta)}s}ds = \sum_i\sqrt{32T_i(n)\log(1/\delta)}\le\sqrt{32nk\log(1/\delta)}$$

Step 3: on $E^c$ the regret is at most $2n$. Take $\delta = n^{-2}$.

∎

Let $E_i(t) = \{\theta_i(t)\le\mu_1 - \varepsilon\}$ and split $\mathbb E[T_i(n)] = \mathbb E\sum_t\mathbb I\{A_t = i,E_i(t)\} + \mathbb E\sum_t\mathbb I\{A_t = i,E_i^c(t)\}$ (36.4).

First part. Let $A_t' = \arg\max_{j\ne1}\theta_j(t)$. Since $\theta_1(t)$ is conditionally independent of the others:

• $\mathbb P(A_t = 1, E_i(t)\mid\mathcal F_{t-1})\ge G_{1T_1}\,\mathbb P(A_t' = i, E_i(t)\mid\mathcal F_{t-1})$ (arm 1’s sample beats $\mu_1 - \varepsilon$, which beats everyone else);
• $\mathbb P(A_t = i, E_i(t)\mid\mathcal F_{t-1})\le(1 - G_{1T_1})\,\mathbb P(A_t' = i, E_i(t)\mid\mathcal F_{t-1})$.

So $\mathbb P(A_t = i, E_i\mid\mathcal F_{t-1})\le\big(\frac1{G_{1T_1(t-1)}} - 1\big)\mathbb P(A_t = 1\mid\mathcal F_{t-1})$. Summing over $t$, each value $T_1(t-1) = s$ occurs in only one round in which arm 1 is played, giving the $\sum_s(1/G_{1s} - 1)$ term (36.6).

Second part. In rounds where arm $i$‘s current $G > 1/n$, count plays of $i$: at most $\sum_s\mathbb I\{G_{is} > 1/n\}$. In the other rounds, $\mathbb P(E_i^c(t))\le1/n$, so they contribute at most 1 in total (Exercise 36.5).

∎

(a) Optimism of the optimal arm. $\mathbb E\sum_s(1/G_{1s} - 1)\le\frac c{\varepsilon^2}\log\frac1\varepsilon$, a constant. The sample $\mathcal N(\hat\mu_{1s},1/s)$ exceeds $\mu_1 - \varepsilon$ unless $\hat\mu_{1s}$ is far below $\mu_1$, which is exponentially unlikely in $s\varepsilon^2$. Use the Gaussian tail lower bound $1 - \Phi(y)\ge\sqrt{2/\pi}\,e^{-y^2/2}/(y + \sqrt{y^2 + 4})$.

(b) Over-sampling. $\mathbb E\sum_s\mathbb I\{G_{is} > 1/n\}\le\frac{2\log n}{(\Delta_i - \varepsilon)^2} + o(\log n)$. For a Gaussian sample with variance $1/s$ to exceed $\mu_1 - \varepsilon$ with probability above $1/n$, roughly $\hat\mu_{is} + \sqrt{2\log n/s}\gtrsim\mu_1 - \varepsilon$: exactly UCB’s condition, so $s\lesssim2\log n/(\Delta_i - \varepsilon)^2$.

(c) Combine with the regret decomposition and let $\varepsilon\to0$. This matches the Lai–Robbins constant of asymptotically optimal UCB.

∎

Let $U_t(a) = \langle a,\hat\theta_{t-1}\rangle + \beta\lVert a\rVert_{V_{t-1}^{-1}}$ with $V_t = I/S^2 + \sum_{s\le t}A_sA_s^\top$. The self-normalised bound gives $\lVert\hat\theta_{t-1} - \theta\rVert_{V_{t-1}}\le\beta$ for all $t$ (event $E$) except with probability $1/n$, which costs at most 2. On $E_t$, using probability matching $\mathbb E_{t-1}U_t(A^*) = \mathbb E_{t-1}U_t(A_t)$ and optimism, $\mathbb E_{t-1}[\mathbb I_{E_t}\langle A^* - A_t,\theta\rangle]\le\mathbb E_{t-1}[\mathbb I_{E_t}(U_t(A_t) - \langle A_t,\theta\rangle)]\le2\beta\lVert A_t\rVert_{V_{t-1}^{-1}}$. Truncate at 2, apply Cauchy–Schwarz over $t$, and use the elliptical potential lemma.

∎

Step 1: $M_t$ is a martingale: $\mathbb E_{t-1}[M_t] = M_{t-1}$. For convex $F$ (using directional derivatives, Fatou, and Jensen),

$$\mathbb E_{t-1}\big[D_F(M_t,M_{t-1})\big]\le\mathbb E_{t-1}[F(M_t)] - F(M_{t-1}) \tag{36.8}$$

since the linear term vanishes in expectation.

Step 2: by the assumption and Cauchy–Schwarz, $\mathrm{BR}_n\le\mathbb E\sum_t\sqrt{\beta\mathbb E_{t-1}D_F}\le\sqrt{\beta n\,\mathbb E\sum_t\mathbb E_{t-1}D_F}$.

Step 3: by (36.8) the sum telescopes to $\mathbb E[F(M_n)] - F(M_0)\le\mathrm{diam}_F(\mathcal P_{k-1})$.

∎

Write $p_a = \mathbb P_{t-1}(A_t = a) = \mathbb P_{t-1}(A^* = a)$ (probability matching). Then

$$\mathbb E_{t-1}[\Delta_t] = \sum_ap_a\big(\mathbb E_{t-1}[X_{ta}\mid A^* = a] - \mathbb E_{t-1}[X_{ta}]\big)\le\sum_ap_a\sqrt{\tfrac12D\big(\mathbb P_{X_{ta}\mid A^*=a},\mathbb P_{X_{ta}}\big)}$$

by Pinsker, since $X\in[0,1]$. Cauchy–Schwarz over $k$ terms gives at most $\sqrt{\frac k2\sum_ap_a^2D(\cdots)}$. Bound $p_a^2D_{aa}$ by the full double sum $\sum_{a,b}p_ap_bD(\mathbb P_{X_{ta}\mid A^*=b},\mathbb P_{X_{ta}})$, which equals the mutual information between $A^*$ and the observation $(A_t,X_{tA_t})$ (by Bayes, Exercise 36.7), i.e. the expected KL from prior to posterior on $A^*$.

∎

Lemma 36.7 gives $\beta = k/2$ with negentropy, whose diameter on the simplex is $\log k$. Theorem 36.6 gives $\sqrt{n\cdot\frac k2\log k}$.

∎