- 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
-
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.
-
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
-
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.
-
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
-
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?
-
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.
-
Theoretical justification: Can you establish conditions under which GTV-Tsallis achieves provable sublinear regret?
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 algorithm with importance-weighted estimates, step sizes 21+di/t and λ≥2/(1+dmin) has a network regret of at most 4∑i1+di1∑aΔalnT+B, where di is the degree of agent i and B does not depend on T. 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 ∑alogT/Δ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 λ. The requested ablation removes the second while keeping the first. We ran Algorithm 1 with λ=0 on the SBM, with the same gate, burn-in, communication, graphs and random seeds as the gated variants (N=40, K=10, T=10,000, 20 runs, mean ± SEM). In the stochastic regime, the ℓ1 variant reaches a final regret of 88.2±1.3 at λ=1/T and 90.2±1.2 at λ=0, against 116.4±1.0 for local Tsallis-INF. In the adversarial regime the corresponding values are 109.3±1.2, 112.0±1.1 and 141.8±1.2. Gated pooling therefore accounts for most of the reduction relative to local Tsallis-INF. The explicit ℓ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 variant the two values of λ differ by at most 0.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.