09/07/2020

Coordination without communication: optimal regret in two players multi-armed bandits

Sebastien Bubeck, Thomas Budzinski

Keywords: Bandit problems,

Abstract Paper Similar Papers

Abstract: We consider two agents playing simultaneously the same stochastic three-armed bandit problem. The two agents are cooperating but they cannot communicate. Under the assumption that shared randomness is available, we propose a strategy with no collisions at all between the players (with very high probability), and with near-optimal regret $O(\sqrt{T \log(T)})$. We also argue that the extra logarithmic term $\sqrt{\log(T)}$ should be necessary by proving a lower bound for a full information variant of the problem.

 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at COLT 2020 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd Characters remaining: 140

Similar Papers

 0
 0
 0
 0
 9:25 
 0
 0
 0
 0
 10:13 
 0
 0
 0
 0
 15:32 
 0
 0
 0
 0
 15:50 
 0
 0
 0
 0
 12:14 
 0
 0
 0
 0
 3:15 
 0
 0
 0
 0
 2:47 
 0
 0
 0
 0
 3:22 
 0
 0
 0
 0
 15:20 
 0
 0
 0
 0
 14:48 
 0
 0
 0
 0
 15:16 
 0
 0
 0
 0
 8:20 
 0
 0
 0
 0
 15:59 
 0
 0
 0
 0
 4:52 
 0
 0
 0
 0
 3:20 
 0
 0
 0
 0
 3:24 
 0
 0
 0
 0
 11:33 
 0
 0
 0
 0
 12:07 
 0
 0
 0
 0
 21:56 
 0
 0
 0
 0
 16:33 
 0
 0
 0
 0
 11:56 
 0
 0
 0
 0
 13:28 
 0
 0
 0
 0
 16:00 
 0
 0
 0
 0
 5:11 
 0
 0
 0
 0
 3:32 
 0
 0
 0
 0
 19:13 
 0
 0
 0
 0
 24:42 
 0
 0
 0
 0
 3:01 
 0
 0
 0
 0
 4:49 
 0
 0
 0
 0
 9:53 
 0
 0
 0
 0
 4:54 
 0
 0
 0
 0
 15:01 
 0
 0
 0
 0
 3:39 
 0
 0
 0
 0
 3:09 
 0
 0
 0
 0
 15:07 
 0
 0
 0
 0
 2:49 
 0
 0
 0
 0
 18:07 
 0
 0
 0
 0
 5:40 
 0
 0
 0
 0
 4:49 
 0
 0
 0
 0
 14:18