Finite-dimensional linear contextual bandit model

Fix integers $d,n\ge 1$, real parameters $\lambda >0$, $L\ge 1$, and $m_2\ge 0$, and a deterministic vector ${\theta }^{\ast }\in {\mathbb{R}}^d$ with $\mathrm{\parallel }{\theta }^{\ast }{\mathrm{\parallel }}_2\le m_2$. Replacing any finite feature bound by its maximum with $1$ makes the convention $L\ge 1$ harmless. Work on a probability space with a filtration $({\mathcal{F}}_t{)}_{t=0}^{n+1}$ satisfying ${\mathcal{F}}_t\subseteq {\mathcal{F}}_{t+1}$.

At round $t$, before reward noise is observed, the history sigma-algebra ${\mathcal{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 ${\mathcal{A}}_t\subseteq {\mathbb{R}}^d$. The features arise from a measurable map ${\psi }_t$ between spaces with declared measurable structures by $a={\psi }_t(C_t,\bar{a})$ for available actions $\bar{a}$. The feature set is finite or compact in the Euclidean topology, every candidate $a\in {\mathcal{A}}_t$ satisfies $\mathrm{\parallel }a{\mathrm{\parallel }}_2\le L$, and the selected feature $A_t={\psi }_t(C_t,a_t)\in {\mathcal{A}}_t$ is ${\mathcal{F}}_t$-measurable. The true-mean maximum is attained and its value is ${\mathcal{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 ${\eta }_t$ is an ${\mathcal{F}}_{t+1}$-measurable real random variable and

$X_t=⟨{\theta }^{\ast },A_t⟩+{\eta }_t\mathrm{.}$

For every $q\in \mathbb{R}$, require $e^{q{\eta }_t}$ to be integrable and its conditional expectation version to satisfy

$\mathbb{E}[e^{q{\eta }_t}\mid {\mathcal{F}}_t]\le e^{q^2\mathrm{/}2}\text{almost surely}\mathrm{.}$

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

$V_t:=\lambda I_d+{\sum }_{s=1}^t{A}_s{A}_s^{\mathsf{T}},b_t:={\sum }_{s=1}^t{A}_s{X}_s,$

with empty sums equal to $0$. Set ${\widehat{\theta }}_0=0$ and ${\widehat{\theta }}_t=V_t^{-1}{b}_t$ for $t\ge 1$. For a real symmetric matrix $M$ satisfying $v^{\mathsf{T}}Mv>0$ for all nonzero $v$, write $\mathrm{\parallel }v{\mathrm{\parallel }}_M:=\sqrt{v^{\mathsf{T}}Mv}$. The estimate ${\widehat{\theta }}_t$ is the unique minimizer of ${\sum }_{s=1}^t(X_s-⟨\theta ,A_s⟩{)}^2+\lambda \mathrm{\parallel }\theta {\mathrm{\parallel }}_2^2$; the sum is not divided by $t$.

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: $({\mathcal{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 ${\mathbb{R}}^n$: $⟨x,y⟩=x^{\mathsf{T}}y$ and $\mathrm{\parallel }x{\mathrm{\parallel }}_2^2=x^{\mathsf{T}}x$.

The Tikhonov regularised least-squares objective $\mathrm{\parallel }Ax-b{\mathrm{\parallel }}_2^2+\lambda \mathrm{\parallel }x{\mathrm{\parallel }}_2^2$ for $\lambda >0$: the ridge objective uses the displayed sample-sum least-squares convention.

For every $\lambda >0$, the Tikhonov objective is strictly convex and has the unique minimiser $(A^{\ast }A+\lambda I{)}^{-1}{A}^{\ast }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