Material Detail

Minimax Policies for Combinatorial Prediction Games

Minimax Policies for Combinatorial Prediction Games

This video was recorded at 24th Annual Conference on Learning Theory (COLT), Budapest 2011. We address the online linear optimization problem when the actions of the forecaster are represented by binary vectors. Our goal is to understand the magnitude of the minimax regret for the worst possible set of actions. We study the problem under three different assumptions for the feedback: full information, and the partial information models of the so-called "semi-bandit", and "bandit" problems. We consider both L∞-, and L2-type of restrictions for the losses assigned by the adversary. We formulate a general strategy using Bregman projections on top of a potential-based gradient descent, which generalizes the ones studied in the series of papers György et al. (2007), Dani et al. (2008), Abernethy... Show More


  • User Rating
  • Comments
  • Learning Exercises
  • Bookmark Collections
  • Course ePortfolios
  • Accessibility Info

More about this material


Disciplines with similar materials as Minimax Policies for Combinatorial Prediction Games


Log in to participate in the discussions or sign up if you are not already a MERLOT member.