Minimax Policies for Combinatorial Prediction Games


Jean-Yves Audibert, Sébastien Bubeck, Gábor Lugosi ;
Proceedings of the 24th Annual Conference on Learning Theory, PMLR 19:107-132, 2011.


We address the online linear optimization problem when theactions of the forecaster are represented by binary vectors.Our goal is to understand the magnitude of the minimax regretfor the worst possible set of actions. We study the problemunder three different assumptions for the feedback: full information, and the partial information models of theso-called “semi-bandit”, and “bandit” problems. We consider both L_∞-, and L_2-type of restrictions forthe 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 \citeGLLO07, DHK08, AHR08, CL09, HW09, KWK10, UNK10, KRS10 and \citeAB10. We provide simpleproofs that recover most of the previous results. We propose new upper bounds for the semi-bandit game. Moreover we derive lower bounds for all three feedback assumptions. With the only exception of the bandit game, the upper and lower boundsare tight, up to a constant factor.Finally, we answer a question asked by \citeKWK10 by showing that the exponentially weighted average forecaster is suboptimal against L_∞ adversaries.

Related Material