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

Tail bounds for deterministic prefixes of independent sub-Gaussian rewards

Statement

Let $q \geq 1$ be an integer. Let $Z_{1}, \dots, Z_{q}$ be mutually independent integrable real random variables on a common probability space, with means $m_{j} = E [Z_{j}]$ , and suppose each is 1-sub-Gaussian, meaning that $E [\exp (λ (Z_{j} - m_{j}))] \leq \exp (λ^{2} / 2)$ for every $λ \in R$ . Then for every $t \geq 0$ ,

P ⁣ (\sum_{j = 1}^{q} (Z_{j} - m_{j}) \geq t) \leq \exp ⁣ (- \frac{t^{2}}{2 q}), P ⁣ (\sum_{j = 1}^{q} (Z_{j} - m_{j}) \leq - t) \leq \exp ⁣ (- \frac{t^{2}}{2 q}) .

Statement references

Tor Lattimore and Csaba Szepesvári, Bandit Algorithms: §5.3, Theorem 5.3 and Corollary 5.5, PDF pp. 86–87 / printed pp. 77–78; the independent-sum step is Exercise 5.7.

Sébastien Bubeck and Nicolò Cesa-Bianchi, Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems: Chapter 2 §2.2, Equation (2.2) and fixed-sample MGF tail derivation, PDF pp. 13–14 / printed pp. 10–11.

Facts & Assumptions

Given: A finite family of mutually independent integrable real random variables $Z_{1}, \dots, Z_{q}$ , their means $m_{j}$ , and the 1-sub-Gaussian MGF bounds in the statement.

[F1]

For each $j$ and every real $λ$ , $E [\exp (λ (Z_{j} - m_{j}))] \leq \exp (λ^{2} / 2)$ (Centered 1-sub-Gaussian reward).

[F2]

Independence means the generated sigma-algebras are independent (Independent random elements); therefore the joint law of the finite vector is the product of its marginal laws (Independent random elements have product joint law).

[F3]

Tonelli permits iterated integration of nonnegative product-measurable functions over sigma-finite product spaces (Tonelli's theorem for nonnegative measurable functions on a sigma-finite product); positive scalar factors may be taken outside nonnegative integrals (Monotonicity and nonnegative homogeneity of the nonnegative integral).

[F4]

Expectation of a nonnegative random variable is its Lebesgue integral (Expectation of a nonnegative or integrable random variable).

[F5]

For a nonnegative random variable $W$ and $a > 0$ , $P (W \geq a) \leq E [W] / a$ (Markov's inequality for random variables).

[F6]

The real exponential satisfies $\exp (x + y) = \exp (x) \exp (y)$ (The exponential addition formula $\exp (x + y) = \exp (x) \exp (y)$ ), is positive (The exponential is positive and satisfies $\exp (- x) = 1 / \exp (x)$ ), and is strictly increasing (The exponential function is strictly increasing).

Proof

1.1F2F3F4F6

Put $S = \sum_{j = 1}^{q} (Z_{j} - m_{j})$ . For $q = 1$ the desired MGF bound is [F1]. For $q \geq 2$ and $λ \geq 0$ , the product-law identity in [F2] and the exponential addition formula in [F6] give $E [e^{λ S}] = \int_{R^{q}} \prod_{j = 1}^{q} e^{λ (z_{j} - m_{j})} d ⁣ (⨂_{j = 1}^{q} P_{Z_{j}}) (z_{1}, \dots, z_{q})$ . The integrand is nonnegative and measurable by [F6]. Repeated application of Tonelli in [F3], grouping the first $q - 1$ factors and the last factor, factors this integral into the product of the $q$ one-dimensional integrals.

2.1step 1.1F1F6algebra

Each factor is at most $e^{λ^{2} / 2}$ by [F1], so $E [e^{λ S}] \leq e^{q λ^{2} / 2}$ . The same argument with $- λ$ gives $E [e^{- λ S}] \leq e^{q λ^{2} / 2}$ .

3.1givenstep 2.1F5F6choosealgebra

If $t > 0$ and $λ > 0$ , strict increase and positivity of the exponential in [F6] identify ${S \geq t} = {e^{λ S} \geq e^{λ t}}$ . Markov's inequality [F5] and step 2.1 yield $P (S \geq t) \leq e^{q λ^{2} / 2 - λ t}$ . Choosing $λ = t / q$ gives $P (S \geq t) \leq e^{- t^{2} / (2 q)}$ .

4.1givenstep 2.1F5F6algebra∎

Applying the same argument to $- S$ gives $P (S \leq - t) \leq e^{- t^{2} / (2 q)}$ . At $t = 0$ both asserted bounds reduce to the probability bound $1 \leq 1$ .

Depends on

Used by

Dependency tree · two levels

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