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

Dear reviewer 8LjP:

We sincerely thank the reviewer for their suggestions and positive feedback. Below, we provide detailed responses to the reviewer’s comments.

Question: What is the reason for assuming a finite concept class?

Response:
We would like to point out that assuming a finite concept class is a common practice in contextual bandit research. While the real context space is often continuous, it can be discretized into a finite set. In this way, the finite concept class serves as a foundational model, much like the tabular MDP framework in reinforcement learning.

Of course, the discretization process involves a tradeoff: finer discretization reduces discretization error but increases the size of the concept class, leading to larger regret. However, the cross-learning structure in our setting entirely eliminates this issue, providing further justification for focusing on finite concept classes. Please see our response to the next question for more details.

Question: Where is the variable in Theorem 1 that characterizes the property of $C$?

Response:
We thank the reviewer for raising this excellent question, which touches on one of the most interesting aspects of cross-learning bandits. Indeed, in most cases, the results depend on the size of the concept class. In the vanilla contextual bandit setting, the results typically have a polynomial dependence on the size of the concept class $C$.

However, in our problem, thanks to the cross-learning structure, this polynomial dependence on the size of $C$ is entirely eliminated. As a result, our final regret bound is completely independent of the size of $C$, which is why Theorem 1 does not need to explicitly characterize the property of $C$.

As mentioned in the response to the previous question, the cross-learning structure allows us to bypass the discretization issue for finite concept classes. This is because our result is completely independent of the size of the concept class, enabling arbitrarily fine discretization and resolving this concern entirely.

Question: The statement in line 111 that we can observe the loss for every context seems confusing and does not match the behavior of the algorithm.

Response:
We would like to clarify that this is precisely the core of the cross-learning structure. The cross-learning structure explicitly assumes that we can observe the loss for every context. As discussed in the related works section, this structure is common in practice, with examples including bidding in online auctions, sleeping bandits, repeated Bayesian games, and dynamic pricing.

Regarding the algorithm’s behavior, we respectfully disagree with the reviewer’s assessment. The algorithm indeed matches this assumption since it is explicitly designed for the cross-learning structure.

Question: Readability of Section 3.2

Response:
We thank the reviewer for pointing this out. To improve readability, we have restructured the paper. In the revised version, Section 3.2 has been expanded into a standalone chapter, further divided into three subsections, each focusing on a single topic. This restructuring aims to make the paper more organized and easier to follow. The updated manuscript will be uploaded shortly.

We once again thank the reviewer for their valuable suggestions and positive feedback. Your comments have helped us improve the structure and readability of our paper. We hope our responses have addressed your concerns.

Dear Reviewer uDyz,

Thank you for your positive and encouraging feedback. We greatly appreciate you bringing to our attention an interesting piece of work that we had previously overlooked—it has truly broadened our perspective.

Unfortunately, the mentioned work cannot be directly applied to our problem. However, whether it could be adapted through certain modifications to address our problem is an intriguing question. We have discussed this point in detail in the related works section of the revised version of our paper, which will be uploaded shortly.

Once again, we sincerely thank you for your positive comments and for pointing out this valuable reference.

Dear reviewer NZtQ:

We sincerely thank the reviewer for their valuable suggestions. Below, we address the reviewer’s concerns in detail.

Question: Significance of our results

Response:
We appreciate the reviewer’s accurate understanding of our results and their concerns about our work's significance. We would like to highlight that it is a common practice in adversarial bandit research to focus solely on providing high-probability bounds, as this itself constitutes a significant contribution (e.g., [1,2,3]).

From a technical perspective, as noted by reviewer Sstz, deriving high-probability bounds for existing algorithms in bandit research often requires neat observations and techniques. From a results perspective, high-probability bounds are particularly important in adversarial bandit settings because these scenarios focus on worst-case outcomes, where even low-probability events cannot be ignored. Thus, providing high-probability bounds, rather than just expected regret bounds, is critical for addressing the worst-case nature of adversarial bandits.

Regarding the lack of experiments, we acknowledge that this is a limitation. However, we respectfully note that in theoretical works on adversarial bandits, especially those focusing on high-probability bounds, it is common practice to omit experiments. This is because our proofs are based on rigorous mathematical arguments without relying on any unrealistic assumptions or approximations, and they remain effective under worst-case scenarios. We hope the reviewer will consider this aspect.

To further emphasize our contributions, we have restructured the paper and added a Technical Overview section in the introduction to discuss our technical contributions in detail. The revised version of the manuscript will be uploaded shortly.

Once again, we thank the reviewer for their insightful suggestions, which have helped us improve the structure of our paper and better highlight its contributions. We hope our response has addressed the reviewer’s concerns and that you will consider increasing your support for the paper.

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.

