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.

✓ 9 results · all verified · 1 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 8 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Linear contextual bandits and LinUCB

1 · Prerequisites

2 · Logical flowchart

3 · Definitions, theorems and proofs

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passOpen item page →

The elliptical-potential bound for ridge design matrices

Statement

Let $d, n \geq 1$ , let $λ > 0$ , let $V_{0} = λ I_{d}$ , and let $a_{1}, \dots, a_{n} \in R^{d}$ . Define $V_{t} = V_{t - 1} + a_{t} a_{t}^{T}$ and $u_{t} = a_{t}^{T} V_{t - 1}^{- 1} a_{t}$ for $1 \leq t \leq n$ . Then every $V_{t}$ is positive definite, $u_{t} \geq 0$ , and

$\det V_{t} = \det V_{t - 1} (1 + u_{t}) (1 \leq t \leq n), \sum_{t = 1}^{n} \min {1, u_{t}} \leq 2 \log ⁣ (\frac{\det V_{n}}{\det V_{0}}) .$

Statement references

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

Abbasi-Yadkori, Pál, and Szepesvári, Lemma 4

Facts & Assumptions

Given: Positive integers $d, n$ , a real $λ > 0$ , and vectors $a_{1}, \dots, a_{n} \in R^{d}$ .

[F1]

The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ and Rectangular matrix multiplication and the identity matrix $I_{n}$ , including zero-sized shapes: $x^{T} y = ⟨ x, y ⟩$ and $x^{T} M x = ⟨ x, M x ⟩$ in standard coordinates.

[F2]

Hermitian positive-definite matrices and Cholesky factorisation A = LL* with positive diagonal and A matrix admits a Cholesky factorisation with positive diagonal exactly when it is Hermitian positive definite, and that factor is unique: a real symmetric positive-definite matrix $V$ factors as $V = L L^{T}$ with $L$ lower triangular and positive diagonal.

[F3]

For $n \geq 1$ , the determinant over a commutative ring by the Leibniz formula, and $∣ \det A ∣$ for a real matrix, For same-sized finite square matrices over a commutative ring, $\det (A B) = \det (A) \det (B)$ , For every square matrix over a commutative ring, $\det (A^{T}) = \det (A)$ , and The determinant of a triangular matrix is the product of its diagonal entries: determinant is defined by the Leibniz formula, is multiplicative, is unchanged by transpose, and for triangular $L$ equals the product of its diagonal entries.

[F4]

For $A \in M_{n} (R)$ and columns $u, v$ over a commutative ring, $\det (A + u v^{T}) = \det (A) + v^{T} adj (A) u$ : $\det (V + u v^{T}) = \det (V) + v^{T} adj (V) u$ .

[F5]

For every positive-sized square matrix over a commutative ring, $A adj (A) = adj (A) A = \det (A) I$ : $V adj (V) = \det (V) I$ .

[F6]

A finite square real matrix is invertible if and only if its determinant is nonzero: a real square matrix with nonzero determinant is invertible.

[F7]

The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t and If $f \leq g$ on $[a, b]$ and both are integrable then $\int_{a}^{b} f \leq \int_{a}^{b} g$ ; and $m (b - a) \leq \int_{a}^{b} f \leq M (b - a)$ : for $x \geq 0$ , $\log (1 + x) = \int_{1}^{1 + x} d s / s$ , and pointwise inequalities between integrable functions on an increasing interval give the corresponding integral inequality.

[F8]

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

Proof

1.1givenF1algebra

For every $t \geq 0$ and nonzero $x \in R^{d}$ , $x^{T} V_{t} x = λ ∥ x ∥_{2}^{2} + \sum_{s = 1}^{t} (a_{s}^{T} x)^{2} > 0.$ Each $V_{t}$ is symmetric, so it is positive definite.

1.2F7algebra

If $u = 0$ , then $\min {1, u} = 0 = 2 \log (1 + u)$ . If $u > 0$ , the interval $[1, 1 + u]$ is nondegenerate, so [F7] and $1 / s \geq 1 / (1 + u)$ on that interval give $\log (1 + u) \geq u / (1 + u)$ . If $0 < u \leq 1$ , then $u / (1 + u) \geq u / 2$ ; if $u \geq 1$ , then $u / (1 + u) \geq 1 / 2$ . Thus $\min {1, u} \leq 2 \log (1 + u)$ in every case.

2.1step 1.1F2F3F6

By [F2]–[F3], write $V_{t} = L_{t} L_{t}^{T}$ with positive diagonal. Then $\det V_{t} = (\det L_{t})^{2} = (\prod_{i = 1}^{d} (L_{t})_{i i})^{2} > 0$ , so [F6] makes $V_{t}$ invertible. In particular $u_{t}$ is defined.

3.1step 1.1step 2.1F1algebra

The inverse of a positive-definite matrix is positive definite: if $a_{t} \neq 0$ and $y = V_{t - 1}^{- 1} a_{t}$ , then $y \neq 0$ and $u_{t} = a_{t}^{T} V_{t - 1}^{- 1} a_{t} = y^{T} V_{t - 1} y > 0$ ; if $a_{t} = 0$ , then $u_{t} = 0$ . Thus $u_{t} \geq 0$ .

3.2step 2.1F4F5algebra

Apply [F4] with $u = v = a_{t}$ and $V = V_{t - 1}$ . Since [F5] and invertibility in step 2.1 give $adj (V_{t - 1}) = \det (V_{t - 1}) V_{t - 1}^{- 1}$ , the result is $\det V_{t} = \det V_{t - 1} (1 + u_{t})$ .

4.1step 2.1step 3.2F8algebra

Divide the update identities of step 3.2 by the positive determinants of step 2.1 and multiply them for $t = 1, \dots, n$ . This gives $\det V_{n} / \det V_{0} = \prod_{t = 1}^{n} (1 + u_{t})$ , hence $\log (\det V_{n} / \det V_{0}) = \sum_{t = 1}^{n} \log (1 + u_{t})$ by [F8].

5.1step 3.1step 4.1step 1.2algebra∎

Apply step 1.2 to each nonnegative $u_{t}$ from step 3.1 and sum. Step 4.1 identifies the sum of logarithms with $\log (\det V_{n} / \det V_{0})$ , proving the claimed bound.

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passOpen item page →

Trace control of the regularized design determinant

Statement

Let $d, n \geq 1$ , let $λ > 0$ , let $L \geq 0$ , and let $a_{1}, \dots, a_{n} \in R^{d}$ satisfy $∥ a_{t} ∥_{2} \leq L$ . Put $V_{t} = λ I_{d} + \sum_{s = 1}^{t} a_{s} a_{s}^{T}$ and $V_{0} = λ I_{d}$ , and define $tr (M) = \sum_{i = 1}^{d} M_{i i}$ . Then

$0 < \det V_{t} (0 \leq t \leq n), \log ⁣ (\frac{\det V_{n}}{\det V_{0}}) \leq d \log ⁣ (1 + \frac{n L^{2}}{d λ}) .$

Statement references

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

Abbasi-Yadkori, Pál, and Szepesvári, Lemma 4

Facts & Assumptions

Given: Positive integers $d, n$ , reals $λ > 0$ and $L \geq 0$ , and vectors $a_{t} \in R^{d}$ with $∥ a_{t} ∥_{2} \leq L$ .

[F1]

The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ : $∥ x ∥_{2}^{2} = x^{T} x$ and the standard inner product is positive definite.

[F2]

Real spectral theorem: a self-adjoint endomorphism of a finite-dimensional real inner product space has an orthonormal eigenbasis: every real symmetric matrix has an orthonormal eigenbasis.

[F3]

For $n \geq 1$ , the determinant over a commutative ring by the Leibniz formula, and $∣ \det A ∣$ for a real matrix, For same-sized finite square matrices over a commutative ring, $\det (A B) = \det (A) \det (B)$ , and For every square matrix over a commutative ring, $\det (A^{T}) = \det (A)$ : determinant is defined by the Leibniz formula, is multiplicative, and is unchanged by transpose; a diagonal determinant is the product of its diagonal entries by The determinant of a triangular matrix is the product of its diagonal entries.

[F4]

The arithmetic mean, geometric mean inequality: for positive reals $μ_{1}, \dots, μ_{d}$ , $\prod_{i} μ_{i} \leq (\frac{1}{d} \sum_{i} μ_{i})^{d}$ .

[F5]

Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm: the natural logarithm is strictly increasing on positive reals and $\log (x^{d}) = d \log x$ for $x > 0$ .

Proof

1.1givenF1F2algebrachoose

For every nonzero $x \in R^{d}$ , $x^{T} V_{n} x = λ ∥ x ∥_{2}^{2} + \sum_{t = 1}^{n} (a_{t}^{T} x)^{2} > 0.$ Thus $V_{n}$ is symmetric positive definite. By [F2], choose an orthogonal matrix $Q$ and positive eigenvalues $μ_{1}, \dots, μ_{d}$ with $V_{n} = Q diag (μ_{1}, \dots, μ_{d}) Q^{T}$ .

1.2givenF1F2F3algebra

