Pipeline-generated

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.

Stochastic finite-armed bandits

1 · Prerequisites

2 · Logical flowchart

3 · Definitions, theorems and proofs

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Centered 1-sub-Gaussian reward

Definition

Let $X$ be an integrable real random variable on a probability space, and write $μ = E [X]$ . The reward $X$ is 1-sub-Gaussian if for every $λ \in R$ ,

E ⁣ [\exp ⁣ (λ (X - μ))] \leq \exp ⁣ (\frac{λ^{2}}{2}) .

The expectation in this condition is the nonnegative Lebesgue integral of the displayed exponential; the inequality requires it to be finite for every real $λ$ .

Definition references

Random elements and real random variables: a real random variable is a measurable map into $(R, B (R))$ .

Expectation of a nonnegative or integrable random variable: expectation is the Lebesgue integral against the underlying probability measure, finite for an integrable real random variable.

The real exponential function and the number $e$ by a power series: $\exp (x)$ is the real exponential function defined for every $x \in R$ .

Tor Lattimore and Csaba Szepesvári, Bandit Algorithms: Definition 5.2, PDF p. 86 / printed p. 77; centered-noise convention, PDF p. 88 / printed p. 79.

Sébastien Bubeck and Nicolò Cesa-Bianchi, Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems: Equation (2.2), Chapter 2 §2.2, PDF p. 13 / printed p. 10.

LemmaStatement: AI-adaptedProof: AI-generatedjudge pass (gpt-6-luna)Open item page →

The zeta sums at 2 and 3 are finite

Statement

For $p \in {2, 3}$ , let $ζ_{p} : = \sum_{k = 1}^{\infty} k^{- p}$ , where each positive integer in the summand is identified with its canonical real image. Both sums converge and satisfy $ζ_{p} \geq 1$ .

Statement references

For a nonincreasing nonnegative sequence, $\sum a_{k}$ converges iff $\sum 2^{k} a_{2^{k}}$ converges: convergence of a nonnegative nonincreasing series is equivalent to convergence of its condensed series.

For $∣ r ∣ < 1$ , $\sum_{k \geq 0} r^{k} = 1 / (1 - r)$ , and for $∣ r ∣ \geq 1$ the series diverges: a geometric series with ratio of absolute value less than one converges.

Integer powers $a^{m}$ : negative integer powers of a nonzero real are defined by reciprocals of natural powers.

The canonical natural $ι (n) = n \cdot 1_{F}$ of a field: positive natural indices are represented by their canonical real images.

Canonical naturals are positive and strictly increasing: canonical real images of positive naturals are positive.

Facts & Assumptions

Given: An integer $p \in {2, 3}$ and the sequence $a_{k} = k^{- p}$ for positive integer $k$ , with integer indices interpreted in $R$ by the canonical embedding.

[F1]

If a nonnegative sequence $(a_{k})_{k \geq 1}$ is nonincreasing, then $\sum_{k \geq 1} a_{k}$ converges if and only if $\sum_{r \geq 0} 2^{r} a_{2^{r}}$ converges (For a nonincreasing nonnegative sequence, $\sum a_{k}$ converges iff $\sum 2^{k} a_{2^{k}}$ converges).

[F2]

A geometric series $\sum_{r \geq 0} q^{r}$ converges whenever $∣ q ∣ < 1$ (For $∣ r ∣ < 1$ , $\sum_{k \geq 0} r^{k} = 1 / (1 - r)$ , and for $∣ r ∣ \geq 1$ the series diverges).

[F3]

For a positive integer $k$ , its real image is positive, and its negative integer powers are reciprocals of its natural powers (Integer powers $a^{m}$ , The canonical natural $ι (n) = n \cdot 1_{F}$ of a field, Canonical naturals are positive and strictly increasing).

Proof

1.1givenF3algebra

For $p = 2$ or $p = 3$ , every $a_{k} = k^{- p}$ is positive. If $1 \leq k \leq ℓ$ , then $ℓ^{p} \geq k^{p} > 0$ : for $p = 2$ this follows from $ℓ^{2} - k^{2} = (ℓ - k) (ℓ + k) \geq 0$ , and for $p = 3$ from $ℓ^{3} - k^{3} = (ℓ - k) (ℓ^{2} + ℓ k + k^{2}) \geq 0$ . Taking reciprocals reverses the inequality, so $a_{ℓ} \leq a_{k}$ .

1.2givenF2F3inductionalgebra

For $p = 2$ , the condensed term is $2^{r} / (2^{r})^{2} = 1 / 2^{r} = (1 / 2)^{r}$ . For $p = 3$ , it is $2^{r} / (2^{r})^{3} = 1 / (2^{r})^{2} = (1 / 4)^{r}$ . The final power identities follow by induction on $r$ from the recursive definition of natural powers. Thus the condensed series is geometric with ratio $1 / 2$ or $1 / 4$ , respectively; [F2] makes both series converge.

2.1givenF1step 1.1step 1.2algebra∎

The sequence is nonnegative and nonincreasing by step 1.1, and its condensed series converges by step 1.2. Apply [F1] to conclude that $ζ_{p}$ converges. Its first term is $1$ and all terms are positive, hence $ζ_{p} \geq 1$ .

LemmaStatement: AI-adaptedProof: AI-generatedjudge pass (gpt-6-luna)Open item page →

Expectation of a countably valued nonnegative random variable is its weighted series

Statement

Let $(Ω, F, P)$ be a probability space. Let $(E_{j})_{j \geq 1}$ be a countable measurable partition of $Ω$ , let $c_{j} \in [0, \infty)$ be finite real numbers, and let $Z : Ω \to [0, \infty)$ be measurable with $Z = c_{j}$ on $E_{j}$ . Then, as an extended nonnegative value,

E [Z] = \sum_{j = 1}^{\infty} c_{j} P (E_{j}) .

If this series is finite, then $Z$ is integrable and its expectation is that finite sum.

Statement references

Probability measures and probability spaces: a probability measure has total mass one.

Expectation of a nonnegative or integrable random variable: expectation of a nonnegative measurable random variable is its Lebesgue integral.

