acceptodds
Under review as a conference paper at ICLR 2027

Federated Multi-Armed Bandits via Distributed Tsallis Mirror Descent

Abstract

We study a multi-agent multi-armed bandit problem in which the agents of a network learn personalized (agent-specific) policies. Our method is designed for networks whose agents form clusters with similar loss distributions, in particular a shared optimal arm, while the cluster assignments are unknown; each agent's regret is measured against the optimal arm of its own cluster. We propose GTV-Tsallis, which couples local instances of Tsallis-INF, a best-of-both-worlds mirror-descent bandit algorithm, through generalized total variation minimization (GTVMin) on the agents' policies. Consensus-based methods force all agents onto one shared policy. GTVMin instead penalizes disagreement between neighbors, so policies stay piecewise constant across cluster boundaries and distinct clusters converge to different arms without first estimating the clusters. A policy-similarity gate restricts the coupling to neighbors whose policies agree. We evaluate GTV-Tsallis in homogeneous and heterogeneous settings, under stochastic and adversarial losses, across four network topologies and two real-world graphs. Whenever agents have same-cluster neighbors it reduces regret relative to non-cooperative Tsallis-INF and to cooperative baselines that assume a shared optimal arm: final regret falls by more than half in the homogeneous setting and by 17–30% on the real-world graphs. When every edge crosses clusters, the policy-similarity gate matches the non-cooperative baseline.

Primary area:
reinforcement learning
Keywords:
multi-armed bandits, federated learning, clustered federated learning, generalized total variation minimization, online mirror descent

Reviews

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

The paper studies decentralized multi-agent bandits with unknown clusters of agents whose optimal arms may differ. It proposes GTV-Tsallis, combining local Tsallis-INF updates with generalized total-variation regularization and policy-similarity gating to enable selective cooperation. Experiments cover homogeneous and heterogeneous settings, stochastic and phased adversarial losses, synthetic graph topologies, and MovieLens and LastFM datasets, and showcase improved performance compared to baseline methods.

Critical strengths
  1. Extensive experimental evaluation: The authors evaluate the proposed algorithm across various scenarios, including homogeneous and heterogeneous environments, stochastic and phased adversarial losses, four synthetic graph families, and two real datasets. Additional experiments examine the number of clusters, inter-cluster connectivity, and configurations without within-cluster edges. The results showcase consistent superiority over baseline methods when useful cooperation is available. This provides substantial empirical support for the effectiveness of the algorithm provided in the manuscript.

  2. Personalized decentralized cooperation: The proposed algorithm addresses a meaningful limitation of conventional cooperative bandit approaches: indiscriminate information sharing can harm agents whose optimal arms differ. Combining graph total-variation regularization with policy-similarity gating provides an intuitive mechanism for encouraging cooperation among similar agents while limiting harmful sharing across clusters. Furthermore, this approach operates without a central server, known cluster assignments, or a specified number of clusters, making it relevant to personalized online decision-making over communication networks without the need to obtain prior information.

Critical weaknesses
  1. No theoretical guarantees for the proposed algorithm: While an extensive experimental evaluation showcases desired performance, the paper provides no regret or sample-complexity bounds for the proposed GTV-Tsallis algorithm. Given the relative simplicity of the finite MAB setting and the central role of regret analysis in bandit research, I would expect at least a guarantee under restricted assumptions. This is the main weakness, and it substantially affects my assessment. My suggestion to the authors is to derive a lower bound for the regret of the proposed framework, as well as an upper bound for the suggested algorithm, similar to existing bounds for Tsallis-INF. Quantifying how performance depends on the graph connectivity, cluster separation, and parameter choices would be interesting.

  2. Insufficient comparative evidence: Coop-UCB2 and DFTRL are evaluated only in the homogeneous setting, while the heterogeneous and real-data experiments mainly compare against independent Tsallis-INF. Additional cooperative or cluster-aware baselines would better establish the advantages of the proposed algorithm. Additionally, an ablation retaining gated information sharing while removing GTV regularization would also help isolate the proposed regularizer’s contribution.

