acceptodds
Under review as a conference paper at ICLR 2027

Minimax-Optimal Regret for Heterogeneous Federated Bandits

Abstract

In heterogeneous federated bandits, agents on a communication graph face different reward distributions and seek the arm with the highest global mean, that is, the mean reward averaged across agents. We propose Adaptive Federated Elimination (AFE). It estimates global means from all agents' samples and removes clearly suboptimal arms early, so that agents incur little regret while waiting for messages. For agents, arms, and rounds on any connected graph of diameter , AFE achieves expected regret for every agent. We establish a matching lower bound on every connected graph, showing that AFE is minimax optimal. AFE also adapts to the suboptimality gaps and achieves regret plus a cost of waiting for messages that does not depend on . This bound applies the same factor to every arm. We refine it and show that each arm needs only a smaller factor, which depends on the arm's gap and on how many arms have gaps smaller than or close to that gap. When all suboptimal arms have similar gaps, a lower bound shows that AFE is optimal up to additive costs that do not depend on . In a complete-graph example, AFE's refined bound is smaller than the guarantees of recent algorithms by a factor of order .

Primary area:
learning theory
Keywords:
federated bandits, regret bounds

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_Ukx9OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies heterogeneous federated multi-armed bandits over a general connected communication graph. The authors propose AFE, which combines global reward estimation with arm elimination while accounting for communication delays. They show that AFE achieves the minimax-optimal regret rate Θ ⁣(D+KT/N)\Theta\!\left(D+\sqrt{KT/N}\right) on any connected graph with diameter DD, and provide matching lower bounds. The paper also develops gap-dependent regret guarantees.

Critical strengths
  1. The paper provides a complete theoretical solution to a focused problem. It establishes matching upper and lower bounds for the regret.
  2. The paper is clearly written. The motivation, problem setting, and main contributions are presented in a clean way.
  3. The main theoretical results are accompanied by useful proof sketches and intuition.
  4. The authors clearly state the assumptions and limitations of the results and do not overclaim the generality or significance of the contributions.
Critical weaknesses
  1. The problem setting is already well studied, and the contribution is mainly a sharper theoretical characterization rather than a new problem formulation. Therefore the overall scope remains relatively narrow.
  2. The instance-dependent optimality result is incomplete. The refined upper bound is matched only for the similar-gap class, and it remains open whether it is optimal when the gaps differ substantially. In addition, the additive waiting and localization costs are not matched even in the similar-gap case. (I believe this is just a small issue.)
  3. The communication model is relatively idealized. The analysis captures communication delay through the graph diameter, but does not explicitly optimize the number of communication rounds, communication frequency, or message size. (main issue, needs to be discussed.)
  4. AFE is algorithmically new, but its building blocks are largely classical (authors also admit this fact). The novelty lies mainly in the way they are combined and analyzed to achieve the exact minimax rate in this federated setting.
  5. The paper does not include experiments.

Overall, although the paper has some minor issues, it is well written and provides a fairly complete solution to a focused problem.

Questions for authors
  1. Could the authors provide more intuition for why the gap-dependent upper bound is not matched by the lower bound for general heterogeneous gaps? Is this mainly a limitation of the current analysis, or does it suggest that AFE may be suboptimal in this regime?
  2. AFE assumes that the graph diameter DD is known and uses it explicitly in the localization schedule. Is knowledge of DD essential for attaining the minimax regret, or could AFE be made adaptive to an unknown diameter while preserving the minimax regret?
  3. The algorithm uses TT in both its stopping rule and confidence schedule. Do the authors expect an anytime version of AFE (e.g., with doubling trick) to retain the same minimax regret?
  4. Could the authors improve the presentation of the notation and prior-work comparison in the main text? The paper introduces many notations, so a compact notation table would be helpful. I would also appreciate a more explicit related-work section in the main paper, rather than leaving most of the detailed comparison to the appendix.
  5. How essential is the unlimited-message assumption for achieving the minimax regret rate? Could the same rate be achieved with a o(T)o(T) number of communication rounds or bounded message sizes?
7 comments
AuthorsOpenReview ↗

To Reviewer Ukx9 (1/4)

We sincerely thank you for the careful review and the constructive questions. We have carefully considered your concerns and provided a detailed explanation below. Please feel free to let us know if you have any additional concerns or questions.


W1. The setting is well studied, and the contribution is a sharper characterization rather than a new formulation, so the scope is narrow.

