Skip navigation
Please use this identifier to cite or link to this item:
Title: Infinite-Armed Bandits with Multiple Players
Authors: Fong, Christian
Advisors: Bubeck, Sebastien
Department: Operations Research and Financial Engineering
Class Year: 2014
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.
Extent: 39
Type of Material: Princeton University Senior Theses
Language: en_US
Appears in Collections:Operations Research and Financial Engineering, 2000-2016

Files in This Item:
File SizeFormat 
Fong, Christian Final Thesis.pdf469.45 kBAdobe PDF    Request a copy

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.