Response to Reviewer QJSj
Dear Reviewer QJSj,
Thanks a lot for your engagement. Section 4.1 in the paper describes in detail how to estimate the sum of the variances $\sum_{\ell=1}^t \sigma_\ell^2$ (up to multiplicative accuracy). See Lemma 4.2 and Corollary 4.3.
The idea of this result is to:
1. Estimate a regression model of the historical dataset (see lines 312 to 314). In this case we consider a filtered least squares estimator because we require to estimate the variances in each uncertainty bucket in Algorithm 2. We will continue the discussion using the simpler scenario when $b_\ell=1$ for all $\ell \in\mathbb{N}$. Call this estimator $f_t$.
2. Use this regression model to produce an estimator of the **sum** of the variances $\sum_{\ell=1}^{t-1} \sigma_\ell^2$ by computing $\sum_{\ell=1}^{t-1} r_\ell – f_t(x_\ell, a_\ell))^2$. This is what we call $W_t$.
The proof of Lemma 4.2 and Corollaries 4.3 uses the following logic. A martingale argument shows that for any fixed $f$, the conditional expectations $E[ ( r_\ell – f(x_\ell, a_\ell))^2 | F_\ell ] = \sigma_\ell^2 + (f(x_\ell, a_\ell) – f_\star(x_\ell, a_\ell))^2 $ where in this response we use the notation $F_\ell$ as the sigma algebra of all events up until and including the selection of $x_\ell, a_\ell$. A martingale argument based on a Bernstein bound (see Proposition A.5 in Appendix A) shows that,
$$ \Omega( \sum_{\ell=1}^{t-1} \sigma_\ell^2 + (f(x_\ell, a_\ell) – f_\star(x_\ell, a_\ell))^2 - B^2 \log(t/\delta’)) \leq \sum_{\ell=1}^{t-1} ( r_\ell – f(x_\ell, a_\ell))^2 \leq O( \sum_{\ell=1}^{t-1} \sigma_\ell^2 + (f(x_\ell, a_\ell) – f_\star(x_\ell, a_\ell))^2 + B^2 \log(t/\delta’) )$$
With probability at least $1-\delta’$ for all $t \in \mathbb{N}$. After a union bound over all functions in the class and setting $\delta’ = \delta/|F|$, we can plug in $f_t$ and conclude that,
$$ \Omega( \sum_{\ell=1}^{t-1} \sigma_\ell^2 + (f_t(x_\ell, a_\ell) – f_\star(x_\ell, a_\ell))^2 - B^2 \log(t|F|/\delta)) \leq \sum_{\ell=1}^{t-1} ( r_\ell – f_t(x_\ell, a_\ell))^2 \leq O( \sum_{\ell=1}^{t-1} \sigma_\ell^2 + (f_t(x_\ell, a_\ell) – f_\star(x_\ell, a_\ell))^2 + B^2 \log(t|F|/\delta) )$$
Finally, we use that $\sum_{\ell=1}^{t-1} (f_t( x_\ell, a_\ell) – f_\star(x_\ell, a_\ell) ) = O( B^2 \log(t|F|/\delta) ) $ (see Lemma 4.1 – apply an anytime version of this result) with probability $1-\delta$ for all $t \in \mathbb{N}$. Substituting this result in the expression above and rearranging terms we conclude that,
$$ \Omega( \sum_{\ell=1}^{t-1} \sigma_\ell^2 - B^2 \log(t|F|/\delta’)) \leq \sum_{\ell=1}^{t-1} ( r_\ell – f_t(x_\ell, a_\ell))^2 \leq O( \sum_{\ell=1}^{t-1} \sigma_\ell^2 + B^2 \log(t|F|/\delta’) )$$
This argument can be found in the proof of Lemma 4.2 and Corollary 4.3 in line 1219-1274 of Appendix. E.1
This is the same as when we estimate the sums of the means of an adapted process. Using standard martingale arguments one can show it is possible to estimate the sum of the means of this process even if these change at all time-steps.
**Moving fixed variance results to the appendix.** We want to push back against the reviewers suggestion. It is true that our changing variance results imply fixed variance results by setting all $\sigma_\ell = \sigma$. Nonetheless, our changing variance results have an extra factor of $\sqrt{d_{eluder}}$ in their regret in contrast with the fixed variance setting (See Theorem 4.6 vs Theorem 4.10). On the other hand, we have developed a sharp analysis and algorithm for the fixed unknown variance case (Algorithm 1 with unknown variance - Section 4.2) whose dimension dependence is (we believe) optimal since it matches the sharpest results for linear contextual problems (Theorem 4.6).
We hope this addresses the reviewer's concerns. In case it does, we would really appreciate it if the reviewer could consider increasing their score.