Name
Abstract | ||
|---|---|---|
Information sharing is an important issue for stochastic bandit problems in a distributed setting. Consider N players dealing with the same multi-armed bandit problem. All players receive requests simultaneously and must choose one of M actions for each request. Sharing information among these N players can decrease the regret for each of them but also incurs cooperation and communication overhead. In this setting, we study how cooperation and communication can impact the system performance measured by regret and communication cost. For both scenarios, we establish a uniform lower bound to the regret for the entire system as a function of time and network size. Concerning cooperation, we study the problem from a game-theoretic perspective. When each player's actions and payoffs are immediately visible to all others, we identify strategies for all players under which co-operative exploration is ensured. Regarding the communication cost, we consider incomplete information sharing such that a player's payoffs and actions are not entirely available to others. The players communicate observations to each other to reduce their regret, however with a cost. We show that a logarithmic communication cost is necessary to achieve the optimal regret. For Bernoulli arrivals, we specify a policy that achieves the optimal regret with a logarithmic communication cost. Our work opens a novel direction towards understanding information sharing for active learning in a distributed environment. |
Year | Venue | Field |
|---|---|---|
2015 | 2015 IEEE CONFERENCE ON COMPUTER COMMUNICATIONS (INFOCOM) | Network size,Mathematical optimization,Active learning,Regret,Distributed Computing Environment,Computer science,Upper and lower bounds,Complete information,Information sharing |
DocType | ISSN | Citations |
Conference | 0743-166X | 2 |
PageRank | References | Authors |
0.39 | 9 | 3 |