BanditAlgorithm.bandit_etc_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$. Histories $h$ of length $n$ list (arm, reward) pairs $(A_t(h), X_t(h))$; $\hat\mu_j(h)$ is the empirical mean of arm $j$ in $h$ (junk value $0$ if $j$ unpulled); $\mathbb{P}^n_{\nu,\pi}$ is the history measure generated by policy $\pi$ interacting with $\nu$ ($\mathbb{P}^0 = \delta_{()}$, $\mathbb{P}^{m+1} = (\mathbb{P}^m \otimes K_m) \circ \mathrm{append}^{-1}$, with $K_m$ drawing an arm from $\pi_m(\cdot \mid h)$ then a reward from that arm's distribution); and the regret is $R_n(\nu,\pi) = n\,\mu^* - \int \sum_{t<n} X_t \, d\mathbb{P}^n_{\nu,\pi}$ (integral $= 0$ if the integrand is not integrable).

Claim. Suppose:

• $k > 0$;
• $\nu$ is $1$-subgaussian: for every arm $i$, $x \mapsto x$ is $P_i$-integrable, and for every $t \in \mathbb{R}$, $x \mapsto e^{t(x - \mu_i)}$ is $P_i$-integrable with $\int e^{t(x - \mu_i)} dP_i \le e^{t^2/2}$;
• $m \ge 1$ and $m k \le n$ (natural numbers);
• $\pi$ satisfies the explore-then-commit predicate with parameters $(k, m)$: there exists a commit map $c$ from length-$mk$ histories to arms such that (i) for every length-$mk$ history $h_0$ and every arm $j$, $\hat\mu_j(h_0) \le \hat\mu_{c(h_0)}(h_0)$ (with the $\hat\mu = 0$ convention for unpulled arms), and (ii) at every round $t < mk$ the policy is the Dirac measure at arm $t \bmod k$, while at every round $t \ge mk$ it is the Dirac measure at $c(\text{first } mk \text{ rounds of the history})$.

Then

Edge cases:

• $(n - mk)$ is real subtraction of the casts, and is $\ge 0$ under the hypothesis $mk \le n$ (no natural-number truncation).
• Both sums range over all arms, including optimal ones, whose terms vanish since $\Delta_i = 0$; for $k \ge 1$ all gaps satisfy $\Delta_i \ge 0$.
• The exponent is exactly $-m \Delta_i^2 / 4$; the subgaussian variance proxy is fixed at $1$ (i.e. $\sigma = 1$).
• The theorem asserts nothing about the existence of a policy satisfying the predicate; if none exists for the given $m, k$, the statement is vacuous for those parameters.