EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Heterogeneous Multi-agent Multi-armed Bandit on Stochastic Block Models

Mengfan Xu, Liren Shan, Fatemeh Ghaffari, Xuchuang Wang, Xutong Liu, Mohammad Hajiesmaili

ACM SIGMETRICS Performance Evaluation Review · 20.07.2026 · 54 (1) · 7-9

DOI: 10.1145/3820171.3806887 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM SIGMETRICS Performance Evaluation Review, online erschienen am 27.07.2026. Verfasst von Mengfan Xu und 5 weiteren Autor:innen. Die Arbeit nennt 25 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: NSF (National Science Foundation).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We study a novel heterogeneous multi-agent multi-armed bandit problem with a cluster structure induced by stochastic block models (SBMs), influencing not only graph topology, but also reward heterogeneity. Specifically, agents are distributed on random graphs based on SBMs, a generalized Erdos-Renyi model with heterogeneous edge probabilities: agents are grouped into clusters (known or unknown); edge probabilities for agents within the same cluster differ from those across clusters. The same cluster structure in SBMs also determines our heterogeneous rewards. Rewards distributions of the same arm vary across agents in different clusters but remain consistent within a cluster, unifying homogeneous and heterogeneous settings and varying degree of heterogeneity. Rewards are independent samples from these distributions. The objective is to minimize system-wide regret across all agents. To address this, we propose a novel algorithm applicable to both known and unknown cluster settings. The algorithm combines an averaging-based consensus approach with a newly introduced information aggregation and weighting technique, resulting in a UCB-type strategy. It accounts for graph randomness, leverages both intra-cluster (homogeneous) and inter-cluster (heterogeneous) information from rewards and graphs, and incorporates cluster detection for unknown cluster settings. We derive optimal instance-dependent regret upper bounds of order log T under sub-Gaussian rewards. Importantly, our regret bounds capture the degree of heterogeneity in the system (an additional layer of complexity), exhibit smaller constants, scale better for large systems, and impose significantly relaxed assumptions on edge probabilities.

Förderung

  • NSF (National Science Foundation)

Zitieren

APA

Xu, M., Shan, L., Ghaffari, F., Wang, X., Liu, X., & Hajiesmaili, M. (2026). Heterogeneous Multi-agent Multi-armed Bandit on Stochastic Block Models. ACM SIGMETRICS Performance Evaluation Review, 54(1), 7-9. https://doi.org/10.1145/3820171.3806887

Vancouver

Xu M, Shan L, Ghaffari F, Wang X, Liu X, Hajiesmaili M. Heterogeneous Multi-agent Multi-armed Bandit on Stochastic Block Models. ACM SIGMETRICS Performance Evaluation Review. 2026;54(1):7-9. doi:10.1145/3820171.3806887

BibTeX
@article{Xu2026,
  author = {Xu, Mengfan and Shan, Liren and Ghaffari, Fatemeh and Wang, Xuchuang and Liu, Xutong and Hajiesmaili, Mohammad},
  title = {Heterogeneous Multi-agent Multi-armed Bandit on Stochastic Block Models},
  journal = {ACM SIGMETRICS Performance Evaluation Review},
  year = {2026},
  volume = {54},
  number = {1},
  pages = {7--9},
  doi = {10.1145/3820171.3806887}
}
Kostenlos starten →