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

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

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

63 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)

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