R1. Thank you for the comment. The paper studies an existing setting [1–4], and the goal of the paper is to determine the minimax regret of this setting. We would like to add some context on why we believe the result is of interest.

The question was raised in prior work, since Qiu et al. [4, Section 4.2] list the tight minimax rate for distributed stochastic bandits with heterogeneous losses as an open problem. Theorem 4.1 answers the question in our communication model, in which agents may send arbitrary messages to their neighbors, with matching upper and lower bounds of order KT/N+D\sqrt{KT/N}+D on every connected graph. To our knowledge, Theorem 4.1 gives the first matching bounds for the setting.

In addition, we hope that the result is informative beyond the rate itself, in three ways. First, the graph enters only through an additive DD, whereas in the earlier bounds [1, 3, 4] the graph term is multiplied by KK or grows with TT. Second, the additive DD is caused by heterogeneity and not by statistical difficulty, because the best arm can depend on the local means of distant agents, and information about distant agents needs about D/2D/2 rounds to arrive under any protocol and any message size. Third, pooling the samples of NN agents costs no log factor, because KT/N\sqrt{KT/N} is exactly the single-learner regret KNT\sqrt{KNT} with NTNT pulls, divided by NN. Following the comment, the revised introduction states the three points explicitly and compares our bound with prior bounds in a new Table 1.


W2. Instance-dependent optimality is shown only for similar gaps; optimality for general gaps is open, and the additive waiting and localization costs are not matched even for similar gaps (minor).

R2. Thank you for the careful reading of Section 5. The first point, general gaps, is the subject of Q1 and is discussed in A1. For the second point, the additive costs, we explain here why the bounds of Theorem 5.3 still match for large TT.

Consider instances in which every suboptimal arm has a gap between Γ\Gamma and 2Γ2\Gamma. On such instances, Theorem 5.3 shows that the minimax regret is at least c (SΓ(T)+ΓD)c\,(S_\Gamma(T)+\Gamma D) and that the regret of AFE is at most C (SΓ(T)+BG)C\,(S_\Gamma(T)+B_G). The term SΓ(T)=KNΓlog⁡(1+NTΓ2/K)S_\Gamma(T)=\frac{K}{N\Gamma}\log(1+NT\Gamma^2/K) is the statistical cost of separating KK arms with gap Γ\Gamma from pooled samples. The term ΓD\Gamma D is the cost of delay that no algorithm can avoid, because some agent has to wait about D/2D/2 rounds for information from distant agents and every wrong pull during the wait costs at least Γ\Gamma. The term BGB_G is the cost that AFE pays for waiting and for localization, where localization is the initial phase in which AFE removes all arms with a large gap so that later waiting rounds are cheap. The statistical term SΓ(T)S_\Gamma(T) grows with TT, whereas BGB_G depends only on the graph, NN, and KK. The upper and lower bounds therefore match up to constants once TT is large enough for SΓ(T)S_\Gamma(T) to dominate BGB_G, and the difference between ΓD\Gamma D and BGB_G affects only a term that does not grow with TT.

AuthorsOpenReview ↗

To Reviewer Ukx9 (2/4)

W3 & Q5. The communication model is idealized. Delay is captured through DD, but the number of communication rounds, the frequency, and the message size are not optimized. How essential is the unlimited-message assumption, and can the rate be achieved with o(T)o(T) communication rounds or bounded message sizes?

R3 & A5. Thank you for raising this important issue. The revision adds a discussion of the communication model in a new Appendix I, with a summary in the conclusion. In short, the minimax rate requires neither frequent communication nor unbounded messages, because AFE communicates in only O(Dlog⁡Klog⁡(NT))O(D\log K\log(NT)) rounds, and a variant of AFE attains the same rate with messages of O(Klog⁡(NT))O(K\log(NT)) bits.

Role of the assumption. The communication model allows a message of any size on every edge in every round. The assumption makes the lower bound stronger, because the lower bound holds even with unlimited messages, so no amount of communication can beat KT/N+D\sqrt{KT/N}+D. For the upper bound, the assumption is a convenience rather than a necessity, as the following two results show.

Number of communication rounds (Proposition I.1). AFE alternates sampling blocks and forwarding phases. During a sampling block, agents pull arms and send nothing, and during the DD rounds after the block, agents forward the reward sums of the block. Since AFE has O(log⁡Klog⁡(NT))O(\log K\log(NT)) blocks, AFE communicates in O(min⁡{T,Dlog⁡Klog⁡(NT)})O(\min\{T,D\log K\log(NT)\}) rounds. The number of communication rounds is therefore O(log⁡T)O(\log T) for a fixed graph and fixed KK.

