Static, dynamic, interval, and strongly adaptive regret

Let a finite-horizon online protocol have horizon $T$, action set $K$, round losses $f_t:K\to \mathbb{R}$, and learner choices $x_t\in K$. Whenever a minimum below is used, assume it is finite and attained. For a fixed comparator $u\in K$, the realized regret is

$$R_T(u):=\sum _{t=1}^T{f}_t(x_t)-\sum _{t=1}^T{f}_t(u)\mathrm{.}$$

The static regret is

$$R_T^{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{t}}:=\sum _{t=1}^T{f}_t(x_t)-\underset{u\in K}{\min }\sum _{t=1}^T{f}_t(u)\mathrm{.}$$

For randomized learners or environments, expected regret is the expectation of the specified regret random variable over their joint randomness, when that random variable is measurable and integrable. In a stochastic finite-arm reward model with means $({\mu }_i{)}_{i\in [N]}$, let ${\mu }^{\ast }:={\max }_{i\in [N]}{\mu }_i$. The pseudo-regret is the random variable

$${\bar{R}}_T:=\sum _{t=1}^T({\mu }^{\ast }-{\mu }_{A_t}),$$

whereas the realized reward regret is

$$R_T^{\mathrm{r}\mathrm{e}\mathrm{w}}:=\sum _{t=1}^T({\mu }^{\ast }-Y_t)\mathrm{.}$$

For dynamic comparators, suppose $K\subseteq {\mathbb{R}}^d$ for a positive integer $d$ and fix a norm $\mathrm{\parallel }\cdot \mathrm{\parallel }:{\mathbb{R}}^d\to [0,\mathrm{\infty })$, meaning $\mathrm{\parallel }v\mathrm{\parallel }=0$ exactly when $v=0$, $\mathrm{\parallel }\lambda v\mathrm{\parallel }=\mathrm{\mid }\lambda \mathrm{\mid }\mathrm{\parallel }v\mathrm{\parallel }$ for every $\lambda \in \mathbb{R}$, and $\mathrm{\parallel }v+w\mathrm{\parallel }\le \mathrm{\parallel }v\mathrm{\parallel }+\mathrm{\parallel }w\mathrm{\parallel }$. Given a comparator sequence $u_{1:T}=(u_1,\dots ,u_T)\in K^T$, the dynamic regret and its path length are

$$R_T^{\mathrm{d}\mathrm{y}\mathrm{n}}(u_{1:T}):=\sum _{t=1}^T{f}_t(x_t)-\sum _{t=1}^T{f}_t(u_t),P(u_{1:T}):=1+\sum _{t=1}^{T-1}\mathrm{\parallel }{u}_t-u_{t+1}\mathrm{\parallel }\mathrm{.}$$

For a nonempty contiguous integer interval $I=[r,s]$ with $1\le r\le s\le T$, its interval regret is

$$R_I:=\sum _{t=r}^s{f}_t(x_t)-\underset{u\in K}{\min }\sum _{t=r}^s{f}_t(u),$$

and the adaptive regret is ${\max }_{1\le r\le s\le T}{R}_{[r,s]}$. For an algorithm $A$ producing the choices $x_1,\dots ,x_T$, write $R_I(A)$ for its interval regret on $I$. The algorithm is strongly adaptive relative to a specified loss, feedback, adversary, and comparator class precisely when there are a stated base algorithm $A_0$, constants $C>0$ and $p\ge 0$, and a specified bound $B_{A_0}(n)$ on $A_0$'s static regret at horizon $n$ in that same class, such that, uniformly over every positive horizon $T$ and every environment in that class, for every nonempty contiguous interval $I\subseteq \{1,\dots ,T\}$,

$$R_I(A)\le C(\log (eT){)}^p{B}_{A_0}(\mathrm{\mid }I\mathrm{\mid }),$$

where $\log$ is the natural logarithm and $\mathrm{\mid }I\mathrm{\mid }=s-r+1$; $A_0$, $B_{A_0}$, $C$, and $p$ are fixed independently of $T$, $I$, and the environment. The displayed criterion is pathwise, including for randomized protocols. Strong adaptivity in expectation instead requires $\mathbb{E}[R_I(A)]$ to satisfy the displayed bound for every deterministic interval $I$, with measurable, integrable interval regrets and with $B_{A_0}(n)$ an expected static-regret bound in the same class. Almost-sure or high-probability versions must be explicitly qualified: for each horizon, all interval inequalities must hold simultaneously with probability one or at least the stated $1-\delta$, respectively, and the base bound must use the same probability mode with any dependence on $\delta$ specified. Strong adaptivity is a regret property relative to intervals; it does not imply anytime statistical validity.

Online decision protocol: the horizon, action set, round losses, and learner choices used in the regret formulas.

Adversary and feedback models: the stochastic finite-arm model and the distinction between its reward means and adversarial losses.

Expectation of a nonnegative or integrable random variable: expected regret is an integral on the underlying probability space when the regret is measurable and integrable.

Elad Hazan, Introduction to Online Convex Optimization, second edition: §1.1, PDF pp. 23–24; §§10.1–10.2.1, PDF pp. 190–194.

Tor Lattimore and Csaba Szepesvári, Bandit Algorithms: §4.4, PDF pp. 68–69.

Tengyu Ma, Lecture Notes for Machine Learning Theory: §11.1.1, PDF pp. 148–149.

Amit Daniely, Alon Gonen, and Shai Shalev-Shwartz, Strongly Adaptive Online Learning: §1.1, PDF p. 2; expectation is the randomized convention there, while the modes above are distinguished explicitly.