ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedprecheck pass

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

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

18 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)
Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári, Online Least Squares Estimation with Self-Normalized Processes: An Application to Bandit Problems (standard reference, not scraped)