Fast convergence of policies in zero sum markov games with limited feedback
Fast Last-Iterate Convergence in Zero-Sum Markov Games with Bandit Feedback
Machine LearningComputer Science and Game Theory
Summary
This paper looks at how two players learn strategies over time when they compete in a zero-sum game, but can only see limited information from the game. The authors develop a new learning algorithm called Adaptive Regularized TD Learning (ARTD) that improves how quickly the players’ strategies converge to an equilibrium. Unlike previous methods, ARTD works without knowing some key parameters ahead of time, and it ensures stable learning even when the players update independently. This means the strategies played get better faster, even when players do not observe each other's moves directly.
What this means in practice
- •For game ai developers: Improve training speed and stability of AI agents competing in strategic games with limited action observability.
- •For autonomous systems engineers: Enhance adaptive decision-making in multi-agent systems that learn from limited feedback without communication.
Authors
Yuheng Zhang
Abstract
We study last-iterate convergence in unknown two-player zero-sum discounted Markov games with bandit feedback. The players learn independently along a single trajectory without observing each other's actions. We develop Adaptive Regularized TD Learning (ARTD), which achieves a $\widetilde{\mathcal{O}}(t^{-1/4})$ duality gap bound for the current policies under a uniform hitting time assumption, with high probability simultaneously over all rounds and starting states. This improves the $\widetilde{\mathcal{O}}(t^{-1/(9+ν)})$ rate of Cai et al. (2023), for any fixed $ν>0$, under the same feedback model and hitting time assumption. Our algorithm requires no knowledge of the hitting time bound, the time horizon, or the confidence level. To stabilize policy learning as value estimates change, we separate fast temporal difference averaging from bounded value updates. We adapt log-barrier regularization to the progress of value estimation, controlling both policy and value errors throughout learning. Together, these mechanisms enable fast convergence of the policies actually played, even when the players learn independently from bandit feedback.