Pipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

✓ 3 results · all verified · 0 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 3 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Online protocols and regret benchmarks — Examples

1 · Prerequisites

2 · Logical flowchart

3 · Definitions, theorems and proofs

None yet.

4 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passOpen item page →

Full-information finite experts

Example

For $T = 2$ rounds and three experts, let the learner's decisions be probability vectors in $Δ_{3} : = {x \in [0, 1]^{3} : x_{1} + x_{2} + x_{3} = 1}$ , with $x_{1} = (1 / 2, 1 / 3, 1 / 6)$ and $x_{2} = (1 / 6, 1 / 3, 1 / 2)$ . Let the expert-loss vectors be $ℓ_{1} = (0, 1, 1)$ and $ℓ_{2} = (1, 0, 1)$ , let $f_{t} (x) = ℓ_{t} \cdot x$ , and reveal the entire vector $ℓ_{t}$ after each round. The learner's total loss is $7 / 6$ , the minimum total loss of one fixed vector in $Δ_{3}$ is $1$ , and the resulting static regret is $1 / 6$ .

Example references

Online decision protocol: choices are made from the past before the current round loss is observed.

Adversary and feedback models: full-information feedback reveals the entire round loss function or expert-loss vector.

Static, dynamic, interval, and strongly adaptive regret: static regret subtracts the minimum cumulative loss of one fixed comparator.

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

Tengyu Ma, Lecture Notes for Machine Learning Theory: §11.2, PDF p. 149.

Facts & Assumptions

Given: The simplex $Δ_{3}$ , decisions $x_{1} = (1 / 2, 1 / 3, 1 / 6)$ and $x_{2} = (1 / 6, 1 / 3, 1 / 2)$ , losses $f_{1} (x) = x_{2} + x_{3}$ and $f_{2} (x) = x_{1} + x_{3}$ , and full-information feedback revealing each entire loss vector.

[F1]

In an online protocol, the learner chooses from the past before incurring and receiving feedback about the current round loss (Online decision protocol).

[F2]

Full-information feedback reveals the entire function $f_{t}$ or, for $N$ experts, the full vector of their $N$ losses (Adversary and feedback models).

[F3]

Static regret is learner cumulative loss minus the attained minimum cumulative loss over one fixed $u \in K$ (Static, dynamic, interval, and strongly adaptive regret).

Verification

1.1givenF1F2

The loss vectors are $ℓ_{1} = (0, 1, 1)$ and $ℓ_{2} = (1, 0, 1)$ , and the full-information rule reveals both vectors after their respective choices, as required by the online timing and feedback model.

1.2givenF3algebra

For any $u \in Δ_{3}$ , $f_{1} (u) + f_{2} (u) = u_{1} + u_{2} + 2 u_{3} = 1 + u_{3} \geq 1$ , with equality whenever $u_{3} = 0$ ; hence the attained minimum is $1$ .

2.1givenstep 1.1algebra

Direct evaluation gives $f_{1} (x_{1}) = 1 / 3 + 1 / 6 = 1 / 2$ and $f_{2} (x_{2}) = 1 / 6 + 1 / 2 = 2 / 3$ , so the learner's cumulative loss is $1 / 2 + 2 / 3 = 7 / 6$ .

3.1givenF3step 2.1step 1.2algebra∎

Subtracting this minimum from the learner's cumulative loss in step 2.1 gives $7 / 6 - 1 = 1 / 6$ by the static-regret definition.

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passOpen item page →

A changing comparator separates static and dynamic regret

Example

Let $K = [0, 1]$ with norm $∣ \cdot ∣$ , horizon $T = 3$ , losses $f_{1} (x) = x$ , $f_{2} (x) = 1 - x$ , and $f_{3} (x) = x$ , and learner choices $x_{1} = x_{2} = x_{3} = 1 / 2$ . The realized static regret is $1 / 2$ . For the changing comparator $u_{1} = 0, u_{2} = 1, u_{3} = 0$ , the dynamic regret is $3 / 2$ and the path length is $3$ . The maximum static regret over all nonempty contiguous intervals is $1 / 2$ .

