Research map / Multi-agent systems and games / Cooperative multi-agent RL
Multi-agent Markov Entanglement
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.
Shows that multi-agent MDP value decomposition into a sum of local Q-functions is exact iff the joint transition matrix is separable (a Markov analogue of quantum entanglement), bounds decomposition error by a Markov entanglement measure, and shows index policies in RMAB have O(sqrt N) decomposition error.
Problem
Value decomposition of the global value function into a sum of local value functions is widely used in multi-agent RL and dynamic programming, but there is little theory on when and why it works for multi-agent Markov systems.
Approach
Defines Markov entanglement: a joint transition matrix is separable if it is a (linear, possibly negative-coefficient) combination of tensor products of local transition matrices. Exact Q-decomposition holds iff separable; a distance-to-separable-set measure bounds decomposition error under TV, agent-wise TV, and stationary-weighted norms. Applies mean-field analysis to show index policies in RMAB
Key results
- Markov entanglement is necessary and sufficient for exact Q-value decomposition under arbitrary rewards (two-agent).
- For N-agent RMAB under index policies satisfying non-degeneracy and UGAP, entanglement is bounded by C/sqrt(N), giving decomposition error O(sqrt N).
- In the ride-hailing simulator, the estimated Markov entanglement decays as O(1/sqrt N) and relative decomposition error becomes <=3% for large N.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a separable transition matrix | Two-agent MDP value decomposition · Exact Q-value decomposition | Q-value decomposition error: 0 | Helped |
| Apply any index policy satisfying non-degeneracy and UGAP | N-agent RMAB · RMAB | μ-weighted decomposition error: O(√N) | Helped |
| Increase the number of agents under an index policy | Circulant RMAB · Circulant RMAB | Markov entanglement: O(1/√N) | Helped |
| Increase the number of drivers | Ride-hailing simulator · Ride-hailing simulator | decomposition error relative to global Q-values: O(1/√N); ≤3% | Helped |
| Measure entanglement with agent-wise total variation instead of total variation | Two-agent MDP decomposition error bound · General two-agent MDPs | tightness of the entanglement bound | Helped |
| Use μ-weighted agent-wise total variation | Multi-agent MDP decomposition error bound · General multi-agent MDPs | decomposition error norm | Mixed |
Surprising findings
- Separability requires negative mixture coefficients: the convex-combination set is strictly smaller than the linear-combination set.
- Decomposition error bounds are worst-case; high entanglement can still yield zero error when rewards are zero.
Limitations
- Exact decomposition theory covers only additive local Q-functions; the mean-field O(1/sqrt N) result relies on non-degeneracy and UGAP assumptions.
- Theoretical decay of ride-hailing entanglement is conjectured rather than proven.
Experimental setup
Datasets: NYC yellow cab data
Benchmarks: circulant RMAB benchmark ride-hailing simulator
Metrics: Markov entanglement estimate mu-weighted decomposition error decomposition error relative to global Q-value
Builds on: Whittle index policy weakly-coupled MDP quantum entanglement separability temporal difference learning
Closest papers by meaning
- Quantum Algorithms for Finite-horizon Markov Decision Processes (ICML 2025 · similarity 0.87)
- eQMARL: Entangled Quantum Multi-Agent Reinforcement Learning for Distributed Cooperation over Quantum Channels (ICLR 2025 · similarity 0.84)
- Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward Markov Decision Processes (ICML 2025 · similarity 0.84)
- REValueD: Regularised Ensemble Value-Decomposition for Factorisable Markov Decision Processes (ICLR 2024 · similarity 0.84)
- Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Games (ICML 2024 · similarity 0.83)
- Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regret (ICML 2024 · similarity 0.83)
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.