Dear Reviewer NZtQ,

We sincerely appreciate your time and attention. We hope our responses have addressed your concerns and that you might consider increasing your support for our paper. If you have any further questions, please don't hesitate to ask us!

Dear Reviewer Sstz,

Thank you for your positive, thorough, and thoughtful review. Your feedback has greatly helped us improve our paper. Below, we provide detailed responses to your comments:

Question: Should the definition of regret on page 3 be reversed?

Response:
We respectfully point out that our definition is correct. Our regret definition subtracts the loss of the arm chosen by the algorithm from the loss of policy $\pi$, rather than subtracting the loss of the best arm from the loss of a policy. This ensures that the regret is typically non-negative.

Question: Suggestions on improving the writing of the paper

You suggested that we describe the algorithm earlier, state the main theorem outside the preliminaries, and explicitly explain the meaning of high probability.

Response:
We greatly appreciate your detailed suggestions regarding the paper's structure and presentation, as they are immensely helpful for improving the clarity of our writing. We have carefully considered your suggestions and revised the manuscript as follows:

1. Reorganized the algorithm description:
   The algorithm description is now a standalone section, divided into two subsections. The first subsection revises Section 2.2 of the original paper to explain the intuition behind the algorithm. The second subsection revises Section 3.1 of the original paper to formally describe the algorithm.

2. Moved the theorem statement out of the preliminaries:
   In the revised manuscript, we move the theorem statement out from the preliminaries. Instead, we provide an informal version of the theorem in the Introduction section for early context, and provide the formal version of the theorem in the Main Result and Analysis section.

3. Clarified the meaning of high probability:
   We restructured the theorem's statement to explicitly define the high-probability guarantee. Specifically, our high-probability result means that, for any probability parameter $\delta \in (0,1)$, the algorithm achieves a regret bound with probability at least $1 - \delta$, where the bound depends on $\delta$ only in the form of $\log(1/\delta)$.

The revised manuscript incorporating these changes will be uploaded shortly.

Once again, we sincerely thank you for your positive, thorough, and thoughtful review. Your suggestions have significantly improved the structure and readability of our paper. We hope our response addresses your concerns.

Dear reviewer NaxM:

Thank you for your valuable feedback. We address the comments below in detail:

Question 1: Lack of explanation of the algorithm

The reviewer suggested that we proposed an algorithm, but did not elaborate on its intuition, making it challenging to understand.

Response:

We would like to clarify that we did not propose a new algorithm. Instead, we provided a new and in-depth analysis of an existing algorithm, strengthening its result from an expected regret bound to a high-probability regret bound. This point was explicitly stated multiple times in the manuscript and was well understood by other reviewers.

We are grateful for the reviewer’s feedback. To address this concern, we have rewritten the paper to make it clearer that our contribution lies in the re-analysis of an existing algorithm. A revised version of the paper will be uploaded soon. In the new version, we have included a dedicated section to introduce the existing algorithm in detail. Furthermore, to better clarify the intuition behind the work, we provide an explanation of the algorithm's underlying principles at the beginning of this section.

Question 2: How the indicator function resolves unbounded martingale inequalities

Response: As noted near the end of the original manuscript, we use the indicator function to associate the original random variable sequence with a new random variable sequence. This new random variable sequence forms a bounded martingale, allowing us to apply standard martingale concentration inequalities. Furthermore, through this indicator-based association, we demonstrate that the original and new random variable sequence coincide with high probability. This enables us to transfer the concentration inequalities from the new sequence back to the original.

Once again, we sincerely thank the reviewer for the constructive comments, which have helped us improve the clarity and readability of the manuscript. The revised version will be uploaded soon. We hope our response has addressed the reviewer’s concerns and that you will consider increasing your support for the paper.

Thank you for detailed response. I increase my score to 5 for the revised manuscript but unfortunately, I have concerns to raise score more due to theoretical novelties. While deriving high-probability bound is an interesting problem, the technical novelty to derive the bound is limited. The revised paper heavily relies on the results from Schneider & Zimmert 2013 and the novel part is limited to replace the random variable with the conditionally expected term with high probability. Specifically, the paper replaces the Bias5e with Bias5e$F_e$ (which can be found in other literature with more refined analysis (see e.g., Thoerem 7 in [1])) and follows the analysis in Schneider & Zimmert 2013. Because the paper focuses on theoretical analysis without any novel algorithms or experiments, I believe it should include at least one newly developed lemma that may apply to many settings not only for the cross-learning contextual bandits to be published at a top-tier conference.

[1] Shamir, Eli, and Joel Spencer. "Sharp concentration of the chromatic number on random graphs G n, p." Combinatorica 7 (1987): 121-129.