For each $0 \leq t \leq n$ , $x^{T} V_{t} x = λ ∥ x ∥_{2}^{2} + \sum_{s = 1}^{t} (a_{s}^{T} x)^{2} > 0$ for every nonzero $x$ . Thus $V_{t}$ is symmetric positive definite. By [F2], write $V_{t} = Q_{t} diag (ν_{1}, \dots, ν_{d}) Q_{t}^{T}$ with $Q_{t}$ orthogonal; positive definiteness gives $ν_{i} > 0$ for each $i$ . By [F3], $\det (Q_{t}^{T}) = \det (Q_{t})$ and $\det (diag (ν_{1}, \dots, ν_{d})) = \prod_{i} ν_{i}$ . Since $Q_{t}^{T} Q_{t} = I_{d}$ , multiplicativity gives $\det (Q_{t})^{2} = 1$ , hence $\det V_{t} = \prod_{i} ν_{i} > 0$ .

2.1step 1.1F3algebra

Since $Q^{T} Q = I_{d}$ , [F3] gives $(\det Q)^{2} = 1$ . Applying [F3] to the diagonalization yields $\det V_{n} = (\det Q) (\prod_{i} μ_{i}) (\det Q^{T}) = \prod_{i} μ_{i} > 0$ . Also, expanding the diagonal entries of $Q diag (μ_{i}) Q^{T}$ gives $tr (V_{n}) = \sum_{j = 1}^{d} μ_{j} \sum_{i = 1}^{d} Q_{i j}^{2} = \sum_{j = 1}^{d} μ_{j},$ because each column of $Q$ has Euclidean norm one.

3.1givenstep 2.1F1F4algebra

By [F4] and step 2.1, $\det V_{n} = \prod_{i} μ_{i} \leq {(\frac{\sum_{i} μ_{i}}{d})}^{d} = {(\frac{tr (V_{n})}{d})}^{d} .$ The definition of $V_{n}$ gives $tr (V_{n}) = d λ + \sum_{t} ∥ a_{t} ∥_{2}^{2} \leq d λ + n L^{2}$ .

4.1givenF3step 3.1algebra

Since $V_{0} = λ I_{d}$ is diagonal, [F3] gives $\det V_{0} = λ^{d} > 0$ . Dividing step 3.1 by this positive number yields $\frac{\det V_{n}}{\det V_{0}} \leq {(1 + \frac{n L^{2}}{d λ})}^{d} .$

5.1step 2.1step 4.1step 1.2F5algebra∎

The two sides in step 4.1 are positive by steps 2.1 and 4.1. Applying the increasing natural logarithm and then [F5] gives the claimed bound.

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passOpen item page →

Conditional sub-Gaussian bounds allow bounded predictable coefficients

Statement

Assume the Axiom of Choice. Let $(Ω, F, P)$ be a probability space, let $G \subseteq F$ be a sub-sigma-algebra, and let $η$ be a real random variable such that, for every $q \in R$ , $e^{q η}$ is integrable and

$E [e^{q η} ∣ G] \leq e^{q^{2} / 2} almost surely .$

Then for every bounded, real, $G$ -measurable random variable $Q$ ,

$E [e^{Q η - Q^{2} / 2} ∣ G] \leq 1 almost surely .$

Statement references

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

Abbasi-Yadkori, Pál, and Szepesvári, Lemma 1

Facts & Assumptions

Given: AC, a probability space, a sub-sigma-algebra $G$ , and an integrable real random variable $η$ whose exponential moments satisfy the Statement.

[F1]

Conditional expectation given a sigma algebra: a conditional-expectation version is $G$ -measurable and integrable, and its event integrals equal those of the conditioned variable.

[F2]

Basic algebra and order properties of conditional expectation: conditional expectation is linear and order preserving, preserves total expectation, and satisfies $∣ E [X ∣ G] ∣ \leq E [∣ X ∣ ∣ G]$ almost surely. AC is required for the supplied conditional-expectation classes.

[F3]

The exponential function is smooth and $(\exp)^{'} = \exp$ and The chain rule, in one line from Carathéodory: if $g$ is differentiable at $c$ and $f$ is differentiable at $g (c)$ , then $f \circ g$ is differentiable at $c$ with $(f \circ g)^{'} (c) = f^{'} (g (c)) g^{'} (c)$ : $\frac{d}{d q} e^{q η - q^{2} / 2} = (η - q) e^{q η - q^{2} / 2}$ for each fixed finite value of $η$ .

[F4]

The mean value theorem, as the case $g (x) = x$ of Cauchy's: for $f$ continuous on $[a, b]$ with $a < b$ and differentiable on $(a, b)$ there is $c \in (a, b)$ with $f (b) - f (a) = f^{'} (c) (b - a)$ : a differentiable real function on an interval has each increment equal to its derivative at an intermediate point times the interval length.

[A1]

The Axiom of Choice: every family of nonempty sets has a choice function; this supplies the conditional-expectation versions used in [F2].

Proof

1.1givenA1F1F2algebra

First suppose $Q = \sum_{j = 1}^{m} q_{j} 1_{B_{j}}$ for a finite measurable partition $B_{1}, \dots, B_{m}$ in $G$ . Choose conditional-expectation versions $Y_{j} = E [e^{q_{j} η} ∣ G]$ and set $Y = \sum_{j} 1_{B_{j}} e^{- q_{j}^{2} / 2} Y_{j}$ . Both $Y$ and $e^{Q η - Q^{2} / 2}$ are integrable, and $Y$ is $G$ -measurable. For every $B \in G$ , [F1] applied on $B \cap B_{j}$ gives $\int_{B} Y d P = \sum_{j} e^{- q_{j}^{2} / 2} \int_{B \cap B_{j}} Y_{j} d P = \sum_{j} e^{- q_{j}^{2} / 2} \int_{B \cap B_{j}} e^{q_{j} η} d P = \int_{B} e^{Q η - Q^{2} / 2} d P .$ Thus $Y$ is the required conditional-expectation version. The assumed fixed- $q_{j}$ bounds make it at most $\sum_{j} 1_{B_{j}} = 1$ outside a finite union of null sets.

1.2givenconstruct

For a bounded $Q$ , choose $K \geq 1$ with $∣ Q ∣ \leq K$ and let $Q_{r}$ be the finite-valued $G$ -measurable rounding of $Q$ down to the grid $2^{- r} Z$ ; then $∣ Q_{r} - Q ∣ \leq 2^{- r}$ and $∣ Q_{r} ∣ \leq K + 1$ .

2.1F2F3F4step 1.2algebra

