TheoremStatement: AI-adaptedProof: 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-free 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 \sqrt{8 n k \log n} + 3 \sum_{i = 1}^{k} Δ_{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 finite-horizon schedule.

A sharper expected suboptimal-arm pull count for the unchanged UCB rule: the local once-per-prefix argument gives the sharper expected-pull estimate used in the finite Cauchy–Schwarz proof.

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.2 and proof, Chapter 7 §7.1, PDF p. 117 / printed p. 108.

Facts & Assumptions

Given: The unchanged finite reward-stack bandit, horizon $n \geq \max {k, 2}$ , centered 1-sub-Gaussian entries, and UCB with $δ = n^{- 2}$ in the Statement.

[F1]

The gaps are nonnegative and exactly one arm is pulled each round, so $\sum_{i} T_{i} (n) = n$ . Finite stochastic bandit model, gaps, and regret

[F2]

Reward entries satisfy the exact centered MGF condition, and the algorithm uses the stated confidence schedule. Centered 1-sub-Gaussian reward Finite-horizon upper-confidence-bound bandit algorithm

[F3]

The reward-stack model supplies the eventwise conditional-mean hypothesis of the finite-arm regret decomposition. The independent reward-stack model has the prescribed conditional arm laws

[F4]

Under that hypothesis, expected reward regret equals $\sum_{i} Δ_{i} E [T_{i} (n)]$ . Finite-arm regret decomposes into expected action counts

[F5]

For every suboptimal arm, the unchanged UCB rule satisfies $E [T_{i} (n)] \leq 3 + 8 \log (n) / Δ_{i}^{2}$ . A sharper expected suboptimal-arm pull count for the unchanged UCB rule

[F6]

For finite real lists, $(\sum_{i} a_{i} b_{i})^{2} \leq (\sum_{i} a_{i}^{2}) (\sum_{i} b_{i}^{2})$ , with the corresponding nonnegative square-root inequality. The Cauchy-Schwarz inequality for finite sums

[F7]

The logarithm is increasing, so $L = \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

[F8]

Expectation is linear for finite sums of integrable random variables. Linearity, monotonicity, and the modulus bound for expectation

Proof

1.1givenF1F3F4F8

By [F3], the actual reward table meets the conditional-mean premise of [F4], hence $R_{n} = \sum_{i} Δ_{i} E [T_{i} (n)]$ . All counts are bounded, and [F1] gives $\sum_{i} E [T_{i} (n)] = n$ .

2.1F1F2F5F7step 1.1constructalgebra

Let $I = {i : Δ_{i} > 0}$ and, for $i \in I$ , put $q_{i} = (E [T_{i} (n)] - 3)_{+}$ . By [F5], $Δ_{i}^{2} q_{i} \leq 8 L$ . Also $q_{i} \leq E [T_{i} (n)]$ , so $\sum_{i \in I} q_{i} \leq n$ by step 1.1. Therefore $R_{n} \leq 3 \sum_{i} Δ_{i} + \sum_{i \in I} Δ_{i} q_{i} .$ Zero-gap arms contribute zero, and no reciprocal of a zero gap occurs.

3.1F6F7step 2.1casesalgebra∎

Apply [F6] to the finite nonnegative lists $a_{i} = Δ_{i} \sqrt{q_{i}}$ and $b_{i} = \sqrt{q_{i}}$ for $i \in I$ . Step 2.1 yields $\sum_{i \in I} Δ_{i} q_{i} \leq \sqrt{(\sum_{i \in I} Δ_{i}^{2} q_{i}) (\sum_{i \in I} q_{i})} \leq \sqrt{8 ∣ I ∣ L n} \leq \sqrt{8 n k \log n} .$ If $I$ is empty both sums and the regret are zero; otherwise the same finite inequality applies. Substitution in step 2.1 proves the unchanged Statement.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

49 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)