Asymptotic optimality for decentralised bandits

DOI10.1007/S13235-022-00451-1zbMATH Open1516.91031arXiv2109.09427OpenAlexW3193742863MaRDI QIDQ6159519FDOQ6159519

Authors:

Publication date: 20 June 2023

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

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

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

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

Mathematics Subject Classification ID

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

Cites Work

• Bandit algorithms
• Asymptotically efficient adaptive allocation rules
• Title not available (Why is that?)
• 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
• Team optimal decentralized estimation by multiple agents with asymmetric information
• Delay and cooperation in nonstochastic bandits

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)