Distributed learning in congested environments with partial information

2021/03/29 by Tomer Boyarski, Boyarski, Tomer, Amir Leshem +3
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Cognitive Radio Networks and Spectrum Sensing #FOS: Computer and information sciences #Game Theory and Applications #Multiagent Systems (cs.MA) #cs.MA

paper · pdf · doi:10.48550/arxiv.2103.15901

openalex publication_date 2021/03/29 · arxiv created 2021/05/11 · arxiv updated 2021/05/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

How can non-communicating agents learn to share congested resources efficiently? This is a challenging task when the agents can access the same resource simultaneously (in contrast to multi-agent multi-armed bandit problems) and the resource valuations differ among agents. We present a fully distributed algorithm for learning to share in congested environments and prove that the agents' regret with respect to the optimal allocation is poly-logarithmic in the time horizon. Performance in the non-asymptotic regime is illustrated in numerical simulations. The distributed algorithm has applications in cloud computing and spectrum sharing. Keywords: Distributed learning, congestion games, poly-logarithmic regret.

Citations

• Multiplayer Multi-armed Bandits for Optimal Assignment in Heterogeneous Networks
• Non-Stochastic Multi-Player Multi-Armed Bandits: Optimal Rate With Collision Information, Sublinear Without

Related

• Online Learning in Decentralized Multiuser Resource Sharing Problems
• Distributed Learning: Sequential Decision Making in Resource-Constrained Environments
• Distributed Bandit Learning: Near-Optimal Regret with Efficient Communication
• Distributed Linear Bandits under Communication Constraints
• Distributed Learning with Partial Information Sharing