BanditAlgorithm.bandit_ucb_minimax_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 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 unpulled). The index with parameter $\delta$ is $U_i^{\delta}(h) = \hat\mu_i(h) + \sqrt{2\log(1/\delta)/T_i(h)}$ with junk conventions $1/0 = 0$, $\log$ of a nonpositive $= 0$, $\sqrt{\phantom{x}}$ of a negative $= 0$ (unpulled arms have index $0$). $\mathbb{P}^n_{\nu,\pi}$ is the history measure generated by $\pi$ interacting with $\nu$, 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$: deterministic at every history, playing an unpulled arm whenever one exists, and otherwise an arm maximizing $U_j^{1/n^2}$.

Then

Edge cases:

• Inside the square root, $n$, $k$, $\log n$ are multiplied as real numbers; for $n \ge 1$, $\log n \ge 0$, so the radicand is nonnegative and no junk square-root convention is triggered. For $n = 1$, $\log n = 0$ and the first term vanishes, leaving $R_1 \le 3 \sum_i \Delta_i$.
• The second term still depends on the gaps of the particular bandit $\nu$ (it is the same $3\sum_i \Delta_i$ term as in the gap-dependent bound); the sum ranges over all arms, with optimal arms contributing $0$.
• The bound is asserted for every policy satisfying the UCB predicate (tie-breaking and the choice among unpulled arms are unconstrained by the predicate).