ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-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.

A rarely sampled arm has a high-variance importance-weighted estimate

Example

Take one round with two actions, rewards $(x_{1, 1}, x_{1, 2}) = (0, 1)$ , and sampling probabilities $(P_{1, 1}, P_{1, 2}) = (1 / 10, 9 / 10)$ . The first arm's loss is $1$ , so its importance-weighted loss estimate is $10$ with probability $1 / 10$ and $0$ with probability $9 / 10$ . Its mean is $1$ , second moment is $10$ , and variance is $9$ . The corresponding reward estimate is $- 9$ or $1$ with those respective probabilities, despite the true first-arm reward being $0$ .

Example references

Bandit importance-weighted estimator: the loss estimate is the observed loss divided by the probability of selecting its arm.

Conditional moments of the bandit importance-weighted estimator: the conditional mean, second moment, and variance formulas.

Facts & Assumptions

Given: One round, two arms, fixed rewards $(0, 1)$ , and conditional arm probabilities $(1 / 10, 9 / 10)$ .

[F1]

Bandit importance-weighted estimator: $Y_{1} = 1 - X_{1}$ and ${\hat{Y}}_{1, i} = 1 {A_{1} = i} Y_{1} / P_{1, i}$ , with ${\hat{X}}_{1, i} = 1 - {\hat{Y}}_{1, i}$ .

[F2]

Conditional moments of the bandit importance-weighted estimator: for loss $y_{i}$ and arm probability $p_{i} > 0$ , the conditional mean, second moment, and variance are $y_{i}$ , $y_{i}^{2} / p_{i}$ , and $y_{i}^{2} (1 - p_{i}) / p_{i}$ .

Verification

1.1givenF1

The first-arm loss is $y_{1, 1} = 1$ . On $A_{1} = 1$ , which has probability $1 / 10$ , its estimate is $1 / (1 / 10) = 10$ ; on $A_{1} = 2$ , which has probability $9 / 10$ , its estimate is zero.

1.2F2algebra

By [F2] with $y = 1$ and $p = 1 / 10$ , the mean is $1$ , the second moment is $1 / (1 / 10) = 10$ , and the variance is $1^{2} (1 - 1 / 10) / (1 / 10) = 9$ .

2.1F1step 1.1algebra∎

Since ${\hat{X}}_{1, 1} = 1 - {\hat{Y}}_{1, 1}$ , its values are $- 9$ and $1$ on the two events, respectively, so it can fall outside the true reward range $[0, 1]$ .

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

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