Research map / Multi-agent systems and games / Cooperative multi-agent RL
Exploiting Structure in Offline Multi-Agent RL: The Benefits of Low Interaction Rank
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces interaction rank (IR), a structural assumption under which reward/critic functions are more robust to distribution shift, and uses it with chi^2 regularization and no-regret policy updates to obtain decentralized, polynomially sample-efficient offline MARL algorithms for contextual games and decoupled-transition Markov games, with a small experiment favoring low-IR critics.
Problem
Learning an approximate coarse correlated equilibrium from offline multi-agent data is computationally hard and sample complexity can scale exponentially with the number of agents under unilateral concentrability.
Approach
Define interaction rank K as the maximum order of additive decomposition of a function over agents; show low-IR functions have error under distribution shift that scales with K rather than the number of agents, and combine IR-structured reward/critic classes with chi^2 regularization and decentralized no-regret policy mirror descent.
Key results
- In the 50-agent 2-IR synthetic game, the 2-IR critic achieves the smallest maximum gap by a significant margin over joint-action and 1-IR critics.
- The 1-IR critic performs worst among the three critic types in the 2-IR environment, despite being the simplest.
- Theory: sample complexity for DR-AC scales polynomially in N for fixed K, under single-agent all-policy concentrability.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a 2-IR critic instead of a joint-action critic | TD3+BC · Synthetic contextual game (2-IR reward) | maximum gap | Helped |
| Use a 2-IR critic instead of a 1-IR critic | TD3+BC · Synthetic contextual game (2-IR reward) | maximum gap | Helped |
| Use a 1-IR critic instead of a 2-IR critic | TD3+BC · Synthetic contextual game (2-IR reward) | maximum gap | Hurt |
| Use a 1-IR critic instead of a joint-action critic | TD3+BC · Synthetic contextual game (1-IR reward) | maximum gap | Hurt |
| Use a 2-IR critic instead of a joint-action critic | TD3+BC · Synthetic contextual game (1-IR reward) | maximum gap | Helped |
Surprising findings
- The simplest 1-IR critic performs worst in the offline 2-IR setting, indicating single-agent critics can fail catastrophically offline.
Limitations
- Experiments are limited to a simple synthetic contextual game with N=50 agents.
- Theoretical guarantees rely on single-agent all-policy concentrability and realizability assumptions.
- Extension to more general Markov games without decoupled transitions is left open.
Experimental setup
Datasets: synthetic contextual game data
Benchmarks: synthetic 50-agent contextual game with 2-IR reward synthetic 1-IR reward game
Metrics: maximum gap across agents
Baselines: joint-action critic 1-IR critic BCEL
Builds on: TD3+BC policy mirror descent BCEL
Closest papers by meaning
- Offline Multi-Agent Reinforcement Learning via In-Sample Sequential Policy Optimization (AAAI 2025 · similarity 0.90)
- Dispelling the Mirage of Progress in Offline MARL through Standardised Baselines and Evaluation (NeurIPS 2024 · similarity 0.90)
- ComaDICE: Offline Cooperative Multi-Agent Reinforcement Learning with Stationary Distribution Shift Regularization (ICLR 2025 · similarity 0.89)
- Foundations of Multi-Agent Learning in Dynamic Environments: Where Reinforcement Learning Meets Strategic Decision-Making (AAAI 2025 · similarity 0.89)
- O-MAPL: Offline Multi-agent Preference Learning (ICML 2025 · similarity 0.88)
- Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games (ICML 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.