On minimaxity of Follow the Leader strategy in the stochastic setting

We consider the setting of prediction with expert advice with an additional assumption that each expert generates its losses i.i.d. according to some distribution. We first identify a class of “admissible” strategies, which we call permutation invariant, and show that every strategy outside this class will perform not better than some permutation invariant strategy. We then show that when the losses are binary, a simple Follow the Leader (FL) algorithm is the minimax strategy for this game, where minimaxity is simultaneously achieved for the expected regret, the pseudo-regret, and the excess risk. Furthermore, FL has also the smallest regret, pseudo-regret, and excess risk over all permutation invariant prediction strategies, simultaneously for all distributions over binary losses. We generalize these minimax results to the case in which each expert generates its losses from a distribution belonging to a one-dimensional exponential family, as well as to the case of loss vectors generated jointly from a multinomial distribution. We also show that when the losses are in the interval [0,1] and the learner competes against all distributions over [0,1], FL remains minimax only when an additional trick called “loss binarization” is applied.