Corollary 10. **Under the condition of Theorem 8, with probability at least** 1 − δ,

$$\forall t\geq1,\quad\left\|\hat{\theta}_{t}-\theta_{*}\right\|_{V_{t}}\leq R\sqrt{2\log\left(\frac{1}{\theta_{*}}\right)}$$  _Also, with probability at least $1-\delta$,_
2 log **det(**Vt)

![0_image_0.png](0_image_0.png)

$$\overline{{{\frac{(\lambda I)^{4/2}}{}}}}\Bigg)+\lambda^{1/2}\,S.$$
$$\forall t\geq1,\quad\left\|{\hat{\theta}}_{t}-{\theta}_{*}\right\|_{V_{t}}\leq R{\sqrt{d\log\left({\frac{1+{\frac{t L}{\lambda}}}{\delta}}\right)}}+\lambda^{1/2}\,S.$$

Proof. **Plugging in** x = Vt( ˆθt − θ∗**) into (17), we get**

$$\left\|\hat{\theta}_{t}-\theta_{*}\right\|_{V_{\rm r}}^{2}\leq\left\|V_{t}(\hat{\theta}_{t}-\theta_{*})\right\|_{V_{\rm r}^{-1}}\left(R\sqrt{2\log\left(\frac{\det(V_{t})^{1/2}\det(\lambda I)^{1/2}}{\delta}\right)}+\lambda^{1/2}\,S\right).\tag{19}$$  Now, $\left\|V_{t}(\hat{\theta}_{t}-\theta_{*})\right\|_{V_{\rm r}^{-1}}^{2}=\left\|\hat{\theta}_{t}-\theta_{*}\right\|_{V_{\rm r}}^{2}$ and therefore either $\left\|\hat{\theta}_{t}-\theta_{*}\right\|_{V_{\rm r}}=0$, in which case the conclusion holds, or we can divide both sides of (19) by $\left\|\hat{\theta}_{t}-\theta_{*}\right\|_{V_{\rm r}}$ to obtain the desired result.  
$$(19)$$

clusion holds, or we can divide both sides of (19) by ˆθt − θ∗
Vt to obtain the desired result.

Remark 11. **In fact, the theorem and the corollary are equivalent. To see this note that** x
⊤(
ˆθt−θ∗) =
(
ˆθt − θ∗)
⊤V
1/2 t V
−1/2 t x**, thus**

$$\operatorname*{sup}_{x\neq0}{\frac{|x^{\top}({\hat{\theta}}_{t}-\theta_{*})|}{\|x\|_{V_{t}^{-1}}}}=\left\|{\hat{\theta}}_{t}-\theta_{*}\right\|_{V_{t}}.$$

Remark 12. **The above bound could be compared with a similar bound of Dani et al. (2008) whose**
bound, under identical conditions, states that (with appropriate **initialization) with probability 1**−δ,

for all $t$ large enough,  $$\left\|\hat{\theta}_{t}-\theta_{*}\right\|_{V_{t}}\leq R\max\left\{\sqrt{128\,d\log(t)\,\log\left(\frac{t^{2}}{\delta}\right)},\frac{8}{3}\,\log\left(\frac{t^{2}}{\delta}\right)\right\}\,,\tag{20}$$
where large enough means that t satisfies 0 **< δ < t**2e
−1/16. Denote by pβt(δ**) the right-hand side**
in the above bound. The restriction on t comes from the fact that βt(δ) ≥ 2d(1 + 2 log(t**)) is needed**
in the proof of the last inequality of their Theorem 5.
On the other hand, Theorem 2 gives rise to the following result: For any fixed t ≥ **2, for any**
0 < δ < **1, with probability at least 1** − δ,
$$\left\|{\hat{\theta}}_{t}-\theta_{*}\right\|_{V_{\mathrm{t}}}\leq2\,\kappa^{2}R{\sqrt{\log t}}\,{\sqrt{t}}$$
2Rplog tpd log(t) + log(1/δ) + λ
1/2S ,
where κ is as in Theorem 2. To get a uniform bound one can use a union bound with δt = δ/t2.

Then P∞
t=2 δt = δ( π 2 6 − 1) ≤ δ. This thus gives that for any 0 < δ < **1, with probability at least**
1 − δ, for all t ≥ 2, ˆθt − θ∗
Vt
≤ 2 κ 2Rplog tpd log(t**) + log(**t 2/δ) + λ 1/2S ,
This looks tighter than (20), but is still lagging beyond the result of Corollary 10.

## 5.1 The Linear Bandit Problem

We now turn our attention to the linear bandit problem. Assume the actions lie in D ⊂ R
d **and for**
any x ∈ D, kxk 2 ≤ L. Assume the reward of taking action x ∈ D **has the form of**
ht(x) = θ
⊤
∗ x + ηt and assume ∀x ∈ D, θ⊤
∗ x ∈ [−1, **1]. Define the regret by**

$$R(T)=\sum_{t=1}^{T}(\theta_{*}^{\top}x_{*}-\theta_{*}^{\top}x_{t}),$$
where $x_{*}$ is the optimal action $(x_{*}=\operatorname*{argmax}_{x\in\mathcal{D}}\theta_{*}^{\top}x)$. Define the confidence set,
$${\mathcal{C}}_{t}(\delta)=\left\{\theta:(\theta-{\hat{\theta}}_{t})^{\top}V_{t}(\theta-{\hat{\theta}}_{t})\leq\beta_{t}(\delta)\right\},$$
o, **(21)**
$$(21)$$
