What is the computational power of best-response computations in repeated game playing? I will give a precise answer to this question in the context of no-regret learning in zero-sum games, and discuss the implications within the theory of online learning and regret minimization.

Based on joint work with Elad Hazan (STOC'16).