Infinite-Armed Bandits with Multiple Players

Abstract

So far, mutli-armed bandit researchers have restricted their attention to games with a single player. I consider a multiplayer multi-armed bandit problem with infinitely many Bernoulli arms. The mean rewards of these arms follow the uniform distribution. However, players do not have perfect freedom in communicating their actions and payoffs. Instead, players are arranged in a star such the root player at the center of the star can observe all other players, but the peripheral players can only observe the root player. This thesis adapts the algorithm provided by Bonald and Proutière for this multiplayer setting. The root player creates a pool of arms whose posterior distribution on mean rewards is beta, allowing the peripheral players achieve better regret (by a constant multiplicative factor) by pulling from this pool of arms. Through coordination, the players are on average able to beat the lower bound from the single player setting.