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.

Deterministic rewards can give a negative estimated reward

Example

Take one round with deterministic rewards $(x_{1, 1}, x_{1, 2}) = (1, 0)$ and sampling probabilities $(P_{1, 1}, P_{1, 2}) = (3 / 4, 1 / 4)$ . Arm 2 has loss $1$ , so its estimated loss is $4$ with probability $1 / 4$ and $0$ with probability $3 / 4$ . Its mean is $1$ , second moment is $4$ , and variance is $3$ . The corresponding estimated reward is $- 3$ or $1$ with those respective probabilities, although arm 2's true reward is $0$ .

Example references

Bandit importance-weighted estimator: the loss and reward estimate definitions for a single sampled arm.

Conditional moments of the bandit importance-weighted estimator: the conditional moments for a positive arm probability.

Facts & Assumptions

Given: One round, two arms, deterministic rewards $(1, 0)$ , and conditional arm probabilities $(3 / 4, 1 / 4)$ .

[F1]

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

[F2]

Conditional moments of the bandit importance-weighted estimator: for loss $y_{i}$ and 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

Arm 2 has loss $y_{1, 2} = 1$ . If $A_{1} = 2$ , an event of probability $1 / 4$ , then ${\hat{Y}}_{1, 2} = 1 / (1 / 4) = 4$ ; if $A_{1} = 1$ , an event of probability $3 / 4$ , then ${\hat{Y}}_{1, 2} = 0$ .

1.2F2algebra

By [F2] with $y = 1$ and $p = 1 / 4$ , the conditional mean is $1$ , the second moment is $1 / (1 / 4) = 4$ , and the variance is $(1 - 1 / 4) / (1 / 4) = 3$ .

2.1F1step 1.1algebra∎

Since ${\hat{X}}_{1, 2} = 1 - {\hat{Y}}_{1, 2}$ , it equals $- 3$ when arm 2 is drawn and $1$ when arm 1 is drawn. Thus a deterministic reward in $[0, 1]$ can produce an estimated reward outside $[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)