Research map / Multi-agent systems and games / Cooperative multi-agent RL
Scalable Safe Policy Improvement for Factored Multi-Agent MDPs
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.
Proposes FV-MCTS-SPIBB, a scalable safe policy improvement method for factored multi-agent MDPs that combines MCTS with constrained Max-Plus/Var-El action selection and local state-action counting.
Problem
Safe policy improvement from offline trajectory data is not scalable to multi-agent MDPs with exponentially large joint state and action spaces; existing SPI methods only handle tiny problems (around 25 states, fewer than 10 actions).
Approach
Combines factored-value MCTS with SPIBB's bootstrapping: joint actions are taken from the behavior policy when bootstrapped, otherwise chosen by a constrained Max-Plus or Var-El over non-bootstrapped local actions, plus local (agent-level) state-action counting based on the transition factorization.
Key results
- On SysAdmin ring with 8 agents, FV-MCTS-SPIBB reaches about 22.0 return versus about 12.0 for the behavior policy and about 13.0 for MCTS-SPIBB.
- On multi-UAV Delivery, FV-MCTS-SPIBB-Max-Plus improves return from 457.7 to 655.6 with 8 agents and from 454.2 to 748.1 with 16 agents.
- With small datasets (5 trajectories) on SysAdmin, unsafe FV-MCTS-Max-Plus with MLE model falls below the behavior policy while FV-MCTS-SPIBB-Max-Plus stays above it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use FV-MCTS-SPIBB-Max-Plus instead of MCTS-SPIBB | SysAdmin ring, 8 agents · SysAdmin ring, 8 agents | average return: around 13.0 to around 22.0 | Helped |
| use FV-MCTS-SPIBB-Max-Plus instead of the behavior policy | SysAdmin ring, 8 agents · SysAdmin ring, 8 agents | average return: about 12.0 to around 22.0 | Helped |
| use FV-MCTS-SPIBB-Max-Plus instead of the MLE model without safety constraints | SysAdmin ring, 8 agents, 5 trajectories · SysAdmin ring, 8 agents, 5 trajectories | average return: 10.9 to 13.1 | Helped |
| use FV-MCTS-SPIBB-Max-Plus instead of the behavior policy | Multi-UAV Delivery, 8 agents · Multi-UAV Delivery, 8 agents | average return: 457.7 to 655.6 | Helped |
| use FV-MCTS-SPIBB-Max-Plus instead of the behavior policy | Multi-UAV Delivery, 16 agents · Multi-UAV Delivery, 16 agents | average return: 454.2 to 748.1 | Helped |
| use FV-MCTS-SPIBB-Max-Plus instead of FV-MCTS-Max-Plus with the MLE transition model | Multi-UAV Delivery, 8 agents, 50 trajectories · Multi-UAV Delivery, 8 agents, 50 trajectories | average return: 372.1 to 412.1 | Helped |
| replace Max-Plus with Var-El for action selection (ablation) | FV-MCTS-SPIBB on SysAdmin ring · SysAdmin ring | average return | Mixed |
| increase the number of simulations from 100 to 1000 (ablation) | FV-MCTS-SPIBB on SysAdmin, 8 agents · SysAdmin, 8 agents | average return | Helped |
| vary the UCT exploration constant (ablation) | FV-MCTS-SPIBB on SysAdmin, 8 agents · SysAdmin, 8 agents | average return | Mixed |
| vary the MCTS tree depth (ablation) | FV-MCTS-SPIBB on SysAdmin, 8 agents · SysAdmin, 8 agents | average return | Mixed |
Surprising findings
- With 16 agents, FV-MCTS-SPIBB-Var-El cannot compute actions in reasonable time, so Max-Plus is the only scalable variant at larger sizes.
- Other SPI methods besides MCTS-SPIBB could not scale beyond 3 agents in the tested domains.
Limitations
- Var-El is exponential in induced width and becomes infeasible at 16 agents in SysAdmin.
- Convergence of Max-Plus/Var-El with UCB exploration inside MCTS is not theoretically proven (open problem).
- Evaluated only on two synthetic multi-agent domains; the setting is offline with a fixed dataset and no sequential data collection.
Experimental setup
Datasets: multi-agent SysAdmin (ring and star topologies) multi-UAV Delivery
Benchmarks: multi-agent SysAdmin multi-UAV Delivery
Metrics: average return 15% CVaR
Baselines: SPIBB Lower-SPIBB DUIPI Adv-Approx-Soft-SPIBB Lower-Approx-Soft-SPIBB Approx-Soft-SPIBB MCTS-SPIBB FV-MCTS-Max-Plus FV-MCTS-Var-El
Builds on: SPIBB MCTS-SPIBB FV-MCTS with Max-Plus Factored SPIBB Var-El
Closest papers by meaning
- Scalable Constrained Policy Optimization for Safe Multi-agent Reinforcement Learning (NeurIPS 2024 · similarity 0.90)
- Discrete GCBF Proximal Policy Optimization for Multi-agent Safe Optimal Control (ICLR 2025 · similarity 0.87)
- HMARL-CBF – Hierarchical Multi-Agent Reinforcement Learning with Control Barrier Functions for Safety-Critical Autonomous Systems (NeurIPS 2025 · similarity 0.87)
- Embedding Safety into RL: A New Take on Trust Region Methods (ICML 2025 · similarity 0.86)
- Locally Interdependent Multi-Agent MDP: Theoretical Framework for Decentralized Agents with Dynamic Dependencies (ICML 2024 · similarity 0.86)
- AdvEvo-MARL: Shaping Internalized Safety through Adversarial Co-Evolution in Multi-Agent Reinforcement Learning (ICML 2026 · similarity 0.85)
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.