@inproceedings{
chakrabarti2023efficient,
title={Efficient Learning in Polyhedral Games via Best Response Oracles},
author={Darshan Chakrabarti and Gabriele Farina and Christian Kroer},
booktitle={OPT 2023: Optimization for Machine Learning},
year={2023},
url={https://openreview.net/forum?id=OwMafGz3KJ}
}
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.
Efficient Learning in Polyhedral Games via Best Response Oracles
Darshan Chakrabarti Gabriele Farina Christian Kroer