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

Conditional moments of the bandit importance-weighted estimator

Statement

In the bandit importance-weighted estimator definition, fix a round $t$ and arm $i$ , and write $p = P_{t, i} > 0$ and $y = y_{t, i}$ . Then

E [{\hat{Y}}_{t, i} ∣ F_{t - 1}] = y_{t, i}, E [{\hat{Y}}_{t, i}^{2} ∣ F_{t - 1}] = \frac{y_{t, i}^{2}}{P_{t, i}} .

With conditional variance defined by $Var (Z ∣ F_{t - 1}) = E [(Z - E [Z ∣ F_{t - 1}])^{2} ∣ F_{t - 1}]$ , one also has

Var ({\hat{Y}}_{t, i} ∣ F_{t - 1}) = \frac{y_{t, i}^{2} (1 - P_{t, i})}{P_{t, i}} .

Statement references

Bandit importance-weighted estimator: the arm probabilities, observed loss, and importance-weighted loss estimate used here.

Facts & Assumptions

Given: A finite arm set $[k]$ , a pre-action history at round $t$ , a reward vector $x_{t} \in [0, 1]^{k}$ , and a distribution $P_{t} \in Δ_{k}$ with $P_{t, i} > 0$ .

[F1]

Bandit importance-weighted estimator: given the pre-action history, $P (A_{t} = i ∣ F_{t - 1}) = P_{t, i}$ , $Y_{t} = y_{t, A_{t}}$ , and ${\hat{Y}}_{t, i} = 1 {A_{t} = i} Y_{t} / P_{t, i}$ .

[F2]

Conditional expectation given a sigma algebra: a conditional-expectation version is measurable and integrable and has the same integral as the original variable on every event in the conditioning sigma-algebra.

[F3]

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

[F4]

Filtration and filtered probability space: a filtration consists of nested sub-sigma-algebras of the ambient sigma-algebra. In Bandit importance-weighted estimator, $F_{t - 1}$ is specifically generated by the complete histories before the round- $t$ action.

Proof

1.1F1F2F3F4

Fix a positive-probability atom $H$ of the finite pre-action history. On $H$ , $y_{t, i}$ and $P_{t, i}$ are fixed. By [F1], $P (H \cap {A_{t} = i}) = P_{t, i} P (H)$ ; the estimator is $y_{t, i} / P_{t, i}$ on that event and zero on the rest of $H$ . Hence $\int_{H} {\hat{Y}}_{t, i} d P = y_{t, i} P (H)$ . The function with value $y_{t, i}$ on each history atom is measurable and integrable, and finite additivity gives the same integral identity on every event in $F_{t - 1}$ . By [F2], it is a conditional-expectation version, proving $E [{\hat{Y}}_{t, i} ∣ F_{t - 1}] = y_{t, i}$ .

1.2F1F2F3algebra

On the same atom $H$ , ${\hat{Y}}_{t, i}^{2}$ is $y_{t, i}^{2} / P_{t, i}^{2}$ on $H \cap {A_{t} = i}$ and zero otherwise. Thus $\int_{H} {\hat{Y}}_{t, i}^{2} d P = (y_{t, i}^{2} / P_{t, i}^{2}) P_{t, i} P (H) = (y_{t, i}^{2} / P_{t, i}) P (H)$ . Extending over the finite atoms and applying [F2] proves $E [{\hat{Y}}_{t, i}^{2} ∣ F_{t - 1}] = y_{t, i}^{2} / P_{t, i}$ .

2.1F1F2F4step 1.1algebra∎

At a fixed history, the centered estimator has value $y_{t, i} (1 - P_{t, i}) / P_{t, i}$ with probability $P_{t, i}$ and value $- y_{t, i}$ with probability $1 - P_{t, i}$ , by step 1.1. Its conditional variance is therefore $P_{t, i} [y_{t, i} (1 - P_{t, i}) / P_{t, i}]^{2} + (1 - P_{t, i}) y_{t, i}^{2} = y_{t, i}^{2} (1 - P_{t, i}) / P_{t, i}$ .

Depends on

Used by

Dependency tree · two levels

12 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)
Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert Schapire, The Nonstochastic Multiarmed Bandit Problem (standard reference, not scraped)