Distributed learning in congested environments with partial information
arXiv:2103.15901
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.
References in corpus (5)
- A Practical Algorithm for Multiplayer Bandits when Arm Means Vary Among Players
- Game of Thrones: Fully Distributed Learning for Multi-Player Bandits
- Multi-Player Bandits Revisited
- Multiplayer Multi-armed Bandits for Optimal Assignment in Heterogeneous Networks
- Non-Stochastic Multi-Player Multi-Armed Bandits: Optimal Rate With Collision Information, Sublinear Without