High Probability Bound for Cross-Learning Contextual Bandits with Unknown Context Distributions

Dear review McaC:

Thank you for your positive feedback. We answer your question below.

---

Question: The line 319 seems overfull

Thanks for pointing this out. We will fix it in the new version.

---

Question: whether this analysis approach can be applied to other bandit algorithms

This is an good question. We believe that this analysis could potentially be applied to other algorithms that have an epoch-based execution structure and have weakly dependent structures between epochs. We will further investigate this question in future research.

---

Once again, we sincerely thank you for your positive review. We hope our response addresses your concern.

Dear Reviewer m6dx,

Thank you for your positive feedback. We answer your question below.

---

Question: the novelty and the broader impact

The reviewer questioned the novelty of our work, particularly noting that our contribution appears to be “only the analysis.” We would like to clarify this point. First, in the field of adversarial bandit research, providing a high-probability bound alone is often regarded as a substantial contribution. Second, we respectfully argue that enhancing the results of an existing algorithm through novel analysis—achieving the same outcome with a simpler approach—can, in a certain sense, be considered an advantage over proposing a more complex algorithm. Finally, our work demonstrates technical novelty, as decomposing regret by epochs is a relatively uncommon approach in high-probability bound studies.

Regarding the broader impact of our work, the reviewer asked, “Are those techniques useful in other settings?” This is an excellent question and aligns with the direction we aim to explore next. We believe our techniques could be beneficial to other algorithms that involve epoch-based subroutine and exhibit weakly dependent relationships between epochs. We are committed to further investigating this question.

---

Once again, we sincerely thank you for your positive review. We hope our response addresses your concern.

Dear Reviewer JF8C,

Thank you for your positive feedback. We answer your question below.

---

Question: the significance of this term $\sum \sum Pr(c) <\pi_c, \tilde{l} _{t, c} - l_{t, c} >$

To achieve a high-probability bound, saving this term is essential. In Schneider & Zimmert (2023), this term is not saved. Thus they need to bound the term $\sum\sum Pr(c) < \pi_c, \hat{l}_{t, c} - \tilde{l}_{t, c} >$ (implicitly in their $\text{bias}_2$ term). As a result, their approach yields a bound in expectation only. In our work, saving the term $\sum \sum Pr(c) < \pi_c, \tilde{l}_{t, c} - l_{t, c} >$ allows us to counteract the random deviation, thereby strengthening the expectation bound into a high-probability bound.

---

Once again, we sincerely thank you for your positive review. We hope our response addresses your concern.

Dear Reviewer Kzo3,

We sincerely appreciate your valuable suggestions and thoughtful feedback. Below, we address each of your concerns in detail.

---

Question: The impact of our results on the theoretical community

The reviewer noted that “the result seems to be a specific treatment to a specific algorithm and seems to be incremental.” We respectfully disagree with this assessment. We would like to emphasize that in the field of adversarial bandit research, providing high-probability bounds is a widely recognized and significant contribution in its own right (e.g., [1, 2, 3]). From a technical perspective, our argument for the high-probability bound is novel. Specifically, we decompose the regret across different epochs and leverage the weakly dependent structures between these epochs—a method that, to the best of our knowledge, is not commonly employed in existing high-probability bounds for adversarial bandits.

---

Question: the suggestion for empirical verification on realistic datasets

We thank the reviewer for raising this point, as it highlights an opportunity to strengthen our work. In response, we will include experimental data in the revised version of the paper to reinforce the need for a deeper theoretical understanding and to complement our theoretical findings.

---

Question: the mathematical definition of cross-learning in Section 2 [110R]

We are grateful to the reviewer for pointing out this oversight. While we provided an explanation of cross-learning in [122R], we acknowledge that a clearer presentation is warranted. Based on your suggestion, we will introduce a standalone definition of cross-learning in the revised version to ensure this concept is explicitly and effectively conveyed.

---

Question: What is the mathematical meaning of "weakly dependent" [110R]? Where is it used in the derivation (which inequality in the appendix)?

"Weakly dependent" is an informal term commonly used in the context of concentration inequalities([4]). It generally refers to a sequence of random variables $X_i$ that, while not fully independent, forms a martingale, allowing us to derive concentration inequalities akin to those for independent random variables. In our work, it means that we can decompose the regret into epochs and the regrets of different epochs form an martingale sequence.

This property is utilized wherever epoch-based decomposition appears in our proofs. For example, it is applied in bounding $\sum_e \text{Bias5}_e$ in Appendix B.2 and $\sum_e \text{Bias4}_e$ in Appendix B.3.

---

Once again, we express our gratitude to the reviewer for their insightful and valuable feedback. These comments have greatly assisted us in refining the presentation of our paper and better articulating its contributions. We hope that our responses adequately address your concerns and that you will consider increasing your support for our work in light of these revisions.

---

References:

[1] Luo, H., Tong, H., Zhang, M., & Zhang, Y. (2022). Improved High-Probability Regret for Adversarial Bandits with Time-Varying Feedback Graphs. International Conference on Algorithmic Learning Theory.

[2] Neu, G. (2015). Explore no more: Improved high-probability regret bounds for non-stochastic bandits. Neural Information Processing Systems.

[3] Bartlett, P.L., Dani, V., Hayes, T.P., Kakade, S.M., Rakhlin, A., & Tewari, A. (2008). High-Probability Regret Bounds for Bandit Online Linear Optimization. Annual Conference Computational Learning Theory.

[4] Pelekis, C., & Ramon, J. (2015). Hoeffding's inequality for sums of weakly dependent random variables. arXiv: Probability.