Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximation

2023-02-07 · Qiwen Cui, Kaiqing Zhang, Simon S. Du

We propose a new model, independent linear Markov game, for multi-agent reinforcement learning with a large state space and a large number of agents. This is a class of Markov games with independent linear function approximation, where each agent has its own function approximation for the state-action value functions that are marginalized by other players' policies. We design new algorithms for learning the Markov coarse correlated equilibria (CCE) and Markov correlated equilibria (CE) with sample complexity bounds that only scale polynomially with each agent's own function class complexity, thus breaking the curse of multiagents. In contrast, existing works for Markov games with function approximation have sample complexity bounds scale with the size of the \emph{joint action space} when specialized to the canonical tabular Markov game setting, which is exponentially large in the number of agents. Our algorithms rely on two key technical innovations: (1) utilizing policy replay to tackle non-stationarity incurred by multiple agents and the use of function approximation; (2) separating learning Markov equilibria and exploration in the Markov games, which allows us to use the full-information no-regret learning oracle instead of the stronger bandit-feedback no-regret learning oracle used in the tabular setting. Furthermore, we propose an iterative-best-response type algorithm that can learn pure Markov Nash equilibria in independent linear Markov potential games. In the tabular case, by adapting the policy replay mechanism for independent linear Markov games, we propose an algorithm with $\widetilde{O}(\epsilon^{-2})$ sample complexity to learn Markov CCE, which improves the state-of-the-art result $\widetilde{O}(\epsilon^{-3})$ in Daskalakis et al. 2022, where $\epsilon$ is the desired accuracy, and also significantly improves other problem parameters.

📄 PDF Abstract BibTeX arXiv:2302.03673

Code (0)

등록된 구현이 없습니다.

Tasks

Multi-agent Reinforcement Learning

The Blessing and Curse of Dimensionality in Safety Alignment

2025-07-27 · Rachel S. Y. Teo, Laziz U. Abdullaev, Tan M. Nguyen arxiv

The focus on safety alignment in large language models (LLMs) has increased significantly due to their widespread adoption across different domains. The scale of LLMs play a contributing role in their success, and the gr…

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

2021-10-27 · Chi Jin, Qinghua Liu, Yuanhao Wang, Tiancheng Yu

A major challenge of multiagent reinforcement learning (MARL) is the curse of multiagents, where the size of the joint action space scales exponentially with the number of agents. This remains to be a bottleneck for desi…

Medical Visual Question Answering Q-Learning

Breaking the Curse of Many Agents: Provable Mean Embedding Q-Iteration for Mean-Field Reinforcement Learning

2020-06-21 · Lingxiao Wang, Zhuoran Yang, Zhaoran Wang

Multi-agent reinforcement learning (MARL) achieves significant empirical successes. However, MARL suffers from the curse of many agents. In this paper, we exploit the symmetry of agents in MARL. In the most generic form,…

Multi-agent Reinforcement Learning reinforcement-learning Reinforcement Learning (RL)

Breaking the Curse of Many Agents: Provable Mean Embedding $Q$-Iteration for Mean-Field Reinforcement Learning

2020-01-01 · ICML 2020 1 · Lingxiao Wang, Zhuoran Yang, Zhaoran Wang

Multi-agent Reinforcement Learning reinforcement-learning Reinforcement Learning (RL)

Breaking the curse of dimensionality with Isolation Kernel

2021-09-29 · Kai Ming Ting, Takashi Washio, Ye Zhu, Yang Xu

The curse of dimensionality has been studied in different aspects. However, breaking the curse has been elusive. We show for the first time that it is possible to break the curse using the recently introduced Isolation K…

Clustering