Independent and Decentralized Learning in Markov Potential Games

2022-05-29 · Chinmay Maheshwari, Manxi Wu, Druv Pai, Shankar Sastry

We study a multi-agent reinforcement learning dynamics, and analyze its asymptotic behavior in infinite-horizon discounted Markov potential games. We focus on the independent and decentralized setting, where players do not know the game parameters, and cannot communicate or coordinate. In each stage, players update their estimate of Q-function that evaluates their total contingent payoff based on the realized one-stage reward in an asynchronous manner. Then, players independently update their policies by incorporating an optimal one-stage deviation strategy based on the estimated Q-function. Inspired by the actor-critic algorithm in single-agent reinforcement learning, a key feature of our learning dynamics is that agents update their Q-function estimates at a faster timescale than the policies. Leveraging tools from two-timescale asynchronous stochastic approximation theory, we characterize the convergent set of learning dynamics.

📄 PDF Abstract BibTeX arXiv:2205.14590

Code (0)

등록된 구현이 없습니다.

Tasks

Multi-agent Reinforcement Learning reinforcement-learning Reinforcement Learning

Convergence of Decentralized Actor-Critic Algorithm in General-sum Markov Games

2024-09-06 · Chinmay Maheshwari, Manxi Wu, Shankar Sastry

Markov games provide a powerful framework for modeling strategic multi-agent interactions in dynamic environments. Traditionally, convergence properties of decentralized learning algorithms in these settings have been es…

On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learning

2021-10-12 · Weichao Mao, Lin F. Yang, Kaiqing Zhang, Tamer Başar

Multi-agent reinforcement learning (MARL) algorithms often suffer from an exponential sample complexity dependence on the number of agents, a phenomenon known as \emph{the curse of multiagents}. In this paper, we address…

Multi-agent Reinforcement Learning Q-Learning reinforcement-learning Reinforcement Learning (RL)+1

Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games

2023-03-22 · Dylan J. Foster, Noah Golowich, Sham M. Kakade

We consider the problem of decentralized multi-agent reinforcement learning in Markov games. A fundamental question is whether there exist algorithms that, when adopted by all agents and run independently in a decentrali…

Computational Efficiency Multi-agent Reinforcement Learning

Scalable and Independent Learning of Nash Equilibrium Policies in $n$-Player Stochastic Games with Unknown Independent Chains

2023-12-04 · Tiancheng Qin, S. Rasoul Etesami

We study a subclass of $n$-player stochastic games, namely, stochastic games with independent chains and unknown transition matrices. In this class of games, players control their own internal Markov chains whose transit…

Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Games

2021-10-12 · Weichao Mao, Tamer Başar

This paper addresses the problem of learning an equilibrium efficiently in general-sum Markov games through decentralized multi-agent reinforcement learning. Given the fundamental difficulty of calculating a Nash equilib…

Multi-agent Reinforcement Learning Q-Learning reinforcement-learning Reinforcement Learning+1