Expected regret of explore-then-commit

By [F2], the conditional-mean hypothesis of [F3] holds, so $R_n={\sum }_{i=1}^k{\mathrm{\Delta }}_i\mathbb{E}[T_i(n)]$. Let $J$ be the committed arm. The first $mk$ rounds pull each arm exactly $m$ times, and every later round pulls $J$; hence $T_i(n)=m+(n-mk){\mathbf{1}}_{\{J=i\}}$. Taking expectations gives $R_n=m{\sum }_{i=1}^k{\mathrm{\Delta }}_i+(n-mk){\sum }_{i=1}^k{\mathrm{\Delta }}_i\mathbb{P}(J=i)$.

Fix an optimal arm $i^{\ast }$ with ${\mu }_{i^{\ast }}={\mu }^{\ast }$. If a suboptimal arm $i$ is committed, its exploration mean is at least that of $i^{\ast }$, so $\{J=i\}\subseteq \{m^{-1}{\sum }_{s=1}^m(X_{s,i}-{\mu }_i)-m^{-1}{\sum }_{s=1}^m(X_{s,i^{\ast }}-{\mu }^{\ast })\ge {\mathrm{\Delta }}_i\}$. The displayed sum has $2m$ mutually independent terms: these are measurable transforms of distinct independent table entries by [F6]. The positive centered terms are 1-sub-Gaussian by [A1], and the negated centered terms satisfy the same MGF bound by applying [A1] at $-\lambda$. Apply [F5] to these deterministic reward-stack prefixes with threshold $m{\mathrm{\Delta }}_i$ to obtain $\mathbb{P}(J=i)\le \exp (-m{\mathrm{\Delta }}_i^2\mathrm{/}4)$. For an optimal arm the theorem's summand has ${\mathrm{\Delta }}_i=0$, so no event bound is needed.

Substituting these bounds on $\mathbb{P}(J=i)$ for each suboptimal arm into step 1.1, and using ${\mathrm{\Delta }}_i\ge 0$ for every arm, gives $R_n\le m{\sum }_{i=1}^k{\mathrm{\Delta }}_i+(n-mk){\sum }_{i=1}^k{\mathrm{\Delta }}_i\exp (-m{\mathrm{\Delta }}_i^2\mathrm{/}4)$. The term with $n-mk=0$ is zero when exploration uses the whole horizon.