Message size (Proposition I.2). AFE as submitted forwards real-valued reward sums, and two changes replace the real-valued sums by short integer messages. First, each agent replaces every observed reward Y∈[0,1]Y\in[0,1] by a random bit that equals 1 with probability YY. The bit has the same mean as YY, so the estimates stay unbiased, and the reward sums become integer counts. Second, agents build a spanning tree once, rooted at the agent with the smallest identifier. The construction takes DD rounds and therefore adds at most DD to the regret. Agents then add up the counts along the tree instead of forwarding the counts of every agent separately. A message then carries one count per arm, i.e., at most KK integers of ⌈log⁡2(NT+1)⌉\lceil\log_2(NT+1)\rceil bits. Aggregation along the tree takes 2D2D rounds instead of DD, and the bound O(KT/N+D)O(\sqrt{KT/N}+D) still holds with a larger constant. Reducing the message size further, e.g., to O(log⁡N)O(\log N) bits per message, is an interesting direction for future work, and the conclusion now mentions the direction.


W4. The building blocks are largely classical; the novelty is in combining and analyzing the building blocks to obtain the exact minimax rate.

R4. Thank you for the comment on the novelty. AFE builds on median selection and validation on fresh samples. The technical contribution lies in making the upper bound match the lower bound, because a direct combination of the two building blocks on a graph incurs two losses. First, every sampling block is followed by DD waiting rounds, and AFE has O(log⁡Klog⁡(NT))O(\log K\log(NT)) blocks, so waiting at constant regret per round costs DD times a polylog factor. Second, standard elimination relies on a union bound over arms and stages, and the union bound costs a log⁡T\sqrt{\log T} factor in the statistical term.

AFE removes the two losses as follows. For the waiting cost, AFE first removes all arms with a gap above a threshold β\beta, so that every later waiting round costs at most β\beta. For the statistical term, AFE uses a confidence level that is much weaker than a union bound requires and that scales with the number of surviving arms. With the weaker confidence level, however, the probability that AFE deletes the best remaining arm no longer vanishes as TT grows, so the analysis cannot assume that all estimates are accurate. The analysis instead shows that wrong deletions are cheap, in the sense that the expected losses of all wrong deletions add up to at most the order of the statistical term KT/N\sqrt{KT/N} (Lemmas C.6, C.7, and C.9).

In addition, the matching lower bound holds on every connected graph and for every protocol. Since agents may send arbitrary messages, the proof cannot rely on the message content and uses only the fact that information travels at most one hop per round (Lemma D.3).

AuthorsOpenReview ↗

To Reviewer Ukx9 (3/4)

W5. There are no experiments.

R5. Thank you for raising this point. The main claims of the paper are worst-case statements over all instances and all protocols, and such statements are supported by proofs rather than by simulations on particular instances. Accordingly, the comparison with prior algorithms in Section 5.3 concerns proved bounds, as Section 5.3 states explicitly. Simulations would be a useful complement to the theory, and we plan to study the empirical behavior of AFE in future work.


Q1. Why is the gap-dependent upper bound not matched for general gaps? Is the mismatch a limitation of the analysis, or is AFE suboptimal for general gaps?

A1. The upper and lower bounds match when all gaps are within a constant factor of each other (Theorem 5.3), and a mismatch can appear only when the gaps span many scales. The intuition is as follows.

For an arm ii with gap Δi\Delta_i, the regret bound contains a log factor log⁡(NTΔi2/ki)\log(NT\Delta_i^2/k_i), where the count kik_i measures how many arms compete with arm ii, and a larger count gives a smaller log factor. Every arm with a gap similar to or smaller than Δi\Delta_i counts as one. The difficulty lies in how much an arm jj with a much larger gap Δj≫Δi\Delta_j\gg\Delta_i should count. With similar gaps no such arm exists, so the bounds match.

