Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Model

2022-08-22 · Gen Li, Yuejie Chi, Yuting Wei, Yuxin Chen

This paper studies multi-agent reinforcement learning in Markov games, with the goal of learning Nash equilibria or coarse correlated equilibria (CCE) sample-optimally. All prior results suffer from at least one of the two obstacles: the curse of multiple agents and the barrier of long horizon, regardless of the sampling protocol in use. We take a step towards settling this problem, assuming access to a flexible sampling mechanism: the generative model. Focusing on non-stationary finite-horizon Markov games, we develop a fast learning algorithm called \myalg~and an adaptive sampling scheme that leverage the optimism principle in online adversarial learning (particularly the Follow-the-Regularized-Leader (FTRL) method). Our algorithm learns an $\varepsilon$-approximate CCE in a general-sum Markov game using $$ \widetilde{O}\bigg( \frac{H^4 S \sum_{i=1}^m A_i}{\varepsilon^2} \bigg) $$ samples, where $m$ is the number of players, $S$ indicates the number of states, $H$ is the horizon, and $A_i$ denotes the number of actions for the $i$-th player. This is minimax-optimal (up to log factor) when the number of players is fixed. When applied to two-player zero-sum Markov games, our algorithm provably finds an $\varepsilon$-approximate Nash equilibrium with minimal samples. Along the way, we derive a refined regret bound for FTRL that makes explicit the role of variance-type quantities, which might be of independent interest.

📄 PDF Abstract BibTeX arXiv:2208.10458

Code (0)

등록된 구현이 없습니다.

Tasks

Multi-agent Reinforcement Learning

Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game

2022-05-31 · Wei Xiong, Han Zhong, Chengshuai Shi, Cong Shen 외

Offline reinforcement learning (RL) aims at learning an optimal strategy using a pre-collected dataset without further interactions with the environment. While various algorithms have been proposed for offline RL in the …

Offline RL Reinforcement Learning (RL)

A Multi-Step Minimax Q-learning Algorithm for Two-Player Zero-Sum Markov Games

2024-07-05 · Shreyas S R, Antony Vijesh

An interesting iterative procedure is proposed to solve a two-player zero-sum Markov games. Under suitable assumption, the boundedness of the proposed iterates is obtained theoretically. Using results from stochastic app…

Q-Learning

When is Offline Two-Player Zero-Sum Markov Game Solvable?

2022-01-10 · Qiwen Cui, Simon S. Du

We study what dataset assumption permits solving offline two-player zero-sum Markov games. In stark contrast to the offline single-agent Markov decision process, we show that the single strategy concentration assumption …

Multi-agent Reinforcement Learning reinforcement-learning Reinforcement Learning (RL)Vocal Bursts Valence Prediction

Minimax-Optimal Multi-Agent Robust Reinforcement Learning

2024-12-27 · Yuchen Jiao, Gen Li

Multi-agent robust reinforcement learning, also known as multi-player robust Markov games (RMGs), is a crucial framework for modeling competitive interactions under environmental uncertainties, with wide applications in …

reinforcement-learning Reinforcement Learning

FM3Q: Factorized Multi-Agent MiniMax Q-Learning for Two-Team Zero-Sum Markov Game

2024-02-01 · Guangzheng Hu, Yuanheng Zhu, Haoran Li, Dongbin Zhao

Many real-world applications involve some agents that fall into two teams, with payoffs that are equal within the same team but of opposite sign across the opponent team. The so-called two-team zero-sum Markov games (2t0…

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