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.

✓ 4 results · all verified · 0 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 4 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Linear contextual bandits and LinUCB — Examples

1 · Prerequisites

2 · Logical flowchart

3 · Definitions, theorems and proofs

None yet.

4 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passOpen item page →

A feature outside the assumed norm bound

Example

Take a one-round horizon $n = 1$ , $d = 2$ , $λ = 1$ , $L = 1$ , and $m_{2} = 0$ . Let $Ω = {ω_{0}}$ , $F = {\emptyset, Ω}$ , $P (Ω) = 1$ , and $F_{t} = F$ for all times. Use a single context $c$ , a single available action $\overset{ˉ}{a}$ , and feature map $ψ (c, \overset{ˉ}{a}) = a = (2, 0)$ . Let $θ^{*} = (0, 0)$ and $η_{1} = 0$ , so the reward is $X_{1} = 0$ . The coordinate Euclidean norm is $∥ a ∥_{2} = \sqrt{a_{1}^{2} + a_{2}^{2}}$ . This candidate violates the model's feature bound, although the matrix update formula still gives $V_{1} = diag (5, 1)$ .

Example references

Finite-dimensional linear contextual bandit model: every candidate feature must have Euclidean norm at most $L$ .

Tor Lattimore and Csaba Szepesvári, Bandit Algorithms, §19.3

Facts & Assumptions

Given: The finite-dimensional linear contextual bandit model and the one-round data in the Example.

[F1]

Finite-dimensional linear contextual bandit model: candidate features satisfy $∥ a ∥_{2} \leq L$ ; the information matrix is $V_{1} = λ I_{2} + a a^{T}$ .

[F2]

Rectangular matrix multiplication and the identity matrix $I_{n}$ , including zero-sized shapes: matrix products and the identity use their usual coordinate formulas.

Verification

1.1givenF1algebra

The feature has norm $∥ a ∥_{2} = \sqrt{2^{2} + 0^{2}} = 2 > 1 = L$ , so it violates the model's candidate-feature hypothesis. The zero parameter and zero noise do not repair that failed assumption.

2.1F1F2step 1.1algebra∎

Its outer product is $a a^{T} = (\begin{array}{cc} 4 & 0 \\ 0 & 0 \end{array})$ and $V_{0} = I_{2}$ , hence $V_{1} = I_{2} + a a^{T} = (\begin{array}{cc} 5 & 0 \\ 0 & 1 \end{array})$ . Thus the algebraic ridge update is defined, while the feature-norm premise used by the regret theorem is absent.

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passOpen item page →

A two-context, two-action ridge update

Example

Let $d = 2$ , $n = 2$ , $λ = L = 1$ , $m_{2} = 0$ , and $δ = 1 / 2$ . On the one-point probability space $Ω = {ω_{0}}$ with its full sigma-algebra and unit mass, let the two contexts be $c_{1}, c_{2}$ and the ordered actions be ${\overset{ˉ}{a}}_{1}, {\overset{ˉ}{a}}_{2}$ . At either context set $ψ (c_{i}, {\overset{ˉ}{a}}_{1}) = e_{1} = (1, 0)$ and $ψ (c_{i}, {\overset{ˉ}{a}}_{2}) = e_{2} = (0, 1)$ . Take $θ^{*} = (0, 0)$ and $η_{1} = η_{2} = 0$ . LinUCB ties on the first round, chooses ${\overset{ˉ}{a}}_{1}$ , updates to $V_{1} = diag (2, 1)$ and ${\hat{θ}}_{1} = 0$ , then chooses ${\overset{ˉ}{a}}_{2}$ on the second round because its confidence width is larger.

Example references

Finite-dimensional linear contextual bandit model: the finite-dimensional feature and reward model.

LinUCB with a self-normalized confidence radius: LinUCB's confidence score, tie-breaking, and sample-sum update.

Tor Lattimore and Csaba Szepesvári, Bandit Algorithms, §19.2

Abbasi-Yadkori, Pál, and Szepesvári, §5.1

Facts & Assumptions

Given: The deterministic two-round instance in the Example.

[F1]

Finite-dimensional linear contextual bandit model: $V_{0} = λ I_{2}$ , $b_{t} = \sum_{s \leq t} A_{s} X_{s}$ , $V_{t} = V_{t - 1} + A_{t} A_{t}^{T}$ , and ${\hat{θ}}_{t} = V_{t}^{- 1} b_{t}$ .

[F2]

LinUCB with a self-normalized confidence radius: the score is $⟨ {\hat{θ}}_{t - 1}, a ⟩ + \sqrt{β_{t}} ∥ a ∥_{V_{t - 1}^{- 1}}$ , $β_{t} \geq 1$ , and ties in a finite ordered action set take the first maximizer.

Verification

1.1givenF1algebra

The parameter satisfies $∥ θ^{*} ∥_{2} = 0 \leq m_{2}$ , both feature vectors have norm $1 = L$ , and each reward is $0$ . For every real $q$ , the conditional MGF is $E [e^{q η_{t}} ∣ F_{t}] = 1 \leq e^{q^{2} / 2}$ ; hence the instance satisfies the model.

2.1givenF1F2step 1.1algebra

At $t = 1$ , ${\hat{θ}}_{0} = 0$ and $V_{0} = I_{2}$ , so the two scores are both $\sqrt{β_{1}}$ . The action order therefore makes LinUCB choose ${\overset{ˉ}{a}}_{1}$ and feature $A_{1} = e_{1}$ .

3.1F1step 2.1algebra

Since $X_{1} = 0$ , the update gives $V_{1} = I_{2} + e_{1} e_{1}^{T} = diag (2, 1)$ , $b_{1} = 0$ , and ${\hat{θ}}_{1} = 0$ .

