- Rating
- 3
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper studies the best of both worlds problem of cooperative MAB under the setting where the global communication graph is unknown to the players, and players are allowed to communicate to neighbors in with general message. They have proposed a single algorithm using the switching paradigm (Bubeck & Slivkins, 2012; Auer & Chiang, 2016), and the proposed algorithm has achieved nearly optimal regret in both stochastic and adversarial setting. This paper contributes to show matching-graph lower bounds up log factor and derived the best known result in their setting under both regime. More importantly, they reveal a polynomial gap between adaptive and oblivious adversaries showing that the adaptive adversarial bandit learning is harder.
Critical strengths
- This paper has provided thorough review of relevant literatures, and it is well written and easy to follow.
- This paper has provided several technical contributions to the problem they are solving. For example, they have provided a matching lower bound up to logarithmic factor in the worst-case graph setting to shows that their upper bounds are tight. They also show the polynomial gap between the adaptive and oblivious adversaries. The technical contribution of this paper is non-trivial.
Critical weaknesses
- According to information provided in the main paper, the author provides communication rounds and packetsize guarantee in the stochastic setting, while focusing on packet-size efficiency in the adversarial regime. Can the author please clarify whether a similar communication-rounds guarantee can be obtained in the adversarial regime, or explain the difficulty of it.
Questions for authors
Question 1: Does agent know the total number of agents in the game? Is this number necessary to form a initial tree?
Question 2: See weakness 1.
2 comments
hank you for the clarification regarding the number of agents assumption and its relation to the algorithm. I will maintain my evaluation of this paper.
We appreciate the reviewer's thoughtful comments and helpful suggestions. We respond to each point below.
Q1: Does agent know the total number of agents in the game? Is this number necessary to form a initial tree?
A: As noted in the footnote in Section 2, our algorithm does not require exact knowledge of V. Similar to Bar-On and Mansour (2019), it suffices for agents to know a public upper bound Vˉ≥V. We provide the corresponding algorithmic modifications and theoretical guarantees in Appendix A.4 (Corollary A.1), showing that the same regret bounds hold up to logarithmic factors. In particular, the initial trees can be constructed using only local neighborhood information and this upper bound, without knowing the exact number of agents.
Q2: Can the author please clarify whether a similar communication-rounds guarantee can be obtained in the adversarial regime, or explain the difficulty of it?
A: Achieving a similar communication-round guarantee in the adversarial regime is more challenging. Unlike stochastic losses with fixed means, adversarial losses may change adaptively over time, requiring agents to exchange recent observations to maintain low regret. With only O(logT) communication rounds, agents may experience long periods without updated information, potentially incurring substantial regret. To the best of our knowledge, existing cooperative bandit algorithms in the adversarial setting, e.g., (Cesa-Bianchi et al., 2019, Bar-On & Mansour 2019) typically communicate in every round. Whether near-optimal adversarial regret can be achieved with polylogarithmic or polynomially sublinear communication rounds remains unclear and is an interesting direction for future work.