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

Exp4 updates are well-defined, including zero-probability actions

Statement

For the exact-real Exp4 procedure, take any integers $n \geq 1$ , $k > 1$ , $M > 1$ , any finite real learning rate $η > 0$ , and every oblivious reward/advice instance and supplied measurable draws in its input scope. At every round $t \in [n]$ , the expert vector $Q_{t}$ is a probability vector with strictly positive entries, the action mixture $P_{t}$ belongs to $Δ_{k}$ , and $P_{t, i} = 0$ implies $E (t)_{m, i} = 0$ for every expert $m$ . Every action and expert reward estimate is finite; the corresponding estimated losses $1 - {\hat{X}}_{t, i}$ and $1 - {\tilde{X}}_{t, m}$ are nonnegative. The normalizing denominator is finite and strictly positive, so $Q_{t + 1}$ again has strictly positive entries summing to one. The procedure completes its $n$ prescribed rounds and returns all specified outputs.

The zero-quotient convention is retained exactly. These conclusions do not require positive sampling probability for every action, a uniform exploration mixture, a bound on the magnitude of an importance-weighted estimate, or a restriction on the learning rate beyond $η > 0$ .

Statement references

Exp4 with unbiased estimated rewards

Contextual bandit protocol with finite expert advice

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

Lattimore and Szepesvári, Bandit Algorithms, §18.3 Algorithm 11

Facts & Assumptions

Given: The full finite-horizon Exp4 inputs in the Statement, using exact real arithmetic and the probability space carrying the algorithm's prescribed finite-valued measurable action draws.

[F1]

The input has $n \geq 1$ , $k > 1$ , $M > 1$ , fixed rewards $x_{t} \in [0, 1]^{k}$ , and advice rows with $E (t)_{m, i} \geq 0$ and $\sum_{i} E (t)_{m, i} = 1$ . The observed reward is $X_{t} = x_{t, A_{t}} \in [0, 1]$ ; action draws are measurable, and the pre-action history consists of earlier actions and observed rewards. Contextual bandit protocol with finite expert advice

[F2]

The algorithm initializes $Q_{1, m} = 1 / M$ , sets $P_{t, i} = \sum_{m} Q_{t, m} E (t)_{m, i}$ , and uses ${\hat{X}}_{t, i} = 1 - {\hat{L}}_{t, i}$ with ${\hat{L}}_{t, i} = 1 {A_{t} = i} (1 - X_{t}) / P_{t, i}$ when $P_{t, i} > 0$ , and ${\hat{L}}_{t, i} = 0$ when $P_{t, i} = 0$ . It sets ${\tilde{X}}_{t, m} = \sum_{i} E (t)_{m, i} {\hat{X}}_{t, i}$ and normalizes $Q_{t, m} \exp (η {\tilde{X}}_{t, m})$ to obtain $Q_{t + 1, m}$ . Exp4 with unbiased estimated rewards

[F3]

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

[F4]

Inverses and products of positive real numbers are positive, and positive multiplication preserves inequalities. Inverses of positives are positive, and reciprocation reverses order, Sign rules for products and monotonicity of multiplication

[F5]

Induction propagates a base assertion preserved at each successor through the finite sequence of rounds. The principle of mathematical induction

Proof

1.1givenF2F4basealgebra

At the first round, $M > 1$ makes $1 / M$ a finite strictly positive real by [F4]. The $M$ entries sum to one, so $Q_{1}$ is a strictly positive probability vector.

1.2F1F2F4IHalgebra

Assume $Q_{t}$ is a strictly positive probability vector at a round $t \leq n$ . Every $P_{t, i}$ is a finite nonnegative sum. Reordering its finite double sum gives $\sum_{i} P_{t, i} = \sum_{m} Q_{t, m} \sum_{i} E (t)_{m, i} = \sum_{m} Q_{t, m} = 1$ . Hence each $P_{t, i} \in [0, 1]$ and $P_{t} \in Δ_{k}$ . If $P_{t, i} = 0$ , every term $Q_{t, m} E (t)_{m, i}$ in this nonnegative sum is zero, and strict positivity of $Q_{t, m}$ forces $E (t)_{m, i} = 0$ for every $m$ . Thus unsupported actions carry no expert advice.

2.1F1F2F4step 1.2algebra

Fix the round's action. Since $0 \leq X_{t} \leq 1$ , a supported coordinate has finite nonnegative ${\hat{L}}_{t, i}$ by [F4], while an unsupported coordinate has the defined value zero. Thus every ${\hat{X}}_{t, i} = 1 - {\hat{L}}_{t, i}$ is finite, with no division by zero. The finite sum defining ${\tilde{X}}_{t, m}$ is also finite. As each advice row sums to one, ${\tilde{L}}_{t, m} : = 1 - {\tilde{X}}_{t, m} = \sum_{i} E (t)_{m, i} {\hat{L}}_{t, i} \geq 0$ . The reasoning uses the zero convention even on null outcomes, so no pointwise undefined quotient is hidden behind a probability-zero claim.

3.1F2F3F4step 2.1IHalgebra

By step 2.1, $η {\tilde{X}}_{t, m}$ is a finite real number for every expert. By [F3], every weight $w_{m} = Q_{t, m} \exp (η {\tilde{X}}_{t, m})$ is finite and strictly positive. Since $M$ is finite and nonzero, $Z_{t} = \sum_{m} w_{m}$ is finite and strictly positive. Therefore every $Q_{t + 1, m} = w_{m} / Z_{t}$ is finite and strictly positive by [F4], and their sum is one. This is the induction step.

4.1givenF1F2F3F5step 1.1step 1.2step 2.1step 3.1discharge-induction∎

By [F5], all stated invariants and finite estimates hold through round $n$ , including $Q_{n + 1}$ . For fixed inputs, $Q_{t}$ and $P_{t}$ are functions of the finite past action sequence, and all other round records are functions of that sequence and the current action. The finite measurable action-history partitions therefore make the states and records measurable with finite ranges; in particular $P_{t}$ is pre-action measurable. There is at least one supported arm at each round because $\sum_{i} P_{t, i} = 1$ , and the algorithm's probability space supplies its measurable draw; no sampler construction is being assumed beyond the input contract. Each round performs only finite sums and the prescribed finite evaluations and draw. After exactly $n$ rounds the loop ends and returns $(Q_{t}, P_{t}, A_{t}, X_{t}, {\hat{X}}_{t}, {\tilde{X}}_{t})_{t = 1}^{n}$ and $Q_{n + 1}$ . This proves well-definedness and finite-horizon completion without any extra exploration or learning-rate hypothesis.

Depends on

Used by

Nothing in the library uses this result yet.

Cited to discharge well-definedness by Exp4 with unbiased estimated rewards.

Dependency tree · two levels

30 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

Lattimore and Szepesvári, Bandit Algorithms, §18.3 Algorithm 11 (Exp4 procedure background) (standard reference, not scraped)