LemmaStatement: 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.

Expected pull count for a suboptimal UCB arm

Statement

Let $n, k$ be integers with $n \geq \max {k, 2}$ . In an $n$ -round $k$ -armed stochastic bandit, suppose every reward-stack entry is 1-sub-Gaussian. Run the upper-confidence-bound algorithm with $δ = n^{- 2}$ . For every arm $i$ with gap $Δ_{i} > 0$ , its number of pulls satisfies

E [T_{i} (n)] \leq 3 + \frac{16 \log n}{Δ_{i}^{2}},

where $\log$ is the natural logarithm and the expectation is over the reward table and learner randomization.

Statement references

Centered 1-sub-Gaussian reward: each reward is mean-centred and satisfies the exact MGF bound for every real parameter.

Tor Lattimore and Csaba Szepesvári, Bandit Algorithms: Theorem 7.1 proof, §7.1, PDF pp. 114–117 / printed pp. 105–108; fixed-prefix warning, PDF p. 112 / printed p. 103.

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

Facts & Assumptions

Given: An $n$ -round reward-stack model with $n \geq \max {k, 2}$ , all reward entries 1-sub-Gaussian, a suboptimal arm $i$ with $Δ_{i} > 0$ , and the UCB algorithm run with $δ = n^{- 2}$ .

[F1]

Each arm has finite mean $μ_{i}$ , gap $Δ_{i} = μ^{*} - μ_{i}$ , and stack entries $X_{s, i}$ are independent with law $P_{i}$ (Finite stochastic bandit model, gaps, and regret).

[A1]

Every table entry is centered 1-sub-Gaussian in the exact MGF sense (Centered 1-sub-Gaussian reward).

[F2]

For every deterministic $s \in [n]$ , the prefix mean ${\hat{μ}}_{i, s} = s^{- 1} \sum_{r = 1}^{s} X_{r, i}$ satisfies $P ({\hat{μ}}_{i, s} - μ_{i} \geq x), P ({\hat{μ}}_{i, s} - μ_{i} \leq - x) \leq e^{- s x^{2} / 2}$ for $x \geq 0$ (Tail bounds for deterministic prefixes of independent sub-Gaussian rewards).

[F3]

After initialization, the UCB index of arm $i$ with $s > 0$ observations is its observed-prefix mean plus $\sqrt{2 \log (1 / δ) / s}$ ; the least-index maximizer is selected (Finite-horizon upper-confidence-bound bandit algorithm).

[F4]

For $n \geq 2$ , $\log n > 0$ and $\log (n^{2}) = 2 \log n$ (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.1givenF1F3F4algebra

Fix a suboptimal arm $i$ , let $i^{*}$ be the least index with $μ_{i^{*}} = μ^{*}$ , write $L = \log n > 0$ , and put $u_{i} = ⌈ 16 L / Δ_{i}^{2} ⌉$ . For each deterministic prefix length $s \in [n]$ , set $r_{s} = \sqrt{4 L / s}$ ; by [F4] this is the UCB bonus when $δ = n^{- 2}$ . If $u_{i} \geq n$ , then $T_{i} (n) \leq n \leq u_{i} \leq 16 L / Δ_{i}^{2} + 1$ , which is stronger than the claim. Hence assume $u_{i} < n$ , so $r_{u_{i}} \leq Δ_{i} / 2$ .

2.1givenF1F3step 1.1

Define the good event $G_{i} = (⋂_{s = 1}^{n} {{\hat{μ}}_{i^{*}, s} + r_{s} \geq μ^{*}}) \cap {{\hat{μ}}_{i, u_{i}} + r_{u_{i}} < μ^{*}}$ . On $G_{i}$ , arm $i$ cannot be selected at any round when it already has $u_{i}$ pulls: its index is then below $μ^{*}$ , whereas the good event makes the index of arm $i^{*}$ at least $μ^{*}$ for every possible deterministic prefix length $s \in [n]$ . Since each pull increases $T_{i}$ by one, $T_{i} (n) \leq u_{i}$ on $G_{i}$ .

3.1givenA1F2step 2.1algebra

The complement of the first event in $G_{i}$ is contained in the union of the $n$ deterministic-prefix events ${{\hat{μ}}_{i^{*}, s} - μ^{*} < - r_{s}}$ . By [F2] under [A1] and the union bound, its probability is at most $\sum_{s = 1}^{n} e^{- s r_{s}^{2} / 2} = n e^{- 2 L} = 1 / n$ . This union is over fixed $s$ , not the random pull count $T_{i^{*}} (t)$ .

3.2givenA1F2step 1.1step 2.1algebra

Since $r_{u_{i}} \leq Δ_{i} / 2$ , the other failure event in $G_{i}$ is contained in ${{\hat{μ}}_{i, u_{i}} - μ_{i} \geq Δ_{i} / 2}$ . By [F2] under [A1] its probability is at most $e^{- u_{i} Δ_{i}^{2} / 8} \leq e^{- 2 L} = n^{- 2}$ . Therefore $P (G_{i}^{c}) \leq 1 / n + 1 / n^{2}$ .

4.1givenstep 1.1step 2.1step 3.2algebra∎

Always $T_{i} (n) \leq n$ , while step 2.1 gives $T_{i} (n) \leq u_{i}$ on $G_{i}$ . Thus $E [T_{i} (n)] \leq u_{i} + n P (G_{i}^{c}) \leq 16 L / Δ_{i}^{2} + 1 + 1 + 1 / n \leq 16 \log n / Δ_{i}^{2} + 3$ , where $n \geq 2$ was used in the last inequality. This proves the claim.

Depends on

Used by

Gap-dependent expected regret of UCB Theorem

Dependency tree · two levels

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