# Locally Interdependent Multi-Agent MDP: Theoretical Framework for Decentralized Agents with Dynamic Dependencies

arXiv: https://arxiv.org/abs/2406.06823 · HTML: https://mlsanity.com/paper/2406.06823/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 38 references that are in the map.
- First posted on arXiv 10 Jun 2024.

## Builds on (most cited first, 20 of 20)

- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [The Complexity of Decentralized Control of Markov Decision Processes](https://mlsanity.com/paper/1301.3836/) (2013)
- [Mean Field Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1802.05438/) (2018)
- [Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agents](https://mlsanity.com/paper/1802.08757/) (2018)
- [V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL](https://mlsanity.com/paper/2110.14555/) (2021)
- [Survey of Deep Reinforcement Learning for Motion Planning of Autonomous Vehicles](https://mlsanity.com/paper/2001.11231/) (2020)
- [Near-Optimal Reinforcement Learning with Self-Play](https://mlsanity.com/paper/2006.12007/) (2020)
- [Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium](https://mlsanity.com/paper/2002.07066/) (2020)
- [Towards Optimally Decentralized Multi-Robot Collision Avoidance via Deep Reinforcement Learning](https://mlsanity.com/paper/1709.10082/) (2017)
- [Model-Free Mean-Field Reinforcement Learning: Mean-Field MDP and Mean-Field Q-Learning](https://mlsanity.com/paper/1910.12802/) (2019)
- [Multi-Agent Connected Autonomous Driving using Deep Reinforcement Learning](https://mlsanity.com/paper/1911.04175/) (2019)
- [Scalable Multi-Agent Reinforcement Learning for Networked Systems with Average Reward](https://mlsanity.com/paper/2006.06626/) (2020)
- [Mean-Field Controls with Q-learning for Cooperative MARL: Convergence and Complexity Analysis](https://mlsanity.com/paper/2002.04131/) (2020)
- [The Power of Exploiter: Provable Multi-Agent RL in Large State Spaces](https://mlsanity.com/paper/2106.03352/) (2021)
- [Towards General Function Approximation in Zero-Sum Markov Games](https://mlsanity.com/paper/2107.14702/) (2021)
- [Multi-Agent Reinforcement Learning in Stochastic Networked Systems](https://mlsanity.com/paper/2006.06555/) (2020)
- [Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximation](https://mlsanity.com/paper/2302.06606/) (2023)
- [Scalable Reinforcement Learning for Multi-Agent Networked Systems](https://mlsanity.com/paper/1912.02906/) (2019)
- [A Multi-Agent Off-Policy Actor-Critic Algorithm for Distributed Reinforcement Learning](https://mlsanity.com/paper/1903.06372/) (2019)
- [Decentralized Control of Quadrotor Swarms with End-to-end Deep Reinforcement Learning](https://mlsanity.com/paper/2109.07735/) (2021)

## Built on by (most cited first, 6 of 6)

- [Mean-Field Sampling for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2412.00661/) (2024)
- [Exploiting Structure in Offline Multi-Agent RL: The Benefits of Low Interaction Rank](https://mlsanity.com/paper/2410.01101/) (2024)
- [Learning Approximate Nash Equilibria in Cooperative Multi-Agent Reinforcement Learning via Mean-Field Subsampling](https://mlsanity.com/paper/2603.03759/) (2026)
- [Revisiting Policy Gradients for Restricted Policy Classes: Escaping Myopic Local Optima with k-step Policy Gradients](https://mlsanity.com/paper/2605.10909/) (2026)
- [A Theoretical Framework for Parallel Lifelong MAPF Using Group Decentralized Planning](https://mlsanity.com/paper/2608.17928/) (2026)
- [Observe, Share, or Predict? Disentangling Partner Information in Embodied Multi-Agent Collaboration](https://mlsanity.com/paper/2610.16895/) (2026)

## Abstract (arXiv)

Many multi-agent systems in practice are decentralized and have dynamically varying dependencies. There has been a lack of attempts in the literature to analyze these systems theoretically. In this paper, we propose and theoretically analyze a decentralized model with dynamically varying dependencies called the Locally Interdependent Multi-Agent MDP. This model can represent problems in many disparate domains such as cooperative navigation, obstacle avoidance, and formation control. Despite the intractability that general partially observable multi-agent systems suffer from, we propose three closed-form policies that are theoretically near-optimal in this setting and can be scalable to compute and store. Consequentially, we reveal a fundamental property of Locally Interdependent Multi-Agent MDP's that the partially observable decentralized solution is exponentially close to the fully observable solution with respect to the visibility radius. We then discuss extensions of our closed-form policies to further improve tractability. We conclude by providing simulations to investigate some long horizon behaviors of our closed-form policies.