BanditAlgorithm.bandit_asymptotically_optimal_ucb_limsup

Setup and notation. A $k$-armed bandit $\nu$ is a family of Borel probability measures $(P_i)_{i<k}$ on $\mathbb{R}$, with means $\mu_i=\int x\,dP_i$ (Bochner integral, $0$ if not integrable), optimal value $\mu^{*}=\sup_i\mu_i$ ($=0$ when $k=0$) and gaps $\Delta_i=\mu^{*}-\mu_i$. For a policy $\pi$ (a family of Markov kernels from length-$m$ histories to arm distributions), $\mathbb{P}^{n}_{\nu,\pi}$ is the canonical measure on length-$n$ histories (point mass at the empty history for $n=0$; at each further step an arm is drawn from the policy kernel given the current history and a reward is drawn from that arm's distribution, and the pair is appended), and the expected regret is $R_n=n\mu^{*}-\int\bigl(\sum_{t<n}X_t\bigr)d\mathbb{P}^{n}_{\nu,\pi}$ (integral $=0$ by convention if the total reward is not integrable). The schedule is $f(t)=1+t(\log t)^2$ ($\log 0=0$), the index of arm $i$ at a length-$m$ history $h$ is $\gamma_i(h)=\hat\mu_i(h)+\sqrt{2\log f(m+1)/T_i(h)}$ where $T_i$, $\hat\mu_i$ are the pull count and empirical mean (both $0$ for unpulled arms, by the $x/0=0$ convention), and the policy property assumed of $\pi$ is: at every history there is an arm $a$ selected with probability one, which is unpulled if any arm is unpulled, and which maximizes $\gamma$ (non-strictly, over all arms) if all arms are pulled. Write $(x)^{+}=\max(x,0)$, regarded as an element of the extended interval $[0,\infty]$.

Assertion.

the limit superior being taken in the complete lattice $[0,\infty]$ along $n\to\infty$; the sum ranges over the arms with strictly positive gap, and for such arms $(2/\Delta_i)^{+}=2/\Delta_i$.

Hypotheses.

• $\nu$ is $1$-sub-Gaussian: each arm's identity is integrable and each centered variable $x\mapsto x-\mu_i$ satisfies $\int e^{\lambda(x-\mu_i)}\,dP_i\le e^{\lambda^{2}/2}$ (with integrability) for every real $\lambda$.
• $\pi$ satisfies the index-policy property described above.

Edge cases.

• Negative values of $R_n/\log n$ are truncated to $0$ before taking the limit superior.
• For $n\in\{0,1\}$, $\log n=0$ and the real division convention gives $R_n/0=0$; these initial terms cannot affect the limsup.
• If no arm has strictly positive gap, the right side is $0$ and the claim asserts that the truncated limsup equals $0$.
• For $k=0$ the policy property is unsatisfiable, so the statement holds vacuously.
• Only a non-strict upper bound on the limit superior is asserted — nothing about a liminf or an actual limit.