Questions for authors
  1. Motivation: Which practical applications justify identical loss distributions within each cluster? This seems like quite a strong assumption. Do the MovieLens and LastFM experiments satisfy this assumption, or only the weaker condition of sharing an optimal arm?

  2. Graph and clusters: What relationship between links on the communication graph and latent clusters should be expected in the motivating applications? The authors experimentally examine several layouts, but it remains unclear to me how these two notions relate to each other in practice.

  3. Theoretical justification: Can you establish conditions under which GTV-Tsallis achieves provable sublinear regret?

1 comment

We thank the reviewer for the careful reading and respond to each point in turn. Section and appendix numbers refer to the revised paper.

Theoretical guarantees. We agree that the submitted version lacks a guarantee for the network. Theorem 1 is the bound of Zimmert and Seldin for Tsallis-INF, stated in Section 3 to present the base algorithm. The revised paper adds a guarantee for the homogeneous setting. Theorem 2 (Section 5, proof in Appendix A) shows that on every graph, the ungated ℓ1\ell_1 algorithm with importance-weighted estimates, step sizes 21+di/t2\sqrt{1+d_i}/\sqrt{t} and λ≥2/(1+dmin⁡)\lambda \ge 2/(1+d_{\min}) has a network regret of at most 4∑i11+di∑aln⁡TΔa+B4\sum_i \frac{1}{1+d_i}\sum_a \frac{\ln T}{\Delta_a} + B, where did_i is the degree of agent ii and BB does not depend on TT. The bound also holds in the stochastically constrained adversarial regime. Section 5 also states the lower bound of Lai and Robbins (1985): even a central learner that observes all losses incurs a network regret of order ∑alog⁡T/Δa\sum_a \log T/\Delta_a. The revised paper does not cover the clustered case. We expect the same argument to extend to it, with the number of same-cluster neighbors in place of the degree and an additional cost for the gate weight left on cross-cluster edges, but this extension is future work.

Comparative evidence. We agree that the heterogeneous and real-data experiments compare mainly against independent Tsallis-INF, and that we do not include a cluster-aware baseline. Coop-UCB2 and DFTRL assume a shared optimal arm, so we evaluated them only in the homogeneous setting. The closest evidence on non-personalized cooperation in the heterogeneous setting is the ungated variant in Appendix E, where pooling across the cluster boundary reaches several times the regret of local play.

Ablation of the GTV regularizer. The variation between neighboring policies enters the algorithm in two ways: through the gate, which sets each neighbor's weight in the pool from the distance between the two policies, and through the explicit coupling term weighted by λ\lambda. The requested ablation removes the second while keeping the first. We ran Algorithm 1 with λ=0\lambda = 0 on the SBM, with the same gate, burn-in, communication, graphs and random seeds as the gated variants (N=40N = 40, K=10K = 10, T=10,000T = 10{,}000, 20 runs, mean ±\pm SEM). In the stochastic regime, the ℓ1\ell_1 variant reaches a final regret of 88.2±1.388.2 \pm 1.3 at λ=1/T\lambda = 1/\sqrt{T} and 90.2±1.290.2 \pm 1.2 at λ=0\lambda = 0, against 116.4±1.0116.4 \pm 1.0 for local Tsallis-INF. In the adversarial regime the corresponding values are 109.3±1.2109.3 \pm 1.2, 112.0±1.1112.0 \pm 1.1 and 141.8±1.2141.8 \pm 1.2. Gated pooling therefore accounts for most of the reduction relative to local Tsallis-INF. The explicit ℓ1\ell_1 coupling adds a small further reduction that is consistent across runs (lower regret in 20 of 20 stochastic and 18 of 20 adversarial runs), whereas for the ℓ2\ell_2 variant the two values of λ\lambda differ by at most 0.60.6.

Identical loss distributions and the real data. Identical distributions within a cluster are a simplification that makes the objective of Section 2 easy to state, and the algorithm does not use them. The MovieLens and LastFM experiments satisfy only the weaker condition: each user has their own mean loss vector, and a cluster is a group of users sharing the same optimal arm. This weaker condition is the realistic one for the applications we have in mind, such as users of one region or devices of one hardware type, and GTV-Tsallis still reduces regret relative to local Tsallis-INF under it. The revised paper states this in Sections 1, 2 and 6.4.

