Relax and Randomize: From Value to Algorithms

We show a principled way of deriving online learning algorithms from a minimax analysis. Various upper bounds on the minimax value, previously thought to be nonconstructive, are shown to yield algo