Is optimization computationally equivalent to online learning?

Vapnik's fundamental theorem of statistical learning establishes a computational equivalence between optimization (empirical risk minimization) and learning in the statistical setting. Is the same true for learning in games? We give a precise answer to this question.