ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedjudge pass (gpt-6-luna)

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.

A two-arm deterministic gap and explore-then-commit

Example

Let $m \geq 1$ be an integer, let $n \geq 2 m + 1$ , and fix $0 < Δ < 1$ . In a two-arm $n$ -round bandit, let every reward-stack entry of arm 1 equal $1$ and every reward-stack entry of arm 2 equal $1 - Δ$ . Under explore-then-commit with exploration count $m$ , the algorithm commits to arm 1 and has expected reward regret exactly $m Δ$ . The expected-regret theorem gives the upper bound $m Δ + (n - 2 m) Δ e^{- m Δ^{2} / 4}$ for this instance.

Example references

Finite stochastic bandit model, gaps, and regret: arm means, gaps, and expected reward regret.

Centered 1-sub-Gaussian reward: the mean-centred MGF condition checked for deterministic rewards.

The exponential is positive and satisfies $\exp (- x) = 1 / \exp (x)$ : the exponential factor in the regret bound is positive.

Explore-then-commit for a finite stochastic bandit: the fixed round-robin exploration and empirical-mean commitment rule.

Expected regret of explore-then-commit: the expected-regret bound compared with the exact regret.

Facts & Assumptions

Given: The deterministic reward table and explore-then-commit parameters in the example.

[F1]

Arm means, gaps, and expected reward regret are defined by the stochastic-bandit model (Finite stochastic bandit model, gaps, and regret).

[F2]

Each reward is 1-sub-Gaussian exactly when its mean-centred MGF satisfies the stated bound (Centered 1-sub-Gaussian reward).

[F3]

Explore-then-commit samples each arm $m$ times, commits to a least-index empirical-mean maximizer, then repeats it (Explore-then-commit for a finite stochastic bandit).

[F4]

Under the finite-mean 1-sub-Gaussian assumptions, the theorem bounds expected reward regret by the stated ETC expression (Expected regret of explore-then-commit).

[F5]

The real exponential is positive at every real input (The exponential is positive and satisfies $\exp (- x) = 1 / \exp (x)$ ).

Verification

1.1givenF1F2algebra

The arm laws are point masses at $1$ and $1 - Δ$ , so $μ_{1} = 1$ , $μ_{2} = 1 - Δ$ , and $(Δ_{1}, Δ_{2}) = (0, Δ)$ . Each centered reward is identically $0$ , so its MGF is $1 \leq e^{λ^{2} / 2}$ for every real $λ$ and [F4] applies.

2.1givenF1F3step 1.1algebra

The exploration means equal the deterministic rewards, so [F3] commits to arm 1. During exploration it pulls arm 2 exactly $m$ times, each with gap $Δ$ ; all other pulls have gap $0$ . Therefore both the realized reward regret and its expectation equal $m Δ$ .

3.1givenF4F5step 2.1algebra∎

Substituting $Δ_{1} = 0$ and $Δ_{2} = Δ$ into [F4] gives $m Δ + (n - 2 m) Δ e^{- m Δ^{2} / 4}$ , which is at least $m Δ$ because $n - 2 m > 0$ , $Δ > 0$ , and [F5] makes the exponential factor positive.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

21 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.