Decentralized Q-Learning in Zero-sum Markov Games

Abstract

We study multi-agent reinforcement learning (MARL) in infinite-horizon discounted zero-sum Markov games. We focus on the practical but challenging setting of decentralized MARL, where agents make decisions without coordination by a centralized controller, but only based on their own payoffs and local actions executed. The agents need not observe the opponent's actions or payoffs, possibly being even oblivious to the presence of the opponent, nor be aware of the zero-sum structure of the underlying game, a setting also referred to as radically uncoupled in the literature of learning in games. In this paper, we develop a radically uncoupled Q-learning dynamics that is both rational and convergent: the learning dynamics converges to the best response to the opponent's strategy when the opponent follows an asymptotically stationary strategy; when both agents adopt the learning dynamics, they converge to the Nash equilibrium of the game. The key challenge in this decentralized setting is the non-stationarity of the environment from an agent's perspective, since both her own payoffs and the system evolution depend on the actions of other agents, and each agent adapts her policies simultaneously and independently. To address this issue, we develop a two-timescale learning dynamics where each agent updates her local Q-function and value function estimates concurrently, with the latter happening at a slower timescale.

To appear at NeurIPS 2021. Strengthened the results in Theorem 1 and Corollary 1

References in corpus (9)

• Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm
• StarCraft II: A New Challenge for Reinforcement Learning
• Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving
• Policy Optimization Provably Converges to Nash Equilibria in Zero-Sum Linear Quadratic Games
• Provable Self-Play Algorithms for Competitive Reinforcement Learning
• Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexity
• Independent Policy Gradient Methods for Competitive Reinforcement Learning
• Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Games
• On Reinforcement Learning for Turn-based Zero-sum Markov Games

Cited by in corpus (1)

• V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL