- 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 on any connected graph with diameter , and provide matching lower bounds. The paper also develops gap-dependent regret guarantees.
Critical strengths
- The paper provides a complete theoretical solution to a focused problem. It establishes matching upper and lower bounds for the regret.
- The paper is clearly written. The motivation, problem setting, and main contributions are presented in a clean way.
- The main theoretical results are accompanied by useful proof sketches and intuition.
- The authors clearly state the assumptions and limitations of the results and do not overclaim the generality or significance of the contributions.
Critical weaknesses
- 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.
- 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.)
- 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.)
- 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.
- 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
- 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?
- AFE assumes that the graph diameter is known and uses it explicitly in the localization schedule. Is knowledge of essential for attaining the minimax regret, or could AFE be made adaptive to an unknown diameter while preserving the minimax regret?
- The algorithm uses 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?
- 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.
- How essential is the unlimited-message assumption for achieving the minimax regret rate? Could the same rate be achieved with a number of communication rounds or bounded message sizes?
7 comments
To Reviewer Ukx9 (2/4)
W3 & Q5. The communication model is idealized. Delay is captured through , 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 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 rounds, and a variant of AFE attains the same rate with messages of 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 . 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 rounds after the block, agents forward the reward sums of the block. Since AFE has blocks, AFE communicates in rounds. The number of communication rounds is therefore for a fixed graph and fixed .
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 by a random bit that equals 1 with probability . The bit has the same mean as , 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 rounds and therefore adds at most 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 integers of bits. Aggregation along the tree takes rounds instead of , and the bound still holds with a larger constant. Reducing the message size further, e.g., to 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 waiting rounds, and AFE has blocks, so waiting at constant regret per round costs times a polylog factor. Second, standard elimination relies on a union bound over arms and stages, and the union bound costs a 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 , so that every later waiting round costs at most . 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 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 (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).
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 with gap , the regret bound contains a log factor , where the count measures how many arms compete with arm , and a larger count gives a smaller log factor. Every arm with a gap similar to or smaller than counts as one. The difficulty lies in how much an arm with a much larger gap 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 is removed long before the stage that decides arm , so arm receives only the weight . For a single agent, the algorithm of [5] attains the larger weight by recomputing the confidence level of every arm in every round, and the log factor of [5] is smaller by at most an additive . In the federated setting, however, every update of the shared statistics costs waiting rounds, so AFE updates only once per sampling block, and the sparse updates keep the total waiting cost within the rate . 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 (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 essential, or can AFE adapt to an unknown diameter?
A2. Knowledge of is not essential, because agents that know only can learn 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 rounds every agent holds the neighbor lists of all agents, and every agent can therefore reconstruct the graph and compute . All agents then start AFE in round , and the extra rounds add at most to the regret, so the bound 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 again, and the number of epochs is about , so the total is instead of . A long enough first epoch removes the extra . With epoch lengths and , the inequality holds in every epoch, so the regret of epoch is . The epoch bounds then form a geometric sum, and the regret after rounds is for all .
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 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 D, whereas in the earlier bounds [1, 3, 4] the graph term is multiplied by K or grows with T. Second, the additive D 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/2 rounds to arrive under any protocol and any message size. Third, pooling the samples of N agents costs no log factor, because KT/N is exactly the single-learner regret KNT with NT pulls, divided by N. 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 T.
Consider instances in which every suboptimal arm has a gap between Γ and 2Γ. On such instances, Theorem 5.3 shows that the minimax regret is at least c(SΓ(T)+ΓD) and that the regret of AFE is at most C(SΓ(T)+BG). The term SΓ(T)=NΓKlog(1+NTΓ2/K) is the statistical cost of separating K arms with gap Γ from pooled samples. The term ΓD is the cost of delay that no algorithm can avoid, because some agent has to wait about D/2 rounds for information from distant agents and every wrong pull during the wait costs at least Γ. The term BG 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) grows with T, whereas BG depends only on the graph, N, and K. The upper and lower bounds therefore match up to constants once T is large enough for SΓ(T) to dominate BG, and the difference between ΓD and BG affects only a term that does not grow with T.