Communication graph and latent clusters. The paper makes no assumption on this relation, and in the motivating applications we expect it to vary. For recommendation across regions, links tend to follow geography, so they align with the clusters, as in the SBM. When the system builds the graph from user similarity, as in our MovieLens experiment, links follow preferences by construction (18% of edges cross clusters). In social networks, links connect users with related preferences without separating them cleanly: in the LastFM friendship graph, which is not built from listening behavior, 37.5% of the edges cross clusters. For edge devices, links may reflect physical proximity and carry little information about hardware type, which is closer to our Erdős–Rényi setting. The experiments span this range, from about one cross-cluster edge in twenty (ring) to about one in two (ER), up to the independent-set configuration of Appendix D, in which every edge crosses clusters. The method does not need the graph to align with the clusters, only that agents have some same-cluster neighbors. When none exist, the gated variants track local Tsallis-INF. The revised paper adds this discussion to Section 2.1.

Reviewer_Ds49OpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper focuses on a multi-agent multi-armed bandit problem in which the agents of a network learn personalized (agent-specific) policies. In the problem setting, all agents share the similar loss distributions, while the cluster assignments are unknown. Each agent’s regret is measured against the optimal arm of its own cluster. The authors propose algorithm GTVTSALLIS, which couples local instances of Tsallis-INF, a best-of-both-worlds mirror-descent bandit algorithm, through generalized total variation minimization (GTVMin) on the agents’ policies. Consensus-based methods force all agents onto one shared policy. GTVMin instead penalizes disagreement between neighbors, so policies stay piecewise constant across cluster boundaries and distinct clusters converge to different arms without first estimating the clusters. A policy-similarity gate restricts the coupling to neighbors whose policies agree. Experiments shows that, whenever agents have same-cluster neighbors it reduces regret relative to non-cooperative Tsallis-INF and to cooperative baselines that assume a shared optimal arm: final regret falls by more than half in the homogeneous setting and by 17–30% on the real-world graphs. When every edge crosses clusters, the policy-similarity gate matches the non-cooperative baseline.

Critical strengths
  1. The problem setting is realistic and interesting. There is a trade-off between reduced variance from within-group collaboration and cross-group information contamination, especially in networked personalized bandits; the technique Policy-similarity gate and GTV can serve as an engineering-relevant heuristic.
  2. The algorithm design is intuitive. The strategy GTV gives a natural mechanism for agents tending to work under the same policy instead of using the strong command. The policy-similarity gate is a possible way to reduce contamination from cross-cluster neighbors.
  3. This experiment of this work has a certain breadth and a relatively clear experimental motivation.
Critical weaknesses
  1. The significance of this work is questionable. In this setting, each agent cluster can be considered as an independent multi-agent system. Applying the federated algorithms specifically to these agent clusters seems to yield the same or even better results. In this paper, agents in different clusters have different goal, but they are not against. Hence, the reason for studying them together no longer exists. The authors should explain this point.
  2. The novelty relative to existing GTV-based and clustered bandit algorithms needs clearer positioning. Besides, this work needs theoretical advance beyond combining existing GTV regularization with Tsallis-INF and an adaptive neighbor-weighting mechanism.
  3. The real-world experiments may not fully match the problem setting. In the theoretical section, agents in the same cluster share the same reward distribution. However, in the real-world experiments, agents shares the same best arm does not necessarily imply that they have identical reward distributions.
Questions for authors

For theorem 1, the regret upper bound is ∑︁alog⁡T/∆a∑︁_a \log T/∆_a. However, the existing work is ∑︁aN−1∆a−1log⁡T∑︁_a N^{−1}∆^{−1}_a \log T , where NN is the agent number of each cluster. Can the authors explain the loss of this term?

