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.

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.

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)