Algorithm achieves optimal learning in two-player matrix games
Minimax Last-Iterate Convergence in Matrix Games with Observed Actions
Machine LearningComputer Science and Game Theory
Summary
This paper looks at how two players can learn to play a zero-sum game — where one wins what the other loses — when they don’t initially know the game’s payoffs but can observe each other’s moves. The authors developed an algorithm that learns to play nearly as well as the best possible strategy by the last round of play, improving on past methods especially when there are many possible actions. Their method is both fast to run and uses little memory. The results provide a mathematically optimal balance between learning speed and game complexity.
What this means in practice
- •For algorithm engineers: Design efficient learning algorithms for strategic interactions with limited feedback and many actions.
- •For online advertising teams: Optimize bidding strategies in competitive auctions where opponent behavior is partially observable but payoff details are unknown.
A theory result. No direct application yet.
Authors
Yuheng Zhang
Abstract
We study last-iterate convergence in unknown two-player zero-sum matrix games with bandit payoff feedback and observed opponent actions. For games with $d$ actions per player, we develop an algorithm achieving a duality gap of $\widetilde{\mathcal{O}}(\sqrt{d/t})$ with high probability, simultaneously at every round $t$. This improves the dimension dependence of the best previously known guarantee by a factor of $d^{3/2}$. The rate matches a standard bandit lower bound, establishing minimax optimality in both the number of actions and the number of rounds, up to logarithmic factors. The algorithm is computationally efficient, requiring only $\mathcal{O}(d)$ time and memory per round. Our technical contribution is a joint design of adaptive averaging and corrected exponential weights that absorbs estimation variance, together with a potential argument that bounds phase durations.