In a federated system, communication is of vital importance, but the evaluation mainly focuses on regret. Reporting communication and computational cost helps to measure the trade-off relationship between learning performance and decentralized coordination.

More detailed information could be provided regarding how users are se lected, how the clustering is constructed, and the relationship between the final benchmark and the assumed loss model, the real-world evaluation would be much more powerful.

2 comments

We thank the reviewer for the careful reading. Section and appendix numbers refer to the revised paper.

Significance. We agree that agents in different clusters have different goals and that nothing is sought from cooperating across clusters. If the cluster assignments were known, running a federated algorithm within each cluster would be the natural solution. We study the setting in which the assignments are unknown and the communication graph is given, so an agent cannot tell which neighbors belong to its cluster and cannot form the per-cluster system the reviewer describes. The agents are studied together because they share a network, and the difficulty is deciding from bandit feedback which neighbors to pool with: in Appendix E, pooling over all neighbors reaches four times the regret of local play. A cluster may also be poorly connected or disconnected in the given graph, as in the independent-set configuration of Appendix D. Novelty and positioning. The closest GTV-based bandit method is the network-lasso bandit of Dhouib et al. (TMLR 2025), which, like the Laplacian-regularized GOB.Lin of Cesa-Bianchi et al. (2013), penalizes differences between the parameters of neighboring users. First, it is centralized: a single learner serves one randomly drawn user per round and solves the network lasso over the whole graph, whereas each of our agents acts in every round and updates from its neighbors' messages only. Second, it estimates the parameters of a linear contextual model under stochastic rewards, whereas we penalize differences between the agents' policies, make no parametric assumption on the losses and, building on Tsallis-INF, also handle adversarial losses. Third, it assumes that the graph induces the clusters, with each cluster connected, and keeps the edge weights fixed. We assume nothing about how the graph relates to the clusters, and the policy-similarity gate reweights each edge during learning, so the method does not degrade when edges cross clusters (Appendices D and E). The revised paper discusses these works in Section 1.1.

Theorem 1 and the factor 1/N1/N. Theorem 1 is the bound of Zimmert and Seldin for Tsallis-INF, stated in Section 3 to present the base algorithm, so it contains no factor in the number of agents. The revised paper adds Theorem 2 (Section 5, proof in Appendix A): in the homogeneous setting and on every graph, the ungated algorithm with importance-weighted estimates has a network regret of at most 4∑i11+di∑aln⁡TΔa+B4\sum_i \frac{1}{1+d_i}\sum_a \frac{\ln T}{\Delta_a} + B, where did_i is the degree of agent ii and BB does not depend on TT. The factor 1/(1+di)1/(1+d_i) is the counterpart of the factor N−1N^{-1} in the bound the reviewer cites, with the neighborhood of each agent in place of its cluster. The revised paper does not cover the clustered case. We expect the argument to extend to it, with the number of same-cluster neighbors in place of the degree and a cost for the gate weight left on cross-cluster edges, but this is future work.

Communication and computation. After the burn-in, in each round every agent sends its neighbors its policy and its loss estimate. This is O(K)O(K) per directed edge and O(K∣E∣)O(K|E|) over the network per round. Per agent and round, the computation is O(K∣N(i)∣)O(K|\mathcal{N}(i)|) for the gate and the pooled estimate, plus a one-dimensional Newton solve. The revised paper adds this to Appendix B.

Real-world experiments and the loss model.

The cluster assumption. In Section 2, all agents of a cluster have the same loss distribution. This is a simplification that makes the objective easy to state, and the algorithm does not use it. In the real-data experiments, every loss is Bernoulli, but each user's means come from that user's own ratings or listening weights. Two users of the same cluster therefore have different means, and hence different loss distributions. What they share is the arm with the lowest mean loss, because clusters are formed by grouping users with the same best arm. This weaker condition is the realistic one for applications such as recommendation across regions, and GTV-Tsallis still reduces regret relative to local Tsallis-INF under it. The revised paper states this in Sections 1, 2 and 6.4.