Example references

Online decision protocol: the horizon, actions, and round losses form a finite-horizon online protocol.

Static, dynamic, interval, and strongly adaptive regret: static, dynamic, path-length, interval, and adaptive regret conventions.

Elad Hazan, Introduction to Online Convex Optimization, second edition: §§10.1–10.2, PDF pp. 190–193.

Facts & Assumptions

Given: $K = [0, 1]$ , $T = 3$ , $f_{1} (x) = x$ , $f_{2} (x) = 1 - x$ , $f_{3} (x) = x$ , learner choices $x_{t} = 1 / 2$ , and comparator sequence $(0, 1, 0)$ .

[F1]

An online protocol fixes the horizon and action set; each learner choice uses only earlier revealed history and available private randomness and is made before its current loss is observed. The environment may fix each loss before the choice or select it afterward, as specified by its model (Online decision protocol).

[F2]

Static regret compares with one fixed minimizer; dynamic regret compares with a supplied sequence; path length is $1 + \sum_{t < T} ∥ u_{t} - u_{t + 1} ∥$ ; interval regret minimizes cumulative loss over one comparator on that interval (Static, dynamic, interval, and strongly adaptive regret).

Verification

1.1givenF1F2algebra

The learner's losses are $1 / 2, 1 / 2, 1 / 2$ , so their sum is $3 / 2$ . For any fixed $u \in [0, 1]$ , the cumulative loss is $u + (1 - u) + u = 1 + u$ , whose minimum is $1$ at $u = 0$ . Thus static regret is $3 / 2 - 1 = 1 / 2$ .

1.2givenF2algebra

The comparator losses are $f_{1} (0) = 0$ , $f_{2} (1) = 0$ , and $f_{3} (0) = 0$ , so its total loss is zero and dynamic regret is $3 / 2$ . Its path length is $1 + ∣ 0 - 1 ∣ + ∣ 1 - 0 ∣ = 3$ .

2.1givenF2algebra∎

The singleton interval regrets are $1 / 2$ on each of $[1, 1]$ , $[2, 2]$ , and $[3, 3]$ , because each learner loss is $1 / 2$ and each corresponding linear loss has minimum $0$ . On $[1, 2]$ and $[2, 3]$ , the cumulative loss is identically $1$ , as $f_{1} + f_{2} = 1$ and $f_{2} + f_{3} = 1$ , so both regrets are zero. On $[1, 3]$ , the cumulative loss is $1 + x$ , its minimum is $1$ , and the learner incurs $3 / 2$ , so its regret is $1 / 2$ . The maximum over these six nonempty contiguous intervals is therefore $1 / 2$ .

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passOpen item page →

Two stochastic arms: pseudo-regret and reward regret

Example

Take horizon $T = 1$ and two fixed Borel probability laws $P_{1}, P_{2}$ on $(R, B (R))$ , each concentrated on ${0, 1}$ , such that $P_{1} ({1}) = 3 / 4$ , $P_{1} ({0}) = 1 / 4$ , and $P_{2} ({1}) = P_{2} ({0}) = 1 / 2$ . The arm means are the integrals of the coordinate $y \mapsto y$ , so $μ_{1} = 3 / 4$ and $μ_{2} = 1 / 2$ . The learner chooses arm $A_{1} = 2$ . Realize the chosen reward on $Ω = {0, 1}$ with the full power set and each point of probability $1 / 2$ , setting $Y_{1} (ω) = ω$ . Then the pseudo-regret is $1 / 4$ , the expected realized reward regret is $1 / 4$ , and the expected action-count decomposition equals $1 / 4$ .

Example references

Adversary and feedback models: a finite-arm stochastic reward model specifies fixed arm laws and generates the reward after the chosen arm.

Static, dynamic, interval, and strongly adaptive regret: pseudo-regret uses arm means; realized reward regret uses sampled rewards.

Finite-arm regret decomposes into expected action counts: expected reward regret equals expected pseudo-regret and the gap-weighted expected pull counts.

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