For fixed $ω$ , put $g_{ω} (q) = e^{q η (ω) - q^{2} / 2}$ . By [F3]–[F4], on $[- K - 1, K + 1]$ its increments satisfy $∣ g_{ω} (q) - g_{ω} (q^{'}) ∣ \leq ∣ q - q^{'} ∣ (∣ η (ω) ∣ + K + 1) e^{(K + 1) ∣ η (ω) ∣} .$ For $x \geq 0$ , $(x + K + 1) e^{(K + 1) x} \leq (K + 2) e^{(K + 2) x}$ because $x + K + 1 \leq (K + 2) e^{x}$ . Also $e^{(K + 2) ∣ η ∣} \leq e^{(K + 2) η} + e^{- (K + 2) η}$ , whose expectation is at most $2 e^{(K + 2)^{2} / 2}$ by [F2]. The Lipschitz envelope is therefore integrable, so $∣ Q_{r} - Q ∣ \leq 2^{- r}$ implies $E ∣ g (Q_{r}) - g (Q) ∣ \to 0$ .

3.1step 1.1step 2.1F2algebra∎

Set $Y_{r} = E [g (Q_{r}) ∣ G]$ and $Y = E [g (Q) ∣ G]$ . By [F2] and step 2.1, $E ∣ Y_{r} - Y ∣ \leq E ∣ g (Q_{r}) - g (Q) ∣ \to 0$ . Step 1.1 gives $Y_{r} \leq 1$ almost surely for every $r$ ; after removing the countable union of their exceptional null sets, $(Y - 1)_{+} \leq ∣ Y - Y_{r} ∣$ for each $r$ . Taking expectations and passing to the limit gives $E [(Y - 1)_{+}] = 0$ , hence $Y \leq 1$ almost surely.

DefinitionDefinition: Literature-sourcedProof: Not applicableOpen item page →

Finite-dimensional linear contextual bandit model

Definition

Fix integers $d, n \geq 1$ , real parameters $λ > 0$ , $L \geq 1$ , and $m_{2} \geq 0$ , and a deterministic vector $θ^{*} \in R^{d}$ with $∥ θ^{*} ∥_{2} \leq m_{2}$ . Replacing any finite feature bound by its maximum with $1$ makes the convention $L \geq 1$ harmless. Work on a probability space with a filtration $(F_{t})_{t = 0}^{n + 1}$ satisfying $F_{t} \subseteq F_{t + 1}$ .

At round $t$ , before reward noise is observed, the history sigma-algebra $F_{t}$ contains all contexts, choices, and feedback through rounds $s < t$ , as well as the current context $C_{t}$ , the nonempty available action set, and its available feature set $A_{t} \subseteq R^{d}$ . The features arise from a measurable map $ψ_{t}$ between spaces with declared measurable structures by $a = ψ_{t} (C_{t}, \overset{ˉ}{a})$ for available actions $\overset{ˉ}{a}$ . The feature set is finite or compact in the Euclidean topology, every candidate $a \in A_{t}$ satisfies $∥ a ∥_{2} \leq L$ , and the selected feature $A_{t} = ψ_{t} (C_{t}, a_{t}) \in A_{t}$ is $F_{t}$ -measurable. The true-mean maximum is attained and its value is $F_{t}$ -measurable. A policy using LinUCB must also select an attained upper-confidence maximizer measurably from the pre-reward information; finite ordered action sets select the first maximizer, while a compact set is used only when such a predictable selection is supplied.

After $A_{t}$ is selected, the reward $X_{t}$ is observed, where $η_{t}$ is an $F_{t + 1}$ -measurable real random variable and

$X_{t} = ⟨ θ^{*}, A_{t} ⟩ + η_{t} .$

For every $q \in R$ , require $e^{q η_{t}}$ to be integrable and its conditional expectation version to satisfy

$E [e^{q η_{t}} ∣ F_{t}] \leq e^{q^{2} / 2} almost surely .$

This is conditional $1$ -sub-Gaussian noise with the pre-reward convention for $F_{t}$ . No independence between rounds is assumed. For $0 \leq t \leq n$ , define the unaveraged ridge information matrix and response sum by

$V_{t} : = λ I_{d} + \sum_{s = 1}^{t} A_{s} A_{s}^{T}, b_{t} : = \sum_{s = 1}^{t} A_{s} X_{s},$

with empty sums equal to $0$ . Set ${\hat{θ}}_{0} = 0$ and ${\hat{θ}}_{t} = V_{t}^{- 1} b_{t}$ for $t \geq 1$ . For a real symmetric matrix $M$ satisfying $v^{T} M v > 0$ for all nonzero $v$ , write $∥ v ∥_{M} : = \sqrt{v^{T} M v}$ . The estimate ${\hat{θ}}_{t}$ is the unique minimizer of $\sum_{s = 1}^{t} (X_{s} - ⟨ θ, A_{s} ⟩)^{2} + λ ∥ θ ∥_{2}^{2}$ ; the sum is not divided by $t$ .

Definition references

Online decision protocol: the generic protocol restricts a choice to prior history and learner-private randomization before current feedback; the current context and available feature information specified in this contextual model are additional side information.

Random elements and real random variables: contexts, selected features, noise, and rewards are measurable random elements.

A measurable function between measurable spaces: the context/action feature map is measurable between its declared measurable spaces.

Filtration and filtered probability space: $(F_{t})$ is an increasing sequence of sub-sigma-algebras on the probability space.

Conditional expectation given a sigma algebra: each conditional MGF is a measurable integrable version whose event integrals agree with those of the exponential.

The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ : $⟨ x, y ⟩ = x^{T} y$ and $∥ x ∥_{2}^{2} = x^{T} x$ .

The Tikhonov regularised least-squares objective $∥ A x - b ∥_{2}^{2} + λ ∥ x ∥_{2}^{2}$ for $λ > 0$ : the ridge objective uses the displayed sample-sum least-squares convention.

For every $λ > 0$ , the Tikhonov objective is strictly convex and has the unique minimiser $(A^{*} A + λ I)^{- 1} A^{*} b$ : the positive ridge term gives the unique minimizer in the displayed normal-equation form.

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

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

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passOpen item page →

The ridge information matrix is positive definite and invertible

Statement

In the finite-dimensional linear contextual bandit model, for every $0 \leq t \leq n$ the matrix $V_{t} = λ I_{d} + \sum_{s = 1}^{t} A_{s} A_{s}^{T}$ is symmetric and satisfies $x^{T} V_{t} x > 0$ for every nonzero $x \in R^{d}$ . It is invertible, has determinant at least $λ^{d} > 0$ , and for every $x \in R^{d}$ ,

$x^{T} V_{t}^{- 1} x \leq \frac{∥ x ∥_{2}^{2}}{λ} .$

Statement references

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

Facts & Assumptions

Given: The model's fixed $λ > 0$ , feature vectors $A_{s} \in R^{d}$ , and the matrices $V_{t} = λ I_{d} + \sum_{s = 1}^{t} A_{s} A_{s}^{T}$ .

[F1]

Finite-dimensional linear contextual bandit model gives the displayed $V_{t}$ and Euclidean feature vectors.

[F2]

The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ : $x^{T} y = ⟨ x, y ⟩$ and $∥ x ∥_{2}^{2} = x^{T} x$ .

[F3]

Real spectral theorem: a self-adjoint endomorphism of a finite-dimensional real inner product space has an orthonormal eigenbasis: a real symmetric matrix has an orthonormal eigenbasis.

[F4]

Hermitian positive-definite matrices and Cholesky factorisation A = LL* with positive diagonal and A matrix admits a Cholesky factorisation with positive diagonal exactly when it is Hermitian positive definite, and that factor is unique: a real symmetric matrix with positive quadratic form on nonzero vectors factors as $L L^{T}$ with positive diagonal.

[F5]

For $n \geq 1$ , the determinant over a commutative ring by the Leibniz formula, and $∣ \det A ∣$ for a real matrix, For same-sized finite square matrices over a commutative ring, $\det (A B) = \det (A) \det (B)$ , For every square matrix over a commutative ring, $\det (A^{T}) = \det (A)$ , and The determinant of a triangular matrix is the product of its diagonal entries: determinant is multiplicative and unchanged by transpose; for triangular $L$ it is the product of its diagonal entries. Thus for an orthogonal $Q$ , $\det (Q) \det (Q^{T}) = \det (Q Q^{T}) = 1$ .

[F6]

A finite square real matrix is invertible if and only if its determinant is nonzero: a real square matrix with nonzero determinant is invertible.

Proof

1.1givenF1F2algebra

For any $x \neq 0$ , the model formula gives $x^{T} V_{t} x = λ ∥ x ∥_{2}^{2} + \sum_{s = 1}^{t} (A_{s}^{T} x)^{2} > 0,$ since $λ > 0$ and $∥ x ∥_{2} > 0$ . Each summand $A_{s} A_{s}^{T}$ is symmetric, so $V_{t}$ is symmetric as well.

2.1step 1.1F3algebrachoose

By [F3], choose an orthonormal eigenbasis $q_{1}, \dots, q_{d}$ of $V_{t}$ with eigenvalues $μ_{1}, \dots, μ_{d}$ . Applying step 1.1 to each unit eigenvector gives $μ_{i} = q_{i}^{T} V_{t} q_{i} \geq λ$ .

2.2step 1.1F4F5F6algebra

Alternatively identifying the determinant sign explicitly, [F4] gives $V_{t} = L L^{T}$ with positive diagonal. By [F5], $\det V_{t} = (\prod_{i} L_{i i})^{2} > 0$ ; [F6] therefore also yields invertibility.

3.1step 2.1F2algebra

Expand any $x = \sum_{i} c_{i} q_{i}$ in that orthonormal basis. Then $x^{T} V_{t}^{- 1} x = \sum_{i} c_{i}^{2} / μ_{i} \leq λ^{- 1} \sum_{i} c_{i}^{2} = λ^{- 1} ∥ x ∥_{2}^{2}$ , using $μ_{i} \geq λ > 0$ . This also shows $V_{t}^{- 1}$ exists.

3.2step 2.1F3F5algebra

The same diagonalization and [F5] give $\det V_{t} = \det (Q) \det (diag (μ_{1}, \dots, μ_{d})) \det (Q^{T}) = \prod_{i} μ_{i} \geq λ^{d} > 0$ .

4.1step 1.1step 2.2step 3.1step 3.2given∎

Steps 1.1, 2.2, 3.1, and 3.2 prove symmetry, strict positivity of the quadratic form, the inverse bound, the determinant lower bound, and invertibility for each $t$ . The case $t = 0$ uses the same formulas with an empty sum.

LemmaStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

The ridge estimates and self-normalized sums are measurable

Statement

In the finite-dimensional linear contextual bandit model, put

$G_{t} : = \sum_{s = 1}^{t} A_{s} A_{s}^{T}, S_{t} : = \sum_{s = 1}^{t} A_{s} η_{s} (0 \leq t \leq n) .$

Give each finite real matrix space its entrywise Euclidean topology and corresponding Borel sigma-algebra. Then $V_{t}$ , $b_{t}$ , $G_{t}$ , $S_{t}$ , and $D_{t} : = \det (V_{t})$ are $F_{t + 1}$ -measurable matrix, vector, or real random elements, and the ridge estimate ${\hat{θ}}_{t} = V_{t}^{- 1} b_{t}$ is an $F_{t + 1}$ -measurable $R^{d}$ -valued random element for every $0 \leq t \leq n$ .

Statement references

Finite-dimensional linear contextual bandit model: the model's features, rewards, filtration, and ridge notation.

The ridge information matrix is positive definite and invertible: $V_{t}$ is invertible and $\det V_{t} \geq λ^{d} > 0$ .

Jiří Lebl, Basic Analysis II, Proposition 8.2.7 and Propositions 8.2.8–8.2.9

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

Facts & Assumptions

Given: The finite-dimensional bandit model's measurable feature vectors, reward noises, and rewards through the finite horizon.

[F1]

Finite-dimensional linear contextual bandit model: $A_{s}$ is $F_{s}$ -measurable, $η_{s}$ is $F_{s + 1}$ -measurable, $X_{s} = ⟨ θ^{*}, A_{s} ⟩ + η_{s}$ , and $V_{t}$ , $b_{t}$ , and ${\hat{θ}}_{t}$ have the displayed formulas.

[F2]

The vector space $M_{m \times n} (F) : = F^{m \times n}$ of $m$ by $n$ matrices over a field, with entrywise operations and Finite rectangular matrices over a commutative ring, their entries, rows and columns: a matrix is the finite function of its real entries; the entrywise Euclidean coordinates identify $M_{d} (R)$ with $R^{d^{2}}$ .

[F3]

A measurable function between measurable spaces and The Borel sigma-algebra of a topological space: a map is measurable when preimages of Borel sets are measurable, and the Borel sigma-algebra is generated by open sets.

[F4]

Arithmetic and lattice operations preserve measurability whenever they are defined: finite pointwise sums and products of real-valued measurable functions are measurable whenever the operations are defined.

[F5]

For every fixed finite size at least one, the determinant of a real square matrix is a polynomial in its matrix entries: for each fixed finite matrix size, determinant is a finite polynomial in the entries.

[F6]

Deleted-row-and-column minors, cofactors, the cofactor matrix and the adjugate over a commutative ring: each entry of $adj (V)$ is a signed deleted-row-and-column determinant; for size $1$ , the empty minor has determinant $1$ .

[F7]

For every positive-sized square matrix over a commutative ring, $A adj (A) = adj (A) A = \det (A) I$ , The reals form a field, and Every field is a commutative ring with $1 \neq 0$ ; it is an integral domain, and it is a commutative division ring: $V adj (V) = \det (V) I$ for real square matrices.

[F8]

The ridge information matrix is positive definite and invertible: each $V_{t}$ is invertible and $D_{t} : = \det (V_{t}) \geq λ^{d} > 0$ .

[F9]

A continuous map has Borel preimages of Borel sets: a continuous real function has Borel preimages of Borel sets.

[F10]

Rectangular matrix multiplication and the identity matrix $I_{n}$ , including zero-sized shapes: each coordinate of a matrix-vector product is a finite sum of products of entries.

Proof

1.1givenF1F2F4

For $s \leq t$ , each coordinate of $A_{s}$ is $F_{s}$ -measurable and each coordinate of $η_{s}$ is $F_{s + 1}$ -measurable; the filtration gives $F_{s}, F_{s + 1} \subseteq F_{t + 1}$ . The reward equation and [F4] make $X_{s}$ measurable at $F_{t + 1}$ . Applying [F4] coordinatewise to the finite sums and products defining $G_{t}$ , $S_{t}$ , $V_{t}$ , and $b_{t}$ proves that each coordinate is $F_{t + 1}$ -measurable. The Borel sigma-algebra of a finite-dimensional Euclidean vector or matrix space is generated by its coordinate projections: rational open boxes form a countable basis. Thus these maps are measurable random elements. At $t = 0$ all four are constant.

2.1step 1.1F3F5F8

The determinant $D_{t}$ is $F_{t + 1}$ -measurable by step 1.1, [F4], and the polynomial formula [F5]. By [F8] its range lies in $J = [λ^{d}, \infty)$ . It is also measurable as a map into $J$ : for every relatively open set $J \cap U$ , with $U \subseteq R$ open, $D_{t}^{- 1} (J \cap U) = D_{t}^{- 1} (U)$ because $D_{t}$ takes values in $J$ .

3.1step 2.1F3F4F5F6F7F8F9

The reciprocal $r : J \to R$ , $r (x) = 1 / x$ , is continuous since $λ^{d} > 0$ , hence Borel measurable by [F9]. The definition of measurability in [F3] then makes $D_{t}^{- 1} = r \circ D_{t}$ measurable. By [F5]–[F6], every entry of $adj (V_{t})$ is measurable; for $d = 1$ it is the constant $1$ . Since $V_{t}$ is invertible, [F7] gives $adj (V_{t}) = D_{t} V_{t}^{- 1}$ , so $V_{t}^{- 1} = D_{t}^{- 1} adj (V_{t})$ has measurable entries by [F4].

4.1step 1.1step 3.1F2F4F10∎

By [F10], every coordinate of ${\hat{θ}}_{t} = V_{t}^{- 1} b_{t}$ is a finite sum of products of measurable entries from steps 1.1 and 3.1; [F4] makes each coordinate measurable. The coordinate-Borel fact in step 1.1 then makes ${\hat{θ}}_{t}$ a measurable random element. At $t = 0$ , ${\hat{θ}}_{0} = 0$ is constant. Thus every stated vector and matrix is an $F_{t + 1}$ -measurable random element.

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passOpen item page →

The conditional Gaussian mixture is a nonnegative supermartingale

Statement

Assume AC and Countable Choice and the finite-dimensional linear contextual bandit model. Put $S_{t} = \sum_{s = 1}^{t} A_{s} η_{s}$ , $G_{t} = \sum_{s = 1}^{t} A_{s} A_{s}^{T}$ , and $V_{t} = λ I_{d} + G_{t}$ . Let $H_{t} : = F_{t + 1}$ be the information after round $t$ has been observed. Then

$Z_{t} : = \sqrt{\frac{\det (V_{0})}{\det (V_{t})}} \exp ⁣ (\frac{1}{2} S_{t}^{T} V_{t}^{- 1} S_{t}), Z_{0} : = 1,$

is a nonnegative integrable supermartingale with respect to $(H_{t})_{t = 0}^{n}$ .

Statement references

Tor Lattimore and Csaba Szepesvári, Bandit Algorithms, §20.1, Lemma 20.3 and Theorem 20.4

Abbasi-Yadkori, Pál, and Szepesvári, Lemma 1 and Theorem 3

Facts & Assumptions

Given: AC, Countable Choice, the model's predictable feature vectors and conditional MGF bounds, and the matrix sums $S_{t}, G_{t}, V_{t}$ in the Statement.

[A1]

The Axiom of Choice: every family of nonempty sets has a choice function; it supplies the conditional-expectation existence and supermartingale interfaces used here.

[A2]

The Axiom of Countable Choice ( ${A C}_{ω}$ ): every countable family of nonempty sets has a choice function; it is the exact choice premise of the Gaussian integral and Lebesgue change-of-variables suppliers.

[F1]

Finite-dimensional linear contextual bandit model: $A_{t}$ is $F_{t}$ -measurable, $∥ A_{t} ∥_{2} \leq L$ , and $E [e^{q η_{t}} ∣ F_{t}] \leq e^{q^{2} / 2}$ for each real $q$ .

[F2]

Conditional sub-Gaussian bounds allow bounded predictable coefficients: for bounded $F_{t}$ -measurable $Q$ , $E [e^{Q η_{t} - Q^{2} / 2} ∣ F_{t}] \leq 1$ almost surely.

[F3]

Cauchy-Schwarz $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥_{2} ∥ y ∥_{2}$ with its equality case, the triangle inequality for $∥ \cdot ∥_{2}$ , the parallelogram law and polarisation: $∣ u^{T} A_{t} ∣ \leq ∥ u ∥_{2} ∥ A_{t} ∥_{2}$ .

[F4]

The ridge information matrix is positive definite and invertible: $V_{t}$ is symmetric positive definite and $\det V_{t} > 0$ .

[F5]

Conditional expectation given a sigma algebra, Conditional expectation as an ae class, Conditional expectation exists by radon nikodym, and Martingale submartingale and supermartingale: conditional-expectation versions are measurable and integrable and have the same integrals as the conditioned variable on every event in the conditioning sigma-algebra; a supermartingale is an integrable adapted process whose next conditional-expectation class is at most its current value. The existence and supermartingale interfaces use AC.

[F6]

Basic algebra and order properties of conditional expectation: conditional expectation is linear and order preserving, preserves total expectation, and contracts $L^{1}$ .

[F7]

Monotone convergence for the integral: increasing nonnegative measurable functions pass to the limit under the integral.

[F8]

Gaussian integral for a positive-definite quadratic form: for symmetric positive-definite $V$ , $\int_{R^{d}} e^{- u^{T} V u / 2} d u = (2 π)^{d / 2} / \sqrt{\det V}$ under Countable Choice.

[F9]

A C^1 diffeomorphism satisfies the change-of-variables formula for nonnegative Lebesgue measurable functions: a $C^{1}$ diffeomorphism changes a nonnegative Lebesgue integral by the absolute Jacobian determinant; translations have Jacobian determinant $1$ .

[F10]

Tonelli's theorem for nonnegative measurable functions on a sigma-finite product: for a nonnegative product-measurable function on sigma-finite spaces, the iterated integrals equal the product integral and the section integrals are measurable.

[F11]

The product sigma-algebra and its finite iterates, A measurable function between measurable spaces, The vector space $M_{m \times n} (F) : = F^{m \times n}$ of $m$ by $n$ matrices over a field, with entrywise operations, The Borel sigma-algebra of a topological space, A continuous map has Borel preimages of Borel sets, and Closure properties of measurable functions used by the integral: finite-coordinate measurable maps, continuous polynomial/exponential operations, and their compositions are measurable on the relevant finite product spaces.

[F12]

The determinant of a triangular matrix is the product of its diagonal entries: $\det (λ I_{d}) = λ^{d}$ .

Proof

1.1givenF1F2F3F6algebra

For fixed $u \in R^{d}$ , define $M_{t} (u) = \exp ⁣ (u^{T} S_{t} - \frac{1}{2} u^{T} G_{t} u)$ , $M_{0} (u) = 1$ , and $R_{t} (u) = e^{Q_{t} η_{t} - Q_{t}^{2} / 2}$ where $Q_{t} = u^{T} A_{t}$ . The model makes $Q_{t}$ $F_{t}$ -measurable and, by [F3], bounds $∣ Q_{t} ∣ \leq L ∥ u ∥_{2}$ . Thus [F2] gives $E [R_{t} (u) ∣ F_{t}] \leq 1$ and [F6] gives $E [R_{t} (u)] \leq 1$ . Also $M_{t} (u) = M_{t - 1} (u) R_{t} (u)$ , and $M_{t} (u)$ is $H_{t} = F_{t + 1}$ -measurable.

1.2givenA2F8F10F11

For fixed $t$ , each coordinate of $S_{t}$ and $G_{t}$ is a finite sum and product of variables observed by time $t$ . On $(Ω \times R^{d}, H_{t} \otimes B (R^{d}))$ , the projections from each factor are measurable, so each coordinate of $S_{t} (ω)$ , $G_{t} (ω)$ , and $u$ is measurable. The Borel sigma-algebra of the finite-dimensional Euclidean product is generated by coordinate projections, since rational open boxes form a countable basis; hence $(ω, u) \mapsto (S_{t} (ω), G_{t} (ω), u)$ is measurable. The maps $(S, G, u) \mapsto u^{T} S - \frac{1}{2} u^{T} G u$ and $x \mapsto e^{x}$ are continuous, so $(ω, u) \mapsto M_{t} (u, ω)$ is product-measurable by [F11]. Tonelli's section-measurability clause [F10] therefore makes ${\overline{M}}_{t} = \int M_{t} (u) p_{λ} (u) d u$ $H_{t}$ -measurable. The density $p_{λ} (u) = (λ / (2 π))^{d / 2} e^{- λ ∥ u ∥_{2}^{2} / 2}$ is nonnegative and integrates to $1$ by [F8] with $V = λ I_{d}$ .

1.3givenF4algebra

By the definitions of $S_{t}, G_{t}, V_{t}$ and the Gaussian density, ${\overline{M}}_{t} = {(\frac{λ}{2 π})}^{d / 2} \int_{R^{d}} \exp ⁣ (u^{T} S_{t} - \frac{1}{2} u^{T} V_{t} u) d u .$ Completing the square gives $u^{T} S_{t} - \frac{1}{2} u^{T} V_{t} u = \frac{1}{2} S_{t}^{T} V_{t}^{- 1} S_{t} - \frac{1}{2} (u - V_{t}^{- 1} S_{t})^{T} V_{t} (u - V_{t}^{- 1} S_{t}) .$

2.1step 1.1F5F7constructalgebra

For fixed $u, t$ and every $B \in F_{t}$ , step 1.1 and the defining event integrals [F5] give $E [1_{B} R_{t} (u)] \leq P (B)$ . Hence for any nonnegative finite-valued $F_{t}$ -measurable $W = \sum_{j} c_{j} 1_{B_{j}}$ , summing these inequalities gives $E [W R_{t} (u)] \leq E [W]$ . For a bounded nonnegative $F_{t}$ -measurable $W$ , the finite-valued dyadic approximants $W_{r} = 2^{- r} ⌊ 2^{r} W ⌋$ increase to $W$ . Since $R_{t} (u) \geq 0$ , monotone convergence [F7] on both sides gives the same inequality for $W$ .

3.1step 1.1step 2.1A1F5F7algebra

Induct on $t$ to prove integrability and the supermartingale inequality. The base $M_{0} (u) = 1$ is integrable. If $M_{t - 1} (u)$ is integrable, put $W_{k} = \min {M_{t - 1} (u), k}$ , a bounded nonnegative $F_{t}$ -measurable variable. Step 2.1 gives $E [W_{k} R_{t} (u)] \leq E [W_{k}]$ . Since $W_{k} R_{t} (u) ↑ M_{t} (u)$ , [F7] gives $E [M_{t} (u)] \leq E [M_{t - 1} (u)] \leq 1$ . Replacing $W_{k}$ by $1_{B} W_{k}$ for any $B \in F_{t}$ and applying [F7] again gives $E [1_{B} M_{t} (u)] \leq E [1_{B} M_{t - 1} (u)]$ . Let $Y_{t}$ be a conditional-expectation version of $M_{t} (u)$ given $F_{t}$ , which exists by [A1] and [F5]. For each $k \geq 1$ , $B_{k} : = {Y_{t} \geq M_{t - 1} (u) + 1 / k} \in F_{t}$ . On $B_{k}$ , the event-integral property in [F5] and the preceding inequality imply $\int_{B_{k}} Y_{t} d P = \int_{B_{k}} M_{t} (u) d P \leq \int_{B_{k}} M_{t - 1} (u) d P,$ whereas the definition of $B_{k}$ makes the left side at least the right side plus $P (B_{k}) / k$ . Thus $P (B_{k}) = 0$ for every $k$ ; since ${Y_{t} > M_{t - 1} (u)} = ⋃_{k \geq 1} B_{k}$ , we have $Y_{t} \leq M_{t - 1} (u)$ almost surely. This is the supermartingale conditional-expectation inequality.

4.1step 3.1step 1.2A1F5F10algebra

For any $B \in H_{t - 1} = F_{t}$ , Tonelli [F10] and step 3.1 give $E [1_{B} {\overline{M}}_{t}] = \int E [1_{B} M_{t} (u)] p_{λ} (u) d u \leq \int E [1_{B} M_{t - 1} (u)] p_{λ} (u) d u = E [1_{B} {\overline{M}}_{t - 1}] .$ Taking $B = Ω$ shows ${\overline{M}}_{t}$ is integrable. Let $Y_{t}$ be a conditional-expectation version of ${\overline{M}}_{t}$ given $H_{t - 1}$ ; it exists by [A1] and [F5]. For each $k \geq 1$ , $B_{k} : = {Y_{t} \geq {\overline{M}}_{t - 1} + 1 / k} \in H_{t - 1}$ . The event-integral property [F5] and the displayed event inequality imply $\int_{B_{k}} Y_{t} d P = E [1_{B_{k}} {\overline{M}}_{t}] \leq E [1_{B_{k}} {\overline{M}}_{t - 1}],$ while the definition of $B_{k}$ makes the left side at least the right side plus $P (B_{k}) / k$ . Thus every $B_{k}$ is null and $Y_{t} \leq {\overline{M}}_{t - 1}$ almost surely. Together with adaptedness from step 1.2 and ${\overline{M}}_{0} = 1$ , this is the integrable supermartingale property.

5.1step 4.1step 1.3A2F4F8F9F12algebra∎

The translation $w = u - V_{t}^{- 1} S_{t}$ is a $C^{1}$ diffeomorphism with Jacobian determinant $1$ , so [F9] and [F8] evaluate the last integral as $(2 π)^{d / 2} / \sqrt{\det V_{t}}$ . Since $\det V_{0} = λ^{d}$ by [F12], this gives ${\overline{M}}_{t} = \sqrt{\frac{\det V_{0}}{\det V_{t}}} \exp ⁣ (\frac{1}{2} S_{t}^{T} V_{t}^{- 1} S_{t}) = Z_{t} .$ Thus the process in the Statement is the supermartingale established in step 4.1.

AlgorithmAlgorithm: Literature-sourcedProof: Not applicableOpen item page →

LinUCB with a self-normalized confidence radius

Definition

Inputs and admissibility. Take the finite-dimensional linear contextual bandit model and a confidence level $δ \in (0, 1)$ . At each round, the nonempty available action set is finite and ordered with its feature vectors, or the available feature set is compact with a supplied attained measurable predictable maximizer for the score below. In the finite case evaluate the score for each action's feature and resolve ties by the first action. All model assumptions, including $λ > 0$ , the feature and parameter bounds, pre-reward information, and the conditional noise bound, are in force.

Outputs. Before each reward is observed, output the selected feature $A_{t}$ ; after the reward $X_{t}$ is observed, record it. At the horizon return the online sequence $(A_{t}, X_{t})_{t = 1}^{n}$ and terminal state $(V_{n}, b_{n}, {\hat{θ}}_{n})$ .

Initialize $V_{0} = λ I_{d}$ , $b_{0} = 0$ , ${\hat{θ}}_{0} = 0$ , $W_{0} = λ^{- 1} I_{d}$ , and $D_{0} = λ^{d}$ . At each round $t = 1, \dots, n$ , compute

$ρ_{t} = \sqrt{λ} m_{2} + \sqrt{2 \log (1 / δ) + \log (D_{t - 1} / D_{0})}, β_{t} = \max {1, ρ_{t}^{2}},$

Next select an available feature vector

$A_{t} \in \arg \max_{a \in A_{t}} {⟨ {\hat{θ}}_{t - 1}, a ⟩ + \sqrt{β_{t}} \sqrt{a^{T} W_{t - 1} a}} .$

For a finite ordered action set, evaluate every action's score and take the first maximizing action's feature; for a compact feature set, call the supplied selector once. After observing reward $X_{t}$ , update

$V_{t} = V_{t - 1} + A_{t} A_{t}^{T}, b_{t} = b_{t - 1} + A_{t} X_{t} .$

Then compute the updated matrix state $W_{t}, D_{t}$ from $V_{t}$ by the following exact row procedure. Form the augmented matrix $M = [V_{t} ∣ I_{d}]$ , set $s = 1$ and $D = 1$ , and for $k = 0, \dots, d - 1$ choose the least row index $i \geq k$ whose current left-block entry $M_{i k}$ is nonzero. If no such row exists, return failure. If $i \neq k$ , swap rows $i$ and $k$ and replace $s$ by $- s$ . Set $p_{k} = M_{k k}$ , replace $D$ by $D p_{k}$ , divide row $k$ by $p_{k}$ , and for every $j \neq k$ set ${row}_{j} \leftarrow {row}_{j} - M_{j k} {row}_{k}$ . After the loop set $W_{t}$ to the right block and $D_{t} = s D$ , and set ${\hat{θ}}_{t} = W_{t} b_{t}$ . For a compact feature set the supplied selector must return an attained maximizing feature measurably from pre-reward information.

Definition references

Finite-dimensional linear contextual bandit model: the context/feature map, conditional reward model, filtration, norm bound, and sample-sum ridge notation.

The ridge information matrix is positive definite and invertible: the matrices $V_{t}$ are positive definite, invertible, and have positive determinant.

The ridge estimates and self-normalized sums are measurable: the ridge estimate, information matrix, and response sum are measurable from the available data.

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

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

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passOpen item page →

The ridge estimate lies in a time-uniform linear confidence ellipsoid

Statement

Assume AC and Countable Choice and the finite-dimensional linear contextual bandit model. For $δ \in (0, 1)$ and $1 \leq t \leq n$ , set

$ρ_{t} = \sqrt{λ} m_{2} + \sqrt{2 \log (1 / δ) + \log ⁣ (\frac{\det V_{t - 1}}{λ^{d}})}, C_{t} = {θ \in R^{d} : ∥ θ - {\hat{θ}}_{t - 1} ∥_{V_{t - 1}}^{2} \leq ρ_{t}^{2}} .$

Then

$P {θ^{*} \in C_{t} for every 1 \leq t \leq n} \geq 1 - δ .$

Statement references

Tor Lattimore and Csaba Szepesvári, Bandit Algorithms, Theorems 20.4–20.5

Abbasi-Yadkori, Pál, and Szepesvári, Theorem 3 and Corollary 10

Facts & Assumptions

Given: AC, Countable Choice, the model's deterministic $θ^{*}$ with $∥ θ^{*} ∥_{2} \leq m_{2}$ , predictable feature vectors, reward equation, and conditional MGF bound.

[A1]

The Axiom of Choice: conditional-expectation versions exist under the supplied AC branch; the optional-sampling interface assumes AC.

[A2]

The Axiom of Countable Choice ( ${A C}_{ω}$ ): the Gaussian-integral supplier assumes Countable Choice.

[F1]

Finite-dimensional linear contextual bandit model: $X_{t} = ⟨ θ^{*}, A_{t} ⟩ + η_{t}$ , $b_{t} = \sum_{s \leq t} A_{s} X_{s}$ , $V_{t} = λ I + \sum_{s \leq t} A_{s} A_{s}^{T}$ , and $∥ θ^{*} ∥_{2} \leq m_{2}$ .

[F2]

The ridge information matrix is positive definite and invertible: each $V_{t}$ is symmetric positive definite, $\det (V_{t}) \geq λ^{d} > 0$ , and $x^{T} V_{t}^{- 1} x \leq λ^{- 1} ∥ x ∥_{2}^{2}$ .

[F3]

The conditional Gaussian mixture is a nonnegative supermartingale: $Z_{s} = \sqrt{\det (V_{0}) / \det (V_{s})} \exp (\frac{1}{2} S_{s}^{T} V_{s}^{- 1} S_{s})$ is a nonnegative integrable supermartingale with $Z_{0} = 1$ .

[F4]

Optional sampling for bounded stopping times: for an integrable supermartingale and stopping times $σ \leq τ$ bounded by a deterministic integer, $E [Z_{τ}] \leq E [Z_{σ}]$ .

[F5]

Markov's inequality for random variables: if $Y \geq 0$ and $a > 0$ , then $P (Y \geq a) \leq E [Y] / a$ .

[F6]

Real and complex inner-product spaces and their induced length, The norm $∥ v ∥ = \sqrt{⟨ v, v ⟩}$ induced by a real or complex inner product, and The inner-product norm is definite, homogeneous, and satisfies the triangle inequality: a symmetric positive-definite bilinear form is a real inner product; its induced norm satisfies Cauchy–Schwarz and the triangle inequality.

[F7]

The determinant of a triangular matrix is the product of its diagonal entries: $\det (λ I_{d}) = λ^{d}$ for $λ > 0$ .

[F8]

The ridge estimates and self-normalized sums are measurable: $V_{t}$ , $\det (V_{t})$ , $b_{t}$ , and ${\hat{θ}}_{t}$ are measurable through time $t + 1$ , so the confidence-ellipsoid events and radii are measurable.

[F9]

The natural logarithm as the inverse of the exponential function and Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm: $\log$ is defined on positive reals, continuous, and strictly increasing there.

[F10]

Arithmetic and lattice operations preserve measurability whenever they are defined: finite sums and products of real-valued measurable functions are measurable.

[F11]

Sigma-algebras: a sigma-algebra is closed under complements and countable unions, so finite intersections follow by De Morgan's law.

Proof

1.1F1F3F7construct

Since $V_{0} = λ I_{d}$ is diagonal, [F7] gives $\det V_{0} = λ^{d} > 0$ . On $H_{s} = F_{s + 1}$ , define $σ$ as the first $s \in {0, \dots, n}$ with $Z_{s} \geq 1 / δ$ , and set $σ = n$ if there is no such $s$ . For $k < n$ , ${σ \leq k} = ⋃_{s = 0}^{k} {Z_{s} \geq 1 / δ} \in H_{k}$ , while ${σ \leq n} = Ω$ . Hence $σ$ is a stopping time bounded by $n$ .

1.2F1algebra

For each $0 \leq s < n$ , the model reward equation gives $b_{s} = G_{s} θ^{*} + S_{s} = (V_{s} - λ I_{d}) θ^{*} + S_{s}$ . Therefore ${\hat{θ}}_{s} - θ^{*} = V_{s}^{- 1} S_{s} - λ V_{s}^{- 1} θ^{*} .$

1.3F1F2F6algebra

For fixed $s$ , define $⟨ x, y ⟩_{V_{s}} = x^{T} V_{s} y$ . By [F2] this form is symmetric and positive definite, so [F6] gives its induced norm triangle inequality. Also $∥ V_{s}^{- 1} S_{s} ∥_{V_{s}}^{2} = S_{s}^{T} V_{s}^{- 1} S_{s}$ and $∥ λ V_{s}^{- 1} θ^{*} ∥_{V_{s}}^{2} = λ^{2} (θ^{*})^{T} V_{s}^{- 1} θ^{*} \leq λ ∥ θ^{*} ∥_{2}^{2} \leq λ m_{2}^{2} .$

2.1step 1.1A1A2F3F4F5algebra

By [F4], $E [Z_{σ}] \leq E [Z_{0}] = 1$ . On the event that some $Z_{s}$ crosses $1 / δ$ by time $n$ , the definition of $σ$ gives $Z_{σ} \geq 1 / δ$ . Thus [F5] yields $P {\exists s \leq n : Z_{s} \geq 1 / δ} \leq δ$ .

3.1step 1.1step 2.1F2F3F9algebra

Outside the crossing event bounded in step 2.1, every $0 \leq s \leq n$ has $Z_{s} < 1 / δ$ . Taking logarithms in [F3]'s formula and using $\det V_{0} = λ^{d}$ from step 1.1 gives $S_{s}^{T} V_{s}^{- 1} S_{s} < 2 \log (1 / δ) + \log ⁣ (\frac{\det V_{s}}{λ^{d}}) .$ All logarithm arguments are positive by [F2].

4.1step 3.1step 1.2step 1.3F1F2F8F9F10F11algebra∎

Apply the triangle inequality from step 1.3 to step 1.2, then use step 3.1. For $t = s + 1$ this yields $∥ {\hat{θ}}_{t - 1} - θ^{*} ∥_{V_{t - 1}} \leq \sqrt{S_{t - 1}^{T} V_{t - 1}^{- 1} S_{t - 1}} + \sqrt{λ} m_{2} \leq ρ_{t} .$ The radius $ρ_{t}$ is measurable: its determinant input is measurable by [F8], the logarithm is continuous by [F9], and $x \mapsto \sqrt{x}$ is continuous on $[0, \infty)$ since $∣ \sqrt{x} - \sqrt{y} ∣^{2} \leq ∣ x - y ∣$ there; the radicand is nonnegative by [F2] and $δ \in (0, 1)$ . By [F8] and [F10], the quadratic form defining $C_{t}$ is measurable. The finite intersection of these events is measurable by [F11], so ${θ^{*} \in C_{t} for every 1 \leq t \leq n}$ is measurable. Its probability is at least $1 - δ$ by step 2.1.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passOpen item page →

LinUCB has a log-determinant high-probability pseudo-regret bound

Statement

Assume AC and Countable Choice, the finite-dimensional linear contextual bandit model, and LinUCB with $β_{t} = \max {1, ρ_{t}^{2}}$ as defined in the algorithm. Let $δ \in (0, 1)$ be the confidence input to LinUCB. Suppose also that for every round $t$ ,

$\sup_{a, b \in A_{t}} ⟨ θ^{*}, a - b ⟩ \leq 1.$

Define the random pseudo-regret by

${\hat{R}}_{n} : = \sum_{t = 1}^{n} (\max_{a \in A_{t}} ⟨ θ^{*}, a ⟩ - ⟨ θ^{*}, A_{t} ⟩) .$

Then, with probability at least $1 - δ$ ,

${\hat{R}}_{n} \leq \sqrt{8 n β_{n} \log ⁣ (\frac{\det V_{n}}{\det V_{0}})} \leq \sqrt{8 d n β_{n} \log ⁣ (1 + \frac{n L^{2}}{d λ})} .$

Algorithm properties. For every admissible model input, the algorithm also completes exactly $n$ rounds and outputs $(A_{t}, X_{t})_{t = 1}^{n}$ and $(V_{n}, b_{n}, {\hat{θ}}_{n})$ . Count exact real arithmetic operations, comparisons, square roots, and logarithms with unit cost, and exclude generation of contexts, features, and rewards. Let $F$ be the rounds with finite action sets and let $m_{t}$ be the number of available actions at round $t \in F$ ; let $K$ be the compact-feature rounds. The procedure makes exactly $∣ K ∣$ calls to the supplied maximizing selector and uses $O (n d^{3} + d^{2} \sum_{t \in F} m_{t})$ operations apart from selector costs.

Statement references

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

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

Facts & Assumptions

Given: AC, Countable Choice, the bandit model and LinUCB algorithm, and the per-round optimal-mean range bound in the Statement.

[A1]

The Axiom of Choice: the confidence supplier uses AC for conditional-expectation classes and bounded optional sampling.

[A2]

The Axiom of Countable Choice ( ${A C}_{ω}$ ): the confidence supplier uses Countable Choice for its Gaussian integral.

[F1]

Finite-dimensional linear contextual bandit model: the model's fixed $θ^{*}$ , feature bounds $∥ a ∥_{2} \leq L$ , information matrices $V_{t}$ , and sample-sum ridge estimates.

[F2]

LinUCB with a self-normalized confidence radius: $A_{t}$ maximizes $U_{t} (a) = ⟨ {\hat{θ}}_{t - 1}, a ⟩ + \sqrt{β_{t}} \sqrt{a^{T} W_{t - 1} a}$ and $β_{t} = \max {1, ρ_{t}^{2}}$ .

[F3]

The ridge estimate lies in a time-uniform linear confidence ellipsoid: with probability at least $1 - δ$ , the true parameter is in the ellipsoid of radius $ρ_{t}$ about ${\hat{θ}}_{t - 1}$ for every round in the horizon.

[F4]

The elliptical-potential bound for ridge design matrices: if $u_{t} = ∥ A_{t} ∥_{V_{t - 1}^{- 1}}^{2}$ , then $\sum_{t} \min {1, u_{t}} \leq 2 \log (\det V_{n} / \det V_{0})$ and $\det V_{t} / \det V_{t - 1} = 1 + u_{t} \geq 1$ .

[F5]

Trace control of the regularized design determinant: $\log (\det V_{n} / \det V_{0}) \leq d \log (1 + n L^{2} / (d λ))$ .

[F6]

Cauchy–Schwarz: $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥ ∥ y ∥$ , with equality exactly for dependent pairs: $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥ ∥ y ∥$ in every real inner-product space; Cauchy–Schwarz also applies to the Euclidean inner product on $R^{n}$ .

[F7]

The ridge information matrix is positive definite and invertible: each $V_{t}$ is symmetric positive definite, so $⟨ x, y ⟩_{V_{t}} : = x^{T} V_{t} y$ is a real inner product and $V_{t}^{- 1}$ is positive definite.

[F8]

LinUCB with a self-normalized confidence radius: the procedure initializes $W_{0}, D_{0}$ , executes the stated finite loop, uses row swaps, nonzero row scalings, and row additions on the augmented matrix to construct $W_{t}, D_{t}$ , and returns the specified online and terminal outputs. For $n \geq 1$ , the determinant over a commutative ring by the Leibniz formula, and $∣ \det A ∣$ for a real matrix gives $\det (I_{d}) = 1$ and $\det (λ I_{d}) = λ^{d}$ by its Leibniz formula; For every square matrix, including singular ones, a row swap negates the determinant, scaling a row by any scalar scales it, and row addition leaves it unchanged gives the determinant changes for the row operations.

Proof

1.1F1F2F7F8algebra

For each round, [F7] makes $V_{t}$ invertible and gives $\det V_{t} \geq λ^{d} > 0$ . To verify the row procedure, suppose $k < d$ pivots have succeeded. Each row swap, scaling by a nonzero pivot, and row addition is invertible, so the transformed left block remains invertible; elimination leaves it in block form $(\begin{array}{cc} I_{k} & B \\ 0 & C \end{array})$ . The square block $C$ is invertible: otherwise a nonzero $z \in \ker C$ would give $(\begin{array}{c} - B z \\ z \end{array})$ in the kernel of the full left block. Its first column therefore has a nonzero entry, so a row $i \geq k$ with $M_{i k} \neq 0$ exists and the selected pivot $p_{k}$ is nonzero. Induction gives all $d$ pivots and reduces the left block to $I_{d}$ . The same row operations on the right identity block give a matrix $Q$ with $Q V_{t} = I_{d}$ , hence $W_{t} = Q = V_{t}^{- 1}$ . If $s$ is the product of row-swap signs, determinant tracking using [F8] gives $1 = \det (V_{t}) s / (\prod_{k = 0}^{d - 1} p_{k})$ , so the stored value $s \prod_{k = 0}^{d - 1} p_{k}$ is exactly $D_{t} = \det (V_{t})$ . Initially these identities follow directly from $V_{0} = λ I_{d}$ , $W_{0} = λ^{- 1} I_{d}$ , and $D_{0} = λ^{d}$ . Therefore each confidence logarithm is finite and nonnegative, every score is finite, and the model or supplied selector makes an attained measurable choice. The model supplies each finite reward and the update matrices remain positive definite by [F7]. Induction over the fixed loop proves that all $n$ rounds complete and the stated outputs exist.

2.1step 1.1F2F8algebra

At each elimination pivot, searching and swapping rows costs $O (d)$ operations; normalizing one row and eliminating its column from at most $d - 1$ rows costs $O (d^{2})$ . The $d$ pivots therefore cost $O (d^{3})$ . Each matrix update and multiplication by $b_{t}$ costs $O (d^{2})$ ; one finite-action score costs $O (d^{2})$ and a maximization over $m_{t}$ actions costs $O (d^{2} m_{t})$ . Storing the returned feature and reward costs $O (d)$ per round. Summing over $n$ rounds gives $O (n d^{3} + d^{2} \sum_{t \in F} m_{t})$ operations, and there is exactly one selector call for each $t \in K$ .

2.2A1A2F2F3step 1.1algebra

On the confidence event $E = {θ^{*} \in C_{t} for all 1 \leq t \leq n}$ from [F3], step 1.1 and the nonnegative radius formula give $ρ_{t} \geq 0$ . Since $β_{t} \geq ρ_{t}^{2}$ , the algorithm's radius $\sqrt{β_{t}}$ also contains $θ^{*}$ .

3.1F1F2F3F6F7step 1.1step 2.2algebra

For any $a \in A_{t}$ , [F7] makes $⟨ x, y ⟩_{V_{t - 1}} = x^{T} V_{t - 1} y$ a real inner product. Cauchy–Schwarz gives $⟨ θ^{*}, a ⟩ = ⟨ {\hat{θ}}_{t - 1}, a ⟩ + ⟨ θ^{*} - {\hat{θ}}_{t - 1}, V_{t - 1}^{- 1} a ⟩_{V_{t - 1}} \leq ⟨ {\hat{θ}}_{t - 1}, a ⟩ + \sqrt{β_{t}} \sqrt{a^{T} V_{t - 1}^{- 1} a} .$ By step 1.1, $W_{t - 1} = V_{t - 1}^{- 1}$ , so the final expression is $U_{t} (a)$ .

4.1F1F2step 3.1

By the model, the true-mean maximum on $A_{t}$ is attained and its value is measurable. For every $a \in A_{t}$ , step 3.1 gives $⟨ θ^{*}, a ⟩ \leq U_{t} (a)$ , and the algorithm's maximization gives $U_{t} (a) \leq U_{t} (A_{t})$ . Taking the maximum over $a$ yields $\max_{a \in A_{t}} ⟨ θ^{*}, a ⟩ \leq U_{t} (A_{t}) .$

5.1F1F2F3F6F7step 1.1step 2.2step 4.1algebra

Applying Cauchy–Schwarz to $A_{t}$ and the confidence error as in step 3.1 yields $⟨ θ^{*}, A_{t} ⟩ \geq ⟨ {\hat{θ}}_{t - 1}, A_{t} ⟩ - \sqrt{β_{t}} \sqrt{A_{t}^{T} V_{t - 1}^{- 1} A_{t}} = U_{t} (A_{t}) - 2 \sqrt{β_{t}} \sqrt{u_{t}},$ where step 1.1 identifies $W_{t - 1} = V_{t - 1}^{- 1}$ . Define $r_{t} = \max_{a \in A_{t}} ⟨ θ^{*}, a ⟩ - ⟨ θ^{*}, A_{t} ⟩$ . By step 4.1, this gap is nonnegative and at most $2 \sqrt{β_{t}} \sqrt{u_{t}}$ .

6.1F2F4step 5.1algebra

The range hypothesis gives $r_{t} \leq 1$ . By [F4], $\det V_{t} / \det V_{t - 1} = 1 + u_{t} \geq 1$ , so the algorithm's determinant-defined $β_{t}$ is nondecreasing and $β_{t} \leq β_{n}$ . If $u_{t} \leq 1$ , step 5.1 gives $r_{t} \leq 2 \sqrt{β_{n}} \sqrt{u_{t}}$ ; if $u_{t} \geq 1$ , the range bound gives $r_{t} \leq 1 \leq 2 \sqrt{β_{n}}$ . Thus in both cases $r_{t} \leq 2 \sqrt{β_{n}} \min {1, \sqrt{u_{t}}}$ .

7.1step 6.1F6algebra

Squaring step 6.1 gives $r_{t}^{2} \leq 4 β_{n} \min {1, u_{t}}$ . Euclidean Cauchy–Schwarz on $(r_{1}, \dots, r_{n})$ and $(1, \dots, 1)$ therefore yields ${\hat{R}}_{n} = \sum_{t = 1}^{n} r_{t} \leq \sqrt{n \sum_{t = 1}^{n} r_{t}^{2}} \leq 2 \sqrt{n β_{n} \sum_{t = 1}^{n} \min {1, u_{t}}} .$

8.1F3F4F5step 7.1∎

Apply the sum bound in [F4] to step 7.1 to obtain ${\hat{R}}_{n} \leq \sqrt{8 n β_{n} \log (\det V_{n} / \det V_{0})}$ . Then [F5] gives the second displayed bound. These inequalities hold on $E$ , whose probability is at least $1 - δ$ by [F3].

CorollaryStatement: Literature-sourcedProof: AI-adaptedprecheck passOpen item page →

LinUCB has expected pseudo-regret of order $d \sqrt{n} \log (n L)$

Statement

Assume the hypotheses of the LinUCB high-probability regret theorem, with $d \geq 1$ , $λ > 0$ , $L \geq 1$ , $m_{2} \geq 0$ , and horizon $n \geq 2$ . Run LinUCB with $δ = 1 / n$ . Let ${\hat{R}}_{n}$ be its random pseudo-regret and define expected pseudo-regret by $R_{n} : = E [{\hat{R}}_{n}]$ . Put

$q_{n} : = \log ⁣ (1 + \frac{n L^{2}}{d λ}), B_{n} : = \sqrt{8 d n β_{n} q_{n}},$

where $β_{n}$ is the algorithm's confidence schedule, and set

$c : = 1 + \frac{\log (1 + L / λ)}{\log 2}, C_{1} : = 4 + 2 c + \frac{1 + 2 λ m_{2}^{2}}{\log 2}, C : = \sqrt{8 C_{1} c} + \frac{1}{\sqrt{2} \log 2} .$

Here $B_{n}$ is generally random through $β_{n}$ and the design matrix. Then

$R_{n} \leq E [B_{n}] + 1 \leq C d \sqrt{n} \log (n L) .$

This is an expected pseudo-regret bound; it is distinct from a high-probability bound on realized reward regret.

Statement references

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

Abbasi-Yadkori, Pál, and Szepesvári, §5.1, Theorem 13 and its expected-regret caveat

Facts & Assumptions

Given: AC, Countable Choice, LinUCB's confidence schedule, the model hypotheses, and the per-round linear-mean range bound from the high-probability regret theorem.

[A1]

The Axiom of Choice: AC is inherited through the conditional-expectation, supermartingale, and bounded optional-sampling interfaces in the confidence proof.

[A2]

The Axiom of Countable Choice ( ${A C}_{ω}$ ): Countable Choice is inherited through the Gaussian integral in the confidence proof.

[F1]

LinUCB has a log-determinant high-probability pseudo-regret bound: with probability at least $1 - δ$ , ${\hat{R}}_{n} \leq \sqrt{8 d n β_{n} \log (1 + n L^{2} / (d λ))}$ when the per-round mean range is at most $1$ .

[F2]

LinUCB with a self-normalized confidence radius: $β_{n} = \max {1, (\sqrt{λ} m_{2} + \sqrt{2 \log (1 / δ) + \log (\det V_{n - 1} / λ^{d})})^{2}}$ .

[F3]

Trace control of the regularized design determinant: applying its determinant bound to the first $n - 1 \geq 1$ feature vectors and using monotonicity of $\log$ gives $\log (\det V_{n - 1} / λ^{d}) \leq d \log (1 + (n - 1) L^{2} / (d λ)) \leq d \log (1 + n L^{2} / (d λ)) = d q_{n}$ .

[F4]

Finite-dimensional linear contextual bandit model and [F1]: the pseudo-regret is measurable and each round gap lies in $[0, 1]$ under the theorem's range assumption, so $0 \leq {\hat{R}}_{n} \leq n$ .

[F5]

Expectation of a nonnegative or integrable random variable, Linearity, monotonicity, and the modulus bound for expectation, and The expectation of an indicator is the probability of the event: expectations are integrals, preserve order and finite sums, and $E [1_{E}] = P (E)$ .

[F6]

Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm: $\log$ is increasing and $\log (x y) = \log x + \log y$ for positive arguments.

[F7]

The ridge estimates and self-normalized sums are measurable and LinUCB with a self-normalized confidence radius: $\det V_{n - 1}$ is measurable, and the algorithm formulas make $β_{n}$ and $B_{n}$ nonnegative measurable random variables.

Proof

1.1F2F3algebra

With $δ = 1 / n$ , [F2] and [F3] give $β_{n} \leq 1 + {(\sqrt{λ} m_{2} + \sqrt{2 \log n + d q_{n}})}^{2} \leq 1 + 2 λ m_{2}^{2} + 4 \log n + 2 d q_{n} .$ The first inequality uses $\max {1, x} \leq 1 + x$ for $x \geq 0$ ; the second uses $(a + b)^{2} \leq 2 a^{2} + 2 b^{2}$ .

2.1F6step 1.1algebra

Since $n L \geq 2$ , $\log n \leq \log (n L)$ and $1 + \frac{n L^{2}}{d λ} \leq 1 + \frac{n L^{2}}{λ} \leq n L (1 + \frac{L}{λ}) .$ By [F6], $q_{n} \leq \log (n L) + \log (1 + L / λ) \leq c \log (n L)$ . Hence step 1.1 and $d \geq 1$ , $\log (n L) \geq \log 2$ imply $β_{n} \leq C_{1} d \log (n L)$ .

3.1step 2.1F6F7algebra

Step 2.1 and the definition of $B_{n}$ give $B_{n} = \sqrt{8 d n β_{n} q_{n}} \leq \sqrt{8 C_{1} c} d \sqrt{n} \log (n L)$ pointwise. By [F7], $B_{n}$ is measurable; this deterministic bound makes it integrable.

4.1A1A2F1F4F5F7step 3.1algebra

By [F1] with $δ = 1 / n$ , there is a measurable event $E$ with $P (E) \geq 1 - 1 / n$ on which ${\hat{R}}_{n} \leq B_{n}$ . By [F4], $0 \leq {\hat{R}}_{n} \leq n$ on every outcome. Therefore ${\hat{R}}_{n} \leq B_{n} 1_{E} + n 1_{E^{c}}$ pointwise. Taking expectations and using [F5], [F7], and step 2.1 gives $R_{n} \leq E [B_{n} 1_{E}] + n P (E^{c}) \leq E [B_{n}] + 1.$

5.1step 2.1step 3.1step 4.1algebra∎

Also $d \sqrt{n} \log (n L) \geq \sqrt{2} \log 2$ , so $1 \leq d \sqrt{n} \log (n L) / (\sqrt{2} \log 2)$ . Combining this with steps 3.1 and 4.1 proves $R_{n} \leq C d \sqrt{n} \log (n L)$ .

4 · Examples, counterexamples and false statements

None yet.

Linear contextual bandits and LinUCB

2 · Logical flowchart

3 · Definitions, theorems and proofs

The elliptical-potential bound for ridge design matrices

Statement

Statement references

Facts & Assumptions

Proof

Trace control of the regularized design determinant

Statement

Statement references

Facts & Assumptions

Proof

Conditional sub-Gaussian bounds allow bounded predictable coefficients

Statement

Statement references

Facts & Assumptions

Proof

Finite-dimensional linear contextual bandit model

Definition

Definition references

The ridge information matrix is positive definite and invertible

Statement

Statement references

Facts & Assumptions

Proof

The ridge estimates and self-normalized sums are measurable

Statement

Statement references

Facts & Assumptions

Proof

The conditional Gaussian mixture is a nonnegative supermartingale

Statement

Statement references

Facts & Assumptions

Proof

LinUCB with a self-normalized confidence radius

Definition

Definition references

The ridge estimate lies in a time-uniform linear confidence ellipsoid

Statement

Statement references

Facts & Assumptions

Proof

LinUCB has a log-determinant high-probability pseudo-regret bound

Statement

Statement references

Facts & Assumptions

Proof

LinUCB has expected pseudo-regret of order dnlog⁡(nL)dn​log(nL)

Statement

Statement references

Facts & Assumptions

Proof

4 · Examples, counterexamples and false statements

Sources

LinUCB has expected pseudo-regret of order $d \sqrt{n} \log (n L)$