Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback
This work addresses the challenge of efficient game-solving in AI and multi-agent systems by providing accelerated convergence guarantees under limited feedback, though it is incremental as it builds on existing bandit algorithms for a specific game class.
The paper tackles the problem of accelerating no-regret learning in two-player zero-sum games under bandit feedback, showing that using the Tsallis-INF algorithm yields an instance-dependent regret bound of O(c1 log T + sqrt(c2 T)), with c2 becoming zero when a pure strategy Nash equilibrium exists, leading to optimal regret and near-optimal sample complexity for equilibrium identification.
No-regret self-play learning dynamics have become one of the premier ways to solve large-scale games in practice. Accelerating their convergence via improving the regret of the players over the naive $O(\sqrt{T})$ bound after $T$ rounds has been extensively studied in recent years, but almost all studies assume access to exact gradient feedback. We address the question of whether acceleration is possible under bandit feedback only and provide an affirmative answer for two-player zero-sum normal-form games. Specifically, we show that if both players apply the Tsallis-INF algorithm of Zimmert and Seldin (2018, arXiv:1807.07623), then their regret is at most $O(c_1 \log T + \sqrt{c_2 T})$, where $c_1$ and $c_2$ are game-dependent constants that characterize the difficulty of learning -- $c_1$ resembles the complexity of learning a stochastic multi-armed bandit instance and depends inversely on some gap measures, while $c_2$ can be much smaller than the number of actions when the Nash equilibria have a small support or are close to the boundary. In particular, for the case when a pure strategy Nash equilibrium exists, $c_2$ becomes zero, leading to an optimal instance-dependent regret bound as we show. We additionally prove that in this case, our algorithm also enjoys last-iterate convergence and can identify the pure strategy Nash equilibrium with near-optimal sample complexity.