How Does Variance Shape the Regret in Contextual Bandits?

Thank you very much for providing these useful feedback and questions.

Weakness:

• Unclear related work.

We will improve the related work section based on the suggestion.

• Difference between the three settings.

The separation between strong and weak adversary is different from that between oblivious and adaptive adversary. The terms 'strong' and 'weak' come from literature studying adversarial corruption in contextual bandits (e.g., He et al., 2022). In our case, 'strong adversary' decides the variance after seeing the decision of the learner, while 'weak adversary' decides it before. The separation between 'function class' and `model class' has been studied in previous works like [Wang et al., 2024]. The latter provides the full distributional information given context and decision, while the former only the mean.

[He et al., 2022] Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptions.

The most interesting case is strong adversary + learning from function class.

We argue that weak adversary and learning from model class are also of interest. In particular, as we showed, against weak adversary, one may obtain a better regret bound. Also, with a model class, the learner is able to generalize the learned knowledge beyond the 'mean' domain, which is the main consideration in the field of 'distributional RL.' The benefit of learning with a model class is also discussed in, e.g., [Wang et al., 2023, 2024].

• Why the eluder dimension is necessary in all the bounds?

Some intuition has been mentioned in Line 41-54. While in the non-contextual case (e.g., multi-armed bandits), eluder dimension is not necessary, it is necessary in the contextual case as we showed. Consider the case where the function set size |F| >> 2 and the action number A=2. Suppose that the ground truth function $f^\star$ always chooses the better action under every context. Every time, the adversary chooses the context so that one of the functions choose an action that disagrees with all other $|F|-1$ functions' choices. This way, to figure out $f^\star$, the regret must scale with some ``disagreement coefficient'' of $|F|$, instead of just $A$. The eluder dimension takes the role of the disagreement coefficient.

• Running time O(|F|) not discussed.

We will clarify this in our revision. Indeed, in this work, we only focus on the statistical complexity but not the computational complexity.

• Comments left inside the paper. Additional example: line 185 "(our contribution)".

We are sorry for the mistake. The label ``(our contribution)'' is actually not a mistake. It refers to the equation right below Line 179.

• The use of the Hellinger-Eluder dimension is given without any justification or an appropriate citation of previous works. The classic Eluder dimension introduced by Russo and Van-Roy is defined with respect to the norm only. If the authors are using other versions of it, they have to cite related work, if such exists, or justify the used guarantees themselves. In this case, [1] presents a version of the Eluder dimension to bounded metrics, that also holds to the squared Hellinger distance.

The use of the Hellinger-Eluder dimension is given without any justification or an appropriate citation of previous works. The classic Eluder dimension introduced by Russo and Van-Roy is defined with respect to the $\ell_2$norm only. If the authors are using other versions of it, they have to cite related work, if such exists, or justify the used guarantees themselves. In this case, [1] presents a version of the Eluder dimension to bounded metrics, that also holds to the squared Hellinger distance.

Thanks for bringing to our attention the missing citation. Our motivation is the same as [1] to generalize the eluder dimension to general divergence.

[1] Eluder-based regret for stochastic contextual MDPs, Levy et al. 2024.

Question:

• Please provide a specific comparison of your results with the known variance-dependent bounds in previous literature.

Previous work on variance-dependent contextual bandits mostly focused on linear contextual bandits (see Zhao et al., 2023 and the related work therein). Literature on variance-dependent contextual bandits with general function approximation is scarce. [Wang et al., 2024] studied the setting same as our Section 6. Their result is listed in our Table 1. While they conjectured that their bound could be improved, we disproved it by showing a matching lower bound. The work of [Wei et al., 2020] also investigated second-order bounds for contextual bandits, but they focused on the agnostic setting (while we focused on the realizable setting). Though their algorithm can be applied to our setting, the regret is highly sub-optimal. In general, their result is incomparable to ours.

• What does $d_{\mathrm{elu}}(0)$ mean?

In fact, $d_{\mathrm{elu}}(\alpha)$ remains meaningful when $\alpha=0$ (see our Definition 2.1, and simply set $\alpha=0$). For example, a $d$-dimensional linear function class has $d_{\mathrm{elu}}(0)=d$.

I thank the authors for their response. Not sure I understand their response related to the question about $d_{eluder}(0)$. As far as I understand the Eluder dimension, $\alpha$ should be an error parameter. Are you using $1-\alpha$? Would be happy if the authors could elaborate more. Besides that I have no further questions.

• Can the authors summarize the main technical novelty used in the paper?

We have the following technical contributions.

1. Algorithm design through checking disagreement: Our algorithms in Sec 4 and Sec 6 decide whether to use inverse gap weighting based on the degree of disagreement in the function confidence set. Such a design is, to our knowledge, crucial to obtain the tight bound and not seen in previous work. The analysis framework for this algorithm is also new.

2. Refined online regression oracle: The choice of the online regression oracle (i.e., Prod) in Sec 4 and its associated analysis are non-trivial. The usefulness of such an online regression oracle has not been discovered before.

3. In Sec 6, we adapt the inverse-gap weighting technique to learning from model class. This was mentioned as a future work by [Wang et al., 2024]. In this case, we identified the Gaussian-noise condition under which tight bound can be obtained without revealing variance. We believe this is an important step towards resolving the general case.

4. In Sec 6, we identify the important difference between the achievable bounds using $\sum_{t=1}^T \sigma(x_t,a_t)^2$ and $\sum_{t=1}^T \max_a \sigma(x_t,a)^2$ as the total variance measure. This answers the open questions in [Wang et al., 2024]. Similarly, in Sec 4 and 5, we identify the difference between the achievable bounds under strong and weak adversary.

• Concerning the third case, learning with the model class, the authors indicate that the variance information is not required as input in line 105. Does it mean that the variance, given the model, the context and the action, the variance $\sigma_{M_t}^2(x_t,a)$ is revealed, as presented in line 7 in Algorithm 3?

Yes, the variance will be revealed.

• If we only assume that the variance is unknown but it only depends on the context and the arm, can the algorithm be modified such that it can work with estimating the variance on the fly, like [1]?

It would be hard to estimate in general. For instance, if the context space is super huge and no context is repeated twice, then since there is no model class, then there is no way to generalize the variance information since each time, the variance can be arbitrary. So, estimation of the variance on the fly is not possible. On the other hand, if the context space is small, estimating the variance might be possible, but we suspect that would render the regret bound depending on the size of the context space.

• The lower bound result Theorem 6.2 is obtained via instances with the same variance. While the lower bound is indeed a minimax lower bound, as this paper is considering the role of the variance, is it possible to derive a lower bound for the case where the variances are heterogeneous?

Thanks for your suggestion. Our lower bounds can be adapted to any collection of variances (with no ordering) through the following trick. The idea is that for any given collection of variance, we can divide the variances with doubling scales into $\log T$ categories. For the scale with the largest cumulative variance, we put the variances of this scale to all appear first and apply our lower bound to these steps. By pigeonhole principle, our lower bound is worsened by a rate of at most $\log T$. Currently, our lower bounds do not extend to cases where the sequence of variance is given. It is an interesting direction for future research.

[1] Jourdan, M., Rémy, D., & Emilie, K. Dealing with unknown variances in best-arm identification. International Conference on Algorithmic Learning Theory. PMLR. 2023.

Thanks for the feedback. First, we agree that the assumption in Section 4 that variance being revealed is not ideal, and our ultimate goal is to remove it (some initial attempts have been made in Appendix G). At the current stage, however, this assumption is necessary for our technique, and we hope that the our technique could inspire future work that obtains variance-agnostic result.

Still, there are cases where the learner is able to obtain variance information / variance estimation before making decisions, and the use of our algorithm can be justified.

For example, our algorithm works well for the case where the variance is upper bounded by a fixed quantity in all rounds, and the variance is much smaller than the reward range. This could simulate recommendation systems where the reward comes from user rating. Let's say the range of the rating is 0 to 10, but the user feedback has some noise and it is modeled to be within (mean - 1.5, mean + 1.5). In this case, the sigma in our algorithm can be chosen as 3/10, which significantly improve the existing regret bound by variance-unaware algorithms (e.g., SquareCB).

It is also possible that the learner can perform context-aware variance estimation, and plug it into our algorithm. For example, in clinical trials, the context may include information like the type of the drug and the age of the patient. We could create a finite number of categories for these contexts, and estimate the variance for each of them using historical data. This way, we can obtain variance estimation for given contexts before making decisions, and then apply our algorithm.

Thank you very much for providing these useful feedback and questions.

Answers to Weaknesses:

• The main weakness is that the only upper bound results matching the lower bounds require some knowledge of the variance at every single round or under a stronger model class assumption (which then involves picking up a dependence on the size of the model class of variances).

We obtained matched upper bound and lower bound for the variance-aware cases in our paper. For agnostic variance cases, we have both upper bound and lower bound with only a factor of $\sqrt{d_{\mathrm{elu}}}$ between them. Even with this gap, the dependence over the variances $\sqrt{\sum_{t=1}^T \sigma_t^2}$ is tight, and our bounds are sufficient to show the separation between variance aware and agnostic variance cases.

• There could be more discussion of other function classes beyond the generic finite regressor class . For instance, how do the lower bounds and results here about variance-based bounds and Eluder dimension compare with the understanding for linear function classes, high-dimensional classes (like those mentioned for SquareCB in Foster and Rakhlin, 2020), neural network, or non-parametric classes? Do the lower bounds hold in greater generality?

Even though we did not discuss about infinite function class in our paper. But our algorithms and theoretical guarantee can generalize to infinite function classes. For example, for linear classes, using the similar structure of Algorithm 1 in our paper and some proper regression oracle for linear class similar as the one in Foster and Rakhlin (2021), we can obtain an upper bound of $\tilde{\mathcal{O}}(\sqrt{dA\sum_{t=1}^T\sigma_t^2})$. For generalized linear classes, we can get an upper bound of $\tilde{\mathcal{O}}(\sqrt{T\sum_{t=1}^T\sigma_t^2})$. And for other classes including neural networks and nonparametric class, we can get similar variance-dependent bound as long as there are some proper variance-aware regression oracles.

As for the lower bound part, since our lower bound is constructive, i.e. we show that there exists a function class $F$ which achieves the lower bound, we do not know how we can generalize our results to other function classes. But to obtain an instance-dependent lower bound for all possible function class is an interesting future research direction.

Thank you very much for providing these useful feedback and questions.

Answers to Weaknesses:

• Mismatch upper and lower bound for large action space cases

We have such results for cases where $d_{\mathrm{elu}} < A$ (an upper bound $\tilde{\mathcal{O}}(d_{\mathrm{elu}}\sqrt{T\sigma^2\log|\mathcal{F}|})$). Please view Theorem 5.2 in our paper for more details. We admit that this upper bound does not match the provided lower bounds, and we will change our presentation accordingly in the next version.

• Some missing related works. More works on variance-dependent results of heteroscedastic bandits:

Thanks for pointing out these related references. We will add them in the next version of our paper.

• This description of "checking disagreement" (Line 166) is not very accurate. A similar definition of equation (4) has been used in previous works as weights ([4] [5]), bonus functions ([6][7]), and selection rules ([8][9]). I suggest adding more discussions on this.

Here 'check agreement' means checking whether there exists an action where two functions in the function set deviated a lot. Thanks for pointing out these references. We will add them in the next version of our paper.

• Some minor errors: Line 12 worst case over what?

These are words meant to be deleted. We will delete them in our next version.

Answers to Questions:

• Is it possible to prove a variance-dependent upper bound with dependence in the first term of Theorem 4.2?

Yes, we can obtain such an upper bound: $\tilde{\mathcal{O}}(d_{\mathrm{elu}}\sqrt{T\sigma^2\log|\mathcal{F}|})$, which serves as a special case of Theorem 5.2 in our paper.

• What difficulty did you meet when trying to recover Zhao et al. (2023)’s result for unknown variance?

The main difficulty we met is that we are dealing with bandit with function approximation in our paper, compared to the setting of linear bandit in Zhao et al. (2023). Technically, to prove our results, we are required to apply the general Freedman's inequality, rather than the Freedman's inequality specialized for linear setting.