A cluster-aware multi-agent bandit algorithm achieves O((C/M) log T) regret by aggregating information within clusters and communicating only between clusters, improving on the O(M^2 log T) bound of fully heterogeneous prior work.
Improved Algorithm on Online Clustering of Bandits
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We generalize the setting of online clustering of bandits by allowing non-uniform distribution over user frequencies. A more efficient algorithm is proposed with simple set structures to represent clusters. We prove a regret bound for the new algorithm which is free of the minimal frequency over users. The experiments on both synthetic and real datasets consistently show the advantage of the new algorithm over existing methods.
citation-role summary
background 1
citation-polarity summary
fields
cs.LG 1years
2025 1verdicts
CONDITIONAL 1roles
background 1polarities
unclear 1representative citing papers
citing papers explorer
-
Heterogeneous Multi-agent Multi-armed Bandits on Stochastic Block Models
A cluster-aware multi-agent bandit algorithm achieves O((C/M) log T) regret by aggregating information within clusters and communicating only between clusters, improving on the O(M^2 log T) bound of fully heterogeneous prior work.