acceptodds
Under review as a conference paper at ICLR 2027

Nearly Optimal Best-of-Both-Worlds Individual Regret in Cooperative Bandits

Abstract

We study the best-of-both-worlds problem of cooperative multi-armed bandits in the uninformed setting, where agents interact with a common set of arms over an arbitrary connected communication graph, and each agent initially knows only its local neighborhood. Over a horizon of rounds, each agent selects an arm, observes only its local loss, and exchanges information with its neighbors. The environment can be either stochastic or adversarial, and the agents do not know the regime in advance. The objective is to simultaneously achieve small individual regret for every agent in both regimes while minimizing communication cost. We propose a single algorithm that achieves individual regret in the stochastic regime, where is the suboptimality gap of arm , and individual regret in the adaptive adversarial regime. We establish matching worst-graph lower bounds up to logarithmic factors for both regimes. Our regret guarantees strictly improve the best known results in the stochastic regime. We further show that our algorithm requires only communication rounds per agent in the stochastic regime, while every packet has bits in both regimes. Finally, we reveal a polynomial separation between adaptive and oblivious adversaries, showing that adaptivity can make cooperative bandit learning polynomially harder.

Primary area:
learning theory
Keywords:
Cooperative bandits, Best-of-both-worlds, Individual regret

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_CrRrOpenReview ↗
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
  1. This paper has provided thorough review of relevant literatures, and it is well written and easy to follow.
  2. 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
  1. 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

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 VV. Similar to Bar-On and Mansour (2019), it suffices for agents to know a public upper bound Vˉ≥V\bar V\ge 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(log⁡T)O(\log T) 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.

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.

Reviewer_CKG3OpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This papers student a well-known multi-agent mutli-armed bandits problems. In the model, there are cooperative multi-armed bandits in the uninformed setting, where VV agents interact with a common set of KK arms over an arbitrary connected communication network. Each agent initially knows only its local neighborhood. In a horizon of TT rounds, each agent selects an arm, observes only its local loss, and exchanges information with its neighbors.

Authors consider both stochastic environment or adversarial environment. The objective is to simultaneously achieve small individual regret for all agents in both regimes, and at the same time, minimize communication cost.

The authors proposed asymptomatically optimal arm selection and communication strategy for both regimes.

Critical strengths

The main strength of this paper is that it extends some previous results.

Critical weaknesses

Overall, the paper is well-written and I went through the analysis in detail and they look fine.

The only weakness is that there can be some "restriction" in their model, that is, all agents face the same set of arms.

Questions for authors

I am just curious, when the number of agents (VV) is large, it is possible that they won't be faced with the same set of arms but rather, each agent sees only a subset of arms. In addition, this subset of arms may have a non-empty intersection between two agents. In this case, the communication policy will be more challenging. Can you authors generalize their algorithms for such case?

1 comment

We appreciate the reviewer's thoughtful comments and helpful suggestions. We respond to each point below.


Q: Can the algorithm be generalized to heterogeneous setting?

A: The extension to heterogeneous action sets, where different agents have partially overlapping sets of available arms, is non-trivial, and our algorithm cannot be directly applied to this setting. First, the number of agents that can provide observations for each arm may vary, making it more challenging to pool observations efficiently. Second, our adversarial learner uses a shared distribution over arms within each initial tree. If some arms are unavailable to certain agents, they cannot follow the prescribed sampling rule, and the pooled loss estimates would need to be redesigned. We believe this is an interesting direction for future work.

Reviewer_JQtAOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies cooperative multi-armed bandits where agents communicate over a connected graph and initially know only their local neighborhoods. It proposes a single algorithm that adapts to stochastic and adaptive adversarial losses, with guarantees on each agent's pseudo-regret. In the stochastic case, the additive dependence on the number of arms improves from O~(K)\widetilde O(K) to O~(K)\widetilde O(\sqrt K), while retaining the cooperative statistical speedup. The adaptive adversarial bound is O~(KT/V+K1/4T)\widetilde O(\sqrt{KT/V}+K^{1/4}\sqrt T).

The validation is entirely theoretical. The paper provides matching worst-graph lower bounds in the stated senses, logarithmically many sending rounds under stochastic losses, and bounded packet sizes. A separate configuration also establishes a polynomial separation between adaptive and oblivious adversaries.

Critical strengths

I think the combination of guarantees is a strong point of the paper. Improving the stochastic additive term from KK to K\sqrt K is consequential, especially when there are enough agents that the statistical term becomes small. Achieving this while adapting to adversarial losses and keeping stochastic communication sparse makes the contribution more substantial.