Upper bound. AFE sets the confidence level of a stage from the number of remaining arms, and arm jj is removed long before the stage that decides arm ii, so arm jj receives only the weight (Δi/Δj)2(\Delta_i/\Delta_j)^2. For a single agent, the algorithm of [5] attains the larger weight Δi/Δj\Delta_i/\Delta_j by recomputing the confidence level of every arm in every round, and the log factor of [5] is smaller by at most an additive log⁡(Δmax⁡/Δi)\log(\Delta_{\max}/\Delta_i). In the federated setting, however, every update of the shared statistics costs DD waiting rounds, so AFE updates only once per sampling block, and the sparse updates keep the total waiting cost within the rate KT/N+D\sqrt{KT/N}+D. The stage-wise schedule is therefore a natural source of the difference, although we do not know whether the difference comes from the schedule alone or also from our analysis.

Lower bound. The proof of a lower bound over a class of instances changes an instance slightly and shows that no algorithm does well on both versions, and both versions must belong to the class. With similar gaps, raising one suboptimal arm above the best arm keeps all gaps in [Γ,2Γ][\Gamma,2\Gamma] (Proposition F.1). With gaps on many scales, in contrast, the same change alters the gaps of all other arms, so the changed instance leaves the class. The same obstacle exists for a single agent, where the finite-time lower bound of [5] also compares an instance with a changed instance.


Q2. Is knowledge of DD essential, or can AFE adapt to an unknown diameter?

A2. Knowledge of DD is not essential, because agents that know only NN can learn DD before AFE starts. Every agent repeatedly forwards the identifiers and neighbor lists received so far. Since information travels one hop per round, after at most DD rounds every agent holds the neighbor lists of all NN agents, and every agent can therefore reconstruct the graph and compute DD. All agents then start AFE in round D+1D+1, and the DD extra rounds add at most DD to the regret, so the bound O(KT/N+D)O(\sqrt{KT/N}+D) still holds.


Q3. Would an anytime version of AFE (e.g., with the doubling trick) keep the minimax rate?

A3. Yes, with one change to the doubling trick. The doubling trick restarts AFE in epochs of doubling length, and each epoch uses the epoch length as the horizon. With naive doubling, every epoch pays the additive DD again, and the number of epochs is about log⁡T\log T, so the total is Dlog⁡TD\log T instead of DD. A long enough first epoch removes the extra log⁡T\log T. With epoch lengths Tj=2jT0T_j=2^jT_0 and T0=max⁡{N,K,⌈ND2/K⌉}T_0=\max\{N,K,\lceil ND^2/K\rceil\}, the inequality D≤KTj/ND\le\sqrt{KT_j/N} holds in every epoch, so the regret of epoch jj is O(KTj/N)O(\sqrt{KT_j/N}). The epoch bounds then form a geometric sum, and the regret after tt rounds is O(Kt/N+D)O(\sqrt{Kt/N}+D) for all t≥max⁡{N,K}t\ge\max\{N,K\}.

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

This paper proposed Adaptive Federated Elimination (AFE) for heterogeneous federated bandit, in which agents communicate on a connected communication graph, and each agent faces heterogeneous reward distribution on arms. The objective is to identify the arm that maximizes the global cumulative reward. AFE achieved expected regret of O(D+KT/N)O(D+\sqrt{KT/N}) for ever agent. The authors also established lower bound to show the minimax optimality of AFE. The proposed algorithm first starts with a localization stage, which drops arms with large empirical gaps then followed by repetitive elimination stages.

Critical strengths
  1. This paper makes a theoretical contribution by establishing lower bounds that hold on every connected communication graph, from which they demonstrates the minimax optimality of their proposed algorithm. Authors of this paper also provide instance-dependent adaptivity and theoretical guarantee. They further improved the per-arm log factor in the upper bound. With all being said, this paper has justified its theoretical contribution.
Critical weaknesses
  1. Writing in 3.2 LOCALIZATION AND ELIMINATION needs to be improved; especially the selection procedure for the reference arm JrJ_r is not very clear.
  2. Equation (1) used both ν\nu and vv, which looks very similar and are easy to confuse. In addition, ν\nu is used in Equation (1) as an instance before it is introduced. The instance class V(G,J)\mathcal{V}(G,J) is introduced later in line 113 -115.
Questions for authors
  1. Could authors please explain how JrJ_r is selected from the MEDIAN procedure?
3 comments
AuthorsOpenReview ↗

To Reviewer xr1b

We appreciate very much your constructive comments on our paper. We hope our responses adequately address the concerns you raised. Please feel free to let us know if you have any additional concerns or questions.


W1 & Q1. Section 3.2 needs better writing; in particular, it is unclear how the reference arm JrJ_r is selected.

