BanditAlgorithm.bandit_ucb_regret_bound

Notation (all unfolded from the imported definitions). Fix $k$ arms with distributions $P_0, \dots, P_{k-1}$ (probability measures on $\mathbb{R}$), means $\mu_i = \int x \, dP_i$, optimal mean $\mu^* = \sup_i \mu_i$, gaps $\Delta_i = \mu^* - \mu_i$. For a length-$t$ history $h$ of (arm, reward) pairs, $T_i(h)$ is the pull count of arm $i$ and $\hat\mu_i(h)$ its empirical mean ($= 0$ when $T_i(h) = 0$). The index with parameter $\delta$ is $U_i^{\delta}(h) = \hat\mu_i(h) + \sqrt{2\log(1/\delta)/T_i(h)}$, with the junk conventions $1/0 = 0$, $\log x = 0$ for $x \le 0$, $\sqrt{x} = 0$ for $x < 0$ (so an unpulled arm has index $0$). $\mathbb{P}^n_{\nu,\pi}$ is the history measure generated by $\pi$ interacting with $\nu$ (Dirac at the empty history, then iteratively compose with the arm-then-reward step kernel and push forward along append), and $R_n(\nu,\pi) = n\,\mu^* - \int \sum_{t<n} X_t \, d\mathbb{P}^n_{\nu,\pi}$ is the regret.

Claim. Suppose:

• $k > 0$;
• $\nu$ is $1$-subgaussian: every arm is integrable and for every arm $i$ and every $t \in \mathbb{R}$, $\int e^{t(x-\mu_i)} dP_i \le e^{t^2/2}$;
• $n > 0$;
• $\pi$ is a UCB policy at confidence parameter $\delta = 1/n^2$: at every round and every history there is an arm $a$ with $\pi(\cdot \mid h) = \delta_a$ (deterministic), such that $a$ is unpulled whenever some arm is unpulled, and otherwise $a$ maximizes $U_j^{1/n^2}(h)$ over all arms $j$. (For $n \ge 1$ and a pulled arm, $U_i^{1/n^2}(h) = \hat\mu_i(h) + \sqrt{4 \log n / T_i(h)}$, since $\log(n^2) = 2\log n$.)

Then

Edge cases:

• The second sum runs only over arms with strictly positive gap, so its divisions are never by zero; arms with $\Delta_i = 0$ (in particular any optimal arm) contribute only to the first sum, where their term is $0$.
• $\log$ is the natural logarithm; for $n = 1$ one has $\delta = 1$, every index bonus is $0$ (the index degenerates to the empirical mean), $\log n = 0$, and the bound reads $R_1 \le 3\sum_i \Delta_i$.
• The UCB predicate leaves tie-breaking and the choice among unpulled arms free; the bound is asserted for every policy satisfying the predicate.