Asymptotic optimality for decentralised bandits

DOI10.1007/S13235-022-00451-1MaRDI QIDQ6159519zbMATH OpenOpenAlexFDO

Authors

Publication date 20 June 2023

Published in Dynamic Games and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2109.09427

Mathematics Subject Classification ID

Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Distributed algorithms (68W15)

Abstract: We consider a large number of agents collaborating on a multi-armed bandit problem with a large number of arms. The goal is to minimise the regret of each agent in a communication-constrained setting. We present a decentralised algorithm which builds upon and improves the Gossip-Insert-Eliminate method of Chawla et al. arxiv:2001.05452. We provide a theoretical analysis of the regret incurred which shows that our algorithm is asymptotically optimal. In fact, our regret guarantee matches the asymptotically optimal rate achievable in the full communication setting. Finally, we present empirical results which support our conclusions

Recommendations

• Delay and cooperation in nonstochastic bandits
• Game of thrones: fully distributed learning for multiplayer bandits
• Multi-player bandits revisited
• Distributed cooperative decision making in multi-agent multi-armed bandits
• Asymptotically optimal algorithms for budgeted multiple play bandits

Cites work

• scientific article; zbMATH DE number 996442 (Why is no real title available?)
• Asymptotically efficient adaptive allocation rules
• Bandit algorithms
• Tight bounds for rumor spreading in graphs of a given conductance

Cited in

(8)

• Efficient decentralized multi-agent learning in asymmetric bipartite queueing systems
• Special issue: multi-agent dynamic decision making and learning
• Game of thrones: fully distributed learning for multiplayer bandits
• Distributed cooperative decision making in multi-agent multi-armed bandits
• Multi-player bandits revisited
• Decentralized Learning for Multiplayer Multiarmed Bandits
• Delay and cooperation in nonstochastic bandits
• Team optimal decentralized estimation by multiple agents with asymmetric information

This page was built for publication: Asymptotic optimality for decentralised bandits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6159519)