ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedprecheck pass

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.

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.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

17 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Tor Lattimore and Csaba Szepesvári, Bandit Algorithms (standard reference, not scraped)