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.

Duplicated experts change Exp4's uniform prior mass

Example

Take $k = 2$ , $M = 3$ , and at every round let $E (t)_{1} = E (t)_{2} = (1, 0)$ and $E (t)_{3} = (0, 1)$ . Exp4's uniform initial expert distribution gives first-round action distribution $P_{1} = (2 / 3, 1 / 3)$ ; deleting one of the duplicated experts instead gives $(1 / 2, 1 / 2)$ . The two duplicated experts receive identical estimated rewards and remain equal-weighted after every update. For any integer horizon $n \geq 1$ and any fixed oblivious reward sequence $x_{1}, \dots, x_{n} \in [0, 1]^{2}$ , with learning rate $η = \sqrt{\log 3 / n}$ , the expected-regret theorem gives the bound $R_{n} \leq \sqrt{4 n \log 3}$ for the three-expert list.

Example references

Expert advice rows and oblivious instance: the deterministic advice rows and reward sequence meet this protocol.

Exp4 initialization, mixture, and update: the example uses uniform initial expert weights and the common exponential update.

Expected-regret theorem: the three-expert regret bound follows by specializing the theorem to $k = 2$ and $M = 3$ .

Facts & Assumptions

Given: $k = 2$ , $M = 3$ , identical first and second advice rows $(1, 0)$ , third row $(0, 1)$ , a fixed oblivious reward sequence $x_{1}, \dots, x_{n} \in [0, 1]^{2}$ , and Exp4 with learning rate $η = \sqrt{\log 3 / n}$ for a fixed horizon $n \geq 1$ .

[F1]

Contextual bandit protocol with finite expert advice: each row is a probability vector and each fixed expert's advice is admissible in an oblivious instance.

[F2]

Exp4 with unbiased estimated rewards: $Q_{1, m} = 1 / M$ , $P_{t, i} = \sum_{m} Q_{t, m} E (t)_{m, i}$ , and $Q_{t + 1, m}$ is proportional to $Q_{t, m} \exp (η {\tilde{X}}_{t, m})$ .

[F3]

Exp4 expected regret against the best fixed expert: for any fixed oblivious instance with $k > 1$ , $M > 1$ , and horizon $n \geq 1$ , $R_{n} \leq \sqrt{2 n k \log M}$ at the stated learning rate.

Verification

1.1F2algebra

Since $Q_{1, m} = 1 / 3$ , the mixture formula gives $P_{1, 1} = 1 / 3 + 1 / 3 = 2 / 3$ and $P_{1, 2} = 1 / 3$ . If one copy of $(1, 0)$ is removed, the two remaining experts start with mass $1 / 2$ each, giving the alternative distribution $(1 / 2, 1 / 2)$ .

2.1F1F2step 1.1algebra

At every round the first two advice rows are equal, so their estimated rewards are equal. Their initial weights are equal; multiplying both by the same exponential factor and dividing by the common normalizer preserves equality. In particular, writing $g = {\tilde{X}}_{1, 1} = {\tilde{X}}_{1, 2}$ and $h = {\tilde{X}}_{1, 3}$ gives $Q_{2, 1} = Q_{2, 2} = e^{η g} / (2 e^{η g} + e^{η h})$ , so their combined mass is $2 e^{η g} / (2 e^{η g} + e^{η h})$ .

3.1F3algebra∎

Substituting $k = 2$ and $M = 3$ into [F3] gives $R_{n} \leq \sqrt{2 n \cdot 2 \log 3} = \sqrt{4 n \log 3}$ .

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

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