Research map / Multi-agent systems and games / Cooperative multi-agent RL
Locally Interdependent Multi-Agent MDP: Theoretical Framework for Decentralized Agents with Dynamic Dependencies
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 the Locally Interdependent Multi-Agent MDP, a decentralized model with time-varying proximity-based reward dependencies, and derives three closed-form group decentralized policies with near-optimal bounds matched by a lower bound, showing exponential decay in visibility radius.
Problem
Decentralized, partially observable multi-agent systems with dynamically varying local dependencies (e.g., cooperative navigation, obstacle avoidance, formation control) lack theoretical models and tractable near-optimal solutions.
Approach
Model agents in a metric space whose rewards depend on agents within a dependence radius R, with communication within visibility V > R; exploit a Dependence Time Lemma (a buffer of c = floor((V-R)/2) steps) to construct three closed-form group decentralized policies (Amalgam, Cutoff, First Step Finite Horizon Optimal) whose suboptimality decays as gamma^c, plus a matching lower bound.
Key results
- Amalgam Policy bound |V*-V^lambda| <= 2/(1-gamma)^2 * gamma^(c+1) * r_max, Cutoff bound (2-gamma)/(1-gamma)^2 * gamma^(c+1) * r_max, and First Step bound 2/(1-gamma) * gamma^(c+1) * r_max, all matched by a lower bound of (1/2) gamma^(c+2)/(1-gamma) r_max up to constants.
- Corollary: the gap between optimal fully observable value and best group decentralized policy value is O(gamma^V), i.e., exponentially small in visibility.
- In the Bullseye toy example, Amalgam Policy with visibility 25, 35, 45 achieves discounted rewards 6.74, 8.26, 8.85 versus optimal 8.85, while the Cutoff Policy gets -5.38.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase visibility from \mathcal V=25 to \mathcal V=35 | Amalgam Policy · Bullseye Problem | value error: 2.11 -> 0.59 | Helped |
| Increase visibility from \mathcal V=35 to \mathcal V=45 | Amalgam Policy · Bullseye Problem | value error: 0.59 -> 0 | Helped |
| Use the Amalgam Policy instead of the optimal policy | Bullseye Problem, \mathcal V=25 · Bullseye Problem | discounted reward: 8.85 -> 6.74 | Hurt |
| Use the Cutoff Policy instead of the optimal policy | Bullseye Problem, \mathcal V=25 · Bullseye Problem | discounted reward: 8.85 -> -5.38 | Hurt |
| Use the Cutoff Policy instead of the Amalgam Policy | Aisle Walk Problem · Aisle Walk Problem | discounted reward: 234.40 -> 400 | Helped |
| Use the Cutoff Policy instead of the optimal policy | Aisle Walk Problem · Aisle Walk Problem | discounted reward: 496.84 -> 400 | Hurt |
| Use the Amalgam Policy instead of the optimal policy | Highway Problem · Highway Problem | discounted reward: 73.5 -> 70.93 | Hurt |
| Use the Cutoff Policy instead of the optimal policy | Highway Problem · Highway Problem | discounted reward: 73.5 -> 0 | Hurt |
| Use the Amalgam or Cutoff Policy instead of the optimal policy | Lane Merging Problem · Lane Merging Problem | discounted reward: 2514.11 -> 2514.11 | No clear effect |
| Increase visibility | Amalgam, Cutoff, and First Step Finite Horizon Optimal Policies · General Locally Interdependent Multi-Agent MDP | value error: O(\gamma^{\mathcal V}) | Helped |
| Use the Cutoff Policy instead of the Amalgam Policy | Long-horizon settings · Locally Interdependent Multi-Agent MDP simulations | long-horizon performance | Mixed |
Surprising findings
- The Cutoff Policy performs poorly when interdependent rewards are penalties, exhibiting a 'penalty jittering' back-and-forth behavior.
- In the Highway toy problem the Cutoff Policy obtains 0 discounted reward, far below the Amalgam Policy's 70.93 versus optimal 73.5.
Limitations
- Results are theoretical with toy grid-world simulations only; no learning-based experiments.
- Group sizes can grow exponentially, so the closed-form policies remain intractable for large groups without extensions.
- Policies are memoryless and exhibit forgetfulness/penalty jittering in long-horizon settings with limited visibility.
Experimental setup
Benchmarks: Bullseye Problem Aisle Walk Problem Highway Problem Lane Merging Problem Bullseye Problem with Many Agents
Metrics: discounted sum of rewards value function gap to optimal
Baselines: optimal policy Amalgam Policy Cutoff Policy
Builds on: Dec-POMDP Interaction Driven Markov Game Network Distributed POMDP
Closest papers by meaning
- Learning to Act in Decentralized Partially Observable MDPs (ICML 2018 · similarity 0.88)
- Learn to Follow: Decentralized Lifelong Multi-Agent Pathfinding via Planning and Learning (AAAI 2024 · similarity 0.86)
- Scalable Safe Policy Improvement for Factored Multi-Agent MDPs (ICML 2024 · similarity 0.86)
- Graph Diffusion for Robust Multi-Agent Coordination (ICML 2025 · similarity 0.86)
- Learning Decentralized Partially Observable Mean Field Control for Artificial Collective Behavior (ICLR 2024 · similarity 0.85)
- Scalable Constrained Policy Optimization for Safe Multi-agent Reinforcement Learning (NeurIPS 2024 · 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.