4.1givenF1F2step 3.1algebra∎

At the second context, the score of ${\overset{ˉ}{a}}_{1}$ is $\sqrt{β_{2}} / \sqrt{2}$ , while the score of ${\overset{ˉ}{a}}_{2}$ is $\sqrt{β_{2}}$ . Because $β_{2} \geq 1$ , the latter is strictly larger, so the algorithm selects ${\overset{ˉ}{a}}_{2}$ .

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passOpen item page →

No common confidence radius without a parameter norm bound

Example

Fix $δ = 1 / 2$ . For each $M > 0$ , take a one-round model with $d = 1$ , $λ = L = 1$ , $m_{2} = M$ , $θ^{*} = M$ , one available feature $A_{1} = 1$ , and zero noise on a one-point probability space. Consider a proposed time-1 confidence radius obtained from the stated self-normalized formula by omitting its $\sqrt{λ} m_{2}$ term. Then no single such radius covers the family as $M$ ranges over all positive reals.

Example references

Finite-dimensional linear contextual bandit model: each model in the family has a finite parameter norm bound $m_{2} = M$ .

The ridge estimate lies in a time-uniform linear confidence ellipsoid: the raw radius includes the term $\sqrt{λ} m_{2}$ .

Tor Lattimore and Csaba Szepesvári, Bandit Algorithms, §20.1, Theorem 20.5

Abbasi-Yadkori, Pál, and Szepesvári, §5

Facts & Assumptions

Given: The family of one-round models in the Example and the confidence-radius formula with its parameter-norm term omitted for comparison.

[F1]

Finite-dimensional linear contextual bandit model: $V_{0} = λ I_{d}$ , ${\hat{θ}}_{0} = 0$ , and each member of the family has $∥ θ^{*} ∥_{2} \leq m_{2}$ with $m_{2} = M$ .

[F2]

The ridge estimate lies in a time-uniform linear confidence ellipsoid: at time $1$ the confidence radius is $\sqrt{λ} m_{2} + \sqrt{2 \log (1 / δ) + \log (\det (V_{0}) / λ^{d})}$ .

Verification

1.1givenF1F2algebra

For the proposed radius with $\sqrt{λ} m_{2}$ omitted, $δ = 1 / 2$ , $λ = 1$ , $V_{0} = 1$ , and $\det (V_{0}) / λ^{d} = 1$ , the time-1 radius equals $r = \sqrt{2 \log 2}$ .

2.1givenF1step 1.1algebra∎

The time-1 estimate is ${\hat{θ}}_{0} = 0$ and its information norm is $∥ θ^{*} - {\hat{θ}}_{0} ∥_{V_{0}} = M$ . Choosing $M > r$ puts the true parameter outside the proposed interval. Since $M$ is arbitrary across the family, a radius omitting a uniform parameter-norm bound cannot cover the family.

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passOpen item page →

An action set whose linear-mean range exceeds one

Example

Consider one round with dimension $d = 1$ , regularization $λ = 1$ , feature bound $L = 2$ , parameter bound $m_{2} = 1$ , and deterministic parameter $θ^{*} = 1$ . Let the context be constant and let the two available actions have scalar features $0$ and $2$ . Use zero reward noise. Both candidate features satisfy the model's bound, but their true means are $0$ and $2$ , so the linear-mean range is $2$ .

Example references

Finite-dimensional linear contextual bandit model: all candidate features must have norm at most $L$ and the conditional noise MGF must be bounded by $e^{q^{2} / 2}$ .

LinUCB has a log-determinant high-probability pseudo-regret bound: the regret guarantee additionally assumes the true-mean range within each available action set is at most $1$ .

Tor Lattimore and Csaba Szepesvári, Bandit Algorithms, §19.3, Theorem 19.2

Abbasi-Yadkori, Pál, and Szepesvári, Theorem 13

Facts & Assumptions

Given: The one-round finite-dimensional linear contextual bandit instance in the Example.

[F1]

Finite-dimensional linear contextual bandit model: each candidate feature has Euclidean norm at most $L$ , rewards are $⟨ θ^{*}, A_{t} ⟩ + η_{t}$ , and the conditional noise MGF bound is $e^{q^{2} / 2}$ .

[F2]

LinUCB has a log-determinant high-probability pseudo-regret bound: its stated guarantee requires $\sup_{a, b \in A_{t}} ⟨ θ^{*}, a - b ⟩ \leq 1$ .

Verification

1.1givenF1algebra

The candidate features are $0$ and $2$ , so both have absolute value at most $L = 2$ . The parameter satisfies $∣ θ^{*} ∣ = 1 = m_{2}$ , and zero noise has conditional MGF $E [e^{q η_{1}} ∣ F_{1}] = 1 \leq e^{q^{2} / 2}$ for every real $q$ . Thus the instance satisfies the model hypotheses.

2.1givenF1F2step 1.1algebra∎

The true means are $θ^{*} \cdot 0 = 0$ and $θ^{*} \cdot 2 = 2$ . Consequently $\sup_{a, b \in {0, 2}} θ^{*} (a - b) = 2 > 1$ , so the additional range premise of [F2] fails. This example therefore lies outside that theorem's stated guarantee and does not refute its conclusion under its hypotheses.

Linear contextual bandits and LinUCB — Examples

2 · Logical flowchart

3 · Definitions, theorems and proofs

4 · Examples, counterexamples and false statements

A feature outside the assumed norm bound

Example

Example references

Facts & Assumptions

Verification

A two-context, two-action ridge update

Example

Example references

Facts & Assumptions

Verification

No common confidence radius without a parameter norm bound

Example

Example references

Facts & Assumptions

Verification

An action set whose linear-mean range exceeds one

Example

Example references

Facts & Assumptions

Verification

Sources