Second Order Bounds for Contextual Bandits with Function Approximation

We are very happy to see the reviewer agrees our work is novel, tackles an interesting problem and does so convincingly. Regardless, we want to reiterate our contributions. In this work we introduce algorithms for regret minimization of variance aware contextual bandits with function approximation. We solve this problem for two different settings, first the scenario where the noise variance is uniform and equal to a value $\sigma^2$ during all rounds. In this case we show our algorithm (algorithm 1) achieves a regret rate scaling as $\sigma\sqrt{ d \log(F) T} + d\log(F)$ where $d$ is the eluder dimension and $\log(F)$ is the logarithm of the size of the reward function class. This result nails down the complexity of variance aware contextual bandits in the function approximation regime and generalizes existing results in that space that could only prove bounds for linear problems. At the time of submission ours was the first algorithm achieving this type of result. When the variances are unknown and changing at all time steps we achieve a regret bound of order $d \sqrt{ \sum_{t=1}^T \sigma_t^2 \log(F)} + d\log(F)$ (notice the $\sqrt{d}$ degradation with respect to the uniform variance result). This result also recovers and generalizes existing results that deal only with linear problems. The main difficulty in obtaining our results was to generalize the linear techniques to deal with general function approximation.

We address the weaknesses section of the review:

Thanks for finding the typo in Line 264. The label clearly refers to Lemma 3.2 that is right above this line. We changed the name from Proposition to Lemma this typo was introduced. We fail to see how this could have been highly confusing. We believe the reviewer has a typo in their review and they mean Appendix B. This appendix contains a fully self contained discussion on Optimistic Least Squares to make it easier for the reader to understand the related literature. We fail to understand why this is controversial, particularly since a) it is in the appendix, b) there is no claim in the main that this is our contribution. The event $E$ is defined in line 264 (before line 279). Algorithm 3 is the optimistic least squares algorithm the reviewer has pointed out above from Appendix B. It isn’t really needed in the discussion from the main section, so this reference can be removed. Thanks for pointing to this. We are baffled by this “lack of comparison with previous results”. We describe several related works in this area in our introductory section. As the reviewer rightly points out, ours is the first work to deal with second order bounds in the function approximation regime and thus, there is no previous work that works on the exact same problem. That being said, we mention a plethora of related linear works from the literature that had a strong influence in our work along with their regret bounds. If the reviewer has a specific work in mind we should compare to we would be really happy to include it. In short, our fixed variance result matches the best second order bounds for linear bandits, and our changing variance results match the best results for linear bandits up to a factor $\sqrt{d}$ where $d$ equals the eluder dimension of the class. As for the comparison with second order algorithms for function approximation, there are no previous second order algorithms for general function approximation that do not assume the noise process can be fully learned, an assumption that is very strong in our opinion. Our fixed variance result matches the best second order bounds for function approximation even with this stronger assumption, and our changing variance results qualitatively match the best results under noise realizability up to a factor $\sqrt{d}$ where $d$ equals the eluder dimension of the class. Nonetheless, we argue these results are incomparable since, results with noise realizability depend on an eluder dimension that captures the complexity of the noise process, something that could be much much larger than the eluder dimension of the mean rewards function class that we depend on. We agree with this. It is an interesting question how to get around these intractability issues. That being said, we consider our contribution to be conceptual and theoretical and still believe that it can unlock a plethora of research questions along the way, including how to make these algorithms tractable.

We are very happy to see the reviewer agrees our work is novel, tackles an interesting problem and does so convincingly. Regardless, we want to reiterate our contributions. In this work we introduce algorithms for regret minimization of variance aware contextual bandits with function approximation. We solve this problem for two different settings, first the scenario where the noise variance is uniform and equal to a value $\sigma^2$ during all rounds. In this case we show our algorithm (algorithm 1) achieves a regret rate scaling as $\sigma\sqrt{ d \log(F) T} + d\log(F)$ where $d$ is the eluder dimension and $\log(F)$ is the logarithm of the size of the reward function class. This result nails down the complexity of variance aware contextual bandits in the function approximation regime and generalizes existing results in that space that could only prove bounds for linear problems. At the time of submission ours was the first algorithm achieving this type of result. When the variances are unknown and changing at all time steps we achieve a regret bound of order $d \sqrt{ \sum_{t=1}^T \sigma_t^2 \log(F)} + d\log(F)$ (notice the $\sqrt{d}$ degradation with respect to the uniform variance result). This result also recovers and generalizes existing results that deal only with linear problems. The main difficulty in obtaining our results was to generalize the linear techniques to deal with general function approximation.

We address the reviewer’s “weaknesses” comments now.

[1. and 2.] As the reviewer has noticed, one of the main issues and why this generalization is not straightforward is that in linear problems it is possible to make use of weighted least squares objectives to derive variance aware results, while in the function approximation case, and due to the definition of eluder dimension, the weighted regression techniques of [Zhao et al 2023] are not viable. In the fixed variance case, we can overcome this problem by developing a sharp version of the eluder bound on the widths, (see Lemma 3.3 and its proof in the Appendix). This is one of our main contributions and what allows us to obtain a sharp bound that matches linear results even without using weighted regression. In the changing variances case, developing a sharp version of this lemma where the $1/\tau^2$ term depends on the changing variances is much more challenging, so we had instead to rely on Lemma 4.9 where instead we trade off the square dependence on $1/\tau^2$ for a $1/\tau$ that is instead multiplied with $\sqrt{\sum_{\ell}\sigma_\ell^2}$. We think there might exist a way to shave off the extra factor of $\sqrt{d}$ in our bounds. This is an exciting open problem. We really like the reviewer’s suggestion of adding comments detailing the technical challenges here.

