Multi-agent Multi-armed Bandits with Stochastic Sharable Arm Capacities
This addresses distributed selection problems in multi-agent systems, but it is incremental as it builds on existing multi-player bandit models.
The paper tackles the problem of distributed multi-agent multi-armed bandits with stochastic sharable arm capacities, designing a greedy algorithm and an iterative distributed algorithm to achieve optimal arm pulling profiles without communication, with experiments validating the approach.
Motivated by distributed selection problems, we formulate a new variant of multi-player multi-armed bandit (MAB) model, which captures stochastic arrival of requests to each arm, as well as the policy of allocating requests to players. The challenge is how to design a distributed learning algorithm such that players select arms according to the optimal arm pulling profile (an arm pulling profile prescribes the number of players at each arm) without communicating to each other. We first design a greedy algorithm, which locates one of the optimal arm pulling profiles with a polynomial computational complexity. We also design an iterative distributed algorithm for players to commit to an optimal arm pulling profile with a constant number of rounds in expectation. We apply the explore then commit (ETC) framework to address the online setting when model parameters are unknown. We design an exploration strategy for players to estimate the optimal arm pulling profile. Since such estimates can be different across different players, it is challenging for players to commit. We then design an iterative distributed algorithm, which guarantees that players can arrive at a consensus on the optimal arm pulling profile in only M rounds. We conduct experiments to validate our algorithm.