Integrable real and complex functions, and their integrals: a real measurable function is integrable exactly when the integral of its absolute value is finite.

Linearity, monotonicity, and the modulus bound for expectation: expectation is linear on integrable real random variables.

The expectation of an indicator is the probability of the event: the expectation of an event indicator equals its probability.

Monotone convergence for the integral: integrals of increasing nonnegative measurable functions converge to the integral of their pointwise limit.

Series in the nonnegative extended real line: a nonnegative extended series is the supremum of its finite partial sums, including when the value is $+ \infty$ .

Facts & Assumptions

Given: A probability space, a countable measurable partition $(E_{j})_{j \geq 1}$ , finite constants $c_{j} \geq 0$ , and a measurable $Z$ equal to $c_{j}$ on each $E_{j}$ .

[F1]

If measurable nonnegative functions increase pointwise to $Z$ , their integrals increase to $\int Z d P$ (Monotone convergence for the integral).

[F2]

On a probability space, expectation of a nonnegative measurable variable is its nonnegative Lebesgue integral; a real measurable variable is integrable when the integral of its absolute value is finite; a nonnegative extended series is the supremum of its partial sums (Probability measures and probability spaces, Expectation of a nonnegative or integrable random variable, Integrable real and complex functions, and their integrals, Series in the nonnegative extended real line).

[F3]

Event indicators have expectation equal to event probability, and expectation is linear on finite sums of integrable real variables (The expectation of an indicator is the probability of the event, Linearity, monotonicity, and the modulus bound for expectation).

Proof

1.1givenF2construct

For $N \geq 1$ , define $Z_{N} : = \sum_{j = 1}^{N} c_{j} 1_{E_{j}}$ . This is a measurable nonnegative simple function. On $E_{j}$ , $Z_{N} = 0$ for $N < j$ and $Z_{N} = c_{j} = Z$ for $N \geq j$ , so $Z_{N} ↑ Z$ . Each $Z_{N}$ is bounded by the finite maximum of $c_{1}, \dots, c_{N}$ , hence is integrable on the probability space.

2.1step 1.1F3algebra

By linearity and the indicator identity in [F3], $E [Z_{N}] = \sum_{j = 1}^{N} c_{j} P (E_{j})$ .

3.1step 1.1step 2.1F1F2

Apply monotone convergence [F1] to step 1.1 and then use step 2.1. The resulting supremum of finite partial sums is exactly the nonnegative extended sum $\sum_{j = 1}^{\infty} c_{j} P (E_{j})$ by [F2], proving the extended-valued identity.

4.1givenF2step 3.1∎

If the series is finite, step 3.1 gives $\int Z d P < \infty$ . Since $Z \geq 0$ , $∣ Z ∣ = Z$ , so [F2] shows $Z$ is integrable and its ordinary expectation is the same finite sum.

LemmaStatement: AI-adaptedProof: AI-generatedjudge pass (gpt-6-luna)Open item page →

A deterministic-prefix envelope sum for the sharper UCB count bound

Statement

Let $n \geq 5$ be an integer, let $a > 0$ , and put $L = \log n$ . For $x \geq 0$ define $x_{+} = \max {x, 0}$ and $f (x) = \exp (- \frac{(a \sqrt{x} - 2 \sqrt{L})_{+}^{2}}{2}) .$ Then $\sum_{s = 1}^{n - 1} f (s) \leq 1 + \frac{8 L}{a^{2}} .$ For $n \geq 12$ the stronger bound $\sum_{s = 1}^{n - 1} f (s) \leq 8 L / a^{2}$ holds. All integrals in the proof are proper Riemann integrals or their separately convergent improper limits.

Statement references

Lattimore and Szepesvári, Bandit Algorithms, Theorems 7.1–7.2: supplies the UCB proof context; this deterministic estimate is proved locally.

Facts & Assumptions

Given: The integer $n$ , positive $a$ , and $L = \log n$ in the Statement.

[F1]

The Gaussian integral is $\int_{- \infty}^{\infty} e^{- x^{2}} d x = \sqrt{π}$ . The Gaussian integral $\int_{- \infty}^{\infty} e^{- x^{2}} d x = \sqrt{π}$

[F2]

A monotone differentiable surjection between improper intervals preserves the integral, with absolute Jacobian, when its derivative is locally integrable and proper substitution holds on every compact truncation. Change of variable in an improper integral

[F3]

Proper substitution holds for a differentiable substitution with integrable derivative and continuous integrand on an interval containing its image. Substitution: if $φ$ is differentiable on $[c, d]$ with $φ^{'}$ integrable and $f$ is continuous on an interval containing $φ ([c, d])$ , then $\int_{φ (c)}^{φ (d)} f = \int_{c}^{d} (f \circ φ) φ^{'}$

[F4]