Users, losses and clusters. The revised paper describes the construction in Appendix B. The arms are the 10 most-rated movies and the 20 artists with the most listeners. The pools are 300 MovieLens users who rated at least 5 of them and 500 LastFM users who listened to at least 5 of them. A user's mean loss is one minus the rating divided by 5, or one minus the normalized logarithm of one plus the listening weight. Clusters are the two largest groups of users sharing a best arm, with 181 and 51 users on MovieLens and 158 and 70 on LastFM. The MovieLens graph is an 8-nearest-neighbor graph on rating profiles, with 18% of edges crossing clusters; the LastFM graph is the friendship graph, with 37.5%.

Thanks for your reply, which addressed some of my concerns. So the score can be raised to 3.

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

The paper studies decentralized multi-armed bandits where agents belong to unknown clusters with potentially different optimal arms. The proposed GTV-Tsallis method combines local Tsallis-INF learners with neighboring feedback sharing, a total-variation penalty on policies, and a policy-similarity gate intended to prevent harmful cooperation across clusters.

The experiments cover several synthetic graph families, different cluster configurations, and simulations based on MovieLens and LastFM. The reported improvements over independent learning are encouraging, particularly when agents have useful same-cluster neighbors.

Critical strengths

I think the paper addresses a meaningful problem. When agents have different preferences, measuring each against its own optimal arm seems like a natural objective. The proposed approach is also relatively simple and decentralized, and does not require knowing the cluster assignments or number of clusters beforehand.

I also appreciated that the experiments include settings where cooperation can be harmful. The connectivity sweep and the all-cross-cluster experiment help explain when sharing is useful, while Appendix D makes the cost of conservative gating visible even in homogeneous environments. These comparisons gave me a better sense of the method’s tradeoffs.

Critical weaknesses

My main concern is that I could not quite tell how much of the improvement comes from total-variation regularization itself. As I understand it, the method changes both the feedback that agents receive and the way their policies are updated. Could the authors compare against gated feedback sharing with λ=0\lambda=0, while keeping communication and the other settings unchanged? This seems particularly important because selective pooling could already explain a substantial part of the gains. Relatedly, how were gate sharpness and burn-in selected, and were the evaluation instances also used for tuning?

I also had a concern about the DFTRL comparison. My reading of the cited method is that it combines Tsallis and negative Shannon entropy, whereas the submission describes a Tsallis/log-barrier regularizer. Could the authors clarify which regularizer and estimator were implemented, and how the original shared-loss setting was adapted to agent-specific observations? This could simply be a description issue, but given DFTRL’s unusually poor performance in Figure 2, I would find this clarification helpful. (Original DFTRL paper, Section 3.2)

My other main concern is the mathematical justification for the clustering behavior. For the entropy defined in Section 3, I obtain DH(u,w)=∑a(ua−wa)2/waD_H(u,w)=\sum_a(\sqrt{u_a}-\sqrt{w_a})^2/\sqrt{w_a}, which differs from Equation (3). Could the authors help reconcile this expression and the stated equivalence between Equations (3) and (4)? Similarly, I am not sure why Algorithm 1’s explicit sign-subgradient update should inherit the exact-agreement property of total-variation minimizers. My understanding is that a coupling term vanishing at equality does not ensure that noisy updates reach or preserve equality. I could be missing an argument here, and would be happy if the authors could explain it. Since Theorem 1 concerns the original single-agent algorithm, I currently do not see a guarantee establishing this behavior for GTV-Tsallis.

Questions for authors

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

1 comment

We thank the reviewer for the careful reading and respond to each concern in turn. Section and appendix numbers refer to the revised paper.

