09/07/2020

Exploration by Optimisation in Partial Monitoring

Tor Lattimore, Csaba Szepesvari

Keywords: Bandit problems, Online learning

Abstract Paper Similar Papers

Abstract: We provide a novel algorithm for adversarial k-action d-outcome partial monitoring that is adaptive, intuitive and efficient. The highlight is that for the non-degenerate locally observable games, the n-round minimax regret is bounded by 2mk^(3/2)sqrt(3n log(k)), where m is the number of signals. This matches the best known information-theoretic upper bound derived via Bayesian minimax duality. The same algorithm also achieves near-optimal regret for full information, bandit and globally observable games. High probability bounds and simple experiments are also provided.

 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
 13:14 
 0
 0
 0
 0
 12:52 
 0
 0
 0
 0
 4:48 
 0
 0
 0
 0
 15:16 
 0
 0
 0
 0
 19:34 
 0
 0
 0
 0
 9:53 
 0
 0
 0
 0
 4:37 
 0
 0
 0
 0
 4:19 
 0
 0
 0
 0
 11:15 
 0
 0
 0
 0
 13:40 
 0
 0
 0
 0
 3:16 
 0
 0
 0
 0
 14:02 
 0
 0
 0
 0
 5:05 
 0
 0
 0
 0
 2:30 
 0
 0
 0
 0
 3:17 
 0
 0
 0
 0
 3:14 
 0
 0
 0
 0
 1:00 
 0
 0
 0
 0
 3:16 
 0
 0
 0
 0
 3:23 
 0
 0
 0
 0
 15:40 
 0
 0
 0
 0
 15:13 
 0
 0
 0
 0
 14:58 
 0
 0
 0
 0
 5:08 
 0
 0
 0
 0
 3:11 
 0
 0
 0
 0
 12:37 
 0
 0
 0
 0
 15:12 
 0
 0
 0
 0
 6:14 
 0
 0
 0
 0
 13:14 
 1
 1
 0
 0
 5:46 
 0
 0
 0
 0
 2:01 
 0
 0
 0
 0
 12:16 
 0
 0
 0
 0
 3:16 
 0
 0
 0
 0
 6:02 
 0
 0
 0
 0
 2:30 
 0
 0
 0
 0
 5:17 
 0
 0
 0
 0
 17:04 
 0
 0
 0
 0
 3:05 
 1
 0
 0
 0
 13:50 
 0
 0
 0
 0
 16:05 
 0
 0
 0
 0
 3:02