Computational Lower Bounds for No-Regret Learning in Normal-Form Games

A celebrated connection in the interface of online learning and game theory establishes that the repeated interaction of no-regret players leads to a coarse correlated equilibrium (CCE)—a seminal game-theoretic solution concept. Despite the rich history of this foundational problem and the tremendous interest it has received in recent years, a basic question still remains open: how many iterations are needed for no-regret players to approximate an equilibrium under the usual normal-form representation? In this paper, we first establish tight computational lower bounds for that problem in two-player (general-sum) games under the constraint that the CCE reached approximates the optimal social welfare (or some other natural objective). From a technical standpoint, our approach revolves around proving lower bounds for computing a near-optimal T-sparse CCE—a mixture of T product distributions, circumscribing the iteration complexity of no-regret learning even in the centralized model of computation. Our proof proceeds by extending a classical reduction of Gilboa and Zemel (GEB ’89) for optimal Nash to sparse (approximate) CCE through the use of PCP-type gap amplification, thereby ruling out attaining any non-trivial sparsity in polynomial time. Moreover, we strengthen our hardness results to apply in the low-precision regime as well via the planted clique conjecture. Building on those lower bounds, we next address the more challenging problem that lifts the welfare constraint. In particular, we work in the algorithmic framework put forward by Kothari and Mehta (STOC ’18) in the context of computing Nash equilibria, which consists of the sum-of-squares (SoS) relaxation in conjunction with oracle access to a verification oracle; the goal in that framework is to lower bound either the degree of the SoS relaxation or the number of queries to the verification oracle. Here, we obtain two such hardness results, precluding computing i) uniform logn-sparse correlated equilibria (CE) when є =poly(1/logn) and ii) uniform n1 − o(1)-sparse CE when є = poly(1/n).