Exploiting Approximate Symmetry for Efficient Multi-Agent Reinforcement Learning

2024-08-27 · Batuhan Yardim, Niao He

Mean-field games (MFG) have become significant tools for solving large-scale multi-agent reinforcement learning problems under symmetry. However, the assumption of exact symmetry limits the applicability of MFGs, as real-world scenarios often feature inherent heterogeneity. Furthermore, most works on MFG assume access to a known MFG model, which might not be readily available for real-world finite-agent games. In this work, we broaden the applicability of MFGs by providing a methodology to extend any finite-player, possibly asymmetric, game to an "induced MFG". First, we prove that $N$-player dynamic games can be symmetrized and smoothly extended to the infinite-player continuum via explicit Kirszbraun extensions. Next, we propose the notion of $\alpha,\beta$-symmetric games, a new class of dynamic population games that incorporate approximate permutation invariance. For $\alpha,\beta$-symmetric games, we establish explicit approximation bounds, demonstrating that a Nash policy of the induced MFG is an approximate Nash of the $N$-player dynamic game. We show that TD learning converges up to a small bias using trajectories of the $N$-player game with finite-sample guarantees, permitting symmetrized learning without building an explicit MFG model. Finally, for certain games satisfying monotonicity, we prove a sample complexity of $\widetilde{\mathcal{O}}(\varepsilon^{-6})$ for the $N$-agent game to learn an $\varepsilon$-Nash up to symmetrization bias. Our theory is supported by evaluations on MARL benchmarks with thousands of agents.

📄 PDF Abstract BibTeX arXiv:2408.15173

Code (0)

등록된 구현이 없습니다.

Tasks

Multi-agent Reinforcement Learning reinforcement-learning Reinforcement Learning

ESP: Exploiting Symmetry Prior for Multi-Agent Reinforcement Learning

2023-07-30 · Xin Yu, Rongye Shi, Pu Feng, Yongkai Tian 외

Multi-agent reinforcement learning (MARL) has achieved promising results in recent years. However, most existing reinforcement learning methods require a large amount of data for model training. In addition, data-efficie…

Data Augmentation Multi-agent Reinforcement Learning reinforcement-learning Reinforcement Learning

Approximate Equivariance in Reinforcement Learning

2024-11-06 · Jung Yeon Park, Sujay Bhatt, Sihan Zeng, Lawson L. S. Wong 외

Equivariant neural networks have shown great success in reinforcement learning, improving sample efficiency and generalization when there is symmetry in the task. However, in many problems, only approximate symmetry is p…

continuous-control Continuous Control reinforcement-learning Reinforcement Learning+1

EqR: Equivariant Representations for Data-Efficient Reinforcement Learning

2021-09-29 · Arnab Kumar Mondal, Vineet Jain, Kaleem Siddiqi, Siamak Ravanbakhsh

We study different notions of equivariance as an inductive bias in Reinforcement Learning (RL) and propose new mechanisms for recovering representations that are equivariant to both an agent’s action, and symmetry transf…

Atari Games Inductive Bias reinforcement-learning Reinforcement Learning+1

Common Information based Approximate State Representations in Multi-Agent Reinforcement Learning

2021-10-25 · Hsu Kao, Vijay Subramanian

Due to information asymmetry, finding optimal policies for Decentralized Partially Observable Markov Decision Processes (Dec-POMDPs) is hard with the complexity growing doubly exponentially in the horizon length. The cha…

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

Exploiting Symmetry in Dynamics for Model-Based Reinforcement Learning with Asymmetric Rewards

2024-03-27 · Yasin Sonmez, Neelay Junnarkar, Murat Arcak

Recent work in reinforcement learning has leveraged symmetries in the model to improve sample efficiency in training a policy. A commonly used simplifying assumption is that the dynamics and reward both exhibit the same …

Model-based Reinforcement Learning reinforcement-learning Reinforcement Learning