LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck pass

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.

Conditional sub-Gaussian bounds allow bounded predictable coefficients

Statement

Assume the Axiom of Choice. Let $(Ω, F, P)$ be a probability space, let $G \subseteq F$ be a sub-sigma-algebra, and let $η$ be a real random variable such that, for every $q \in R$ , $e^{q η}$ is integrable and

$E [e^{q η} ∣ G] \leq e^{q^{2} / 2} almost surely .$

Then for every bounded, real, $G$ -measurable random variable $Q$ ,

$E [e^{Q η - Q^{2} / 2} ∣ G] \leq 1 almost surely .$

Statement references

Tor Lattimore and Csaba Szepesvári, Bandit Algorithms, §20.1

Abbasi-Yadkori, Pál, and Szepesvári, Lemma 1

Facts & Assumptions

Given: AC, a probability space, a sub-sigma-algebra $G$ , and an integrable real random variable $η$ whose exponential moments satisfy the Statement.

[F1]

Conditional expectation given a sigma algebra: a conditional-expectation version is $G$ -measurable and integrable, and its event integrals equal those of the conditioned variable.

[F2]

Basic algebra and order properties of conditional expectation: conditional expectation is linear and order preserving, preserves total expectation, and satisfies $∣ E [X ∣ G] ∣ \leq E [∣ X ∣ ∣ G]$ almost surely. AC is required for the supplied conditional-expectation classes.

[F3]

The exponential function is smooth and $(\exp)^{'} = \exp$ and The chain rule, in one line from Carathéodory: if $g$ is differentiable at $c$ and $f$ is differentiable at $g (c)$ , then $f \circ g$ is differentiable at $c$ with $(f \circ g)^{'} (c) = f^{'} (g (c)) g^{'} (c)$ : $\frac{d}{d q} e^{q η - q^{2} / 2} = (η - q) e^{q η - q^{2} / 2}$ for each fixed finite value of $η$ .

[F4]

The mean value theorem, as the case $g (x) = x$ of Cauchy's: for $f$ continuous on $[a, b]$ with $a < b$ and differentiable on $(a, b)$ there is $c \in (a, b)$ with $f (b) - f (a) = f^{'} (c) (b - a)$ : a differentiable real function on an interval has each increment equal to its derivative at an intermediate point times the interval length.

[A1]

The Axiom of Choice: every family of nonempty sets has a choice function; this supplies the conditional-expectation versions used in [F2].

Proof

1.1givenA1F1F2algebra

First suppose $Q = \sum_{j = 1}^{m} q_{j} 1_{B_{j}}$ for a finite measurable partition $B_{1}, \dots, B_{m}$ in $G$ . Choose conditional-expectation versions $Y_{j} = E [e^{q_{j} η} ∣ G]$ and set $Y = \sum_{j} 1_{B_{j}} e^{- q_{j}^{2} / 2} Y_{j}$ . Both $Y$ and $e^{Q η - Q^{2} / 2}$ are integrable, and $Y$ is $G$ -measurable. For every $B \in G$ , [F1] applied on $B \cap B_{j}$ gives $\int_{B} Y d P = \sum_{j} e^{- q_{j}^{2} / 2} \int_{B \cap B_{j}} Y_{j} d P = \sum_{j} e^{- q_{j}^{2} / 2} \int_{B \cap B_{j}} e^{q_{j} η} d P = \int_{B} e^{Q η - Q^{2} / 2} d P .$ Thus $Y$ is the required conditional-expectation version. The assumed fixed- $q_{j}$ bounds make it at most $\sum_{j} 1_{B_{j}} = 1$ outside a finite union of null sets.

1.2givenconstruct

For a bounded $Q$ , choose $K \geq 1$ with $∣ Q ∣ \leq K$ and let $Q_{r}$ be the finite-valued $G$ -measurable rounding of $Q$ down to the grid $2^{- r} Z$ ; then $∣ Q_{r} - Q ∣ \leq 2^{- r}$ and $∣ Q_{r} ∣ \leq K + 1$ .

2.1F2F3F4step 1.2algebra

For fixed $ω$ , put $g_{ω} (q) = e^{q η (ω) - q^{2} / 2}$ . By [F3]–[F4], on $[- K - 1, K + 1]$ its increments satisfy $∣ g_{ω} (q) - g_{ω} (q^{'}) ∣ \leq ∣ q - q^{'} ∣ (∣ η (ω) ∣ + K + 1) e^{(K + 1) ∣ η (ω) ∣} .$ For $x \geq 0$ , $(x + K + 1) e^{(K + 1) x} \leq (K + 2) e^{(K + 2) x}$ because $x + K + 1 \leq (K + 2) e^{x}$ . Also $e^{(K + 2) ∣ η ∣} \leq e^{(K + 2) η} + e^{- (K + 2) η}$ , whose expectation is at most $2 e^{(K + 2)^{2} / 2}$ by [F2]. The Lipschitz envelope is therefore integrable, so $∣ Q_{r} - Q ∣ \leq 2^{- r}$ implies $E ∣ g (Q_{r}) - g (Q) ∣ \to 0$ .

3.1step 1.1step 2.1F2algebra∎

Set $Y_{r} = E [g (Q_{r}) ∣ G]$ and $Y = E [g (Q) ∣ G]$ . By [F2] and step 2.1, $E ∣ Y_{r} - Y ∣ \leq E ∣ g (Q_{r}) - g (Q) ∣ \to 0$ . Step 1.1 gives $Y_{r} \leq 1$ almost surely for every $r$ ; after removing the countable union of their exceptional null sets, $(Y - 1)_{+} \leq ∣ Y - Y_{r} ∣$ for each $r$ . Taking expectations and passing to the limit gives $E [(Y - 1)_{+}] = 0$ , hence $Y \leq 1$ almost surely.

Depends on

Used by

The conditional Gaussian mixture is a nonnegative supermartingale Lemma

Dependency tree · two levels

34 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)
Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári, Online Least Squares Estimation with Self-Normalized Processes: An Application to Bandit Problems (standard reference, not scraped)