[3.] Thanks a lot for the question. We would like to respectfully push back against the reviewer’s comment. The changing variance scenario is a precursor to the MDP case. In that case, the policy played is changing at all time-steps and therefore the variance of the policy played depends on it. We believe the techniques we have developed in this work can be further developed to derive variance dependent bounds for RL with function approximation.

We are very happy to see the reviewer agrees our work is novel, tackles an interesting problem and does so convincingly. Regardless, we want to reiterate our contributions. In this work we introduce algorithms for regret minimization of variance aware contextual bandits with function approximation. We solve this problem for two different settings, first the scenario where the noise variance is uniform and equal to a value $\sigma^2$ during all rounds. In this case we show our algorithm (algorithm 1) achieves a regret rate scaling as $\sigma\sqrt{ d \log(F) T} + d\log(F)$ where $d$ is the eluder dimension and $\log(F)$ is the logarithm of the size of the reward function class. This result nails down the complexity of variance aware contextual bandits in the function approximation regime and generalizes existing results in that space that could only prove bounds for linear problems. At the time of submission ours was the first algorithm achieving this type of result. When the variances are unknown and changing at all time steps we achieve a regret bound of order $d \sqrt{ \sum_{t=1}^T \sigma_t^2 \log(F)} + d\log(F)$ (notice the $\sqrt{d}$ degradation with respect to the uniform variance result). This result also recovers and generalizes existing results that deal only with linear problems. The main difficulty in obtaining our results was to generalize the linear techniques to deal with general function approximation. One of the main issues there being that in linear problems it is possible to make use of weighted least squares objectives to derive variance aware results, while in the function approximation case, and due to the definition of eluder dimension, weighted regression is not a viable technique.

Although we sympathize with the reviewer’s request for empirical evaluations, we want to emphasize that we consider the main contribution of our work to be conceptual / theoretical. In this case for example, the hard computational nature of algorithms for function approximation based on the principle of optimism is well known by the statistical learning community It would be a pity to reject a work because it is theory-intensive, particularly given that the reviewer seems to agree our results are novel, correct and meaningful. We are happy to rebut any valid criticism of our theoretical results based on their relationship to other relevant works in the field of statistical learning theory. If the reviewer has any such criticism we are more than happy to provide an answer. That being said, we will make sure the final version of our manuscript is friendlier to the reader than the current one. Any concrete actions the reviewer thinks we should take that do not compromise the quality and formality of our results will be highly appreciated. We also very much agree that it is an important question how to use these ideas to design second order algorithms that can be used empirically.

We are confused by the reviewers comment of the lack of comparison with prior work. We describe several related works in this area in our introductory section (see for example lines 77 to 105). As the reviewer rightly points out, ours is the first work to deal with second order bounds in the function approximation regime and thus, there is no previous work that works on the exact same problem. That being said, we mention a plethora of related linear works from the literature that had a strong influence in our work. If the reviewer has a specific work in mind we should compare to we would be really happy to include it.

To our knowledge, at the time of submission, the only work that dealt with the function approximation regime in second order bounds is [Wang 2024a,b]. We discuss in detail a comparison with that work in the introductory section. As the reviewer identified, we provide several improvements over their results, chief among them having no need for the measurement noise distribution to be learnable, something that we consider a very limiting assumption from [Wang 2024a,b].

In this work we introduce algorithms for regret minimization of variance aware contextual bandits with function approximation. We solve this problem for two different settings, first the scenario where the noise variance is uniform and equal to a value $\sigma^2$ during all rounds. In this case we show our algorithm (algorithm 1) achieves a regret rate scaling as $\sigma\sqrt{ d \log(F) T} + d\log(F)$ where $d$ is the eluder dimension and $\log(F)$ is the logarithm of the size of the reward function class. This result nails down the complexity of variance aware contextual bandits in the function approximation regime and generalizes existing results in that space that could only prove bounds for linear problems. At the time of submission ours was the first algorithm achieving this type of result. When the variances are unknown and changing at all time steps we achieve a regret bound of order $d \sqrt{ \sum_{t=1}^T \sigma_t^2 \log(F)} + d\log(F)$ (notice the $\sqrt{d}$ degradation with respect to the uniform variance result). This result also recovers and generalizes existing results that deal only with linear problems. The main difficulty in obtaining our results was to generalize the linear techniques to deal with general function approximation. One of the main issues there being that in linear problems it is possible to make use of weighted least squares objectives to derive variance aware results, while in the function approximation case, and due to the definition of eluder dimension, weighted regression is not a viable technique.

One of our contributions is precisely the methods we develop for estimation of the variances up to constant accuracy in the case where the variances change at every time-step. As it is well explained in section 4.1 of the main paper, this can be done by considering . This is one of the contributions of our work.

The terms mentioned by the reviewer are defined in the main paper, as a careful reading of our submission would indicate, for example $G_t’$ is defined in line 6 of algorithm 2. Tilde($E_t’$) is a self contained object from Proposition 4.7. Our manuscript also clearly states that the results of section 4.3 pertain to the setting where the variance is unknown but constant for all rounds. Similarly, the results of section 4.3 pertain to the setting where the variances are changing at each step. We disagree about moving the $\sigma_t= \sigma$ case to the appendix as this is one of our main results. Notice that this case has a regret bound with a better $d_{eluder}$ dependence than the changing variance scenario. We do appreciate the reviewer’s comments regarding organization and we will take these into account while making the final version of our manuscript.

Thanks for catching these typos! We will change these in the final version.

We hope the reviewer considers increasing their score if this response addressed the concerns.

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.