There was a paper by Yasin-Abbasi-Yadkori https://arxiv.org/pdf/1102.2670.pdf titled Online Least Squares Estimation with Self-Normalized Processes. I am trying to give a brief context before asking my question. Let $\{x_t, y_t\}$ be data not necessarily independent, such that they are Linearly related by, $$y_t = x_t^T\theta^* + \epsilon$$ where $\epsilon$ is subgaussian noise. Let $\hat{\theta}_t$ be the ridge regression estimate, $$\hat{\theta}_t = (\lambda I + \sum_{i=1}^{t-1}x_ix_i^T)^{-1}\sum_{i=1}^{t-1}x_iy_i$$ and for notational purposes let $V_t = (\lambda I + \sum_{i=1}^{t-1}x_ix_i^T)$. The theorem proven is the following (Corollary 10) $$\|\theta^* - \hat{\theta}_t\|_{V_t} \leq \mathcal{O}\big(\sqrt{\log{t/\delta} }\big) w.p. 1-\delta$$ where inside the $\mathcal{O}$ I have hidden other dependencies on dimension $d$, subgaussian variance parameter of $\epsilon$, norm of $x$, norm of $\theta^*$ etc,etc.
Coming to my question, this looks like a confidence interval, and my understanding is that with increase in data $t$ the confidence interval is supposed to shrink. I think that with increase in $t$ the eigenvalues in $V_t$ are increasing which would indicate the principal axis of the ellipsoid $\mathcal{E}_t = \{\|\theta - \hat{\theta}_t\|_{V_t} \leq \mathcal{O}\big(\sqrt{\log{t/\delta} }\big)\}$ would have to decrease provided that the rate of decrease is faster than the $\sqrt{\log t}$. But I see no concrete way of establishing that the concentration interval gets smaller as more data is revealed.
I would appreciate any help in this matter. I am not a stats guy so I would request you to be a bit patient. Please do clarify if you feel there are gaps in my post, or there are lapses in my understanding.
Cheers
BTW there's also this really nice blog by Tor Lattimore https://banditalgs.com/2016/11/13/ellipsoidal-confidence-bounds-for-least-squares-estimators/#comment-3881 and also his book on Bandits chapter 20 where there are more details on how one can get such estimates
A brief update on what I have been thinking is of the following nature. Let $\{x_i\}$ is independently chosen. Then one can argue by a somewhat rough nature that the minimum eigen value would be of the order of $t$. Then one would necessarily have $$\|\theta^* - \hat{\theta}_t\|_2 \leq 1/\sqrt{\lambda_{min}(V_t)}\sqrt{\log{t}} = \sqrt{\log{t}}/\sqrt{t}$$, which would ensure the decrease to $0$. This ofcouse hinges on certain linear independence properties of the $\{x_i\}$ but most importantly on the assumption that $x_i$-s are chosen independently. This would ofcourse not hold in the Bandit Setting where the chosen arm $x_i$ is highly correlated with the past arms chosen.
