A sharper expected suboptimal-arm pull count for the unchanged UCB rule

Put $L=\log n>0$ and let $i^{\ast }$ be the least-index optimal arm. For a fixed prefix $s\in [n]$, put $r_s=\sqrt{4L\mathrm{/}s}$. By [F8], this is the index bonus at $\delta =n^{-2}$. Let $G={\bigcap }_{s=1}^n\{{\widehat{\mu }}_{i^{\ast },s}+r_s\ge {\mu }^{\ast }\}\mathrm{.}$ Every event in its complement is a fixed-prefix lower-tail event of probability at most $e^{-s{r}_s^2\mathrm{/}2}=n^{-2}$ by [F2] and [F4]. Hence $\mathbb{P}(G^c)\le 1\mathrm{/}n$ by [F5].

Fix the suboptimal arm $i$. It is played once during initialization. On $G$, any later play when its current count is $s$ requires ${\widehat{\mu }}_{i,s}+r_s\ge {\mu }^{\ast }$: its selected index is at least the current index of $i^{\ast }$, which is at least ${\mu }^{\ast }$. Each such count $s\in \{1,\dots ,n-1\}$ can be charged at most once, since a play increases the count by one. Always $T_i(n)\le n$. Thus pointwise $T_i(n)\le 1+{\sum }_{s=1}^{n-1}{\mathbf{1}}_{\{{\widehat{\mu }}_{i,s}+r_s\ge {\mu }^{\ast }\}}+n{\mathbf{1}}_{G^c}\mathrm{.}$

For a fixed $s$, the event inside the sum in step 2.1 is ${\widehat{\mu }}_{i,s}-{\mu }_i\ge {\mathrm{\Delta }}_i-r_s$. If this threshold is positive, [F4] bounds its probability by $\exp (-s({\mathrm{\Delta }}_i-r_s{)}^2\mathrm{/}2)$. If it is nonpositive, use the bound $1$ in [F5]. Consequently, in both cases its probability is at most $\exp (-\frac{({\mathrm{\Delta }}_i\sqrt{s}-2\sqrt{L}{)}_{+}^2}{2})\mathrm{.}$ These are tails at deterministic prefix counts, never a tail theorem evaluated at a random count.

Take expectations in step 2.1, using [F6]. The count and indicators are bounded and therefore integrable. Step 1.1 makes the last term at most $1$, while step 3.1 bounds the finite sum. If $n\ge 5$, [F7] with $a={\mathrm{\Delta }}_i>0$ therefore gives $\mathbb{E}[T_i(n)]\le 2+{\sum }_{s=1}^{n-1}\exp (-\frac{({\mathrm{\Delta }}_i\sqrt{s}-2\sqrt{L}{)}_{+}^2}{2})\le 3+\frac{8L}{{\mathrm{\Delta }}_i^2}\mathrm{.}$

If $2\le n\le 4$, the existence of a suboptimal arm implies $k\ge 2$. Initialization plays every other arm at least once, so $T_i(n)\le n-k+1\le 3$ pointwise. This proves the desired bound in the remaining horizons. If $k=1$ there is no suboptimal arm, so the assertion is vacuous. Together with step 4.1 this proves the Statement.