R1 & A1. Thank you for pointing out this issue. Section 3.2 described the selection of JrJ_r in one sentence and left the pseudo-code of MEDIAN to Appendix B. We have therefore moved MEDIAN (Algorithm 2) into Section 3.2 and added a step-by-step description, summarized below.

Role of JrJ_r. AFE runs in stages, and in stage rr all agents share a set ArA_r of candidate arms and a precision εr\varepsilon_r. The goal of stage rr is to remove the arms of ArA_r that are clearly worse than the best arm of ArA_r. Since the best arm is unknown, stage rr first picks a reference arm JrJ_r with a mean close to the best mean in ArA_r. Stage rr then draws fresh samples and removes every arm with an estimate more than εr\varepsilon_r below the estimate of JrJ_r (Eq. (4)).

How MEDIAN selects JrJ_r. MEDIAN repeatedly halves a temporary copy BB of ArA_r:

  1. Set B=ArB=A_r.
  2. All agents sample the arms in BB uniformly and forward the reward sums for DD rounds, so that all agents compute the same estimates of the arms in BB. The agents then keep the ⌈∣B∣/2⌉\lceil|B|/2\rceil arms of BB with the largest estimates.
  3. Step 2 is repeated until one arm is left, and the remaining arm is JrJ_r. Repetition q=0,1,2,…q=0,1,2,\dots uses the precision θq=(εr/4)(3/4)q\theta_q=(\varepsilon_r/4)(3/4)^q, so the precisions of all repetitions sum to at most εr\varepsilon_r.

Because all agents hold the same estimates and break ties in favor of the smaller label, all agents pick the same JrJ_r.

Three clarifications. First, MEDIAN only shrinks the temporary set BB and never removes arms from ArA_r, so an arm dropped from BB stays in ArA_r and can be removed only by the test in Eq. (4). Second, MEDIAN guarantees that the mean of JrJ_r is within εr\varepsilon_r of the best mean in ArA_r with probability at least 1−pr1-p_r, where prp_r is the failure probability of stage rr (Lemma C.2). Third, halving is used instead of picking the empirical best arm in one shot, because one-shot selection requires all estimates to be accurate at once, which costs a log⁡∣Ar∣\log|A_r| factor in samples. A halving step, in contrast, fails only if the best arm in BB is underestimated or about half of the arms in BB are overestimated, so the sample cost has no log⁡∣Ar∣\log|A_r| factor.

W2. Eq. (1) uses both ν\nu and vv, which are easy to confuse, and ν\nu is used before being defined (V(G,K)\mathcal V(G,K) appears only in lines 113–115).

R2. Thank you for pointing out the two issues. We now write the instance as ω\omega instead of ν\nu. In addition, Section 2 now defines the instance ω=(ωiv)\omega=(\omega_{iv}), i.e., the collection of local reward distributions, and the class V(G,K)\mathcal V(G,K) before Eq. (1). We have also added a notation table in Appendix A.

Thank you for your clarification. I will maintain my positive evaluation on this paper.

Thank you very much for your positive evaluation and for your time and effort throughout the review process.

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

This paper considers the cooperation of agents on a connected communication graph, where the goal is to always select the global optimally arm defined with respect to the average reward of arms across the agents. The paper proposes an adaptive version of the elimination method through the doubling trick. The paper then proves both instance-dependent and minimax regret bounds, including the upper bounds of the proposed method and lower bounds of rationale policies. The two bounds seem to match, and thus support the minimax optimality.

Critical strengths

The paper characterizes the graph dependent lower bounds and upper bounds. These parameters seem to generalize the current dependency.

Critical weaknesses
  1. The novelty is unclear in its current form. The related work section in Appendix does not clearly signal out the novelty, nor the introduction in the main body. The elimination method seems to be quite well developed, and the dependency on graph and agent size also seem to be understood. The comparison with the line of work on heterogeneous federated bandits, including the method, results, and analysis, is necessary, but not sufficiently presented.

  2. The paper's writing, particularly the introduction, needs more work/focus in its current form. It has been a list of what the paper has established, without conveying the insights or the novelty substantially. The subjective feeling is that it seems to try to prove a lot of things, but what new knowledge through the cloud is unclear.

Questions for authors
  1. Can the authors elaborate more on this? "Protocols may use shared or private randomness that does not depend on the instance."

  2. Is the lower bound still based on a construction of a special instance?

  3. What is the technical novelty of the method and the analysis?

  4. Dependency on the graph or the agent seems to be established, and what is the new dependency here?

