Online protocols and regret benchmarks

Fix a positive integer horizon $T$, a nonempty action set $K$, and, when choices or the environment are randomized, a probability space $(\mathrm{\Omega },\mathcal{F},\mathbb{P})$. An online decision protocol has rounds $t=1,\dots ,T$. Before round $t$, the learner has the history $h_{t-1}$ consisting of its earlier choices and all feedback and loss information revealed in earlier rounds. It chooses $x_t\in K$ using only $h_{t-1}$ and any learner-private randomization available by that time. In a randomized protocol, $X_t$ is a measurable random element of $K$, meaning a measurable map from $(\mathrm{\Omega },\mathcal{F})$ into $K$ equipped with its declared measurable structure. The environment supplies a real-valued loss function $f_t:K\to \mathbb{R}$; it may have fixed $f_t$ before the choice or choose it after the choice, as specified by the environment model, but the learner does not observe $f_t$ before choosing $x_t$. The learner incurs loss $f_t(x_t)$ and then receives feedback about round $t$ according to the feedback model. The history $h_t$ adds $x_t$, the feedback received, and any part of $f_t$ explicitly revealed in round $t$. No convexity, boundedness, or regret guarantee is part of this protocol definition.

Random elements and real random variables: a random element is a measurable map from a probability space into a measurable space.

Elad Hazan, Introduction to Online Convex Optimization, second edition: §1.1, PDF pp. 23–24.

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

In an online decision protocol with horizon $T$, the environment and feedback model specifies how each loss function is chosen and what the learner observes after choosing $x_t$. Full-information feedback reveals the entire function $f_t$ (or, for $N$ experts, the full vector of their $N$ losses) after the round-$t$ choice. Bandit feedback reveals only the played loss $f_t(x_t)$ after that choice. An oblivious adversary fixes the whole sequence $(f_1,\dots ,f_T)$ before the learner's random choices are realized; it may know the learner's rule but not its realized private randomization. A non-anticipating adaptive adversary chooses $f_t$ from the history available before $x_t$ is chosen, so $f_t$ may depend on earlier choices and feedback but not on the current choice or the learner's current private randomization. A reactive adversary may choose $f_t$ after observing $x_t$, so its round-$t$ loss may depend on that current choice. These adversary classes have different timing and are not interchangeable; a guarantee established for one class is not asserted for another. For the stochastic reward model, let $\mathcal{B}(\mathbb{R})$ be the smallest collection of subsets of $\mathbb{R}$ that contains every open interval and is closed under complements and countable unions; its members are the Borel sets. A stochastic finite-arm reward environment has $N\ge 1$ arms, a fixed probability measure $P_i$ on $(\mathbb{R},\mathcal{B}(\mathbb{R}))$ for each arm $i\in [N]:=\{1,\dots ,N\}$, and finite first moments ${\int }_{\mathbb{R}}\mathrm{\mid }y\mathrm{\mid }{P}_i(dy)<\mathrm{\infty }$ with means ${\mu }_i:={\int }_{\mathbb{R}}y{P}_i(dy)$. At each round the learner chooses a measurable arm $A_t$ with values in $[N]$ equipped with its full power set, before the reward $Y_t$ is drawn. The fixed-law condition means that, for every $i$, every event $B$ determined by the history before the reward and the chosen arm with $B\subseteq \{A_t=i\}$, and every $C\in \mathcal{B}(\mathbb{R})$, $\mathbb{P}(B\cap \{Y_t\in C\})=\mathbb{P}(B)P_i(C)$. The model also states explicitly the conditional-mean identity used below: $\mathbb{E}[{\mathbf{1}}_B{Y}_t]={\mu }_i\mathbb{P}(B)$ for every such $B$. Here $Y_t$ is an integrable real random variable, ${\mathbf{1}}_B$ is the indicator of event $B$, and the history-and-arm events are measurable in the common probability space. This stochastic reward model is distinct from adversarial loss models and supplies no regret guarantee by itself.

Online decision protocol: the learner chooses before the current round's loss is observed; the horizon and action set are fixed.

Random elements and real random variables: rewards are measurable real-valued random variables and finite-arm choices are measurable maps into the discrete arm set.

Probability measures and probability spaces: each arm law is a probability measure of total mass one, and events belong to its measurable space.

Expectation of a nonnegative or integrable random variable: an integrable reward's mean is its Lebesgue integral on the common probability space.

Elad Hazan, Introduction to Online Convex Optimization, second edition: §1.1, PDF pp. 23–24; §1.2.1, PDF pp. 24–25.

Tor Lattimore and Csaba Szepesvári, Bandit Algorithms: §4.1, PDF p. 64 / printed p. 56.

Tengyu Ma, Lecture Notes for Machine Learning Theory: §§11.1–11.2.1, PDF pp. 147–150.

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

The static regret is

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

whereas the realized reward regret is

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

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

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\}$,

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.

Let $T,N\ge 1$ be integers, let $(\mathrm{\Omega },\mathcal{F},\mathbb{P})$ be a probability space, and let $A_t:\mathrm{\Omega }\to [N]$ be measurable arm choices and $Y_t:\mathrm{\Omega }\to \mathbb{R}$ integrable rewards for $t=1,\dots ,T$. Let ${\mu }_1,\dots ,{\mu }_N\in \mathbb{R}$ be finite arm means and assume the conditional-mean identity

Set ${\mu }^{\ast }:={\max }_{i\in [N]}{\mu }_i$, define the pseudo-regret ${\bar{R}}_T:={\sum }_{t=1}^T({\mu }^{\ast }-{\mu }_{A_t})$, the realized reward regret $R_T^{\mathrm{r}\mathrm{e}\mathrm{w}}:={\sum }_{t=1}^T({\mu }^{\ast }-Y_t)$, and the number of pulls of arm $i$ by $N_i(T):={\sum }_{t=1}^T{\mathbf{1}}_{\{A_t=i\}}$. Then

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

Elad Hazan, Introduction to Online Convex Optimization, second edition: §1.1, PDF pp. 23–24.