We also have that for all θ ∈ Cτt and x,

$\sin\theta\in\Theta_{\tau_{t}}$ and $\omega$,  $$\left|(\theta-\hat{\theta}_{\tau_{t}})^{\top}x\right|\leq\left\|V_{t}^{1/2}(\theta-\hat{\theta}_{\tau})\right\|\sqrt{x^{\top}V_{t}^{-1}x}$$ $$\leq\left\|V_{\tau_{t}}^{1/2}(\theta-\hat{\theta}_{\tau_{t}})\right\|\sqrt{\frac{\det(V_{t})}{\det(V_{\tau_{t}})}}\sqrt{x^{\top}V_{t}^{-1}x}$$ $$\leq\sqrt{2}\left\|V_{\tau_{t}}^{1/2}(\theta-\hat{\theta}_{\tau})\right\|\sqrt{x^{\top}V_{t}^{-1}x}$$ $$\leq\sqrt{2\beta_{\tau_{t}}}\sqrt{x^{\top}V_{t}^{-1}x},$$  follows from Lemma 15 and that this last 
where the second step follows from Lemma 15, and the third step follows from the fact that at time t we have det(Vt) < **2 det(**Vτt
**). The rest of the argument is identical to that of Theorem 13. We**
conclude that with probability at least 1 − δ, ∀T ≥ 1, R(T ) ≤ 4p2T d log(λ + **tL/d**)
λ 1/2S + Rp2 log 1/δ + d log(1 + tL/(λd)).

## 5.3 Problem Dependent Bound (∆ > 0)

Let ∆ be as defined in (Dani et al., 2008). In this section we assume that ∆ > **0. This includes the case when the action set is a polytope. First we state a matrix perturbation theorem**
from Stewart and Sun (1990) that will be used later.

Theorem 16 (Stewart and Sun (1990), Corollary 4.9). Let A be a symmetric matrix with eigenvalues ν1 ≥ ν2 ≥ . . . ≥ νd, E be a symmetric matrix with eigenvalues e1 ≥ e2 ≥ . . . ≥ ed**, and** V = A+E
denote a symmetric perturbation of A such that the eigenvalues of V are ν˜1 ≥ ν˜2 ≥ . . . ≥ ν˜d**. Then,**
for i = 1**, . . . , d**,
ν˜i ∈ [νi + ed, νi + e1].

Theorem 17. Assume that ∆ > 0 for the gap ∆ **defined in (Dani et al., 2008). Further assume**
that λ ≥ 1 and S ≥ 1. With probability at least 1 − δ, ∀T ≥ 1**, the regret of the algorithm shown in**
Table 1 satisfies

$$R(T)=\frac{16R^{2}\Delta S^{2}}{\Delta}\left(\log(L T)+(d-1)\log\frac{64R^{2}\Delta S^{2}L}{\Delta^{2}}+2(d-1)\log\left(d\log\frac{d\lambda+T L^{2}}{d}+2\log(1/\delta)\right)+2\log(1/\delta)\right)$$
2.
Proof. First we bound the regret in terms of log det(VT **). We have that**

$$R(T)=\sum_{t=1}^{T}r_{t}\leq\sum_{t=1}^{T}{\frac{r_{t}^{2}}{\Delta}}\leq{\frac{16\beta_{T}}{\Delta}}\log(\operatorname*{det}(V_{T})),$$
$$(24)$$

∆log(det(VT )), **(24)**
where the first inequality follows from the fact that either rt = 0 or ∆ < rt**, and the second inequality**
can be extracted from the proof of Theorem 13. Let bt be the number of times we have played a suboptimal action (an action xs **for which** θ
⊤
∗ x∗ − θ
⊤
∗ xs ≥ ∆) up to time t**. Next we bound log det(**Vt)
in terms of bt. We bound the eigenvalues of Vt **by using Theorem 16.**
Let Et =Pts:xs6=x∗

xsx
⊤
sand At = Vt − Et = (t − bt)x∗x
⊤ ∗
. The only non-zero eigenvalue of
(t − bt)x∗x
⊤ ∗
is (t − bt)L
∗**, where** L
∗ = x
⊤
∗ x∗ ≤ L. Let the eigenvalues of Vt and Et be λ1 **≥ · · · ≥** λd
and e1 ≥ · · · ≥ ed **respectively. By Theorem 16, we have that**
$\lambda_{1}\in[(t-b_{t})L^{*}+e_{d},(t-b_{t})L^{*}+e_{1}]\quad\text{and}\quad\forall i\in\{2,\ldots,d\},\,\lambda_{i}\in[e_{d},e_{1}].$
Thus,
$$\operatorname*{det}(V_{t})=\prod_{i}^{d}\lambda_{i}\leq((t-b_{t})L^{*}+e_{1})e_{1}^{d-1}\leq((t-b_{t})L+e_{1})e_{1}^{d-1}.$$
Therefore,
log det(Vt) ≤ log((t − bt)L + e1) + (d − **1) log** e1.
Because trace(E) = Pts:xs6=x∗

trace(xsx
⊤ s
) ≤ Lbt, we conclude that e1 ≤ Lbt**. Thus,**
$\log\det(V_{t})\leq\log((t-b_{t})L+Lb_{t})+(d-1)\log(Lb_{t})$, $=\log(Lt)+(d-1)\log(Lb_{t})$.  
= log(Lt) + (d − 1) log(Lbt). **(25)**
$$(25)$$