Efficient Learning in Polyhedral Games via Best Response Oracles

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 condition number when the polyhedral sets satisfy a certain structure.