Safety
Fast Last-Iterate Convergence in Zero-Sum Markov Games with Bandit Feedback
arXiv:2610.05968v1 Announce Type: new Abstract: We study last-iterate convergence in unknown two-player zero-sum discounted Markov games with bandit feedback. The players learn independently along a s
arXiv:2610.05968v1 Announce Type: new 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{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{O}(t^{-1/(9+nu)}) rate of Cai et al. (2023), for any fixed nu>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.
Related
- The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
- Fairness in two-player zero-sum games with bandit feedback
- GARIP: A Running-Average Moving Reference for Last-Iterate Self-Play in Two-Player Zero-Sum Games
- Minimax Last-Iterate Convergence in Matrix Games with Observed Actions
Source: arXiv cs.LG | 2026-10-06