For $u > 0$ , $\log^{'} (u) = 1 / u$ and $\log u = \int_{1}^{u} d t / t$ ; logarithms are increasing and obey the product law. The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm

[F5]

Principal arctangent satisfies $(\arctan x)^{'} = 1 / (1 + x^{2})$ , $\arctan x = \int_{0}^{x} d t / (1 + t^{2})$ , and $\arctan 1 = π / 4$ . Principal arctangent: derivative, integral, power series, and the Gregory–Leibniz series

[F6]

An integrable derivative integrates to the endpoint difference; integration preserves pointwise inequalities between integrable functions. The second fundamental theorem: if $G$ is differentiable on $[a, b]$ with $G^{'} = f$ and $f$ is integrable, then $\int_{a}^{b} f = G (b) - G (a)$ If $f \leq g$ on $[a, b]$ and both are integrable then $\int_{a}^{b} f \leq \int_{a}^{b} g$ ; and $m (b - a) \leq \int_{a}^{b} f \leq M (b - a)$

[F7]

The exponential has derivative equal to itself, and the chain rule differentiates compositions. The exponential function is smooth and $(\exp)^{'} = \exp$ 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)$

[F8]

Convergent improper integrals can be split at a finite interior point and combined linearly. Improper convergence is independent of finite truncations and split points Linearity of convergent improper integrals

[F9]

Nonnegative reals have unique nonnegative square roots. Square roots exist: a unique $\sqrt{a} \geq 0$ with $(\sqrt{a})^{2} = a$ ; the positives are ${x^{2} : x \neq 0}$

[F10]

A continuous function on an interval is decreasing when its derivative is negative throughout the interior. On an interval $I$ , for $f$ continuous on $I$ and differentiable at every interior point: $f^{'} \geq 0$ throughout gives $f$ nondecreasing, $f^{'} > 0$ gives $f$ increasing, $f^{'} \leq 0$ and $f^{'} < 0$ give the two decreasing forms; conversely a nondecreasing $f$ has $f^{'} \geq 0$ and a nonincreasing $f$ has $f^{'} \leq 0$ wherever it is differentiable, and no strict converse is claimed

[F11]

The exponential is positive and strictly increasing. The exponential function is strictly increasing The exponential is positive and satisfies $\exp (- x) = 1 / \exp (x)$

[F12]

Polynomial powers differentiate by the power rule, and sums, products and nonvanishing quotients obey the derivative algebra. For a natural $n \geq 1$ the function $x \mapsto x^{n}$ is differentiable everywhere with derivative $ι (n) x^{n - 1}$ ; for $n = 0$ it is the constant $1$ , with derivative $0$ ; for a natural $n \geq 1$ the function $x \mapsto x^{- n}$ is differentiable at every $x \neq 0$ with derivative $- ι (n) x^{- n - 1}$ ; consequently every polynomial function is differentiable at every real, with the derivative computed term by term Sums, scalar multiples, products and quotients: $(f + g)^{'} (c) = f^{'} (c) + g^{'} (c)$ , $(α f)^{'} (c) = α f^{'} (c)$ , $(f g)^{'} (c) = f^{'} (c) g (c) + f (c) g^{'} (c)$ , and $(f / g)^{'} (c) = (f^{'} (c) g (c) - f (c) g^{'} (c)) / g (c)^{2}$ when $g (c) \neq 0$

[F13]

The exponential tends to zero at negative infinity. The exponential tends to $+ \infty$ at $+ \infty$ and to $0$ at $- \infty$

[F14]

The real exponential is continuous, positive, strictly increasing, and satisfies $\exp (0) = 1$ (The real exponential function and the number $e$ by a power series, The exponential function is strictly increasing, The exponential is positive and satisfies $\exp (- x) = 1 / \exp (x)$ ).

[F15]

Sums and scalar multiples of continuous real functions are continuous, every real polynomial map is continuous, and continuous maps compose continuously (Sums, scalar multiples, products, absolute values, maxima, minima and quotients with nonvanishing denominator of continuous functions are continuous, as are constants, the identity and every polynomial function, A composite of continuous functions is continuous, with no side hypothesis of the kind the composition of limits needs).

[F16]

A continuous real function on a compact interval is Riemann integrable (A continuous function on $[a, b]$ is Riemann integrable, by Heine-Cantor and Riemann's criterion).

[F17]

For an integrable function, proper integrals add over adjacent subintervals (For $a < c < b$ : $f$ is integrable on $[a, b]$ if and only if it is integrable on $[a, c]$ and on $[c, b]$ , and then $\int_{a}^{b} f = \int_{a}^{c} f + \int_{c}^{b} f$ ; with the oriented form for arbitrary $a, b, c$ ).

Proof

1.1givenF6F8F9F14F15F16F17algebraF11

By [F9], for $0 \leq x < y$ the identity $y - x = (\sqrt{y} - \sqrt{x}) (\sqrt{y} + \sqrt{x})$ and $\sqrt{y} + \sqrt{x} > 0$ imply $\sqrt{x} < \sqrt{y}$ : indeed $y > 0$ , and $\sqrt{y} > 0$ follows because its square is $y$ . Thus the nonnegative square-root map is increasing. It is continuous at every $x_{0} > 0$ , since $\sqrt{x} + \sqrt{x_{0}} \geq \sqrt{x_{0}} > 0$ and $∣ \sqrt{x} - \sqrt{x_{0}} ∣ = \frac{∣ x - x_{0} ∣}{\sqrt{x} + \sqrt{x_{0}}} \leq \frac{∣ x - x_{0} ∣}{\sqrt{x_{0}}};$ given $ε > 0$ , $∣ x - x_{0} ∣ < ε \sqrt{x_{0}}$ makes this difference less than $ε$ . At $x_{0} = 0$ , for each $ε > 0$ , $0 \leq x < ε^{2}$ implies $\sqrt{x} < \sqrt{ε^{2}} = ε$ , so it is continuous there as well. The map $u \mapsto u_{+}$ is nondecreasing and continuous, since $∣ u_{+} - v_{+} ∣ \leq ∣ u - v ∣$ by its sign cases. Thus $a \sqrt{x} - 2 \sqrt{L}$ and its positive part are continuous, and [F15] makes the final composition defining $f$ continuous. The positive part is nonnegative and nondecreasing; for $0 \leq u \leq v$ , $v^{2} - u^{2} = (v - u) (v + u) \geq 0$ , so squaring preserves that order. Hence the exponent is nonincreasing, and [F14] makes $f$ nonincreasing; its exponent is nonpositive, so positivity, monotonicity and $\exp (0) = 1$ give $0 < f \leq 1$ . The continuous function $f$ is integrable on $[0, n - 1]$ by [F16], and repeated use of [F17] gives $\int_{0}^{n - 1} f = \sum_{s = 1}^{n - 1} \int_{s - 1}^{s} f$ . For $x \in [s - 1, s]$ , $f (x) \geq f (s)$ ; [F6] gives $f (s) \leq \int_{s - 1}^{s} f (x) d x$ . Hence $S : = \sum_{s = 1}^{n - 1} f (s) \leq \int_{0}^{n - 1} f (x) d x$ . If $\int_{0}^{\infty} f$ converges, nonnegativity of the tail and [F8] give $\int_{0}^{n - 1} f \leq \int_{0}^{\infty} f$ . Also $S \leq n - 1$ .

1.2F1F2F6F7F8F12F13given

Write $b = 2 \sqrt{L} > 0$ . The integrands $e^{- y^{2} / 2}$ and $y e^{- y^{2} / 2}$ are continuous on every compact truncation of $[0, \infty)$ . Evenness in [F1] and the scaling $y = \sqrt{2} x$ give $\int_{0}^{\infty} e^{- y^{2} / 2} d y = \sqrt{π / 2}$ by [F2], with convergence inherited from the Gaussian integral. The primitive $- e^{- y^{2} / 2}$ gives $\int_{0}^{\infty} y e^{- y^{2} / 2} d y = 1$ by [F6] and [F7]; the endpoint limit follows from [F13]. The substitutions are increasing smooth surjections on the half-lines, with continuous derivatives and continuous integrands on every compact truncation, so all hypotheses of [F2] hold and these two improper integrals converge separately.

1.3F5F6F12algebra

The integrand $x^{4} (1 - x)^{4} / (1 + x^{2})$ is continuous on $[0, 1]$ , since $1 + x^{2} > 0$ there. Polynomial division gives $\frac{x^{4} (1 - x)^{4}}{1 + x^{2}} = x^{6} - 4 x^{5} + 5 x^{4} - 4 x^{2} + 4 - \frac{4}{1 + x^{2}} .$ Integrating on $[0, 1]$ using [F5] and [F6] yields $\int_{0}^{1} \frac{x^{4} (1 - x)^{4}}{1 + x^{2}} d x = \frac{1}{7} - \frac{2}{3} + 1 - \frac{4}{3} + 4 - π = \frac{22}{7} - π > 0.$ The strict positivity follows because the integrand is nonnegative and on $[1 / 4, 3 / 4]$ is at least $1 / (2 \cdot 4^{8}) > 0$ . Thus $π < 22 / 7$ .

2.1F2F3F8F9step 1.2algebra

On $[0, b^{2} / a^{2}]$ , $f = 1$ . On the remaining half-line use $x = (y + b)^{2} / a^{2}$ , whose derivative $2 (y + b) / a^{2}$ is positive and continuous and whose image is exactly $[b^{2} / a^{2}, \infty)$ . Proper substitution applies on compact truncations by [F3], so [F2], [F8], and step 1.2 give $\int_{0}^{\infty} f (x) d x = \frac{b^{2}}{a^{2}} + \frac{2}{a^{2}} \int_{0}^{\infty} (y + b) e^{- y^{2} / 2} d y = \frac{4 L + 2 + \sqrt{8 π L}}{a^{2}} .$ This proves finiteness and justifies step 1.1.

2.2F3F4F6F12step 1.3algebra

Put $z = (u - 1) / (u + 1)$ for $u > 1$ , so $0 < z < 1$ and $1 / (1 - t^{2})$ is continuous on $[0, z]$ . The increasing substitution $t \mapsto (1 + t) / (1 - t)$ on $[0, z]$ has continuous derivative and takes that interval onto $[1, u]$ . Hence [F3] and [F4] give $\log u = 2 \int_{0}^{z} d t / (1 - t^{2})$ . For every integer $q \geq 0$ , the finite geometric identity gives $1 / (1 - t^{2}) \geq \sum_{j = 0}^{q} t^{2 j}$ on this interval. Integrating this polynomial by [F6] proves $\log u \geq 2 \sum_{j = 0}^{q} \frac{z^{2 j + 1}}{2 j + 1} .$ At $u = 2, q = 1$ , $u = 3, q = 2$ , and $u = 5, q = 2$ , respectively, this yields $\log 2 \geq \frac{56}{81}, \log 3 \geq \frac{263}{240}, \log 5 \geq \frac{1924}{1215} > \frac{11}{7} > \frac{π}{2} .$

3.1F4step 2.2algebra

By [F4] and step 2.2, $\log 12 = 2 \log 2 + \log 3 \geq \frac{16061}{6480} > \frac{99}{40}, \log 11 > \log 10 = \log 2 + \log 5 \geq \frac{2764}{1215} > \frac{9}{4} .$ All comparisons follow by multiplying positive integer denominators; no decimal approximation is used.

4.1F6F9step 1.1step 2.1step 1.3step 3.1algebra

Define $D (L) = 2 + \sqrt{8 π L} - 4 L$ . If $n \geq 12$ , step 3.1 gives $L > 99 / 40$ . At $L_{0} = 99 / 40$ , $(4 L_{0} - 2)^{2} = \frac{6241}{100} > 8 \frac{22}{7} \frac{99}{40} > 8 π L_{0},$ so $D (L_{0}) < 0$ . For $L_{2} > L_{1} \geq L_{0} > 1$ , the difference of $4 L - 2 - \sqrt{8 π L}$ at these two values equals $(\sqrt{L_{2}} - \sqrt{L_{1}}) (4 (\sqrt{L_{2}} + \sqrt{L_{1}}) - \sqrt{8 π}) > 0$ , since $π < 22 / 7 < 8$ . Thus $D (L) \leq 0$ here. Steps 1.1 and 2.1 give $S \leq 8 L / a^{2}$ , the asserted stronger bound.

4.2F4F6F9F10F12step 2.2step 3.1algebra

Suppose $5 \leq n \leq 11$ . Step 2.2 gives $L > π / 2$ , whence $\sqrt{8 π L} \leq 4 L$ and $D (L) \leq 2$ . For $g (x) = 4 \log x - x + 2$ , the derivative $g^{'} (x) = 4 / x - 1$ is continuous and negative on $[5, 11]$ , so $g$ is decreasing there. Step 3.1 gives $g (11) > 0$ , hence $g (n) \geq g (11) > 0$ and therefore $n - 2 \leq 4 L$ .

5.1givenstep 1.1step 2.1step 4.1step 4.2casesalgebra∎

If $D (L) \leq 0$ , steps 1.1 and 2.1 already give $S \leq 8 L / a^{2}$ . If $D (L) > 0$ and $a^{2} \geq D (L)$ , those steps give $S \leq (8 L + D (L)) / a^{2} \leq 8 L / a^{2} + 1$ . If $0 < a^{2} < D (L) \leq 2$ , step 4.2 gives $(n - 2) a^{2} \leq (n - 2) D (L) \leq 2 (n - 2) \leq 8 L$ , so $S \leq n - 1 \leq 1 + 8 L / a^{2}$ . These cases exhaust $5 \leq n \leq 11$ and prove the Statement together with step 4.1.

LemmaStatement: Literature-sourcedProof: AI-generatedjudge pass (gpt-6-luna)Open item page →

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$ .

DefinitionDefinition: Literature-sourcedProof: Not applicableOpen item page →

Finite stochastic bandit model, gaps, and regret

Definition

Fix positive integers $n$ and $k$ , write $[k] = {1, \dots, k}$ , and let $(Ω, F, P)$ be a probability space. A finite-horizon $k$ -armed stochastic bandit in reward-stack form consists of probability measures $P_{i}$ on $(R, B (R))$ with finite first absolute moments, and an independent table of integrable real random variables $(X_{s, i})_{1 \leq s \leq n, i \in [k]}$ such that the table entries are mutually independent and each $X_{s, i}$ has law $P_{i}$ . Its mean for arm $i$ is $μ_{i} = \int_{R} x P_{i} (d x) = E [X_{s, i}]$ , which does not depend on $s$ . The learner may also use a random element $U$ for private randomization, provided $σ (U)$ is independent of the sigma-algebra generated by the entire table; a deterministic learner uses a constant $U$ .

A non-anticipating policy chooses a measurable arm $A_{t} \in [k]$ at each round $t \in [n]$ using only $U$ and the previously observed history $(A_{1}, Y_{1}, \dots, A_{t - 1}, Y_{t - 1})$ . Write $H_{t - 1} = σ (U, A_{1}, Y_{1}, \dots, A_{t - 1}, Y_{t - 1})$ for that history sigma-algebra. Define the pull count $T_{i} (0) = 0$ and

T_{i} (t) = \sum_{r = 1}^{t} 1_{{A_{r} = i}}, Y_{t} = X_{T_{A_{t}} (t), A_{t}} .

Thus each time arm $i$ is selected the learner receives the next unused entry in arm $i$ 's reward stack. Set

μ^{*} = \max_{i \in [k]} μ_{i}, Δ_{i} = μ^{*} - μ_{i} \geq 0,

define the pseudo-regret ${\overset{ˉ}{R}}_{n} = \sum_{t = 1}^{n} (μ^{*} - μ_{A_{t}})$ , and define the realized reward regret $R_{n}^{r e w} = n μ^{*} - \sum_{t = 1}^{n} Y_{t}$ and expected reward regret $R_{n} = E [R_{n}^{r e w}]$ .

Each $Y_{t}$ is integrable because it selects one entry of the finite table, so $∣ Y_{t} ∣ \leq \sum_{s = 1}^{n} \sum_{i = 1}^{k} ∣ X_{s, i} ∣$ and the right-hand side is integrable. Hence $R_{n}^{r e w}$ is integrable as well.

Definition references

Online decision protocol: the learner chooses before the current round's feedback and uses only earlier revealed history.

Adversary and feedback models: a stochastic finite-arm environment has a fixed probability law for each arm, finite first moments, and the stated conditional reward-law convention.

Static, dynamic, interval, and strongly adaptive regret: pseudo-regret is the sum of mean gaps along the action sequence; realized reward regret subtracts the observed rewards; expected regret integrates realized regret.

Random elements and real random variables: table entries and learner randomization are measurable random elements, with the table entries real-valued.

Law or distribution of a random element: the law of a random element is the pushforward probability measure on its measurable target space.

Change of variables for expectation: expectation of an integrable measurable function of a random element equals its integral against the law, in particular for the identity function on the real line.

Expectation of a nonnegative or integrable random variable: expectation of an integrable real random variable is its Lebesgue integral.

Linearity, monotonicity, and the modulus bound for expectation: finite linear combinations of integrable random variables are integrable and expectation is linear.

Independent random elements: the table entries are mutually independent as random elements, and learner randomization is independent of the table.

Tor Lattimore and Csaba Szepesvári, Bandit Algorithms: §4.1, PDF p. 65 / printed p. 56; §§4.4–4.6, PDF pp. 69–74 / printed pp. 60–65.

Sébastien Bubeck and Nicolò Cesa-Bianchi, Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems: Chapter 2, PDF pp. 11–12 / printed pp. 8–9.

AlgorithmAlgorithm: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Explore-then-commit for a finite stochastic bandit

Definition

Input integers $k, n, m \geq 1$ with $m k \leq n$ , and access to an $n$ -round $k$ -armed stochastic bandit. The output is the sequence of selected arms $A_{1}, \dots, A_{n}$ and the committed arm $J$ .

For rounds $t = 1, \dots, m k$ , choose arm $A_{t} = 1 + ((t - 1) m o d k)$ and observe its reward $Y_{t}$ . Thus each arm is explored exactly $m$ times.
For each $i \in [k]$ , form its exploration mean ${\hat{μ}}_{i} = \frac{1}{m} \sum_{r = 1}^{m} Y_{(r - 1) k + i} .$
Let $J$ be the least index attaining $\max_{i \in [k]} {\hat{μ}}_{i}$ .
For every remaining round $t = m k + 1, \dots, n$ , choose $A_{t} = J$ and observe its reward.

Definition references

Finite stochastic bandit model, gaps, and regret: the horizon, finite arm set, reward observations, and non-anticipating round order used by the procedure.

Tor Lattimore and Csaba Szepesvári, Bandit Algorithms: Chapter 6 §6.1, Algorithm 1, PDF p. 101 / printed p. 92.

AlgorithmAlgorithm: Literature-sourcedProof: Not applicableOpen item page →

Finite-horizon upper-confidence-bound bandit algorithm

Definition

Input integers $k, n$ with $1 \leq k \leq n$ , a confidence parameter $δ \in (0, 1)$ , and access to an $n$ -round $k$ -armed stochastic bandit. Output the selected arms $A_{1}, \dots, A_{n}$ .

Initialize by choosing each arm once: set $A_{t} = t$ for $t = 1, \dots, k$ , and observe each reward.
For each round $t = k + 1, \dots, n$ , compute $T_{i} (t - 1) = \sum_{s = 1}^{t - 1} 1_{{A_{s} = i}}$ for every arm $i$ . If $T_{i} (t - 1) > 0$ , first set ${\hat{μ}}_{i} (t - 1) = (\sum_{s = 1}^{t - 1} 1_{{A_{s} = i}} Y_{s}) / T_{i} (t - 1)$ and then set $U_{i} (t - 1) = {\hat{μ}}_{i} (t - 1) + \sqrt{2 \log (1 / δ) / T_{i} (t - 1)}$ . If $T_{i} (t - 1) = 0$ , set $U_{i} (t - 1) = + \infty$ .
Choose the least index $i$ attaining $\max_{j \in [k]} U_{j} (t - 1)$ as $A_{t}$ , then observe $Y_{t}$ .

Definition references

Finite stochastic bandit model, gaps, and regret: the finite arm set, horizon, pull counts, observed rewards, and round order.

The natural logarithm as the inverse of the exponential function: $\log$ is the inverse of the real exponential on positive reals.

Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm: the natural logarithm is increasing and satisfies the product and quotient laws.

Tor Lattimore and Csaba Szepesvári, Bandit Algorithms: Chapter 7 §7.1, Algorithm 3, PDF p. 112 / printed p. 103.

LemmaStatement: Literature-sourcedProof: AI-generatedjudge pass (gpt-6-luna)Open item page →

The independent reward-stack model has the prescribed conditional arm laws

Statement

In the finite reward-stack model, fix a round $t \in [n]$ , an arm $i \in [k]$ , an event $B \in H_{t - 1}$ with $B \subseteq {A_{t} = i}$ , and a Borel set $C \subseteq R$ . Then

P (B \cap {Y_{t} \in C}) = P (B) P_{i} (C), E [Y_{t} 1_{B}] = μ_{i} P (B) .

In particular, the reward stack satisfies the fixed conditional reward-law and conditional-mean interface for finite-arm stochastic environments.

Statement references

Finite stochastic bandit model, gaps, and regret: the table entries are mutually independent, a policy uses only the revealed history and independent learner randomness, and each pull reveals the next unused entry of the chosen arm's stack.

Adversary and feedback models: the fixed conditional arm-law and conditional-mean identities required by the sequential stochastic reward model.

Tor Lattimore and Csaba Szepesvári, Bandit Algorithms: §4.6, PDF p. 74 / printed p. 65; Exercise 4.4.

Facts & Assumptions

Given: A finite reward-stack model, a non-anticipating policy, a round $t \in [n]$ , an arm $i \in [k]$ , and an event $B \in H_{t - 1}$ contained in ${A_{t} = i}$ .

[F1]

The policy uses only $U$ and the previously revealed actions and rewards; on a fixed action history, the observed rewards are exactly the corresponding initial entries of the arm stacks (Finite stochastic bandit model, gaps, and regret).

[F2]

The learner randomization and all table entries form a finite independent family (Independent random elements), whose joint law is the finite product of its marginal laws (Independent random elements have product joint law).

[F3]

For each arm $i$ , every table entry has law $P_{i}$ and finite first absolute moment, with mean $μ_{i}$ (Finite stochastic bandit model, gaps, and regret).

[F4]

Measurable functions of independent random elements remain independent (Measurable coordinatewise functions preserve independence).

[F5]

Expectations of finite products of mutually independent integrable real random variables factor (Expectation factors over a finite product of mutually independent random variables), and $E [1_{E}] = P (E)$ (The expectation of an indicator is the probability of the event).

[F6]

Expectation is the Lebesgue integral and is linear on integrable real random variables (Expectation of a nonnegative or integrable random variable, Linearity, monotonicity, and the modulus bound for expectation).

Proof

1.1givenF1construct

Partition $B$ by the finitely many past action strings $α = (a_{1}, \dots, a_{t - 1}) \in [k]^{t - 1}$ . Let $c_{j} (α)$ be the number of times arm $j$ occurs in $α$ , and write $B_{α} = B \cap {(A_{1}, \dots, A_{t - 1}) = α}$ . By the recursive non-anticipating policy rule, each $B_{α}$ is measurable with respect to $U$ and the table entries $X_{s, j}$ with $s \leq c_{j} (α)$ : along that fixed action string, those and only those stack entries have been revealed.

2.1givenF1F2step 1.1

If $B_{α}$ is nonempty then $A_{t} = i$ on it, and the next reward is $Y_{t} = X_{c_{i} (α) + 1, i}$ . This table entry is distinct from every coordinate determining $B_{α}$ . By [F2] it is independent of the vector of those coordinates, so the event $B_{α}$ is independent of ${X_{c_{i} (α) + 1, i} \in C}$ for every Borel $C$ . Its law is $P_{i}$ , hence $P (B_{α} \cap {Y_{t} \in C}) = P (B_{α}) P_{i} (C)$ .

3.1givenstep 2.1algebra

The events $B_{α}$ partition $B$ . Summing the identity in step 2.1 over the finite set $[k]^{t - 1}$ gives $P (B \cap {Y_{t} \in C}) = P (B) P_{i} (C)$ for every Borel $C$ .

4.1givenF1F2F3F4F5F6step 1.1step 2.1algebra∎

For each $α$ , the indicator $1_{B_{α}}$ is a measurable function of the exposed-coordinate vector. By [F2] and [F4], it is independent of $X_{c_{i} (α) + 1, i}$ . Both are integrable by [F3], so [F5] and [F6] give $E [Y_{t} 1_{B_{α}}] = μ_{i} P (B_{α})$ . Summing over the finite action strings yields $E [Y_{t} 1_{B}] = μ_{i} P (B)$ .

LemmaStatement: Literature-sourcedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

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.

TheoremStatement: Literature-sourcedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

Expected regret of explore-then-commit

Statement

Let $k, n, m$ be positive integers with $m k \leq n$ . In an $n$ -round $k$ -armed stochastic bandit, suppose all reward-stack entries are 1-sub-Gaussian. Run explore-then-commit with exploration count $m$ . Its expected reward regret satisfies

R_{n} \leq m \sum_{i = 1}^{k} Δ_{i} + (n - m k) \sum_{i = 1}^{k} Δ_{i} \exp ⁣ (- \frac{m Δ_{i}^{2}}{4}) .

This is an expected-regret bound, not a high-probability guarantee.

Statement references

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

Centered 1-sub-Gaussian reward: each reward entry is centered at its finite mean and has MGF bounded by $e^{λ^{2} / 2}$ for every real $λ$ .

Explore-then-commit for a finite stochastic bandit: deterministic round-robin exploration followed by commitment to an empirical-mean maximizer.

Tail bounds for deterministic prefixes of independent sub-Gaussian rewards: two-sided tails for deterministic prefixes of independent sub-Gaussian rewards.

Finite-arm regret decomposes into expected action counts: expected reward regret equals the sum of arm gaps times expected pull counts under the conditional-mean hypothesis.

Tor Lattimore and Csaba Szepesvári, Bandit Algorithms: Theorem 6.1 and proof, Chapter 6 §6.1, PDF pp. 101–102 / printed pp. 92–93.

Facts & Assumptions

Given: Integers $k, n, m \geq 1$ with $m k \leq n$ , the stochastic reward-stack model, 1-sub-Gaussian reward entries, and explore-then-commit with least-index tie-breaking.

[F1]

For each arm, $μ_{i}$ is finite, $Δ_{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]

Every table entry satisfies the exact centered 1-sub-Gaussian MGF bound (Centered 1-sub-Gaussian reward).

[F2]

The observed reward at each pull has the arm's fixed conditional law and conditional mean, even under adaptive choices on the independent reward stacks (The independent reward-stack model has the prescribed conditional arm laws; Adversary and feedback models).

[F3]

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

[F4]

During exploration, the algorithm pulls each arm exactly $m$ times and then commits to a least-index empirical-mean maximizer (Explore-then-commit for a finite stochastic bandit).

[F5]

For any fixed arm pair and deterministic prefix length, the centered sum of independent reward-table entries has the two-sided sub-Gaussian tail bound (Tail bounds for deterministic prefixes of independent sub-Gaussian rewards).

[F6]

Measurable functions applied coordinatewise to independent random elements remain independent (Measurable coordinatewise functions preserve independence).

Proof

1.1givenF1F2F3F4algebra

By [F2], the conditional-mean hypothesis of [F3] holds, so $R_{n} = \sum_{i = 1}^{k} Δ_{i} E [T_{i} (n)]$ . Let $J$ be the committed arm. The first $m k$ rounds pull each arm exactly $m$ times, and every later round pulls $J$ ; hence $T_{i} (n) = m + (n - m k) 1_{{J = i}}$ . Taking expectations gives $R_{n} = m \sum_{i = 1}^{k} Δ_{i} + (n - m k) \sum_{i = 1}^{k} Δ_{i} P (J = i)$ .

2.1givenA1F1F4F5F6step 1.1algebra

Fix an optimal arm $i^{*}$ with $μ_{i^{*}} = μ^{*}$ . If a suboptimal arm $i$ is committed, its exploration mean is at least that of $i^{*}$ , so ${J = i} \subseteq {m^{- 1} \sum_{s = 1}^{m} (X_{s, i} - μ_{i}) - m^{- 1} \sum_{s = 1}^{m} (X_{s, i^{*}} - μ^{*}) \geq Δ_{i}}$ . The displayed sum has $2 m$ mutually independent terms: these are measurable transforms of distinct independent table entries by [F6]. The positive centered terms are 1-sub-Gaussian by [A1], and the negated centered terms satisfy the same MGF bound by applying [A1] at $- λ$ . Apply [F5] to these deterministic reward-stack prefixes with threshold $m Δ_{i}$ to obtain $P (J = i) \leq \exp (- m Δ_{i}^{2} / 4)$ . For an optimal arm the theorem's summand has $Δ_{i} = 0$ , so no event bound is needed.

3.1givenstep 1.1step 2.1algebra∎

Substituting these bounds on $P (J = i)$ for each suboptimal arm into step 1.1, and using $Δ_{i} \geq 0$ for every arm, gives $R_{n} \leq m \sum_{i = 1}^{k} Δ_{i} + (n - m k) \sum_{i = 1}^{k} Δ_{i} \exp (- m Δ_{i}^{2} / 4)$ . The term with $n - m k = 0$ is zero when exploration uses the whole horizon.

LemmaStatement: AI-adaptedProof: AI-generatedjudge pass (gpt-6-luna)Open item page →

A sharper expected suboptimal-arm pull count for the unchanged UCB rule

Statement

Let $n \geq \max {k, 2}$ be integers. In the finite reward-stack bandit model, assume all entries are centered 1-sub-Gaussian and run the stated UCB algorithm with $δ = n^{- 2}$ . Every arm $i$ with gap $Δ_{i} > 0$ satisfies $E [T_{i} (n)] \leq 3 + \frac{8 \log n}{Δ_{i}^{2}} .$ This is a local sharpening of the coefficient-16 expected-pull bound; the algorithm and confidence radius are unchanged.

Statement references

Lattimore and Szepesvári, Bandit Algorithms, Theorem 7.1: proves the coefficient-16 count estimate; the smaller coefficient is proved here.

Facts & Assumptions

Given: The finite independent reward table, UCB rule, horizon and suboptimal arm in the Statement.

[F1]

An arm has fixed mean $μ_{i}$ , gap $Δ_{i} = μ^{*} - μ_{i}$ , and its $s$ observations are the first $s$ entries of its independent stack. Finite stochastic bandit model, gaps, and regret

[F2]

All reward entries satisfy the centered 1-sub-Gaussian MGF condition. Centered 1-sub-Gaussian reward

[F3]

UCB first plays every arm once, then selects an index maximizer with index ${\hat{μ}}_{i, s} + \sqrt{2 \log (1 / δ) / s}$ at count $s \geq 1$ . Finite-horizon upper-confidence-bound bandit algorithm

[F4]

For each fixed prefix of length $s$ , both centered mean tails at threshold $x \geq 0$ are at most $e^{- s x^{2} / 2}$ . Tail bounds for deterministic prefixes of independent sub-Gaussian rewards

[F5]

Finite unions have probability at most the sum of their probabilities, and event probabilities are at most one. Basic identities for a probability measure

[F6]

Expectation is linear and monotone on integrable finite sums, and the expectation of an indicator is its probability. Linearity, monotonicity, and the modulus bound for expectation The expectation of an indicator is the probability of the event

[F7]

If $n \geq 5$ , $L = \log n$ and $a > 0$ , the sum of $\exp (- ((a \sqrt{s} - 2 \sqrt{L})_{+})^{2} / 2)$ for $1 \leq s < n$ is at most $1 + 8 L / a^{2}$ . A deterministic-prefix envelope sum for the sharper UCB count bound

[F8]

The natural logarithm is increasing and satisfies its product and reciprocal laws. 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.1givenF1F2F3F4F5F8constructalgebra

Put $L = \log n > 0$ and let $i^{*}$ be the least-index optimal arm. For a fixed prefix $s \in [n]$ , put $r_{s} = \sqrt{4 L / s}$ . By [F8], this is the index bonus at $δ = n^{- 2}$ . Let $G = ⋂_{s = 1}^{n} {{\hat{μ}}_{i^{*}, s} + r_{s} \geq μ^{*}} .$ Every event in its complement is a fixed-prefix lower-tail event of probability at most $e^{- s r_{s}^{2} / 2} = n^{- 2}$ by [F2] and [F4]. Hence $P (G^{c}) \leq 1 / n$ by [F5].

2.1F1F3step 1.1given

Fix the suboptimal arm $i$ . It is played once during initialization. On $G$ , any later play when its current count is $s$ requires ${\hat{μ}}_{i, s} + r_{s} \geq μ^{*}$ : its selected index is at least the current index of $i^{*}$ , which is at least $μ^{*}$ . Each such count $s \in {1, \dots, n - 1}$ can be charged at most once, since a play increases the count by one. Always $T_{i} (n) \leq n$ . Thus pointwise $T_{i} (n) \leq 1 + \sum_{s = 1}^{n - 1} 1_{{{\hat{μ}}_{i, s} + r_{s} \geq μ^{*}}} + n 1_{G^{c}} .$

3.1givenF1F2F4F5step 1.1algebra

For a fixed $s$ , the event inside the sum in step 2.1 is ${\hat{μ}}_{i, s} - μ_{i} \geq Δ_{i} - r_{s}$ . If this threshold is positive, [F4] bounds its probability by $\exp (- s (Δ_{i} - r_{s})^{2} / 2)$ . If it is nonpositive, use the bound $1$ in [F5]. Consequently, in both cases its probability is at most $\exp (- \frac{(Δ_{i} \sqrt{s} - 2 \sqrt{L})_{+}^{2}}{2}) .$ These are tails at deterministic prefix counts, never a tail theorem evaluated at a random count.

4.1F6F7step 1.1step 2.1step 3.1algebra

Take expectations in step 2.1, using [F6]. The count and indicators are bounded and therefore integrable. Step 1.1 makes the last term at most $1$ , while step 3.1 bounds the finite sum. If $n \geq 5$ , [F7] with $a = Δ_{i} > 0$ therefore gives $E [T_{i} (n)] \leq 2 + \sum_{s = 1}^{n - 1} \exp (- \frac{(Δ_{i} \sqrt{s} - 2 \sqrt{L})_{+}^{2}}{2}) \leq 3 + \frac{8 L}{Δ_{i}^{2}} .$

5.1F1F3F6step 4.1givencasesalgebra∎

If $2 \leq n \leq 4$ , the existence of a suboptimal arm implies $k \geq 2$ . Initialization plays every other arm at least once, so $T_{i} (n) \leq n - k + 1 \leq 3$ pointwise. This proves the desired bound in the remaining horizons. If $k = 1$ there is no suboptimal arm, so the assertion is vacuous. Together with step 4.1 this proves the Statement.

TheoremStatement: Literature-sourcedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

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.

TheoremStatement: AI-adaptedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

Gap-free expected regret of UCB

Statement

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.

4 · Examples, counterexamples and false statements

None yet.

Stochastic finite-armed bandits

2 · Logical flowchart

3 · Definitions, theorems and proofs

Centered 1-sub-Gaussian reward

Definition

Definition references

The zeta sums at 2 and 3 are finite

Statement

Statement references

Facts & Assumptions

Proof

Expectation of a countably valued nonnegative random variable is its weighted series

Statement

Statement references

Facts & Assumptions

Proof

A deterministic-prefix envelope sum for the sharper UCB count bound

Statement

Statement references

Facts & Assumptions

Proof

Tail bounds for deterministic prefixes of independent sub-Gaussian rewards

Statement

Statement references

Facts & Assumptions

Proof

Finite stochastic bandit model, gaps, and regret

Definition

Definition references

Explore-then-commit for a finite stochastic bandit

Definition

Definition references

Finite-horizon upper-confidence-bound bandit algorithm

Definition

Definition references

The independent reward-stack model has the prescribed conditional arm laws

Statement

Statement references

Facts & Assumptions

Proof

Expected pull count for a suboptimal UCB arm

Statement

Statement references

Facts & Assumptions

Proof

Expected regret of explore-then-commit

Statement

Statement references

Facts & Assumptions

Proof

A sharper expected suboptimal-arm pull count for the unchanged UCB rule

Statement

Statement references

Facts & Assumptions

Proof

Gap-dependent expected regret of UCB

Statement

Statement references

Facts & Assumptions

Proof

Gap-free expected regret of UCB

Statement

Statement references

Facts & Assumptions

Proof

4 · Examples, counterexamples and false statements

Sources