Contribution of the TV term. The variation between neighboring policies enters the algorithm in two ways: through the gate, which sets each neighbor's weight in the pool from the distance between the two policies, and through the explicit coupling term weighted by λ\lambda. The requested ablation isolates the second channel while keeping the first. We ran Algorithm 1 with λ=0\lambda = 0 on the SBM, with the same gate, burn-in, communication, graphs and random seeds as the gated variants (N=40N = 40, K=10K = 10, T=10,000T = 10{,}000, 20 runs, mean ±\pm SEM). In the stochastic regime, the ℓ1\ell_1 variant reaches a final regret of 88.2±1.388.2 \pm 1.3 at λ=1/T\lambda = 1/\sqrt{T} and 90.2±1.290.2 \pm 1.2 at λ=0\lambda = 0, against 116.4±1.0116.4 \pm 1.0 for local Tsallis-INF. In the adversarial regime the corresponding values are 109.3±1.2109.3 \pm 1.2, 112.0±1.1112.0 \pm 1.1 and 141.8±1.2141.8 \pm 1.2. Gated pooling therefore accounts for most of the reduction relative to local Tsallis-INF. The explicit ℓ1\ell_1 coupling adds a small further reduction that is consistent across runs, whereas for the ℓ2\ell_2 variant the two values of λ\lambda differ by at most 0.60.6. The two variants are nearly tied at λ=0\lambda = 0, so the advantage of ℓ1\ell_1 comes from its coupling term.

Selection of β\beta and t0t_0. These values were chosen by a sweep over candidate settings on the instance families used for evaluation, with random seeds different from those of the reported runs. Since the graph distributions and loss means were the same, this is not a held-out evaluation. We acknowledge that the submitted version reports these values without describing this procedure; the revised paper describes it in Section 4.4.

DFTRL. The reviewer's reading is correct, and "log-barrier" in Sections 1.1 and 5 of the submitted version is a description error, which the revised paper corrects; Appendix B of the revised paper describes our implementation. It uses the regularizer of Eq. (2) in Yi and Vojnović (2023), a Tsallis term plus negative Shannon entropy, with the step sizes of their Section 3.2. The estimator follows their Algorithm 2 with delay d=1d = 1: the loss of an arm is divided by the probability that at least one member of the closed neighborhood pulled that arm, computed from the delayed policies. Their setting shares one realized loss per arm and round among all agents; in ours, losses are independent across agents. When several members of a closed neighborhood pull the same arm, we use the loss of the lowest-indexed one, once, so the estimator remains unbiased for the mean loss in the homogeneous setting.

Equations (3) and (4). The reviewer is correct. The revised Section 3 presents Tsallis-INF in its FTRL form, Eq. (3), gives the Bregman divergence the reviewer computes, and restricts the equivalence with mirror descent to a constant step size. The algorithm we implemented and evaluated is this FTRL form, whose stationarity condition is Eq. (4), which is the algorithm of Zimmert and Seldin, so the experiments and Theorem 1 are unaffected.

Exact agreement. We agree that the paper overstates this behavior, and the reviewer's argument is correct. Exact agreement is a property of the minimizers of the GTVMin objective, which a proximal method computes. Algorithm 1 instead takes an explicit step of fixed size λ/2\lambda/2 in each coordinate where two neighboring policies differ. Each agent also adds its own pooled loss estimate, so two neighbors in the same cluster coincide only by chance, and the fixed step overshoots rather than settles at equality. What the coupling does provide is a pull that does not weaken as neighbors approach each other, unlike the ℓ2\ell_2 term, whose pull is proportional to the distance. The revised paper removes the claims of exact agreement and hard clustering (abstract and Sections 4 and 6.1) and describes the clustering behavior as approximate (Section 4.2).

Guarantees. The reviewer is correct that Theorem 1, the bound of Zimmert and Seldin recalled in Section 3 to present the base algorithm, concerns a single agent. The revised paper adds Theorem 2 (Section 5, proof in Appendix A): in the homogeneous setting and on every graph, the ungated ℓ1\ell_1 algorithm with importance-weighted estimates has a network regret of at most 4∑i11+di∑aln⁡TΔa+B4\sum_i \frac{1}{1+d_i}\sum_a \frac{\ln T}{\Delta_a} + B, where did_i is the degree of agent ii and BB does not depend on TT. The revised paper does not cover the clustered case, and it gives no guarantee for the clustering behavior itself. We expect the regret argument to extend to the clustered case, with the number of same-cluster neighbors in place of the degree and a cost for the gate weight left on cross-cluster edges, but this extension is 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.