Contextual Bandits for Unbounded Context Distributions

Thanks the reviewer for your careful reading of this paper!

We respond to your comments as follows.

1. We have read the paper you have mentioned: Self-Tuning Bandits over Unknown Covariate-Shifts. In ICALT. We think that this paper is indeed highly relevant, so we will compare it with our paper in our revised version.

2. Assumption 1(a): here $X$ is a random variable, instead of a fixed value. The randomness in probability $P(0<\eta^*(X)-\eta_a(X)<u)$ also comes from the randomness in X, Therefore, we do not need "for all x\in \mathcal{X}".

3. Assumption 1(b)：Thanks for these two comments. $W_i$ should be $W_t$, and $\lambda \in \mathbb{R}$ needs to be mentioned.

4. Line 158: $c$ is some constant. We will clarify it.

5. Line 296 right: Yes, $x$ should be bold

6. Line 259 right: This notation comes from Guan et al. 2018. We will clarify the meaning of this notation.

7. Remark 2: $N$ is the number of samples for nonparametric classification with i.i.d samples. We will clarify it.

8. (92): Yes, it should be $T^{2d+2}$, instead of $T(2d+2)$.

9. Lemma 5,6 and 12: Thanks. We will clarify them.

Question 1: About assumption 3(b)

This is not common in previous literatures, since existing works only discuss bounded context support. We think you have raised a very good question. It is indeed a bit counterintuitive that we need small suboptimal gap $\Delta_a$. For unbounded context support, there exists some region with very low density $f(\mathbf{x})$, such that even if the suboptimal gap is large, we still can not identify the optimal action. Therefore, noting that the regret is upper bounded by the suboptimal gap, instead of trying to identify the optimal action, now we give an upper bound of the suboptimal gap, so that the regret (with unidentified optimal action) can be controlled. This is an important distinction between bounded and unbounded context support. For bounded support, since the density is lower bounded (Assumption 2: $f(\mathbf{x})\geq c$), we hope that suboptimal gap is as large as possible. However, for unbounded case, things become more complex and large suboptimal gap does not always make the problem easier.

Question2: Novelty

The main novelty is the treatment of tails. The proof of theorem 2 is novel, as it requires treatment of heavy tails.

In Appendix B, the "expected sample density" has not been proposed by existing analysis.

Lemma 5,6,7,8 and Appendix E are entirely new.

We guess that some lemmas (such as Lemma 4) appears to be similar to existing works, which leaves an impression that the proof is simple and standard. However, these lemmas are tools that are required for the completeness of analysis. For all other parts of our theoretical analysis, different techniques are used.

The main technical challenge is to achieve both exploration-exploitation tradeoff and bias-variance tradeoff. In bounded context space, one only needs to achieve the former one.

Thank you very much for your positive feedback on the importance and novelty of this paper. We reply to questions as follows.

1. $C_\alpha$ is a constant. In eq.(38), $K$ has $h^{d-\alpha}$ dependence. Throughout the paper, $C_\alpha$ remains a constant.

2. Thanks for the suggestion. We think that all our results hold for intrinsic dimension $d$. This means that even though the overall dimensionality is significantly larger than $d$, the result in all theorems in the paper still hold.

In our revised paper, we will polish the proof further and provide more necessary intuition and explanation.

Thanks for your review. We are encouraged that you agree that our claims are all clear and proved.

Regarding the novelty of algorithm. We disagree that "the authors merely restate how the parameter $k$ is chosen". For our adaptive method, we select $k$ according to eq.(16). For Reeve et al. (2018), $k$ is selected in Algorithm 1, in particular, in step 2(b). The UCB is defined in the page before Algorithm 1, with $\phi(t)$ not fully determined. As can be observed from our paper and Reeve et al.'s paper, the selection rule is quite different: we select $k$ as the maximum one that satisfies $L\rho_{a,t,j}(x)\leq \sqrt{\ln T/j}$, while Reeve et al.'s paper select $k$ by minimizing a new defined UCB. The UCB calculations are also different: we calculate UCB in eq.(17) in our paper, which is also different from Reeve et al.'s paper, in the equation before Algorithm 1.

However, we do think that the question (about anything that prevents the algorithm in Reeve et al. from being used in unbounded context) raised by the reviewer is very valuable. Actually, if we only consider implementation, without considering the theoretical bounds, then the algorithm can indeed be applied into unbounded contexts. However, the convergence rate is not analyzed right now, and we believe that it will be much more complex than our method. It is unknown whether the method proposed in Reeve et al. will match the lower bound. Therefore, to the best of our knowledge, our work is still the first one to establish the minimax lower bound of contextual bandits with unbounded contexts, and provide algorithms with matching upper bounds.

In addition, although less important, we would like to mention that our selection of $k$ requires $O(\ln T)$ time, while Reeve et al's method requires $O(T)$ time. Therefore we also have advantages in time complexity.

Thank you very much for acknowledging the writing of this paper. We respond to questions and weaknesses as follows.

1. Importance of unbounded context distribution

The bounded action space can be easily generalized to unbounded action space (assuming continuous action space). Unbounded action space does not involve too much additional technical difficulties.

However, generalizing bounded context distribution to unbounded one is significantly different. We strongly agree with your comment " I think the setting of unbounded context set would be of special importance either if the bounded setting and the unbounded setting are fundamentally different by some obvious intuitions, or if the practical results of unbounded context set departs too much from the theory about bounded context set." We think that these two reasons both hold.

(1) Fundamental difference by intuition. In bounded context space, we only need to achieve a tradeoff between exploration and exploitation. However, with unbounded context space, since the sample density is crucially different in different regions, we need to also achieve a better tradeoff between bias and variance. As emphasized in the abstract and introduction, the challenge is to achieve both exploration-exploitation tradeoff and bias-variance tradeoff simultaneously. This problem does not exist for bounded context space.

(2) Difference in practical results. We refer to Theorem 6. The bounded context case corresponds to Theorem 6 with $\beta \rightarrow \infty$, which yields a $O(T^{1-\frac{\alpha+1}{d+2}})$ regret. As long as $\beta$ is not infinite, the regret bound is clearly different from the bounded context case. In particular, with $\beta<1/(d+2)$, the difference is more significant as the main cause of regret comes from the tail, instead of exploration.

2. Whether the size of action set is treated as constant

It is common to treat size of action set in related works. See the following results as examples:

Shah, Devavrat, and Qiaomin Xie. "Q-learning with nearest neighbors." Advances in Neural Information Processing Systems 31 (2018).

Zhao, Puning, and Lifeng Lai. "Minimax optimal q learning with nearest neighbors." IEEE Transactions on Information Theory (2024).

3. Interpretation of phase transition in Theorem 3

As discussed in the response of weaknesses 1, in unbounded state space, we need to achieve both exploration-exploitation tradeoff and bias-variance tradeoff. Fixed $k$ method fails to achieve the latter one, as in heavy-tailed contexts, bias-variance tradeoff is more complicated and smaller $k$ may be necessary.

This result further explains the importance of studying unbounded context supports. At first glance, one may think that it is simple to generalize fixed k method to unbounded context, but our analysis show that such method is no longer optimal. We need to find new method to achieve minimax optimal regret.