# Efficient Learning in Polyhedral Games via Best Response Oracles

arXiv: https://arxiv.org/abs/2312.03696 · HTML: https://mlsanity.com/paper/2312.03696/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Dec 2023.

## Built on by (most cited first, 3 of 3)

- [Full Swap Regret and Discretized Calibration](https://mlsanity.com/paper/2502.09332/) (2025)
- [Linear Convergence of the Frank-Wolfe Algorithm over Product Polytopes](https://mlsanity.com/paper/2505.11259/) (2025)
- [Pyramidal Width Can Increase Under Vertex Insertion](https://mlsanity.com/paper/2607.29555/) (2026)

## Abstract (arXiv)

We study online learning and equilibrium computation in games with polyhedral decision sets, a property shared by both normal-form games and extensive-form games (EFGs), when the learning agent is restricted to using a best-response oracle. We show how to achieve constant regret in zero-sum games and O(T1/4) regret in general-sum games while using only O(log t) best-response queries at a given iteration t, thus improving over the best prior result, which required O(T) queries per iteration. Moreover, our framework yields the first last-iterate convergence guarantees for self-play with best-response oracles in zero-sum games. This convergence occurs at a linear rate, though with a condition-number dependence. We go on to show a O(1/√T) best-iterate convergence rate without such a dependence. Our results build on linear-rate convergence results for variants of the Frank-Wolfe (FW) algorithm for strongly convex and smooth minimization problems over polyhedral domains. These FW results depend on a condition number of the polytope, known as facial distance. In order to enable application to settings such as EFGs, we show two broad new results: 1) the facial distance for polytopes in standard form is at least γ/√k where γ is the minimum value of a nonzero coordinate of a vertex of the polytope and k≤ n is the number of tight inequality constraints in the optimal face, and 2) the facial distance for polytopes of the form Aboldsymbolx=boldsymbolb,Cboldsymbolx≤boldsymbold, boldsymbolx≥ 0 where boldsymbolx∈ℝn, C≥boldsymbol0 is a nonzero integral matrix, and boldsymbold≥ boldsymbol0, is at least 1/(|C|_∞√n). This yields the first such results for several problems such as sequence-form polytopes, flow polytopes, and matching polytopes.