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.

Contextual expert bandits — 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 finite two-expert Exp4 instance

Example

Consider one round with two actions, two experts, reward vector $x_{1} = (1, 0)$ , and deterministic advice rows $E (1)_{1} = (1, 0)$ and $E (1)_{2} = (0, 1)$ . For any learning rate $η > 0$ , Exp4 starts with equal expert weights and samples each action with probability $1 / 2$ . The expected learner reward is $1 / 2$ , the best fixed expert reward is $1$ , and the expected regret is $1 / 2$ , independently of $η$ . For the theorem-bound clause, use the tuned learning rate $η = \sqrt{\log 2}$ ; the general Exp4 theorem then gives $R_{1} \leq \sqrt{4 \log 2}$ .

Example references

Contextual bandit protocol: the finite expert advice and expected-regret conventions used in the calculation.

Exp4 initialization and action mixture: the uniform initial expert weights and mixture action distribution used here.

Expected-regret theorem: the stated general bound specialized to this one-round instance.

Facts & Assumptions

Given: One round, actions $[2]$ , experts $[2]$ , reward vector $(1, 0)$ , advice rows $(1, 0)$ and $(0, 1)$ , and Exp4 with $η = \sqrt{\log 2}$ for the theorem-bound clause.

[F1]

Contextual bandit protocol with finite expert advice: an expert's round reward is the dot product of its advice row with the reward vector.

[F2]

Exp4 with unbiased estimated rewards: $Q_{1, m} = 1 / M$ and $P_{1, i} = \sum_{m} Q_{1, m} E (1)_{m, i}$ .

[F3]

Exp4 expected regret against the best fixed expert: for $n = 1$ , $k = 2$ , and $M = 2$ , the expected regret is at most $\sqrt{4 \log 2}$ .

Verification

1.1F2algebra

The uniform initial weights give $Q_{1, 1} = Q_{1, 2} = 1 / 2$ . Hence $P_{1, 1} = 1 / 2$ and $P_{1, 2} = 1 / 2$ . The realized reward equals one with probability $1 / 2$ and zero with probability $1 / 2$ , so its expectation is $1 / 2$ .

2.1F1step 1.1algebra

The two experts' expected rewards are $⟨ (1, 0), (1, 0) ⟩ = 1$ and $⟨ (0, 1), (1, 0) ⟩ = 0$ . Thus the best fixed expert reward is one and the expected regret is $1 - 1 / 2 = 1 / 2$ .

3.1F3algebra∎

Substituting $n = 1$ , $k = 2$ , and $M = 2$ into [F3] gives the stated bound $\sqrt{4 \log 2}$ .

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

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

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

A context-specific expert class with no shared policy structure

Example

Let $n \geq 1$ be an integer, let $C$ be a nonempty finite context set of size $c$ , and let $k > 1$ be an integer number of actions. Fix a context sequence $c_{1}, \dots, c_{n} \in C$ and reward vectors $x_{t} \in [0, 1]^{k}$ for $t \in [n]$ , all before learner randomization. Take as experts every function $ϕ : C \to [k]$ , with advice row $E (t)_{ϕ, i} = 1 {ϕ (c_{t}) = i}$ . There are $M = k^{c}$ such experts and no constraint links the action assigned to one context to the action assigned to another. With learning rate $η = \sqrt{2 \log (k^{c}) / (n k)}$ , Exp4's expected regret against this class is at most $\sqrt{2 n k c \log k}$ .

Example references

Contextual bandit protocol: expert advice rows and fixed oblivious context/reward sequences use this protocol.

Exp4 algorithm: each deterministic policy map supplies one advice row at the observed context.

Expected-regret theorem: the general finite-expert bound applies to the $k^{c}$ policy maps.

Natural-logarithm product law: $\log (k^{c}) = c \log k$ .

Facts & Assumptions

Given: $n \geq 1$ , a finite nonempty context set $C$ with $∣ C ∣ = c$ , a fixed oblivious context sequence, fixed oblivious reward vectors $x_{t} \in [0, 1]^{k}$ for $t \in [n]$ , $k > 1$ , and the expert class of all maps $ϕ : C \to [k]$ .

[F1]

Contextual bandit protocol with finite expert advice: the theorem applies to deterministic advice matrices fixed before learner randomization, with each expert row a probability vector.

[F2]

Exp4 expected regret against the best fixed expert: with $M > 1$ experts, horizon $n \geq 1$ , $k > 1$ , and its tuned learning rate, $R_{n} \leq \sqrt{2 n k \log M}$ .

[F3]

Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm: for positive $a, b$ , $\log (a b) = \log a + \log b$ .

Verification

1.1F1givenconstructalgebra

For each map $ϕ$ and each round $t$ , exactly one indicator $1 {ϕ (c_{t}) = i}$ equals one, so its advice row is a probability vector. A map chooses one of $k$ actions independently at each of the $c$ contexts; therefore there are exactly $M = k^{c}$ experts. The fixed context sequence makes the resulting advice sequence oblivious.

2.1F2F3step 1.1algebra∎

Since $c \geq 1$ and $k > 1$ , $M = k^{c} > 1$ , so [F2] applies and gives $R_{n} \leq \sqrt{2 n k \log (k^{c})}$ . Repeated use of [F3] gives $\log (k^{c}) = c \log k$ , hence $R_{n} \leq \sqrt{2 n k c \log k}$ . This is a finite-sequence regret bound; it asserts no stochastic contextual generalization.

Sources

Tor Lattimore and Csaba Szepesvári, Bandit Algorithms