What I found most interesting, however, was the adaptive versus oblivious separation. For K=V=TK=V=T on a path, the adaptive lower bound is Ω(T3/4)\Omega(T^{3/4}), while the oblivious upper bound is O~(T2/3)\widetilde O(T^{2/3}). The fact that the lower bound allows arbitrary aggregation and forwarding makes this a useful statement about the underlying information constraint.

Critical weaknesses

My main difficulty was getting a clear picture of which ideas are doing the most important work. There are several interacting constructions, and I sometimes understood what a component does before understanding why it is needed. Could the authors give a more direct explanation of why the K\sqrt K cooperation scale is appropriate and how the distributed tests control regret before an alarm reaches an agent? I think this would make the main contribution considerably easier to understand and assess.

I also had some uncertainty about the finite-horizon significance of the improvement. My understanding is that the hidden factors can be quite large, for example through the window multiplier proportional to Γ6\Gamma^6. I may be missing something here, and I would be happy if the authors could clarify the dominant logarithmic factors and indicate the parameter ranges where the improved dependence on KK gives a smaller guarantee than previous methods. I do not think experiments are necessary for this theoretical contribution, but this clarification would help me understand its quantitative significance.

Questions for authors

Please respond to the questions and concerns raised in the main review above.

1 comment

We appreciate the reviewer's thoughtful comments and helpful suggestions. We respond to each point below.


Q1: Why the K\sqrt{K}-cooperation scale is appropriate?

A: In our algorithm, the cooperation scale rs=min⁡2s⌈2K⌉,Vr_s=\min\\{2^s\lceil 2\sqrt K\rceil,V\\} starts at order K\sqrt K and increases as the phases progress. This choice is key to achieving the additive O~(K)\widetilde O(\sqrt K) term in the stochastic regime and the O~(K1/4T)\widetilde O(K^{1/4}\sqrt T) term in the adversarial regime. In the stochastic regime, larger groups collect more observations per round but incur longer communication delays. Estimating arm losses to precision τs\tau_s requires roughly K/(rsτs2)K/(r_s\tau_s^2) rounds, while communication incurs a delay of order rsr_s. Balancing these terms motivates rs≍K/τsr_s\asymp\sqrt K/\tau_s, ensuring that each growing phase incurs at most O~(rsτs)=O~(K)\widetilde O(r_s\tau_s)=\widetilde O(\sqrt K) regret. In the adversarial regime, the learner operates on the fixed initial trees, with regret bounded by O~((K/r0+r0)T)\widetilde O(\sqrt{(K/r_0+r_0)T}). Here, K/r0K/r_0 reflects the benefit of pooling observations, while r0r_0 accounts for communication delay. Balancing these terms with r0≍Kr_0\asymp\sqrt K yields the O~(K1/4T)\widetilde O(K^{1/4}\sqrt T) term. We have added this explanation to Section 3.2 (Phase groups) of the revised manuscript.


Q2: How the distributed tests control regret before an alarm reaches an agent?

A: The primary purpose of distributed tests is to monitor whether the observed losses remain consistent with the stochastic estimates, rather than to directly minimize regret. Having every agent test every arm would incur substantial additional exploration costs and undermine the benefits of cooperation. Instead, agents share the testing burden by randomly assigning testing arms across the network. Each agent allocates a small sampling probability to its assigned arms in each round and uses the observed losses to detect significant deviations from the current estimates. Once a violation is detected, an alarm is raised to trigger a switch to the adversarial learner. Moreover, before an alarm reaches an agent, sufficiently early tests must have passed, which provides bounds on cumulative losses. We have clarified these points in Sections 3.3 (Sampling and test assignment) and 3.4 (Mode switch) of the revised manuscript.


Q3: Clarification of the dominant logarithmic factors and the ranges where the improved dependence on KK matters.

A: Our analysis gives a stochastic regret bound of O(Γ8(K+Rsto))O(\Gamma^8(\sqrt K+R_{\mathrm{sto}})) and an adaptive adversarial regret bound of O(Γ11/2(KT/V+K1/4T))O(\Gamma^{11/2}(\sqrt{KT/V}+K^{1/4}\sqrt T)), where RstoR_{\mathrm{sto}} is defined in Table 1 and Γ=log⁡(210KVT8/δ)\Gamma=\log(2^{10}KVT^8/\delta). We have made these logarithmic factors explicit in the revised appendix. Our improvement in the dependence on KK is polynomial, establishing a stronger asymptotic guarantee than previous results. A precise finite-horizon comparison also depends on the leading constants in the respective bounds, which are often conservative and not explicitly optimized in theoretical analysis. Our primary goal is to match the lower bounds up to logarithmic factors, rather than to optimize the logarithmic dependence or leading constants. We agree that improving these quantitative factors is valuable and view this as an interesting direction for future work.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.