Proof. **The proof is standard (and is given only for the sake of completeness). We claim that** Pt = P
λ t is a supermartingale. Let

$$D_{k}=\exp\left(\frac{\eta_{k}\langle\lambda,m_{k-1}\rangle}{R}-\frac{1}{2}\,\langle\lambda,m_{k-1}\rangle^{2}\right).$$
, $D_k$ is $\mathcal{F}_k$-ac. 
 $\text{oted,as is}P_k.\text{\ Further,}$  . 
$$:\mathbb{E}\left[D_{k}\left|{\mathcal{F}}_{k-1}\right.\right]$$

Observe that by (1), we have E[Dk |Fk−1] ≤ 1. Clearly, Dk is Fk-adapted, as is Pk**. Further,**
E[Pt|Ft−1] = E[D1 · · · Dt−1Dt |Ft−1] = D1 **· · ·** Dt−1 E[Dt |Ft−1] ≤ Pt−1, showing that (Pt**) is indeed a supermartingale.**
Now, this immediately leads to the desired result when τ = t **for some deterministic time** t.

This is based on the fact that the mean of any supermartingale can be bounded by the mean of its first element. In the case of (Pt), for example, we have E[Pt] = E[E[Pt|Ft−1]] ≤ E[Pt−1] ≤ **. . .** ≤
E[P0] = E[D0**] = 1.**
Now, in order to consider the general case, let St = Pτ∧t.

1It is well known that (St**) is still**
a supermartingale with E[St] ≤ E[S0] = E[P0] = 1. Further, since Pt **was nonnegative, so is**
St**. Hence, by the convergence theorem for nonnegative supermartingales, almost surely, lim**t→∞ St exists, i.e., Pτ is almost surely well-defined. Further, E[Pτ ] = E[lim inf t→∞ St] ≤ **lim inf** t→∞ E[St] ≤
1 by Fatou's Lemma.

Before stating our main results, we give some recent results, which **can essentially be extracted**
from the paper by Rusmevichientong and Tsitsiklis (2010).

Theorem 2. Consider the processes (St), (V t) **as defined above and let**

$$\left({4}\right)$$
$\kappa=\sqrt{3+1}$
$\log(1/\delta)$ . 
κ =p3 + 2 log((L2 + trace(V ))/λ0). (4)
Then, for any 0 < δ < 1, t ≥ 2**, with probability at least** 1 − δ,

$$<1,\;t\geq2$$
$$\|S_{t}\|_{\overline{{{V}}}_{t}^{-1}}\leq2\,\kappa^{2}R\sqrt{\log t}\,\sqrt{d\,\log(t)+\log(1/\delta)}\,.$$

2Rplog tpd log(t) + log(1/δ). (5)
We now show how to strengthen the previous result using the method of mixtures, originally used by Robbins and Siegmund (1970) to evaluate boundary crossing probabilities for Brownian motion.

Theorem 3 (Self-normalized bound for vector-valued martingales). Let (ηt), (mt), (St), (V t)**, and**
(Ft) be as before and let τ be a stopping time with respect to the filtration (Ft)**. Assume that** V is deterministic. Then, for any 0 < δ < 1**, with probability** 1 − δ,

$$\|S_{\tau}\|_{\overline{{{V}}}_{\tau}^{-1}}^{2}\leq2R^{2}\log\left(\frac{\operatorname*{det}(\overline{{{V}}}_{\tau})^{1/2}\operatorname*{det}(V)^{4/2}}{\delta}\right)\,.$$

. (6)
Proof. Without loss of generality, assume that R = 1 (by appropriately scaling St**, this can always**
be achieved). Let

$$(6)$$

$$M_{t}(\lambda)=\exp\bigg(\left\langle\lambda,S_{t}\right\rangle-\frac{1}{2}\,\left\|\lambda\right\|_{V_{t}}^{2}\bigg)$$

.
Notice that by Lemma 1, the mean of Mτ (λ**) is not larger than one.**
Let Λ be a Gaussian random variable which is independent of all the other random variables and whose covariance is V
−1**. Define**
Mt = E[Mt(Λ)|F∞] .

Clearly, we still have E[Mτ ] = E[ E[ Mτ (Λ)|**Λ ] ]** ≤ 1.

Let us calculate Mt: Let f denote the density of Λ and for a positive definite matrix P let c(P) = p(2π)
d/ det(P) = R**exp(**−12 x
⊤P x)dx**. Then,**

Mt = Z Rd exp hλ, Sti − 12kλk 2 Vt f(λ) dλ = Z Rd exp − 1 2 λ − V −1 t St  2 Vt + 1 2kStk 2 V −1 t f(λ) dλ =1 c(V ) exp 12kStk 2 V −1 t  Z Rd exp −1 2 nλ − V −1 t St  2 Vt + kλk 2 V o dλ.

1 τ ∧ t is a shorthand notation for min(**τ, t**).