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

For each round, [F7] makes $V_t$ invertible and gives $\det V_t\ge {\lambda }^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 $\left(\begin{array}{cc}{I}_k& B\\ 0& C\end{array}\right)$. The square block $C$ is invertible: otherwise a nonzero $z\in \ker C$ would give $\left(\begin{array}{c}-Bz\\ z\end{array}\right)$ in the kernel of the full left block. Its first column therefore has a nonzero entry, so a row $i\ge k$ with $M_{ik}\mathrm{\ne }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\mathrm{/}({\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=\lambda I_d$, $W_0={\lambda }^{-1}{I}_d$, and $D_0={\lambda }^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.

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

On the confidence event $E=\{{\theta }^{\ast }\in C_t\text{ for all }1\le t\le n\}$ from [F3], step 1.1 and the nonnegative radius formula give ${\rho }_t\ge 0$. Since ${\beta }_t\ge {\rho }_t^2$, the algorithm's radius $\sqrt{{\beta }_t}$ also contains ${\theta }^{\ast }$.

For any $a\in {\mathcal{A}}_t$, [F7] makes $⟨x,y{⟩}_{V_{t-1}}=x^{\mathsf{T}}{V}_{t-1}y$ a real inner product. Cauchy–Schwarz gives $⟨{\theta }^{\ast },a⟩=⟨{\widehat{\theta }}_{t-1},a⟩+⟨{\theta }^{\ast }-{\widehat{\theta }}_{t-1},V_{t-1}^{-1}a{⟩}_{V_{t-1}}\le ⟨{\widehat{\theta }}_{t-1},a⟩+\sqrt{{\beta }_t}\sqrt{a^{\mathsf{T}}{V}_{t-1}^{-1}a}\mathrm{.}$ By step 1.1, $W_{t-1}=V_{t-1}^{-1}$, so the final expression is $U_t(a)$.

By the model, the true-mean maximum on ${\mathcal{A}}_t$ is attained and its value is measurable. For every $a\in {\mathcal{A}}_t$, step 3.1 gives $⟨{\theta }^{\ast },a⟩\le U_t(a)$, and the algorithm's maximization gives $U_t(a)\le U_t(A_t)$. Taking the maximum over $a$ yields ${\max }_{a\in {\mathcal{A}}_t}⟨{\theta }^{\ast },a⟩\le U_t(A_t)\mathrm{.}$

Applying Cauchy–Schwarz to $A_t$ and the confidence error as in step 3.1 yields $⟨{\theta }^{\ast },A_t⟩\ge ⟨{\widehat{\theta }}_{t-1},A_t⟩-\sqrt{{\beta }_t}\sqrt{A_t^{\mathsf{T}}{V}_{t-1}^{-1}{A}_t}=U_t(A_t)-2\sqrt{{\beta }_t}\sqrt{u_t},$ where step 1.1 identifies $W_{t-1}=V_{t-1}^{-1}$. Define $r_t={\max }_{a\in {\mathcal{A}}_t}⟨{\theta }^{\ast },a⟩-⟨{\theta }^{\ast },A_t⟩$. By step 4.1, this gap is nonnegative and at most $2\sqrt{{\beta }_t}\sqrt{u_t}$.

The range hypothesis gives $r_t\le 1$. By [F4], $\det V_t\mathrm{/}\det V_{t-1}=1+u_t\ge 1$, so the algorithm's determinant-defined ${\beta }_t$ is nondecreasing and ${\beta }_t\le {\beta }_n$. If $u_t\le 1$, step 5.1 gives $r_t\le 2\sqrt{{\beta }_n}\sqrt{u_t}$; if $u_t\ge 1$, the range bound gives $r_t\le 1\le 2\sqrt{{\beta }_n}$. Thus in both cases $r_t\le 2\sqrt{{\beta }_n}\min \{1,\sqrt{u_t}\}$.

Squaring step 6.1 gives $r_t^2\le 4{\beta }_n\min \{1,u_t\}$. Euclidean Cauchy–Schwarz on $(r_1,\dots ,r_n)$ and $(1,\dots ,1)$ therefore yields ${\widehat{R}}_n={\sum }_{t=1}^n{r}_t\le \sqrt{n{\sum }_{t=1}^n{r}_t^2}\le 2\sqrt{n{\beta }_n{\sum }_{t=1}^n\min \{1,u_t\}}\mathrm{.}$

Apply the sum bound in [F4] to step 7.1 to obtain ${\widehat{R}}_n\le \sqrt{8n{\beta }_n\log (\det V_n\mathrm{/}\det V_0)}$. Then [F5] gives the second displayed bound. These inequalities hold on $E$, whose probability is at least $1-\delta$ by [F3].