0
$\begingroup$

Elliptical Potential Lemma: Let $V_0 \in \mathbb{R}^{d \times d}$ be positive definite and $a_1,a_2,...,a_n \in \mathbb{R}^{d}$ be a sequence of vectors with $||a_t ||_2 \leq L < \infty$ for all $t \in [n]$, $V_t=V_0+\sum_{s=1}^{t}a_s a_s^{T}.$ Then, $$ \sum_{t=1}^{n}\min\big\{ 1,||a_t||_{V_{t-1}^{-1}}^2 \big\} \leq 2\log\bigg(\frac{det (V_n)}{det (V_0)}\bigg) \leq 2d\log\bigg(\frac{traceV_0+nL^2}{det(V_0)^{1/d}}\bigg). $$

This lemma's proof can be found in Lemma 19.4 (Bandit Algorithms). What I'm curious about is, if $a_t \in \mathbb{R}^d$ is random variable and $V_t$ is redefined as $V_t=V_0+\mathbb{E}[\sum_{s=1}^{t}a_s a_s^{T}]$, does the following inequality hold?

$$ \sum_{t=1}^{n}\min\big\{ 1,\mathbb{E}\big[||a_t||_{V_{t-1}^{-1}}^2\big] \big\} \leq 2\log\bigg(\frac{det (V_n)}{det (V_0)}\bigg) \leq 2d\log\bigg(\frac{traceV_0+nL^2}{det(V_0)^{1/d}}\bigg). $$

I've already tried the case that $d=1$, and this inequality still holds. However, I have no idea about $d>1$. Can any one provide some help?

$\endgroup$

0

You must log in to answer this question.

Browse other questions tagged .