TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-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.

Exp4 expected regret against the best fixed expert

Statement

Let $n \geq 1$ , $k > 1$ , and $M > 1$ be integers. For each $t \in [n]$ , let $x_{t} \in [0, 1]^{k}$ and let $E (t)$ be an $M \times k$ matrix with nonnegative entries whose every row sums to one. Assume the reward vectors and advice matrices are deterministic and fixed before learner randomization, each advice matrix is revealed before its action, and the learner observes only the reward of its sampled action. Run Exp4 with

η = \sqrt{\frac{2 \log M}{n k}},

where $\log$ is the natural logarithm and the square root is the nonnegative real root. Define expected regret against the best fixed expert by

R_{n} = E [\max_{m \in [M]} \sum_{t = 1}^{n} \sum_{i = 1}^{k} E (t)_{m, i} x_{t, i} - \sum_{t = 1}^{n} X_{t}], [M] = {1, \dots, M} .

Then

R_{n} \leq \sqrt{2 n k \log M} .

Statement references

Oblivious contextual bandit protocol and expected regret: the fixed reward/advice scope, action feedback, and reward-regret convention are defined there.

Exp4 algorithm: the action mixture, importance-weighted estimates, and expert update used in the theorem are defined there.

Conditional unbiasedness of expert reward estimates: supported action estimates recover each fixed expert's expected reward, including the zero-support boundary.

Weighted estimated-loss second moment: the expected quadratic term in the potential bound is at most $k$ per round.

Exp4 potential inequality: every fixed expert's estimated-reward advantage is bounded by the log-prior term and estimated-loss second moments.

Facts & Assumptions

Given: The finite oblivious contextual bandit instance, Exp4 with the stated learning rate, and expected regret against its best fixed expert.

[A1]

The reward vectors $x_{t}$ and advice matrices $E (t)$ are fixed before learner randomization, as stated in the Statement; hence a best expert can be chosen deterministically.

[F1]

Contextual bandit protocol with finite expert advice: advice rows are probability vectors, the instance is oblivious, the learner observes $X_{t} = x_{t, A_{t}}$ , and $R_{n}$ is the expectation of the best-fixed-expert reward minus the learner's cumulative reward.

[F2]

Exp4 with unbiased estimated rewards: $P_{t, i} = \sum_{m} Q_{t, m} E (t)_{m, i}$ , $Q_{t}$ is determined before the current draw, and all estimates are finite under the zero-quotient convention.

[F3]

Exp4 expert reward estimates are conditionally unbiased: $E [{\tilde{X}}_{t, m} ∣ F_{t - 1}] = \sum_{i} E (t)_{m, i} x_{t, i}$ for every expert, including zero-probability actions.

[F4]

Exp4 weighted estimated loss has conditional second moment at most k: $E [\sum_{m} Q_{t, m} {\tilde{L}}_{t, m}^{2} ∣ F_{t - 1}] \leq k$ .

[F5]

Exp4 exponential-weights potential inequality: for every fixed $m^{*}$ , the pathwise estimated-reward gap is at most $\log (M) / η + (η / 2) \sum_{t, m} Q_{t, m} {\tilde{L}}_{t, m}^{2}$ .

[F6]

Static, dynamic, interval, and strongly adaptive regret: expected regret is the expectation of the specified measurable, integrable regret random variable.

[F7]

Conditional expectation given a sigma algebra: a conditional expectation is characterized by its integrals on events in the pre-action sigma-algebra.

[F8]

Expectation of a nonnegative or integrable random variable: expectation of an integrable random variable is its Lebesgue integral.

[F9]

Linearity, monotonicity, and the modulus bound for expectation: finite sums of integrable random variables have the corresponding sum of expectations.

[F10]

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

[F11]

Nonnegative real square roots exist uniquely: each nonnegative real number has a unique nonnegative square root.

Proof

1.1A1F1F2F3F6F7F8F9algebrachoose

Since $[M]$ is finite and the advice and rewards are fixed, choose a maximizing expert $m^{*}$ ; it is nonrandom. At any positive-probability pre-action history, [F2] makes $Q_{t}$ and $P_{t}$ fixed. By [F3], the conditional mean of the comparator estimate is its true expert reward. Finite summation and $P_{t, i} = \sum_{m} Q_{t, m} E (t)_{m, i}$ give $E [\sum_{m} Q_{t, m} {\tilde{X}}_{t, m} ∣ F_{t - 1}] = \sum_{m} Q_{t, m} \sum_{i} E (t)_{m, i} x_{t, i} = \sum_{i} P_{t, i} x_{t, i} = E [X_{t} ∣ F_{t - 1}]$ . All histories and estimates are finite, so summing these conditional identities over histories and rounds gives $R_{n} = E [\sum_{t} {\tilde{X}}_{t, m^{*}} - \sum_{t, m} Q_{t, m} {\tilde{X}}_{t, m}]$ . This uses finite conditional sums, not a general tower-property theorem.

2.1F4F5F7F8F9step 1.1algebra

Apply [F5] pathwise to $m^{*}$ . Taking expectations, using [F9], and summing the conditional bound [F4] over the finite pre-action histories gives $R_{n} \leq \log M / η + (η / 2) \sum_{t = 1}^{n} E [\sum_{m} Q_{t, m} {\tilde{L}}_{t, m}^{2}] \leq \log M / η + η n k / 2$ .

3.1F10F11step 2.1algebra∎

Since $M > 1$ , [F10] gives $\log M > 0$ . Thus $2 \log M / (n k) > 0$ , and [F11] supplies the positive learning rate in the Statement. Substituting it into step 2.1 makes both terms equal to $\sqrt{n k \log M / 2}$ , whose sum is $\sqrt{2 n k \log M}$ .

Depends on

Used by

A context-specific expert class with no shared policy structure Example
A finite two-expert Exp4 instance Example
Duplicated experts change Exp4's uniform prior mass Example

Dependency tree · two levels

36 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)
Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert Schapire, The Nonstochastic Multiarmed Bandit Problem (standard reference, not scraped)