BanditAlgorithm.linear_bandit_phased_elimination_regret

Setup and notation. This is an existence statement about $k$-armed stochastic bandits with linear structure. A $k$-armed bandit $\nu$ is a $k$-tuple of probability measures $\nu_j$ on $\mathbb{R}$ with means $\mu_j = \int r\, d\nu_j(r)$, optimal mean $\mu^* = \max_j \mu_j$, and gaps $\Delta_j = \mu^* - \mu_j$. A policy $\pi$ is a family of Markov kernels from histories to arms; $\mathbb{P}_{\nu,\pi,n}$ is the induced law on length-$n$ histories (arm from the policy kernel, then reward from that arm's distribution); for a history $h$, $T_j(h)$ denotes the number of rounds in which arm $j$ was played; and the expected regret is $\mathfrak{R}_n(\nu,\pi) = n\mu^* - \mathbb{E}[\sum_{t=0}^{n-1} X_t]$. For features $\phi_j \in \mathbb{R}^d$ and $\theta_* \in \mathbb{R}^d$, "$\nu$ realizes $(\phi, \theta_*)$" means $\mu_j = \langle \phi_j, \theta_*\rangle$ for every $j$ and $\nu$ is $1$-sub-Gaussian (each $\nu_j$ integrable and $\int e^{u(r-\mu_j)} d\nu_j \le e^{u^2/2}$ for all real $u$, with the corresponding integrability).

Assertion. There exists $C > 0$ such that for all $k, d \ge 1$ and $n \ge 2$, all feature maps $\phi$, and every $\delta \in (0,1)$ (open), there exists a policy $\pi$ such that for every pair $(\theta_*, \nu)$ with $\nu$ realizing $(\phi, \theta_*)$ and all gaps bounded, $\Delta_j \le 1$ for every arm $j$, both of the following hold:

(the probability expressed as a real number), and

Hypotheses (in quantifier order).

• One constant $C > 0$ uniform over everything.
• $k \ge 1$, $d \ge 1$, $n \ge 2$; features $\phi$ arbitrary (no norm bound on $\phi_j$ is assumed); $\delta \in (0,1)$.
• $\pi$ is chosen after $(k, d, n, \phi, \delta)$ but before $(\theta_*, \nu)$: one policy serves all realizing pairs.
• $\nu$ realizes $(\phi, \theta_*)$: linear means plus $1$-sub-Gaussian noise (variance proxy $1$).
• Gap bound: $\Delta_j \le 1$ for every arm $j$; no bound on $\|\theta_*\|$ is assumed.

Edge cases.

• The second clause is conditional on the supplied $\delta$ being exactly $1/n$; for any other $\delta$ it holds vacuously, and only the high-probability clause has content.
• The nested-logarithm argument $k \log n / \delta$ can be less than $1$ (e.g. small $n$ and $k$ with $\delta$ near $1$), making the inner logarithm negative; the real square root of the then-negative product is $0$ by convention, and the event degenerates to $\sum_j T_j(h)\Delta_j \le 0$.
• Gaps satisfy $\Delta_j \ge 0$ automatically (the optimal mean is a maximum over the nonempty finite arm set), so the pull-count-weighted sum is a nonnegative "pseudo-regret of the realized history".
• Expected regret is defined through a Bochner integral ($0$ by convention if non-integrable); the two clauses must hold jointly for the same policy.