LinUCB with a self-normalized confidence radius

Inputs and admissibility. Take the finite-dimensional linear contextual bandit model and a confidence level $\delta \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 $\lambda >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,{\widehat{\theta }}_n)$.

Initialize $V_0=\lambda I_d$, $b_0=0$, ${\widehat{\theta }}_0=0$, $W_0={\lambda }^{-1}{I}_d$, and $D_0={\lambda }^d$. At each round $t=1,\dots ,n$, compute

${\rho }_t=\sqrt{\lambda }{m}_2+\sqrt{2\log (1\mathrm{/}\delta )+\log (D_{t-1}\mathrm{/}{D}_0)},{\beta }_t=\max \{1,{\rho }_t^2\},$

Next select an available feature vector

$A_t\in \arg {\max }_{a\in {\mathcal{A}}_t}\{⟨{\widehat{\theta }}_{t-1},a⟩+\sqrt{{\beta }_t}\sqrt{a^{\mathsf{T}}{W}_{t-1}a}\}\mathrm{.}$

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^{\mathsf{T}},b_t=b_{t-1}+A_t{X}_t\mathrm{.}$

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\mid I_d]$, set $s=1$ and $D=1$, and for $k=0,\dots ,d-1$ choose the least row index $i\ge k$ whose current left-block entry $M_{ik}$ is nonzero. If no such row exists, return failure. If $i\mathrm{\ne }k$, swap rows $i$ and $k$ and replace $s$ by $-s$. Set $p_k=M_{kk}$, replace $D$ by $D{p}_k$, divide row $k$ by $p_k$, and for every $j\mathrm{\ne }k$ set ${\mathrm{row}}_j\leftarrow {\mathrm{row}}_j-M_{jk}{\mathrm{row}}_k$. After the loop set $W_t$ to the right block and $D_t=sD$, and set ${\widehat{\theta }}_t=W_t{b}_t$. For a compact feature set the supplied selector must return an attained maximizing feature measurably from pre-reward information.

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