Efficient Learning in Polyhedral Games via Best Response Oracles

Abstract

We study online learning and equilibrium computation in games with polyhedral decision sets with only first-order oracle and best-response oracle access. Our approach achieves constant regret in zero-sum games and $O(T^{1/4})$ in general-sum games while using only $O(\log t)$ best-response queries at a given iteration $t$. This convergence occurs at a linear rate, though with a condition-number dependence. Our algorithm also achieves best-iterate convergence at a rate of $O(1/\sqrt{T})$ without such a dependence. Our algorithm uses a linearly convergent variant of Frank-Wolfe (FW) whose linear convergence depends on a condition number of the polytope known as the facial distance. We show two broad new results, characterizing the facial distance when the polyhedral sets satisfy a certain structure.