Facts & Assumptions

Given: The two fixed Borel Bernoulli reward laws, $T = 1$ , $A_{1} = 2$ , and the equiprobable sample space $Ω = {0, 1}$ with $Y_{1} (ω) = ω$ .

[F1]

In the fixed-law finite-arm model, the conditional-mean event identity is stated for every history-and-arm event contained in the chosen-arm event (Adversary and feedback models).

[F2]

Pseudo-regret is $\sum_{t} (μ^{*} - μ_{A_{t}})$ and realized reward regret is $\sum_{t} (μ^{*} - Y_{t})$ (Static, dynamic, interval, and strongly adaptive regret). Arm counts sum the indicators of the chosen-arm events (Finite-arm regret decomposes into expected action counts).

[F3]

For the stated conditional-mean model, the finite-arm lemma gives $E [R_{T}^{r e w}] = E [{\overset{ˉ}{R}}_{T}] = \sum_{i} (μ^{*} - μ_{i}) E [N_{i} (T)]$ (Finite-arm regret decomposes into expected action counts).

[F4]

For an event $B$ , $E [1_{B}] = P (B)$ (The expectation of an indicator is the probability of the event).

[F5]

Expectation is linear for integrable random variables (Linearity, monotonicity, and the modulus bound for expectation).

Verification

1.1givenalgebra

Under each arm law, the coordinate $y \mapsto y$ equals $1_{{1}}$ almost surely, so its integral is the probability of ${1}$ : $μ_{1} = 3 / 4$ and $μ_{2} = 1 / 2$ . Thus $μ^{*} = 3 / 4$ . In the realized process, $Y_{1} (ω) = ω$ has Borel law $P_{2}$ , since both put mass $1 / 2$ at each of $0$ and $1$ and zero elsewhere, so $E [Y_{1}] = 1 / 2$ .

2.1givenF1step 1.1

The pre-reward history is trivial and $A_{1} = 2$ deterministically. Thus for arm 2 the history-and-arm events are $B = \emptyset$ or $B = Ω$ , while for arm 1 only $B = \emptyset$ is possible. For every Borel $C$ , the fixed-law identity for $B = Ω$ is $P (Ω \cap {Y_{1} \in C}) = P_{2} (C) = P (Ω) P_{2} (C)$ by step 1.1; it is trivial for $B = \emptyset$ . The conditional-mean identity likewise holds: for $B = Ω$ , $E [1_{B} Y_{1}] = 1 / 2 = μ_{2} P (B)$ , and for $B = \emptyset$ both sides are zero.

2.2givenF2step 1.1algebra

The sole chosen arm is 2, so ${\overset{ˉ}{R}}_{1} = 3 / 4 - 1 / 2 = 1 / 4$ , $N_{1} (1) = 0$ , and $N_{2} (1) = 1$ .

2.3givenF4F5step 1.1algebra

The realized reward regret is $3 / 4 - Y_{1}$ . By linearity and $E [Y_{1}] = P (ω = 1) = 1 / 2$ , its expectation is $3 / 4 - 1 / 2 = 1 / 4$ .

3.1givenF3step 2.2step 2.3algebra∎

The gap-weighted count sum is $(3 / 4 - 3 / 4) E [N_{1} (1)] + (3 / 4 - 1 / 2) E [N_{2} (1)] = 0 \cdot 0 + (1 / 4) \cdot 1 = 1 / 4$ . This agrees with the pseudo-regret and realized-regret expectations in steps 2.2 and 2.3, as the finite-arm lemma asserts.

Online protocols and regret benchmarks — Examples

2 · Logical flowchart

3 · Definitions, theorems and proofs

4 · Examples, counterexamples and false statements

Full-information finite experts

Example

Example references

Facts & Assumptions

Verification

A changing comparator separates static and dynamic regret

Example

Example references

Facts & Assumptions

Verification

Two stochastic arms: pseudo-regret and reward regret

Example

Example references

Facts & Assumptions

Verification

Sources