5 comments
AuthorsOpenReview ↗

To Reviewer KHU7 (1/3)

We sincerely thank you for providing valuable feedback. We detail our response below point by point. Please kindly let us know whether you have any further concerns. If our response addresses your concerns, we would greatly appreciate it if you could reconsider the rating.


W1 & Q4. The novelty is unclear in both the introduction and the related work. The elimination method is well developed, and the dependence on the graph and on the number of agents seems understood. A comparison with prior work on heterogeneous federated bandits (method, results, analysis) is needed.

R1 & A4. Thank you for raising this point. Prior upper bounds already contain a 1/N1/\sqrt N speed-up and graph-dependent terms, and what remained open is the tight dependence. Before our work, it was not known whether the graph cost must depend on the spectral gap, must be multiplied by KK, or must grow with TT, as in the existing bounds. Theorem 4.1 shows that none of the three is necessary, because the minimax regret is Θ(KT/N+D)\Theta(\sqrt{KT/N}+D) on every connected graph, with upper and lower bounds that match up to absolute constants. We give the comparison below.

What was known. Prior work gives upper bounds for specific algorithms:

AlgorithmRegret boundGraph cost
DRRB [1]KTlog⁡T/N+KD+QK/ρ\sqrt{KT\log T/N}+KD+QK/\rhoKD+QK/ρKD+QK/\rho
FedFTRL [2]KT/N+AP Tlog⁡K\sqrt{KT/N}+\sqrt{A_P\,T\log K}AP Tlog⁡K\sqrt{A_P\,T\log K}
Black-box [3]KT/N+B Tlog⁡K\sqrt{KT/N}+\sqrt{B\,T\log K}B Tlog⁡K\sqrt{B\,T\log K}
AFE (ours)KT/N+D\sqrt{KT/N}+D (tight)DD

Here ρ\rho is the spectral gap of the gossip matrix, and ρ\rho is small on poorly connected graphs. Further, QQ is the consensus prefactor of DRRB, AP=min⁡{log⁡(NT),N}/ρ+2+DA_P=\min\{\log(NT),\sqrt N\}/\rho+2+D, and B=Θ(log⁡(KNT)/ρ)B=\Theta(\log(KNT)/\sqrt\rho).

The upper bounds in the table leave two questions open. The first question is whether any algorithm can achieve a smaller regret. Known lower bounds do not give an answer, because the lower bounds in [1, 4] are asymptotic and assume consistent policies, while the lower bounds in [5] only give the dependence on TT. The second question is whether the graph cost must depend on the spectral gap and must grow with TT, as in the bounds of FedFTRL and the black-box approach. Qiu et al. [3, Section 4.2] also state explicitly that the tight minimax rate for distributed stochastic bandits with heterogeneous losses remains open.

What we prove. Theorem 4.1 answers the two questions. For every connected graph and 2≤N,K≤T2\le N,K\le T, AFE has regret at most C(KT/N+D)C(\sqrt{KT/N}+D) for an absolute constant CC, whereas every algorithm has regret at least (KT/N+D)/64(\sqrt{KT/N}+D)/64 on some instance. To our knowledge, Theorem 4.1 therefore gives the first matching upper and lower bounds for the problem. The matching bounds show that the spectral gap plays no role once agents can forward messages, and that the graph costs only an additive DD, independent of TT and KK. Moreover, the term DD cannot be avoided, because with heterogeneous rewards an agent cannot know the best arm before hearing from the farthest agents (see R2).

The lower bound holds for every protocol and every message size, including gossip, so the additive DD is unavoidable for all algorithms in the table. The comparison with DRRB [1] is direct, because DRRB studies the same stochastic model and, like AFE, places no limit on the size of messages, whereas FedFTRL [2] and the black-box approach [3] communicate by gossip. Moreover, the upper bound of AFE does not rely on unlimited messages, because a variant of AFE attains the same rate with messages of O(Klog⁡(NT))O(K\log(NT)) bits (new Appendix I).

Comparison on a ring. As an example, consider a ring of NN agents, where D≈N/2D\approx N/2 and ρ\rho is of order 1/N21/N^2 for standard gossip weights. The graph cost is then at least of order NTN\sqrt T for FedFTRL, NT\sqrt{NT} up to log factors for the black-box approach, and QKN2QKN^2 for DRRB, compared with only N/2N/2 for AFE. The complete-graph example of Section 5.3 shows only a logarithmic improvement because D=1D=1 and ρ=1\rho=1 on a complete graph, whereas on sparse graphs such as the ring the graph cost improves by a polynomial factor.

