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.

Adversarial bandits and importance-weighted feedback — Examples

1 · Prerequisites

2 · Logical flowchart

3 · Definitions, theorems and proofs

None yet.

4 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-generatedOpen item page →

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

ExampleConstruction: AI-generatedVerification: AI-generatedOpen item page →

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

ExampleConstruction: AI-generatedVerification: AI-generatedOpen item page →

Exp3 and full-information Hedge update differently

Example

Take one round with two arms, reward vector $(1, 0)$ , learning rate $η > 0$ , and uniform initial probabilities. Run full-information Hedge with $ϵ = η$ on losses $(0, 1)$ ; its next distribution is $(\exp (η) / (\exp (η) + 1), 1 / (\exp (η) + 1))$ . After the first round, Exp3 has next distribution $(1 / 2, 1 / 2)$ if it sampled arm 1 and $(\exp (η) / (\exp (η) + \exp (- η)), \exp (- η) / (\exp (η) + \exp (- η)))$ if it sampled arm 2. Both outcomes differ from the full-information distribution.

Example references

Exp3 with importance-weighted loss feedback: the estimated rewards and exponential probability update.

Hedge: full-information losses, equal initial weights, and the exponential loss update.

Bandit importance-weighted estimator: the observed reward and loss-based estimator formulas.

Facts & Assumptions

Given: One round, two arms, reward vector $(1, 0)$ , Exp3 learning rate $η > 0$ , full-information Hedge learning rate $ϵ = η$ , uniform initial weights, and the two update rules.

[F1]

Exp3 with importance-weighted loss feedback: Exp3 samples proportionally to $\exp (η {\hat{S}}_{t - 1, i})$ and updates ${\hat{S}}_{t, i} = {\hat{S}}_{t - 1, i} + {\hat{X}}_{t, i}$ .

[F2]

Hedge: Hedge initializes both weights at one, samples from their normalized values, then updates $W_{t + 1, i} = W_{t, i} \exp (- η ℓ_{t, i})$ after observing the entire loss vector.

[F3]

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

[F4]

The real exponential function and the number $e$ by a power series: $\exp (0) = 1$ .

[F5]

The exponential is positive and satisfies $\exp (- x) = 1 / \exp (x)$ : $\exp (z) > 0$ and $\exp (- z) = 1 / \exp (z)$ for real $z$ .

[F6]

The exponential function is strictly increasing: $\exp$ is strictly increasing on $R$ .

Verification

1.1givenF1F3

Since ${\hat{S}}_{0, 1} = {\hat{S}}_{0, 2} = 0$ , Exp3 starts with probabilities $(1 / 2, 1 / 2)$ . If $A_{1} = 1$ , then $Y_{1} = 0$ and ${\hat{X}}_{1, 1} = {\hat{X}}_{1, 2} = 1$ , so the next Exp3 distribution is uniform. If $A_{1} = 2$ , then $Y_{1} = 1$ , $P_{1, 2} = 1 / 2$ , and $({\hat{Y}}_{1, 1}, {\hat{Y}}_{1, 2}) = (0, 2)$ ; hence ${\hat{X}}_{1} = (1, - 1)$ and the next distribution is $(\exp (η) / (\exp (η) + \exp (- η)), \exp (- η) / (\exp (η) + \exp (- η)))$ .

1.2givenF2F5algebra

Full-information Hedge uses $ϵ = η$ and sees losses $(0, 1)$ , so its next weights are $(1, \exp (- η))$ and its normalized distribution is $(\exp (η) / (\exp (η) + 1), 1 / (\exp (η) + 1))$ .

2.1F4F6step 1.1step 1.2algebra∎

By [F4] and [F6], $\exp (η) > 1$ , so Hedge's first probability exceeds $1 / 2$ and differs from Exp3's first probability after $A_{1} = 1$ . Also $\exp (2 η) > \exp (η)$ , so the odds ratio after $A_{1} = 2$ is $\exp (2 η)$ for Exp3 and $\exp (η)$ for Hedge; these distributions differ as well.

Sources

Tor Lattimore and Csaba Szepesvári, Bandit Algorithms