# Multi-agent Markov Entanglement

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 27 of its 57 references that are in the map.
- First posted on arXiv 3 Jun 2025.

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

- [Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2003.08839/) (2020)
- [QTRAN: Learning to Factorize with Transformation for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1905.05408/) (2019)
- [QPLEX: Duplex Dueling Multi-Agent Q-Learning](https://mlsanity.com/paper/2008.01062/) (2020)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [MAVEN: Multi-Agent Variational Exploration](https://mlsanity.com/paper/1910.07483/) (2019)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [Influence-Based Multi-Agent Exploration](https://mlsanity.com/paper/1910.05512/) (2019)
- [The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems](https://mlsanity.com/paper/2011.10124/) (2020)
- [Whittle index based Q-learning for restless bandits with average reward](https://mlsanity.com/paper/2004.14427/) (2020)
- [Near-optimal Reinforcement Learning in Factored MDPs](https://mlsanity.com/paper/1403.3741/) (2014)
- [Learn to Intervene: An Adaptive Learning Policy for Restless Bandits in Application to Preventive Healthcare](https://mlsanity.com/paper/2105.07965/) (2021)
- [NeurWIN: Neural Whittle Index Network For Restless Bandits Via Deep RL](https://mlsanity.com/paper/2110.02128/) (2021)
- [Towards Understanding Cooperative Multi-Agent Q-Learning with Value Factorization](https://mlsanity.com/paper/2006.00587/) (2020)
- [Temporal Difference Learning as Gradient Splitting](https://mlsanity.com/paper/2010.14657/) (2020)
- [Optimistic Whittle Index Policy: Online Learning for Restless Bandits](https://mlsanity.com/paper/2205.15372/) (2022)
- [Restless Bandits with Many Arms: Beating the Central Limit Theorem](https://mlsanity.com/paper/2107.11911/) (2021)
- [Rethinking Individual Global Max in Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2209.09640/) (2022)
- [Correcting for Interference in Experiments: A Case Study at Douyin](https://mlsanity.com/paper/2305.02542/) (2023)
- [LP-based policies for restless bandits: necessary and sufficient conditions for (exponentially fast) asymptotic optimality](https://mlsanity.com/paper/2106.10067/) (2021)
- [Near-optimality for infinite-horizon restless bandits with many arms](https://mlsanity.com/paper/2203.15853/) (2022)
- [Policy Optimization for Personalized Interventions in Behavioral Health](https://mlsanity.com/paper/2303.12206/) (2023)
- [A Better Match for Drivers and Riders: Reinforcement Learning at Lyft](https://mlsanity.com/paper/2310.13810/) (2023)
- [Reoptimization Nearly Solves Weakly Coupled Markov Decision Processes](https://mlsanity.com/paper/2211.01961/) (2022)
- [Blind Dynamic Resource Allocation in Closed Networks via Mirror Backpressure](https://mlsanity.com/paper/1903.02764/) (2019)
- [Understanding Value Decomposition Algorithms in Deep Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2202.04868/) (2022)
- [Weakly Coupled Deep Q-Networks](https://mlsanity.com/paper/2310.18803/) (2023)
- [Global Rewards in Restless Multi-Armed Bandits](https://mlsanity.com/paper/2406.00738/) (2024)

## Abstract (arXiv)

Value decomposition has long been a fundamental technique in multi-agent dynamic programming and reinforcement learning (RL). Specifically, the value function of a global state (s1,s2,ldots,sN) is often approximated as the sum of local functions: V(s1,s2,ldots,sN)≈sumi=1N Vi(si). This approach traces back to the index policy in restless multi-armed bandit problems and has found various applications in modern RL systems. However, the theoretical justification for why this decomposition works so effectively remains underexplored. In this paper, we uncover the underlying mathematical structure that enables value decomposition. We demonstrate that a multi-agent Markov decision process (MDP) permits value decomposition if and only if its transition matrix is not "entangled" -- a concept analogous to quantum entanglement in quantum physics. Drawing inspiration from how physicists measure quantum entanglement, we introduce how to measure the "Markov entanglement" for multi-agent MDPs and show that this measure can be used to bound the decomposition error in general multi-agent MDPs. Using the concept of Markov entanglement, we proved that a widely-used class of index policies is weakly entangled and enjoys a sublinear mathcal O(√N) scale of decomposition error for N-agent systems. Finally, we show how Markov entanglement can be efficiently estimated in practice, providing practitioners with an empirical proxy for the quality of value decomposition.