AuthorsOpenReview ↗

To Reviewer KHU7 (2/3)

Difference in method. In existing algorithms, each agent averages estimates with neighbors (consensus or gossip), so the bounds of existing algorithms depend on the mixing speed of the averaging, i.e., on ρ\rho. AFE, in contrast, does not average. Instead, agents sample in blocks, and after each block agents forward reward sums for DD rounds, so that every agent obtains the exact totals. Exact forwarding removes ρ\rho from the bound but costs DD waiting rounds per block. The technical challenge is therefore to keep the total waiting cost within the rate KT/N+D\sqrt{KT/N}+D while also avoiding the log⁡T\sqrt{\log T} factor of standard elimination, and A3 gives the details.

The revised introduction includes the table above as the new Table 1, and the related work section (Appendix H) now states the differences in results and method explicitly.


W2. The writing, especially the introduction, reads as a list of results without conveying insight or novelty.

R2. Thank you for the constructive feedback on the writing. The revised introduction now poses one question: what is the minimax regret, and which property of the graph determines it? The answer, Θ(KT/N+D)\Theta(\sqrt{KT/N}+D), gives three insights, which the introduction now states explicitly.

  1. Only the diameter matters, and only additively. A sparse graph adds a fixed delay but does not change the rate of learning, because once T≥ND2/KT\ge ND^2/K the regret is of the same order as on a complete graph. In contrast, for adversarial losses with gossip communication, the graph cost ρ−1/4T\rho^{-1/4}\sqrt T grows with TT [3].
  2. The DD term comes from heterogeneity, not from statistical difficulty. On any connected graph, some agent vv has at least half of the agents at distance at least D/2D/2. Changing only the local means of the distant agents can flip the global best arm while keeping a constant gap. Since agent vv cannot see the change for about D/2D/2 rounds, agent vv suffers regret of order DD on one of the two instances, even though the bandit problem is statistically easy (Lemma D.4). Moreover, the argument holds for any protocol and any message size.
  3. Pooling costs no log factor. A single learner with NTNT pulls has regret of order KNT\sqrt{KNT}, and AFE achieves KT/N\sqrt{KT/N} per agent, exactly KNT\sqrt{KNT} divided by NN. The gap-dependent results of Section 5 are now presented as a refinement: AFE also adapts to the gaps with a per-arm log factor that is tight when the gaps are similar.

Q1. Please elaborate on "Protocols may use shared or private randomness that does not depend on the instance."

A1. The sentence describes the randomness that a protocol is allowed to use. A protocol may draw on two sources of randomness, and the two sources differ in which agents see the random draws. With private randomness, each agent has a separate source that the other agents cannot see, so the random choices of different agents are independent. With shared randomness, in contrast, one common source is fixed before round 1 and is visible to all agents, so the random choices of different agents can be correlated without any communication.

The phrase "does not depend on the instance" means that the two sources are independent of the reward distributions. As a result, the randomness carries no information about the best arm, and an agent can learn about the best arm only from observed rewards and received messages.

AFE needs only private randomness, because in a sampling round each agent pulls an arm chosen uniformly at random from the set of arms that are being sampled. The lower bound, however, holds for every protocol, including protocols that use both private and shared randomness. Section 2 now includes the explanation above.

AuthorsOpenReview ↗

To Reviewer KHU7 (3/3)

Q2. Is the lower bound still based on a special instance?

A2. Yes, as in every worst-case lower bound, including the classical KT\sqrt{KT} lower bound for single-agent bandits, the proof exhibits hard instances. The hard instances, however, are constructed on every connected graph, so the lower bound is not tied to a special graph. Moreover, the lower bound holds for every protocol, for messages of any size, and for every finite T≥max⁡{N,K}T\ge\max\{N,K\}, without a consistency assumption. On every connected graph, the proof uses the following two instances.

  • Instance for the term KT/N\sqrt{KT/N}. All agents have the same reward distributions, and one arm is better than the other arms by a small gap of order K/(NT)\sqrt{K/(NT)}. Because the gap is so small, no algorithm can find the better arm reliably, even with all NTNT samples pooled.
  • Instance for the term DD. The instance is described in R2, point 2: the distant agents determine the best arm, while agent vv cannot see the difference for about D/2D/2 rounds. Since the lower bound is a worst-case statement, a smaller regret is still possible on easier instances. For easier instances, Section 5 gives gap-dependent bounds, together with a matching lower bound when the gaps are similar.

