= Solution
Use the single event
$$
\mathcal E=\bigcap_{t\geq0}\{\theta_\star\in\Theta_t\},\qquad\mathbb P(\mathcal E)\geq1-\delta.
$$
Fix a realization in $\mathcal E$. The action space is nonempty and <compact>, since it is a closed subset of the finite-dimensional unit ball. The <Lipschitz continuous> reward function is continuous, so there is an optimal action $x_\star\in\operatorname*{arg\,max}_{x\in\mathcal X}\mu(\langle x,\theta_\star\rangle)$. Because the same reward function is used at every time, the <pseudoregret> is $R_n=\sum_{t=1}^n r_t$, where
$$
r_t=\mu(\langle x_\star,\theta_\star\rangle)-\mu(\langle X_t,\theta_\star\rangle)\geq0.
$$
The pair $(x_\star,\theta_\star)$ is feasible in the optimization defining $(X_t,\theta_t)$. This <optimism in the face of uncertainty> gives
$$
\mu(\langle x_\star,\theta_\star\rangle)\leq\mu(\langle X_t,\theta_t\rangle),
\qquad
r_t\leq L|\langle X_t,\theta_t-\theta_\star\rangle|.
$$
For any <positive-definite matrix> $V$, the ordinary <Cauchy-Schwarz inequality> applied to $V^{-1/2}x$ and $V^{1/2}z$ proves
$$
|\langle x,z\rangle|\leq|x|_{V^{-1}}|z|_V.
$$
Both $\theta_t$ and $\theta_\star$ belong to the same <confidence ellipsoid> $\Theta_{t-1}$. The <triangle inequality> for the <norm> associated with this <weighted Euclidean inner product> therefore gives
$$
|\theta_t-\theta_\star|_{V_{t-1}}
\leq|\theta_t-\widehat\theta_{t-1}|_{V_{t-1}}
+|\widehat\theta_{t-1}-\theta_\star|_{V_{t-1}}
\leq2\beta_{t-1}(\delta),
$$
and hence $r_t\leq2L\beta_{t-1}(\delta)|X_t|_{V_{t-1}^{-1}}$. Monotonicity of $\beta_t(\delta)$ and another <Cauchy-Schwarz inequality> now yield
$$
\begin{aligned}
R_n&\leq2L\beta_n(\delta)\sum_{t=1}^n|X_t|_{V_{t-1}^{-1}}\\
&\leq\boxed{2L\beta_n(\delta)\sqrt{n\sum_{t=1}^n|X_t|_{V_{t-1}^{-1}}^2}}.
\end{aligned}
$$
This reasoning holds on $\mathcal E$ for every $n$ simultaneously, proving the asserted probability. In combination with part (a), it also gives
$$
R_n\leq2L\beta_n(\delta)\sqrt{2nd\log\left(1+\frac n{d\lambda}\right)}.
$$
Only the supplied simultaneous <confidence set> coverage and the optimistic choice are needed here. No claim that the displayed linear estimator is automatically a suitable estimator for a nonlinear link is required: its coverage was an explicit hypothesis.
Back to article page
