TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-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.

Gap-dependent expected regret of UCB

Statement

Let $n, k$ be integers with $n \geq \max {k, 2}$ . In an $n$ -round $k$ -armed stochastic bandit, suppose all reward-stack entries are 1-sub-Gaussian. Run the upper-confidence-bound algorithm with $δ = n^{- 2}$ . Its expected reward regret satisfies

R_{n} \leq 3 \sum_{i = 1}^{k} Δ_{i} + \sum_{i : Δ_{i} > 0} \frac{16 \log n}{Δ_{i}},

where $\log$ is the natural logarithm. This is an expected-regret bound, not a high-probability guarantee.

Statement references

Finite stochastic bandit model, gaps, and regret: the finite reward-stack model, gaps, and expected reward regret.

Centered 1-sub-Gaussian reward: the exact mean-centred MGF condition for each reward entry.

Finite-horizon upper-confidence-bound bandit algorithm: the UCB index and the finite-horizon schedule used by the theorem.

Expected pull count for a suboptimal UCB arm: the deterministic-prefix expected-pull bound for each suboptimal arm.

Finite-arm regret decomposes into expected action counts: expected regret is the gap-weighted sum of expected pull counts under the fixed conditional-mean law.

Tor Lattimore and Csaba Szepesvári, Bandit Algorithms: Theorem 7.1 and proof, Chapter 7 §7.1, PDF pp. 114–117 / printed pp. 105–108.

Sébastien Bubeck and Nicolò Cesa-Bianchi, Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems: Theorem 2.1 and proof, Chapter 2 §2.2, PDF pp. 14–15 / printed pp. 11–12; its confidence schedule and constants differ.

Facts & Assumptions

Given: Integers $n, k$ with $n \geq \max {k, 2}$ , the finite reward-stack model with all entries 1-sub-Gaussian, and UCB run with $δ = n^{- 2}$ .

[F1]

The gaps are $Δ_{i} = μ^{*} - μ_{i} \geq 0$ and expected reward regret is $R_{n} = E [n μ^{*} - \sum_{t = 1}^{n} Y_{t}]$ (Finite stochastic bandit model, gaps, and regret).

[A1]

Each reward stack entry satisfies $E [\exp (λ (X_{s, i} - μ_{i}))] \leq \exp (λ^{2} / 2)$ for every real $λ$ (Centered 1-sub-Gaussian reward).

[F2]

The reward-stack model satisfies the fixed conditional-mean identity required by the regret-decomposition result (The independent reward-stack model has the prescribed conditional arm laws).

[F3]

Under that identity, $R_{n} = \sum_{i = 1}^{k} Δ_{i} E [T_{i} (n)]$ (Finite-arm regret decomposes into expected action counts).

[F4]

For every $i$ with $Δ_{i} > 0$ , $E [T_{i} (n)] \leq 3 + 16 \log (n) / Δ_{i}^{2}$ (Expected pull count for a suboptimal UCB arm).

[F5]

The algorithm uses the natural logarithm and $\log (n) > 0$ for $n \geq 2$ (The natural logarithm as the inverse of the exponential function, Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm).

Proof

1.1givenF1F2F3

By [F2], the conditional-mean hypothesis of [F3] holds for the observed rewards of the UCB policy. Therefore $R_{n} = \sum_{i = 1}^{k} Δ_{i} E [T_{i} (n)]$ .

2.1givenA1F1F4F5step 1.1algebra∎

If $Δ_{i} = 0$ , its summand is zero. For every remaining arm, substitute [F4] into step 1.1 and distribute the nonnegative coefficient $Δ_{i}$ to obtain $R_{n} \leq \sum_{i : Δ_{i} > 0} (3 Δ_{i} + 16 \log n / Δ_{i}) = 3 \sum_{i = 1}^{k} Δ_{i} + \sum_{i : Δ_{i} > 0} 16 \log n / Δ_{i}$ . This is the asserted expected-regret bound.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

28 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)
Sébastien Bubeck and Nicolò Cesa-Bianchi, Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (standard reference, not scraped)