Q3. What is the technical novelty of the method and the analysis?

A3. The main technical novelty is that the upper and lower bounds match up to constants on every connected graph; to our knowledge, no prior work on the problem achieves matching bounds. AFE builds on median selection and validation on fresh samples [6, 7]. Matching bounds, however, leave no room for slack, so a direct combination of the two building blocks does not suffice, and two difficulties had to be resolved.

  1. Waiting must not cost DD per block. Every sampling block is followed by DD waiting rounds, and AFE has O(log⁡Klog⁡(NT))O(\log K\log(NT)) blocks, so waiting at constant regret per round would cost DD times a polylog factor. AFE therefore first removes all arms with gap above a threshold β\beta, so that every later waiting round costs at most β\beta. A smaller β\beta makes waiting cheaper but requires more samples for the removal, and AFE chooses β\beta to balance the two costs (Section 4.2 and Lemma C.5). The resulting waiting cost does not grow with TT and stays within the rate KT/N+D\sqrt{KT/N}+D (Lemma C.10).
  2. The statistical term must lose no log factor. Standard elimination relies on a union bound over arms and stages, and the union bound costs a log⁡T\sqrt{\log T} factor. AFE avoids the union bound by using a much weaker confidence level, but with the weaker confidence level the probability that AFE deletes the best remaining arm no longer vanishes as TT grows. A standard analysis assumes that all estimates are accurate and therefore no longer applies. The key observation is that wrong deletions cannot be ruled out but are cheap: a wrong deletion lowers the best remaining mean only slightly, and the resulting loss is the drop times the number of remaining rounds. Lemmas C.6, C.7, and C.9 show that the expected losses of all wrong deletions add up to at most the order of the statistical term KT/N\sqrt{KT/N}. The lower bound complements the two points above. Its proof is short, and its strength lies in its generality: the proof uses only the fact that information travels at most one hop per round (Lemma D.3), so the bound holds on every connected graph and for arbitrary messages.

References

[1] H. Zhang, X. Wang, H.-X. Chen, H. Qiu, L. Yang, Y. Gao. Near-optimal regret bounds for federated multi-armed bandits with fully distributed communication. UAI 2025.

[2] Z. Hu, Z. Wang, C. Chen. A near-optimal best-of-both-worlds algorithm for federated bandits. ICLR 2026.

[3] H. Qiu, M. Zhang, N. Cesa-Bianchi. Near-optimal regret for distributed adversarial bandits: A black-box approach. COLT 2026.

[4] H. Zhang, Y. Xu, X. Wang, H.-X. Chen, H. Qiu, L. Yang, Y. Gao. Federated multi-armed bandits with efficient bit-level communications. NeurIPS 2025.

[5] M. Xu, D. Klabjan. Multi-agent multi-armed bandit regret complexity and optimality. AISTATS 2025.

[6] E. Even-Dar, S. Mannor, Y. Mansour. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. JMLR 2006.

[7] Z. Karnin, T. Koren, O. Somekh. Almost optimal exploration in multi-armed bandits. ICML 2013.

Comments on the paper

1 comment
AuthorsOpenReview ↗

To All Reviewers

We sincerely thank all reviewers for the time and effort devoted to reviewing our paper, and for the constructive comments and questions, which have helped us improve the paper.

We have responded to the comments of each reviewer point by point in the individual responses. We have also revised the paper according to the reviewers' suggestions, and all changes are marked in blue in the revised version. For convenience, we summarize the main changes below.

  1. Introduction and related work (KHU7 W1, W2, Q4; Ukx9 W1, Q4). The introduction now states the open problem, compares our bound with prior bounds in a new Table 1 (the table of Section 5.3 is now Table 2), and highlights the main insights. The related work section (Appendix H) now states how our results and method differ from prior work.
  2. Notation (xr1b W2; Ukx9 Q4). The reward instance and the class V(G,K)\mathcal V(G,K) are defined before Eq. (1), the instance is renamed ω\omega, and Appendix A has a notation table.
  3. Reference arm JrJ_r (xr1b W1, Q1). MEDIAN (Algorithm 2) has moved into Section 3.2, with a step-by-step description.
  4. Communication (Ukx9 W3, Q5). The new Appendix I bounds the number of communication rounds of AFE and gives a variant of AFE with finite-bit messages.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.