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.

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.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

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