Multi-agent Markov Entanglement¶

🕒 Published (v1): 2025-01-01 · Source: NeurIPS · Venue: NeurIPS 2025 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

TL;DR¶

This paper introduces Markov entanglement—a concept analogous to quantum entanglement—as the exact mathematical condition governing when value decomposition works in multi-agent MDPs. It proves that a transition matrix admits additive Q-value decomposition if and only if it is "separable" (expressible as a linear combination of tensor products of local transitions), and derives decomposition error bounds proportional to the degree of entanglement. For the practically important class of index policies on Restless Multi-Armed Bandits, the decomposition error scales sublinearly as O(√N) with the number of agents.

Problem¶

Value decomposition V(s₁,...,sN) ≈ Σᵢ Vᵢ(sᵢ) is widely used in MARL (QMIX, VDN, ride-hailing dispatch at DiDi/Lyft) yet has no theoretical foundation explaining when and why it is accurate. Prior work showed Lagrange relaxation can have arbitrarily large errors for general MDPs, and empirical failures have been documented, but a complete characterization of the conditions enabling decomposition has been absent.

Method¶

The paper defines a two-agent MDP as Markov-separable if its policy-induced transition matrix Pᵅᴬᴮ decomposes as a linear combination Σⱼ xⱼ P^(j)_A ⊗ P^(j)_B (without requiring xⱼ ≥ 0, unlike quantum entanglement). The core results are:

Exact decomposition (Theorems 1–2): Markov separability is both sufficient and necessary for exact Q-value decomposition under any reward kernel. Sufficiency uses an "absorbing" tensor-product technique; necessity constructs adversarial rewards from the orthogonal complement of the separable set.
Decomposition error bounds (Theorems 3–5): For entangled systems, error is upper-bounded by E(Pᵅᴬᴮ) = minₚ∈PSEP d(Pᵅᴬᴮ, P), measured via Total Variation, Agent-wise TV (ATV), or stationary-distribution-weighted variants. The bound is 4γ(EA·r^A_max + EB·r^B_max)/(1−γ)².
Index policy analysis (Theorem 6): For N-agent RMABs under any index policy (Whittle, Gittins, fluid-based), the per-agent ATV-weighted entanglement is O(1/√N), yielding O(√N) aggregate decomposition error via mean-field analysis.
Efficient estimation: Markov entanglement is estimated via Monte Carlo by solving a convex minimization over local transition matrices PA, making empirical feasibility checks tractable without ever computing the exponential-sized global Q-value.

Key Contributions¶

Complete characterization: Markov separability ⟺ exact Q-value decomposition under any reward (iff result)
Novel analogy to quantum entanglement with a key structural difference (linear vs. convex combinations)
Agent-wise Total Variation (ATV) distance, a tighter multi-agent-aware metric for bounding decomposition error
Proof that index policies are asymptotically separable with O(1/√N) per-agent entanglement → O(√N) global error
Convex, sample-efficient estimator for Markov entanglement via Monte Carlo + convex optimization
Novel "absorbing" proof technique for tensor-product Bellman equations with independent theoretical interest

Results¶

Circulant RMAB benchmark (up to N=1800 agents, |S|^N = 4^1800 > 10^1000 global states):
Empirically estimated entanglement N·E₁ remains roughly constant as N grows, confirming O(1/√N) decay per agent
µ-weighted decomposition error scales as O(√N), consistent with Theorem 6
Both entanglement estimation and local Q-learning required only T=5N trajectory length (vs. |S|^N state space), confirming sample efficiency
No comparison against alternative MARL baselines on task reward—results are theoretical validation of scaling laws, not task-performance benchmarks

Limitations¶

Exact decomposition characterization applies to additive decompositions; monotone/joint decompositions (QPLEX, QTRAN) are explicitly out of scope
Necessary condition (Theorem 2) requires decomposability under any reward kernel; for a fixed reward, entangled systems may still decompose
Coefficients xⱼ in separability can be negative, unlike quantum entanglement—no clear physical/operational interpretation is provided
O(√N) error bound for index policies is asymptotic; finite-N constants depend on problem-specific parameters not made explicit
Experimental validation is restricted to a single circulant RMAB family; no deep-RL or real-world MARL environments tested

Relevance to Agentic AI / LLM Agents¶

While this paper is primarily a theoretical MARL contribution, it directly bears on multi-agent LLM systems that use decentralized value estimation or reward decomposition—e.g., multi-agent RL from human feedback (RLHF) pipelines where reward is factored per agent. The sufficient-and-necessary entanglement condition provides a principled criterion for when independent per-agent critics (as used in actor-critic LLM agents) introduce bounded vs. unbounded approximation error. The efficient entanglement estimator is practically actionable: before deploying a value-decomposition architecture in a multi-agent LLM workflow, practitioners can check empirical separability on sampled trajectories without enumerating the joint state space.