Multi-agent Markov Entanglement
Authors: Shuze Chen
Tianyi Peng
Venue: NeurIPS 2025 spotlight ()
Keywords: Multi-agent Reinforcement Learning
Reinforcement Learning Theory
Policy Evaluation
Primary area: reinforcement_learning
TL;DR: This paper establishes the mathematical foundation of value decomposition in MARL.

Abstract: Value decomposition has long been a fundamental technique in multi-agent reinforcement learning and dynamic programming. Specifically, the value function of a global state $(s_1,s_2,\ldots,s_N)$ is often approximated as the sum of local functions: $V(s_1,s_2,\ldots,s_N)\approx\sum_{i=1}^N V_i(s_i)$. This approach 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 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" 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 policies, the index policy, is weakly-entangled and enjoys a sublinear $\mathcal O(\sqrt{N})$ scale of decomposition error for $N$-agent systems. Finally, we show Markov entanglement can be efficiently estimated, guiding practitioners on the feasibility of value decomposition.

Multi-agent Markov Entanglement
Shuze Chen Graduate School Business Columbia University New York, NY 10027
Tianyi Peng
Graduate School of Business Columbia University New York, NY 10027
shuze. chen@columbia edu
Sanyiipeng@colmmme edu
Abstract
Value decomposition has long been a fundamental technique in multi-agent rein- forcement learning and dynamic programming. Specifically, the value function of a global state ($1, .2......y. is often approximated as the sum local functions: (811. . 8N) R Ee Vs(s.). This approach has found various applications in modern reinforcement learning systems. However, the theoretical justification for why this decomposition works effectively remains underexplored. In this paper, we uncover the underlying mathematical structure that enables value decom- position. We demonstrate that Markov decision process (MDP) permits value decomposition if and only if its transition matrix is not "entangled"" analogous to quantum entanglement in quantum physies. Drawing inspiration from how physicists measure quantum entanglement, we introduce how to measure the "Markov entanglement" and show that this measure can be used to bound the decomposition error in general multi-agent MDPs. Using the concept Markov entanglement, we proved that widely-used class of policies, the index policy, is veakly-entangled and enjoys sublinear O ((N) scale of decomposition error for N -aggent systems. Finally, we show Markov entanglement can be efficiently estimated, guiding practitioners on the feasibility of value decomposition.
concept
Introduction
Learning the value function given certain policy, policy evaluation, is one of the most fundamental
tasks in RL. Significant attention has been paid single-agent policy evaluation [39, 8. 40]. However, when it comes to multi-agent reinforcement learning (MARL), single-agent methodologies typically suffer from the curse of dimensionality: the state space of the system scales exponentially with the number of agents. To tackle this problem, one common technique is value decomposition,
V(81, 82.
Vi(a.),
where V; is some local function that can be learned independently by each agent. quickly follows that this decomposition greatly reduces the computation complexity from exponential linear dependency on the number of agents N.
The remaining question is whether this decomposition is effective. This is non-trivial due to the coupling of sients-individul agent's action and transition depend on other agents. For example, in ride-hailing platform, if one driver took the order, then other drivers are not allowed fulfill the same order. As a result, value decomposition may lose information and introduce bias without considering the global constraints.
In the past several decades, both positive and negative results have been reported. Back to the last century, [49, 47] apply Lagrange relaxations to decompose the global value and obtain the well-known
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Whittle index policy. The Lagrange decomposition idea has also been proved successful in many other important multi-agent tasks such as network revenue management [1. 50], resource allocation [27, 7], and online matching [11, 12, 36, 28). However, Lagrange decomposition relies on the knowledge of system dynamics and [2] show its decomposition error can he arbitrarily had for general multi-agent MDPs. In more recent days, practitioners apply online (deep) reinforcement learning to train a local value function for each individual agent. This practice gives birth to state-of-the-ar dispatching policies in ride-hailing platforms and has been well recognized by the operations research community, such as DiDi Chuxing [33] (Daniel H. Wagner Prize, 2020) and Lyft [4] (Franz Edelman Laureates, 2024). Intervention policies based on a similar value decomposition idea also demonstrate substantial empirical advantages and have been deployed by a behavioral health platform in Kenya [5] (Pierskalla Award, 2024). In broader MARL literature, value decomposition serves as one key component of centralized training and decentralized execution (CTDE) paradigm, achieving strong empirical performance [38, 29, 35 However, recent research has started reflecting on the invalidity and potential flaw of value decomposition in practice [25, 16].
Despite all these empirical success and failures, there remains little theoretical understanding of whether and how we can decompose the value function multi-agent MDPs.
1.1 This paper
In this paper, we will uncover the underlying mathematical structure that enables/disables value decomposition. Our new theoretical framework quantifies the inter-dependence of agents in multi- agent MDPs and systematically characterizes the effectiveness of value decomposition. For simplicity, we will demonstrate the main results through two-agent MDPs indexed by agent A and B. We later extend our results to general N-agent MDPs in Appendix H.
We start with a trivial example where two agents are independent, i.e. each following independent MDPs. It's clear that the global value function can be decomposed as the sum of value functions of local MDPs. As two agents are independent, it holds p*(s', (s'A "B 8B) px (s'A 8A) pa (s's 8B). or in matrix form,
P PA Pg.
where & is the tensor product or Kronecker product of matrices. The important question is whether can extend beyond this trivial case of independent subsystems.
Sufficient and Necessary Condition We introduce a new condition called "Markov Entangle- ment" describe the intrinsic structure of transition dynamics in multi-agent MDPs.
Definition 1 (Markov Entanglement). Consider a two-agent MDP with transition PAB If there exists
K Pî Exppli 8 P()
1=1
then PIn is separable; otherwise entangled.
Compared with the preceding example of independent subsystems, Markov entanglement offers an intuitive interpretation: a two-agent MDP is separable it can be expressed as a linear combination of independent subsystems. We then demonstrate,
separable P
decomposable VïB
where VăB is decomposable if there exist local value functions VA. VB such that (A sB) (A(sa) + VB($B) for all (SA, sB). This result sharply unravels the secret structure of system dynamics governing value decomposition. As a sufficient condition, our finding strictly generalizes the previous independent subsystem example, extending it to scenarios involving interacting and coupled agents. As necessary condition, we prove that exact value decomposition under any reward kernel requires the system dynamics to be separable. Taken together, this result provides a complete characterization of when exact value function decomposition is possible in multi-agent MDPs.
More interestingly, our Markov entanglement condition turns out be mathematical counterpart of quantum entanglement in quantum physics, whose definition is provided below.

---

Definition 2 (Quantum Entanglement), Consider two-party quantum state PAB. If there exists
K
PAB = 2 2 PB:
(i)
22
then PAB separable; otherwise entangled.
The quantum state is represented by density matrix, a positive semidefinite matrix with unit trace, analogous to transition matrix in the Markov world. The concept of quantum entanglement describes the inter-dependence of particles in a quantum system, while Markov entanglement describes that of agents in Markov system.
Finally, introduce several novel proof techniques concerning the sufficient and necessary condition, including an "absorbing" technique for separable transition matrices and a novel characterization of the linear space spanned by tensor products of transition matrices. We believe these techniques hold independent interest for the broader RL community.
Decomposition Error in General Multi-agent MDPs Despite the precise characterization of Markov entanglement and exact value decomposition, general multi-agent MDPs can exhibit arbitrary complexity, with agents intricately entangled. This raises critical question: value decomposition serve as a meaningful approximation in such scenarios? To address this, we introduce a mathematical quantification measure the Markov entanglement in general multi-agent MDPs,
E PAA)) = min d(PAB: P),
PEPsEP
where PSEP is the set of all separable transition matrices and d(-,)) is some distance measure. In other words, the degree of Markov entanglement is determined by its distance to the closest separable transition matrix. This concept also find its counterpart in quantum physics, with the measure of quantum entanglement defined as
E(PAB) = min d(pAB:P).
where PSEP is the set of all separable quantum states. In quantum physics, various distance measures have been designed for density matrices and capture different physical interpretations [31]. In the Markov world, we analogously design distance measures for transition matrices and relate them to the value decomposition error,
decomposition error of VA = -
where ||-Il depends on the distance we use to measure Markov entanglement. We explore diverse distance measures including the well-known total variation distance and its stationary distribution weighted variant. We also design novel agent-wise distance incorporating the multi-agent structure, which may be of independent interest to the MARL community. We further demonstrate how different distance measures give birth to the decomposition error in different norms.
Applications of Markov Entanglement Finally, we leverage our Markov entanglement theory to analyze several structured multi-agent MDPs. We prove that widely-used class of index policies is asymptotically separable, exhibiting a decomposition error that scales O NN with the number of agents N. This result theoretically justifies the practical effectiveness of value decomposition for index-based policies. Our proof builds on innovations that integrate Markov entanglement with meean-field analysis. We also show that Markov entanglement admits an efficient empirical estimation, thus helping practitioners determine when value decomposition is feasible.
1.2 Other related work
In the first section, we have reviewed typical empirical works on value decomposition. Here, we complement that discussion with related literature on theoretical insights.
Prior theoretical research has extensively investigated the decomposition of optimal value functions in multi-agent settings. A prominent area involves Lagrange relaxation, with the Restless Multi-Arme

---

Bandit (RMAB, [49]) as foundational model. Lagrange relaxation decouples the constraint of agents, yielding a decomposable value that upper bounds the original value. The per-agent decomposition error is proven to decay asymptotically to zero [47, 48, 41J and enjoys a quadratic or exponential rate [20, 21, 11, 51, 52]. Other work generalizes to Weakly-Coupled MDPs (WCMDPs) [6, 13, 19]. However, [2] showed Lagrange relaxation can have arbitrarily large errors and proposed an alternative decomposition called Approximate Linear Programs (ALP), which is proven to have tighter error [12]. Despite these advancements, characterizing decomposition error for general multi-agent MDPs remains unknown. In contrast, our Markov entanglement theory analyzes value decomposition for general multi-agent MDPs under arbitrary policies. including optimal ones.
Another line of theoretical work has concentrated on policy optimization via value decomposition. Despite reported empirical successes, rigorous theoretical analysis remains challenging. [5] derived an approximation ratio for a specific index policy on two-state RMAB. [43, 16] analyzed the convergence of the CTDE paradigm under strong exploration assumptions, while also highlighting scenarios of divergence. In contrast, our work instead focuses on policy evaluation rather than optimization. This enables to derive clear and interpretable bounds on the decomposition error for general finite-state multi-agent MDPs that only require the existence of a stationary distribution.
Notations We abbreviate subscripts (8) = ($1.N) = (81,,8...... "8,,.,8..,,8N ........8)). Particularly, for two-agent case, when the context is clear, we abbreviate (s) == (BAB) = (B). Let [N] = (1, 21....... N} and - be the set of positive integers.
2 Model
We consider a standard two-agent MDP MAB(S. A, (B. with joint state space S = SA SB and joint action space A = AA x AB where A, B represent two agents. For simplicity, let [Aa = SBl = |S| and |AA| = |A = |A]. For agents at global state s = ($A,8B) with action
(a aB) taken, the system will transit s' -s'A s'y) according to transition kernel s' ~ P(- 8, a) and each agent i E {A, B} will receive its local reward ri(si, az). The global reward TAB is defined as the summation of local rewards ( a) r (s + Tn(sn, aB), in BB. where @ is the tensor product and e = E |||||||| is the vector of all ones.' We further assume the local rewards are bounded, i.e. for agent i {A, B). [s; 0;)l
vector form TAB E IR || = T
S r rimax for all (s,, 0:).
Given any global policy T: S + A(A), the global Q-value under policy is defined as the dis- counted summation of global rewards (7 a) = E [E A''' a') т, (s": aa) = (s.a)) a)] where E 10, is the discount factor. The value function is then defined as Vān(s) Ba~x(-1a) (8 a)). We denote PX E RISH11F*115511 as the transition matrix induced by where PAB (8', a' 8, P (s, x (a' s')) Then by the Bellman Equation, we have VA (I PP YAn. Our objective is to decompose this global Q-value QA as the sum- mation of some local functions QA and Qn, i.e. (A a) = Qa(sA, (A) + Qn(sn; an), or in vector form,
(2) Notice we formally introduce our research question using Q-value instead of V-value function as in the introduction. Q-value decomposition is stronger result that implies V-value function decomposition. also turns out that Q-value further incorporates action information enabling more general theoretical analysis. More discussions can be found in Appendix B.
2A = QA 8 Betes @ QB.
2.1 Local (Q-)value functions
Recent literature offers several algorithms for learning local (Q-)values, In this paper, we use a meta-algorithm framework in 1 to summarize their underlying principles.
This meta-algorithm framework simple and intuitive: each agent independently fits its local Q- values based on its local observations. Notably, the framework requires no prior knowledge of the MDP, and learning can be performed in a fully decentralized manner. Furthermore, we use term meta in that we do not pose restrictions on how agents estimate their local Q-values. For tabular case, one
In Appendix J.4, we extend results multi-agent MDP model where the global cannot be decomposed.

---

Meta Algorithm 1: Leaning Local Q-value Functions
Require: Global policy æ; horizon length T. 1: Execute π for 7 epochs and obtain D = (s a'An: AA 8 1+1 T-1
AB xxB) 1=1
2: Each agent E {A, fits Q7 using local observations D, = {() at rf 1+1 a 1===
T-1
can plug in Temporal Difference (TD) learning [39] or its variants. For large-scale problems, one apply linear function approximations (c.g. [5, 24, 8]) or more sophisticated neural networks (e.g. [33, 38, 29]).
Despite the flexibility in fitting local value functions, it is helpful to call out particular approach: TD learning for local Q-values in the tabular case, as it facilitates the analysis and reveals the structure of value decomposition in the next section.
Local TD learning. Although each agent's environment precisely, partially observed Markovian), one can still define its "marginalized" local transition matrix under the stationary distribution. Mathematically, for agent A, we denote PT E [[S|[||x(S|AA) as its local transition where
Markovian in local sense (it is, more
(M d'A SA, = EΣ
PAB (AAB.'B BAR, (AB SA,
(3)
Sg.0'y $2.08
Here, wAB A(S) denotes the global stationary distribution under policy и (for convenience, assume induces unichain, i.c. μ²B is unique and strictly positive). Given this "marginalized" local transition, the local Q-values obtained by Meta Algorithm using tabular TD learning converge to the solution of the following "marginalized" Bellman equation:
Q = -1- -1
TA.
By symmetry, we can derive analogous results for agent B, obtaining its transition matrix Pă and local Q-values Q7 Next, we show how Q" and Q7 contribute to the exact value decomposition.
3 Exact value decomposition
To begin, recall the key condition we identify in the introduction: Markov Entanglement in Defini- tion Our first theorem shows that an MDP with no Markov entanglement indeed sufficient for the exact value decomposition. More importantly, local TD learning (or Meta Algorithm I more
generally) guaranteed recover such decomposition, i.e. QA = Q7 @ eetes
e & Q7-
Theorem Consider two-agent MDP MAB and policy n: S A(A). two agents are ((() _P()
separable, i.e. there exists K E Zt, measure {z, je(K), and transition matrices
JE[K]
such that PAB = =Ø I. x. & p(.). Then it holds PA E 2.P' and Pg = E, Furthermore, the Eq. (2) holds
p(i)
2a= 0
This theorem establishes that even when the system is not independent, as long it can be represented as linear combination of independent subsystems, the global Q-value admits an exact decomposition.
An illustrative example of coupling and Markov entanglement To elucidate the concept of Markov entanglement, we present an example of two-agent MDP where agents are coupled but not entangled. Consider a two-agent MDP MAB with |Aal = |A = 2, where action 1 means activate and 0 means idle. Each agent E (A, B) has its own local transition kemel P. We examine the following policy: at each time-step, we randomly activate one agent and keep another idle, i.e.
For (Ap ag S.A aл) to be well-defined, we require Pãa( (SA, > 0. If Pf (SA, a.) = 0, then action a.a is never taken in state under policy and we exclude such pairs by restricting the feasible action set A(sa). All theoretical results apply to the remaining valid state-action pairs.
5

---

aaa - 1/2 = -0,1) or a (1. Consequently, this policy couples the agents through the constraint a + ag = 1 each timestep. However, we will demonstrate that despite this coupling, there's no entanglement. Specifically, we construct the following decomposition
PAB - 2 P2 B + PA & PB.
where P. refers to the transition matrix of agents E [} taking action a E {0, Intuitively, the right-hand side of Eq. (4) describes how at each time step, the global system randomly selects between two possible transitions: PaA @ P/= or P @ Ph. each with equal probability (akin to rolling a fair dice). This example thus clearly demonstrates a coupled system can still be separable and thus admits an exact value decomposition.
Proof of sufficiency Theorem admits a simple proof based on the several basic properties of tensor product. First of all, given Pū Σド= 23
P() Pf we can plug this into the formulation of It remains to show Eq. (2). Notice that
PA in Eq. (3) and quickly verify PA = Σ 1=
K
K
(1-7PAB)
(r
2
e)
Σn 7
Σ /=1
J
p()) A
@ (rA
p!
1=0
P(p 3
TA E (II (II ra) 0 00==1700 0c.
where we refer to (i) an "absorbing" technique based on the bilinearity and mixed-product property of tensor product'. Specifically, since Pe for any transition matrix P. we have for any 4,
K
K
K
Σ
6 I
p &
(T)@c)= =
Σ
2j
P
P() (
Σ
IJ
(()) rA
2
1=1
1=1
I-1
K Σ r. j=1
K
K
P
1(
Σ x. p(f)
Ta
8e=...=
TA ec.
1=1
Similar results can be derived for Pg such that (I - - AB) combining the above results, we have
(e P
= e e Q8. Finally,
LA = (1- (1 TAB = (1-7PAB)
(rABete@rg)= ( 0
3.1 Necessary condition for the exact value decomposition
We then investigate whether Markov entanglement is necessary for the exact Q-value decomposition. The answer is in general no, since one can construct trivial counterexamples such as P rn 0 or ==0 0, where the decomposition trivially holds. On the other hand, we focus on stronger and more general concept of the exact value decomposition that holds under any reward kernel given 7 >> 0. Formally, we present the following theorem.
Theorem 2. Consider two-agent Markov MDP MAR with discount factor > 0 and n: S - (AA). Suppose there exists local functions Q; r; - IR [9] A) for i E (A, B} such that QAB = Qa(FA) @ + e & (r(PB) holds for any pair of reward A PB, then A, B must be separable.
Combined with Theorem 1, we conclude Markov entanglement serves as a sufficient and necessary condition for the exact value decomposition. We also emphasize that Theorem 2 considers general local functions Q. This generality accommodates all methods for fitting local Qi. such as deep neural networks, provided that the training relies solely on the local observations of agage i.
There exist other possible ways for value decomposition. For example, [38, 16] consider (x a) = L a AA)) + Lg(sg, ag, AAB) where LA La are learned jointly via min- imizing the global Bellman error [35, 29, 37, 42] consider general monotonic operations beyond
We introduce several basic properties of tensor product in Appendix
'n Appendix E, we provide an example of entangled MDP that allows for an exact value decomposition where LA depends both r and rB.

---

additive decompositions. These methods introduce possibly richer representations at the cost of more sophisticated implementations and less interpretability, which beyond the scope of this paper.
Proof sketch of necessity Our proof builds several novel techniques. Recall PsEp is the set of all separable transition matrices.
Step I:
Understanding the orthogonal complement. If a transition matrix is entangled, it will have non-zero component in the orthogonal complement of PSEP, which we construct as
|
|S Σ ==1
PSEP
Σ ==1
(efe
& W
W3 @ (eje7)
W Wiy E (ISSIIIIII
where Ej (1, 0, 0, ...,, 0)T with the first element and (j + 1)-th element -1. Then,
study an intermediate transition matrix (1 1 -I -PAB) We show if it's entangled, able to construct TB based on its component in Psep such that Q is not decomposable under this pair of rewards. We thus conclude decomposable QAB = separable (1 () - PPPB
Step 2: Connecting to "inverse". Finally, we complete the proof via a lemma showing separable < separable PÅB. The = side straightforward since (I -P>PABB the Neumann series of 7P For the converse =,, we seek invert this Neumann series. This achieved by a careful analysis of the operator norm
(1 (I- -
(1 7) PAA)
Value decomposition error in general two-agent MDPs
In general, the system transition PAB can be arbitrarily entangled. In these scenarios, we investigate when value decomposition Q & in the introduction, we define the measure Markov entanglement in Eq. (1) as certain distance between PîB and its closet separable transition matrix. We will examine several distance measures for transition matrices and relate them to the decomposition error.
Q is effective approximation of QAB- As mentioned
4.1 Eitry-wise error bound
Total variation distance One widely used metric for transition matrices is Total Variation (TV) distance. Specifically, for two transition matrices P, P' E |1 define
P - P'Ily = max DTV (P ( a), P ( a))) (s.a)ESxA
(5)
where DTv is the total variation distance between probability measures. While TV distance is straightforward, it does not take into account the inherent multi-agent structure.
Agent-wise distance We thus introduce more refined distance specially designed for multi-agent MDPs. Formally, the Agent-wise Total Variation (ATV) distance between two transition matrices P, P, E PISPIA w.r.t agent A is defined as
P D'II'I
DTV
P(. P(...ss, Σ P'(. s, a)
(6)
(s.a)ESxA
The ATV distance agent B can be defined similarly. Intuitively, compared to TV, ATV focuses an individual agent and measures the difference between its local transitions. One can also verify ATV tighter distance, i.e. PPIl''lATVV S - P'IlTv We can plug ATV into Eq. (1) and obtain the measure of Markov entanglement w.r.t ATV distance E,(PA)) = minpepsmn P PllATV. for E {A, B}. In fact, one can also verify
E (P = min max (x.a)ESxA
Drv (P PA(s) (s.aa)))
(7)
The following theorem connects these measures to the value decomposition emror.
7

---

Theorem 3. Consider a two-agent Markov system MAB and policy :: S - A(A) with the measure of Markov entanglement E E (AA), En (PAB) defined in Eq. (7), then the decomposition error entry-wise bounded by the measure of Markov entanglemens,
47 (EA(PPP)) ( f max + LB AB P maxx
-
(1 11-7) 7)2
4.2 Error weighted by stationary distribution
Entry-wise error bound is very strong result for Q-value decomposition. This comes with the entry-wise TV bounds in both TV and ATV distance. An alterative choice to consider an error weighted by the stationary distribution. Formally, consider
[an- Se (%)
PÂn = (oiiiissoooiineeea000011a
We note that this norm is clearly weaker than the entry-wise norm. Nevertheless, stationary distribution weighted error bound is sufficient in many practical scenarios. Similar ideas are also quite common in policy evaluation literature [14, 40, 9].
Distance weighted by stationary distribution analyze this μ wweihtt decomposition error, we analogously propose the 1 -wiihhhtt distance measure of Markov entanglement. Specifically, we have the following PA weighted version of Eq. (7).
(AA)
min PA
Σ
MaB(s DTV (P s. (s,
sA,a
(8)
Eq. (8) substitutes the weighted average for the maximum operator in Eq. (7). Finally, we have the following variant of Theorem 3.
Theorem 4, Under the same setup as Theorem with W'ig-weihhted measure of Markov entangle- defined in Eq. (8), the WhAs-weighted decomposition error is bounded,
ment E (BAB), Ea(PAB
4y (EA max + (B(PPAn
[ -07 s Q3
PAn
(1-
Compared to Theorem 3, Theorem 4 measures weaker LAB weighted decomposition error, while the condition on Pî also relaxed, requiring only a weighted average bound in Eq. (8).
4.3 Multi-agent Markov entanglement
Finally, we extend the results to multi-agent MDPs with the measure of Markov entanglement (PE.)) for an N-agent MDP. The extension is relatively straightforward. We demonstrate the extension of Theorem 4 below and more details can be found in Appendix H.
Theorem 5. Consider a N -agent MDP M1. with the measure of Markov entanglement E, (PT:)) w.r.t ATV distance, the weii-weghheed decomposition error is bounded by the measure of Markov entanglement,
N 47 ΣN
E. (PT
)r max
(T
Q7
S
1=
I:N
(1 71-
Applications of Markov Entanglement
In this section, apply Markov entanglement and demonstrate widely-used class of index policies is asymptotically separable. To begin, we introduce the model of Restless Multi-Armed Bandit (RMAB, [49]). In an N-agent RMAB, each agent follows a homogeneous two-action MDP with action 1 meaning activate and 0 idle. A central decision maker will activate A < N agents at each timestep and leave other agents idle. In other words, agents transit independently but are coupled under constraint Σi= a; = M. RMAB, arguably the most classical and widely-used policy the index policy, which we formally define as

---

Definition 3 (Index Policy). There exists priority index v. for each local state s. The decision maker will always activate agents in the descending order of the priority until the budget constraint M is met. Ties are resolved fairly via uniform random sampling of agents at the same state.
The index policy traces back to the well-known Gittins Index [46], Whittle Index [49, 47, 20], and busdd-bsed index policies [41, 21J. [33, 4, 5, 30, 44, 3] apply data-driven method to optimize index policies and report great empirical success in industrial implementations. Understanding the mystery behind such success calls for a theory for general index policies. We then present main theorem.
Theorem 6. Consider an N-agen restless multi-armed bandit. For any index policy satisfying mild technical conditions, there exists constant C independent of N, such that for any agent E [N]. its Mi.N- weighted measure of Markov entanglement is bounded, (((..)) S C/VN.
Theorem 6 requires two standard technical conditions for index policies: non-degenerate and uniform global attractor property, which are used in almost all related theoretical work [47, 41, 20, 21] and are detailed in Appendix I. Theorem 6 justifies index polices are asymptotically separable. Combined with an -aagent version of Theorem 4, we obtain the sublinear decomposition error for index policies
(s, (s.
((VN).
PIN
This sublinear error result explains why the value decomposition in [33, 4, 5] manages to effectively approximate the global value function in large-scale practical applications.
5.1 Efficient verification of value decomposition
For practitioners, verifying the feasibility of value decomposition is challenging due to the exponential computational complexity of estimating the global Q-value. As a solution, Markov entanglement offers an efficient way to empirically test whether value decomposition can be safely applied. Consider the -*n--eete weighted measure of Markov entanglement in Eq. (8), we have
EA(PA))
min
Σ
PA a') PA I a')al
(9)
t=1 s'aia's
In other words, we can apply Monte-Carlo estimation for EA(PAB) Notice Eq. (9) is conver for PA. which enables efficient solutions. As a result, Eq. (9) provides an efficient estimation of Markov entanglement via simulation and can be easily extend to N-agent MDPs.
Numerical experiments. Finally, we empirically study the value decomposition for the index policy on a circulant RMAB benchmark [3. 52, 10, 18] that has 4 different states each local agent. As result, the global state space scales as large as 4 18800 > 100000 for N = 1800 agents. The specific transitions and rewards are introduced in Appendix K. For each RMAB instance,
sample trajectory of length = 5N and use the collected data to i) solve Eq. (9) to estimate the measure of Markov entanglement; ii) train local Q-value decomposition. It quickly follows from the results in Figure 1:
The estimated Markov entanglement decays as O (N) in the left panel, consistent with theoretical predictions. This also implies low decomposition error scaling of O(VN), seen in the right panel. Furthermore, the simulated trajectory has a length o' = 5N while the global state space has size S making both entanglement estimation and local Q-value decomposition sample-cfficient.
6 Discussions
Comparison with quantum entanglement One notable difference between the definition of Markov and quantum entanglement that the former does not require coefficients 2 0. In Appendix C, we show there exist separable two-agent MDPs that can only be represented by linear combinations but not convex combinations of independent subsystems, highlighting a structural difference between Markov and quantum entanglement. Finally, we emphasize that our analogy to quantum entanglement is mostly in the mathematical formulation; there no clear physical interpretation analogy between Markoy and quantum entanglement.

---

Empirical Measure of Entangiemen:
Error Weighted by Stationary Distribution
Carto
6.0
Local TD (V-N)
5.0
6.0
2.0
1.0
0.0
0.0
0
300
630
930
1200
1500
1800
300
600
500
1200
1500
1800
Number Agents
Number of Agents
Figure 1: Circulant RMAB under index policy, Left: empirical estimation of Markov entanglement
multiplied by the number of agents, N E1 (PEN). Right: p-weighted decomposition error
Relations to Influenced-based MARL There's another line MARL research that explicitly models the influence of other agents intrinsic rewards for exploration [45, 26]. It turns out the mutual information can be viewed as the measure of Markov entanglement under KL-divergence. Specifically, we can rewrite mutual information in [45] as
pa dgls a) Σ (s a, (2, (log a,0.8/,04
(S A2; S2, 12) AI)
pd (82. 02/ a2)
Σ (s) (x" (118, P2(182, (2),
8.a
This is highly related to our measure of Markov entanglement under ft weiehtttted agent-wise KL-divergence, which we can define as
E2(P12)
min En"(s: (8,, (-1s, (1sss))
Intuitively, the measure of Markov entanglement can be viewed as how closely agent can be approximated as an independent subsystem. This characterization aligns naturally with mutual information. Furthermore, since KL-divergence provides upper bound for total variation distance, consequently bounds our Markov entanglement measure relative to the ATV distance introduced in paper. This connection demonstrates that influence-based MARL methods naturally fit within theoretical framework, corresponding to specialized distance measure.
Conclusion
This paper established the mathematical foundation of value decomposition in MARL. Drawing inspi- ration from quantum physics, we propose the idea of Markov entanglement and prove that it serves sufficient and necessary condition for the exact value decomposition. We further characterize the decomposition error in general multi-agent MDPs through the measure of Markov entanglement. As application examples, prove widely-used index policies asymptotically separable and suggest practitioners using Markov entanglement as a proxy for estimating the effectiveness value decomposition.
Acknowledgments and Disclosure of Funding
We thank all anonymous reviewers for their constructive comments. We are also grateful Prof. Tongyang Li for valuable and insightful discussions.
References
[1] Daniel Adelman. Dynamic bid prices in revenue management. Operations Research, 55(4): 647-661, 2007.
10

---

[2] Daniel Adelman and Adam J. Mersereau. Relaxations of weakly coupled stochastic dynamic programs. Operations Research, 56(3):712-727, 2008. doi: 10.1287/opre.10700 1070.0445.
[3] Konstantin E Avrachenkov and Vivek S Borkar. Whittle index based q-learning for restless bandits with average reward. Automatica, 139:110186, 2022.
[4] Xabi Azagirre, Akshay Balwally, Guillaume Candeli, Nicholas Chamandy; Benjamin Han, Alona King, Hyungjun Lee, Martin Loncaric, Sébastien Martin, Vijay Narasiman, Zhiwei (Tony) Qin, Baptiste Richard, Sara Smoot, Sean Taylor, Garrett van Ryzin, Di Wu, Fei Yu, and Alex Zamoshchin. A better match for drivers and riders: Reinforcement learning at lyft. INFORMS Journal Applied Analytics, 54(1):71-83, 2024.
[5] Jackie Baek, Justin Boutilier, Vivek Farias, Jonas Oddur Jonasson, and Erez Yoeli. Policy op- timization for personalized interventions in behavioral health. arXiv preprint arXiv:2303. /2206, 2023.
[6] Santiago R. Balsciro, David B. Brown, and Chen Chen. Dynamic pricing of relocating resources in large networks. Management Science, 67(7):407544094, 2021.
[7] Santiago R. Balseiro, Haihao Lu, and Vahab Mirrokni. The best of many worlds: Dual mirror descent for online allocation problems. Operations Research, 71(1)101-119, 2023.
[8] Dimitri Bertsekas and John N Tsitsiklis. Heuro-dynamie programming. Athena Scientific, 1996.
[9] Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation. Operations Research, 69(3):950-99) 9933, 2021.
[10] Arpita Biswas, Gaurav Aggarwal, Pradeep Varakantham, and Milind Tambe. Learn to intervene: An adaptive learning policy for restless bandits in application to preventive healthcare. In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI 2021), pages 4036 4049, 2021.
[11] David B Brown and Jingwei Zhang. Dynamic programs with shared resources and signals: Dynamic fluid policies and asymptotic optimality. Operations Research, 7015):3015-3033, 2022.
[12] David Brown and Jingwei Zhang. Technical note- on the strength of relaxations of weakly coupled stochastic dynamic programs. Operations Research, 71(6):2374-2333) 2023. doi: 1..1287/0pr.20222.222 2022.2277.
[13] David B. Brown and Jingwei Zhang. Fluid policics, reoptimization, and performance guarantees in dynamic resource allocation. Operations Research, 73(2):1029-1045 2025.
[14] Qi Cai, Zhuoran Yang, Jason D Lee, and Zhaoran Wang. Neural lemporal-differnne learning converges to global optima. In Advances in Neural Information Processing Systems, volume 32, 2019.
[15] Shao-Hung Chan, Zhe Chen, Teng Guo, Han Zhang, Yue Zhang, Daniel Harabor, Sven Koenig, Cathy Wu, and Jingjin Yu. The league of robot runners competition: Goals, designs, and implementation. In ICAPS 2024 System's 's Demonstration track, 2024.
[16] Zehao Dou, Jakub Grudzien Kuba, and Yaodong Yang. Understanding value decomposition algo- rithms in deep cooperative multi-agent reinforcement learning, arXiv preprint arXiv:2202.04866 2022.
[17] Vivek Farias, Hao Li, Tianyi Peng, Xinyuyang Ren, Huawei Zhang, and Andrew Zheng. Correcting for interference in experiments: A case study at douyin. In Proceedings of the 17th ACM Conference on Recommender Systems, pages 455-466, 2023.
[18] Jing Fu, Yoni Nazarathy, Sarat Moka, and Peter G. Taylor. Towards q-learning the whittle index for restless bandits. In 2019 Australian New Zealand Control Conference (ANZCC), 2019.
[19] Nicolas Gast, Bruno Gaujal, and Chen Yan. Reoptimization nearly solves weakly coupled markov decision processes. arXiv preprint arXiv:2211.019611 2022.

---

[20] Nicolas Gast, Bruno Gaujal, and Chen Yan. Exponential asymptotic optimality of whittle index policy, Queueing Syst. Theory Appl., 104(1-2):00--55,, may 2023.
[21] Nicolas Gast, Bruno Gaujal, and Chen Yan. Linear program based policies for restless bandits: Necessary and sufficient conditions for (exponentially fast) asymptotic optimality. Mathematies of Operations Research, 49(4))2468-24) -4921 2024.
[22] Carlos Guestrin, Daphne Koller, and Ronald Parr. Multiagent planning with factored mdps. In Advances in Neural Information Processing Systems, volume 14. MIT Press, 2001.
[23] Carlos Guestrin, Daphne Koller, Ronald Parr, and Shobha Venkataraman. Efficient solution algorithms for factored mdps. Journal of Artificial Intelligence Research, 19(1 ((39)))99460)) 2003.
[24] Benjamin Han, Hyungjun Lee, and Sébastien Martin, Real-time rideshare driver supply values using online reinforcement learning. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD '22, page 2968-2976, 2022.
[25] Yitian Hong. Yaochu Jin, and Yang Tang. Rethinking individual global max in cooperative multi-agent reinforcement learning. Advances in neural information processing systems, 35: 32438-32443 2022.
[26] Natasha Jaques, Angeliki Lazaridou, Edward Hughes, Caglar Gulcchre, Pedro Ortega, Dj Strouse, Joel Z. Leibo, and Nando De Freitas. Social influence as intrinsic motivation for multi-agent deep reinforcement learning. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages
PMLR, 09-15 Jun 2019.
[27] Igor Kadota, Elif Uysal-Biyikoglu, Rahul Singh, and Eytan Modiano. Minimizing the age of information broadcast wireless networks. In 2016 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 844-851. IEEE, 2016.
[28] Yash Kanoria and Pengyu Qian. Blind dynamic resource allocation in closed networks via mirror backpressure. Management Science, 70(5):5445-542,, 2024.
[29] Anuj Mahajan, Tabish Rashid, Mikayel Samvelyan, and Shimon Whiteson. Maven: Multi-agent variational exploration. Advances in neural information processing systems, 32, 2019.
[30] Khaled Nakhleh, Santosh Ganji, Ping-Chun Hsieh, I-Hong Hou, and Srinivas Shakkottai. Neurwin: Neural whittle index network for restless bandits via deep rl. In Advances in Neural Information Processing Systems, volume 34, pages 828-839, 2021.
[31] Michael A Nielsen and Isaac Chuang. Quantum computation and quantum information. Cambridge university press, 2010.
[32] Ian Osband and Benjamin Van Roy. Near-optimal reinforcement learning in factored mdps. In Proceedings of the 28th International Conference on Neural Information Processing Systems, NIPS' 14, page 604 612, 2014.
[33] Zhiwei (Tony) Qin, Xiaocheng Tang, Yan Jiao, Fan Zhang, Zhe Xu, Hongtu Zhu, and Jieping Ye. Ride-hailing order dispatching at didi via reinforcement learning. INFORMS Journal on Applied Analytics, 50(5):272-25) 22662222222222222 2020. doi:
[34] Naveen Janaki Raman, Zheyuan Ryan Shi, and Fei Fang. Global rewards in restless multi-armed bandits. In The Thirly-eighth Annual Conference on Neural Information Processing Systems, 2024.
[35] Tabish Rashid, Mikayel Samvelyan, Christian Schroeder De Witt, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. Monotonic value function factorisation for deep multi-agent reinforcement learning. Journal of Machine Learning Research, 21 2020.
[36] Ibrahim El Shar and Daniel R. Jiang. Weakly coupled deep n-networks. In Thirty-seventh Conference Neural Information Processing Systems, 2023.
12

---

[37] Kyunghwan Son, Daewoo Kim, Wan Ju Kang, David Earl Hostallero, and Yung Yi. QTRAN: Learning to factorize with transformation for cooperative multi-agent reinforcement learning. In Proceedings of the 36th International Conference on Machine Learning, volume 97, pages 5887-5896. PMLR, 2019.
[38] Peter Sunehag, Guy Lever, Audrunas Gruslys. Wojciech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanctot, Nicolas Sonnerat, Joel Z. Leibo, Karl Tuyls, and Thore Graepel. Value-decoopossiton networks for cooperative multi-agent learning based on team reward. In Proceedings of the 17th International Conference Autonomous Agents and MultiAgent Systems, AAMAS 18, page 2085-2087, 2018.
[39] Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, 2018. ISBN 0262039249.
[40] John Tsitsiklis and Benjamin Van Roy. Analysis of comporal-differrene learning with function approximation. In Advances in Neural Information Processing Systems, volume 9. MIT Press, 1996.
[41] Ina Maria Verloop. Asymptotically optimal priority policies for indexable and nonindexable restless bandits. Annals of Applied Probability, 16:1947- 2016.
[42] Jianhao Wang, Zhizhou Ren, Terry Liu, Yang Yu, and Chongjie Zhang. Qplex: Duplex dueling multi-agent q-learning. arXiv preprint arXiv:2008. 01062, 2020.
[43] Jianhao Wang, Zhizhou Ren, Beining Han, Jianing Ye, and Chongjie Zhang. Towards un- derstanding cooperative multi-agent q-learning with value factorization, Advances in Neural Information Processing Systems, 34:29 142-29155, 2021.
[44] Kai Wang, Lily Xu, Aparna Taneja, and Milind Tambe. Optimistic whittle index policy: Online learning for restless bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 10131-10139, 2023.
[45] Tonghan Wang, Jianhao Wang. Yi Wu, and Chongjie Zhang. Influence- multi-agent exploration. arXiv preprint arXiv: 2019.
[46] Richard Weber. On the gittins index for multiarmed bandits. The Annals of Applied Probability, 2(4): 102):0024- 1033, 1992.
[47] Richard Weber and Gideon Weiss. On an index policy for restless bandits. Journal of Applied Probability, 27(3):637-648, 1990.
[48] Richard R. Weber and Gideon Weiss. Addendum to 'on an index policy for restless bandits'. Advances in Applied Probability, 23(2):429 430, 1991.
[49] P. Whittle. Restless bandits: Activity allocation in a changing world. Journal of Applied Probability, 25:287-298, 1988.
[50] Dan Zhang and Daniel Adelman. An approximate dynamic programming approach to network revenue management with customer choice. Transportation Science, (3(3):381-399) 2009.
[51] Xiangyu Zhang and Peter Frazier. Restless bandits with many arms: Beating the central limit theorem. arXiv preprint arXhv:2107.11911, 2021.
[52] Xiangyu Zhang and Peter Frazier. Near-optimality for infinite-horizon restless bandits with many arms. arXiv preprint arXiv:2203, 15853, 2022.
13

---

Contents
Introduction
1.1
This paper
1.2
Other related work
2
Model
2.1
Local (Q-)value functions
3
Exact value decomposition
3.1
Necessary condition for the exact value decomposition
4
Value decomposition error in general two-agent MDPs
4.1
Entry-wise error bound
4.2
Error weighted by stationary distribution
4.3
Multi-agent Markov entanglement
8
5
Applications of Markoy Entanglement
5.1
Efficient verification of value decomposition
Discussions
7
Conclusion
10
A Linear algebra with tensor product
15
Decompose value functions
15
Comparison with quantum entanglement
15
D Proof of Theorem 2
16
Decomposition via general functions
18
Proof of Theorem 3
18
G Proof of Theorem 4
20
Results for multi-agent MDPs
22
Proof of Theorem
24
J Extensions of Markov entanglement
27
J.1
(Weakly-)couphl MDPs
27
J.2 Coupled MDPs with exogenous information
28
J.3 Factored MDPs
30
14

---

J.4
Fully cooperative Markov games
31
K
Simulation environments
31
K.1
Monte-Carlo estimation of Markov entanglement
32
K.2
Learning local Q-values....
32
K.3 Sample Complexity and Computation
33
A Linear algebra with tensor product
We briefly introduce the basic properties of tensor product or Kronecker product. Let A E
I XR1
B E mm22Xn2, then
an B
B12
alny B
A B
021
U22 B
02n;
F mmmiigg X21n2
0m,
am,
amin nn
Tensor product satisfies the following basic properties,
1. Bilinearity For any matrix A, B, C and constant k, it holds k(A & B) = (kA)
(kB), (A B) C A C B C, and A @ (B C)+C) A B B+AOC.
2. Mixed-product Property For any matrix A, B C, D. if AC and BD form valid
matrix product, then (A & (C & D) = (AC) @ (BD).
Decompose value functions
Compared the decomposition of Q-value, the value function further requires the reward to be state-dependent. To illustrate, notice by Bellman equation,
VăB -
where abuse notation and denote ( =a x(a s) |, and reward (s) La т T(a 8)rAB(S, a). A key subtlety arises because TiB may not decomposable- when TAB is decomposable-unite unless the reward TAB is state-dependent. Consequently, we cannot directly apply the "absorbing" equation as in the proof of Theorem 1.
On the other hand, Q-value decomposition bypasses the state- nate-dependence assumption and provides stronger condition that directly implies value function decomposition. a result, while learning local value functions may seem more intuitive, we recommend learning local Q-values instead and using them to approximate the global value funetion.
C Comparison with quantum entanglement
It turns out that our Markov entanglement condition serves mathematical counterpart of quantum entanglement in quantum physics. We provide the formal definition of the latter for comparison.
Definition (Two-party Quantum Entanglement). Consider two-party quantum system composed of two subsystems A and B. The joint state PAB is separable if there exists K E Z+, probability
measure {2, {æg}şe(ky and density matrices
P PB
(f) (i)
such that
[E[K]
K PAB Σ
TAPA
@
PR
j=1
If there exists no such decomposition, PAB is eniangled.
The density matrices are square matrices satisfying certain properties such as positive semi- definiteness and trace normalization, which can be viewed the counterparts of transition matrices
15

---

in the Markov world. Despite the similarities in mathematical form, quantum entanglement imposes an additional constraint requiring { to be probability measure, i.e. a In contrast, our Markov entanglement defined in Definition permits general linear coefficients {z, { as long
as プコ = 1. This distinction raises the important question of whether negative coefficients are indeed necessary in characterizing Markov entanglement.
To start with, we introduce the set of all separable transition matrices
PSEP
P20
P
P
Σ
3 P
P
Σ
where E Z and (
.P pP() JE(K]
are transition matrices. P 2 0 calls for every element of
PSEP to be valid transition matrix. It's clear that transition matrix PÂB is separable if and only if PAB E PSEP- On the other hand, direct analogy of quantum entanglement gives us the following set that further requires non-negative coefficients,
K P Σ j=1
K x
P20
P 2
Σ 1=1
1,
SEP
Interestingly, turns out PSEP & PSEP. In other words, there exist separable two-agent MDPs that can only be represented by linear combinations but not convex combinations of independent subsystems. Specifically, consider the following basis
1 1
0
E0t = 1 1
1000 1
(
0
Euo =
E10
En =
And the corresponding transition matrix we provide is
0.5
0.5
0.5
0
0
0.5
P
= 2 Evo +
- Eno & En + tin+zBn 2
En @ Evo
2 Ei @ Evo
0.5
0.5
0
0.5
0.5
0
One also verify P can not be represented by the convex combination of tensor products of these basis. This result justifies the necessity of negative coefficients in æ and highlights a structural difference between Markov entanglement and quantum entanglement
D Proof of Theorem 2
We provide the full proof of Theorem 2 in this section.
Step 1: Characterize the Orthogonal Complement. To start with, we consider the smallest subspace containing all transition matrices Ωp span(P) where P are the set of all transition matrices Rm We then study the dimension of 2.p.
Lemma 1. The dimension of 2p is dim(spp = m² m +1+1.
Proof. Let Zij E ER m such that
Zzy(a, b) - -(1 (a (a=iAbo (a=iAb=jvv
O.W.
One basis for all transition matrices is given by (Zij J. whose cardinarlity m² m
Let 2pp = sPan(P1 @ P2) be the minimal subspace containing all separable transition matrices. quickly follows that
dim(Appo)) (dim(Xp)))
16

---

We then construct the orthogonal complement of 12ps under Frobenius inner product. Let
[ey)je|m-1] be a set of vector in R" such that E (1.0..... 0, ......0)) 0) with the first element 1 and j + 1-th element -1. Notice that
Tr (ez) P) (e] Pe) =0,
for all Ey. Consider the following subspace
m--1 1
+ 12-1
St' =
(5,e
& W
Σ
w3 (Eye Wiig Wi. E R
We then show S2 is exactly the orthogonal complement of 2psz, First, notice that
dim() = 2(m 1)m² (m 1)².
and thus dim( + dimp@p m Moreover, can verify for any X E Ωpea and Y E S2, Tr(X Tr(XT)= = 0. As result, it holds
= 0Pea.
The decomposition of Q-value ultimately concerns with the properties of (I (P-7P% The following lemma bridges this gap.
Step 2: Connection to "Inverse"
Lemma 2. Given any transition matrix P and y > O, P is separable if and only if (11-)) separable.
Proof. (=) One verify that (I 7P)e (1 -?)e, which implies (1 -1-10 (1 PP is transition matrix. Moreover, (I--) = 1001=11100 (1-7) (y falls 2pez as E S 0ppe..
(+) This side is more involved. Denote (1 PP) Then if the spectral radius p U) < 1, then
0I
Σ ( TI-UY Uy 2psz.
1m0
This implies U-1 1-1 (I->P) Spaz and thus P E Ωpes, finishing the proof. It then suffices
to show p -U) 1. Notice that
1-7 X(I PP)
1 1-9
Ax - = -1- =1
1 (P:
Let (P(P) = a + bi and taking modulus for both side
7 (PP)
AA - U)
7P(PP)
7h, (P)
(P)
21 -a2
(1 - (1-7a)2 + - 2282
(1 -7)(2ar - 1)
(1 yaaa² 7
(1 71-
<1
(1 7a)2 + 202
We conclude the proof given p(I U) max, |4 - U\ <1.
17

---

Step 3: Put it together By Lemma 2, if PAB is entangled, then (1 7) - - -B 3 is also
entangled. Then there exists Y E S * O such that Tr(Y (I (BB )1 * 0. We apply singular value decomposition to all 1.. Wiej and conclude there exists some j and u, E Rn such that either Tee & (vu") (I PAB) * 0 or Tr((v")) 8 (ee,) (1 10--PP PAB) o 0. We
assume the former without loss of generality, it holds
[e) 2 ) -1- ())) #0.
Now set P4 and rB = v. Since QAB is decomposable, there exists some local function QA Q such that
I -
= @ e e
Left multiply by [e] ), have
(c) [T -I-->PPa (e (e) u (Qx(0) @c)
Then set PA 0 and TB
similarly derive
-e, (I -PPP-PPa--- v) = (e) (Q) s #0,
This gives use (e] u (Q) @ which is contradiction.
E Decomposition via general functions
Entangled P precludes the local decomposition with local value functions, but may admit decom-
positions with more general functions. Consider P p= (ee") @ (ee + (ee" T) & (ee T). where
= 1], = [1 11.
1]. Clearly such P is entangled. We also have ph = 1 (ee 1) 80 (ee 1) for
Then (I ( =I x
(ee" ") @ (ee") + & (I (1-pP)-1 (r^ @e rp) = rA ee ha (7+ /2 @ + rB t hB (7 + 72) /e R
(ee T). Then for any T. TB, we have
+ 20y (e T rB) 6 3 where h PA, PA, = rB-
F
Proof of Theorem 3
Additional Notations For (semi-)norm
lla and norm || lls, define the a, 8-norm for matrix
A as
|| = sup ||
|A la.
We further abbreviate |||||, == la.a- Moreover, we define the operator |æ| taking the absolute value of each element of vector matrix
To prove the theorem, we introduce the key technique of analyzing perturbation bounds of the transition matrix, which is also used in [17].
Lemma 3 (Lemma in [17]). Let P,P' P' E Ruxn such that (I P) and (I P exist. Then holds
-P 1P
We are then ready prove the main theorem.
18

---

Proof of Theorem 3. Let PA. PB be the optimal solution to Eq. (7) w.r. agent A, B. For any subset of state-action pairs of agent A, SA* As. we have
Σ (PA E/
E
E
(PAB PA
LaB(sB, SA.
Snin EF ''aia'a $g
Σ
Σ
E
(PAB PA PB)(s a')a,) VAB(SB, (s)
$8
1/ EJ 5'1ian
Σ
an 8A,0A) = EA
$B,8
where the last inequality follows from the definition of agent-wiss total variation distance. Since the result holds for any F and (SA, aA) E SA x AA, we have
|P - PAllry & EA(PAR),
and similar results hold for Pg. Next we have
PP-PPAB) (TA 8e) (II ((I- TA
TA 8
= (I - 7 PAB) (rA 8 8e) - -I 8 P3) (rx
+ - & PB) (rx (1->>P)) TA 8e
PA P 06) P @ PB) -1 (T^@e)
(T.
(T)
(1--PA)) -aai)~'raaaapa 8e (1- (1-77X)) 1 PA +e
(IT)
where (1) also follows the same "absorbing" technique in the proof of Theorem 1.
For (T), apply Lemma 3, it holds
7 (T (1) (r 8e)
(I PPAB)
(1PT 7PPA & (I- & PB)
(r & e)
(I PP -11
(7 PA PA & PB) (PA) 'A 8
(1 7 PAB)-111
ETA (BB)
(1 (1-7PA) T
E7E )
2,EA ( (
max
|| (I--
-1
Tiaxx
71-
19

---

where (z) follows by the definition of agent-wise total variation distance when ||TAllo O, and also trivially hold when r rallx 0. Similarly, for (II) have
( ( TA) @ ( (I--7PM) -PP) TA) 2
( ((--PPA) - -1-p)p) P.
PP)) "TPP PPa) -7PA) PA
2 EA( (PAB M
(1 -2
Then we have
(PEA((P))) max
8 - -1I- ra 8 S
(1 71)
We can derive similar results for agent i.e.
4 Fy PAB B max (1 7)2
PK- (e e ( (P-)P%) rTB)
5
Put all together we have
[7BB (Q7 (e+ S 4r(FA( AB M ) + En P
AB )r
max
(1 7)2
G Proof of Theorem 4
We first introduce the p-weighted ATV distance Formally, we introduce the following norm.
Definition 5 (μ-norm). Given transition matrix P ||S[AAI with occupancy measure"
IR SIIAA, for any vector x: E RSSIIA the p-norm is defined as
| 1lp =
Σ
als,a) [x(s, = = |
(10)
(s.0)E8XA
One can verify that μ-norm satisfies triangle inequality and is a valid norm when p(s, a) > 0 for all (s, a). Otherwise μ-norm is semi-norm general. We then introduce the distance
Definition 6 (j-weighted Agent-wiss wise Total Variation Distance). Given probability distribution
I |S the p-weighted total variation distance between two transition matrices P. P w.e. agent A is defined as
R RISPIA|
1 2
P P'II,-ATVA
PPP |-||===
sup
The y-weighted ATV distance w.r.t agent B can be defined similarly. We claim that the p-weighted ATV is also counterpart of ATV distance in Definition 6. This follows from the constrained optimization formulation of ATV
P P' AATAA
sup || (P (P- (x ||
(11)
Thus (-ATV substitutes js-norm for the original lor norm. We plug w-weeghttdd ATV into Eq. (1) and obtain the corresponding measure of Markov entanglement E(PA)) and E' (P)))) Similar to ATV in Eq. (7), this y-weighted version of (A(AA) admits the following formulation
EA(PA < min Σ Paa(s DrV (PA s. a), Pa(s P (A))
(12)
'Sice E IR |5|||) is the stationary distribution of P E (881 use "stationary distribution" and "occupancy measure" exchangeably when the context is clear.
20

---

This recovers Eq. (8) that substitutes the y-weighted average for the maximum operator in Eq. (7). Thus intuitively, E(PAB) w.t p-weighted ATV distance measures how closely agent can be approximated as independent subsystem under the stationary distribution.
We provide the proof for agents here, can easily generalize the proof to multi-agent scenarios. Compared to the proof of Theorem 3, this proof follows similar framework and differs in several details.
The first one the following lemma for the "localized" stationary distribution
Lemma 4. PA has stationary distribution PA with
V(SA, aA). (A(SA,
Σ
(AB.(A.SB.QA,AB))
$8008
In other words, the local stationary distribution of each agent is exactly the marginal distribution of global PÂB-
Proof of Lemma 4, We proof by verify the definition of stationary distribution. For any (S'A d'a). holds
Σ
Σ
P"
(A,
Σ
Σ
Σ
pd 5' 54, as ( d' SA,
sn,an
Σ $A,5A
Σ
(An(SB aB SA,
Σ
Σ
(s d's SΛ sn as a')) (An(SA, as,
ΣEΣR SA.RA B B "g.a"
P. & d'p 8A 8 as
d
Σ A' d'). 2g.0/
where the last equation follows from the definition of MAB- Hence we conclude that Exnap ( 8n, an, an) a stationary distribution of PA.
We are then ready prove Theorem 4. We first note that similar ATV distance in Eq. (7), the optimal solution to EA(PT) AB) w.r.t nº wweightd ATV distance also only depends on PA. Thus, let PA. Pg be the optimal solutions E (PA)). EB (PAB) respectively.
Let E RISAlAAl with ||=||00 have
1. Following the same technique in the proof of Theorem 4,
(P]
PA) æc
Σ aA))
Σ (PA
Palc o(5
Σ
(A)) Σ a(Shi1ah
Σ PA & PB) ()) Hin(ss, SA,
P'A.0'a
6/ en.an
Σ
(A (EA((A)) a's'ssd's) Σ (PA PA 8 PB)lo
where the second last inequality follows from Lemma 4. We then conclude
| Pallu. 2EA(PA
and similar results hold for Ps. We then apply the decomposition
21

---

(I (I->PAB) -1 (TA 8 e)
(I- -1 TA Ee
(I PAB) (FA 66) -1-7PA 2 Pn) -1 (rA 06)
(1)
+ (I->PA) -1 PA 8 (I- -1 PA e
(1I)
For (I), we have
[I &e) -I- 8 (I
(ra (ra
uan
(I 1PPxB) (1PAB - - 2 PB) (I PP X PB) ) (rA & 2e)
Pde
(
1 1-1 [1(1P7n -YPA PB) (I PPP)) TA & e
(T)(T)
2yE((T) (
1-7 (I- (I-7PA) -PA)
TA
(1 -1-79 7)²
where (1) follows from the fact that for any x
PP = TT Pmol S p T P|a| = 1u |20| = |101|p-
For (II) one can use Lemma 4 to verify
(1(1= rA) 8e - (e-((1-1) (1--PP7) rA) 8
4hB
-1 -1 TA (I (P)) PA 19
And similar results to (I) holds. We then conclude the proof of Theorem 4.
H Results for multi-agent MDPs
In quantum physics, the concept of quantum entanglement of two-party system can be well extended to multi-party system. In this section, we demonstrate a similar extension of two-agent Markoy entanglement to multi-agent settings. We begin with the model of multi-agent MDPs.
Consider an Nageent MDP MI.N(S,AA, (S, P, 7) with joint state space S S and joint action space A x N A; For simplicity, we assume |S -SS and |Ad]] = |.A] for each agent i.
For agents at global state & = (81, 82,-.., SN)) with action a = (a1, 02 -.,,,................... .Nx) taken, the system will transit s' (s), 82 ,,,..., s'y) according transition kernel s' ~ P(. 8, and each agent i E [N] will receive its local reward ri(st, a:). The global reward T1:N is defined as the summation of local rewards (8, == Eerr az), or in vector form,
N
TEN E RISM
(r
We further assume the local rewards are bounded, i.e. for agent i E [N], |r:(s;, az))
rf mma for all (st, a:). Given any global policy :: S + A(A), we denote P
DIS|"IAI1 x|S|" as the transition matrix induced by where PT. ($ (si.,s.'.. $1:N; d1:N) =
P ( si:,, (1=N) ) ι (a s1,N) Then the global Q-value is defined by Bellman Equation
Qi = (I ) T1:N. The local Q-values follow the similar framework to Meta Algorithm I where each agent i [N] fits Q using its local observations. We then sum up local Q-values to approximate the global Q-value, i.e.
N
(L R3
Q (s:.
i=1
22

---

To illustrate the extension, we first provide the definition of multi-party quantum entanglement here for reference.
Definition 7 (Multi-party Quantum Entanglement). Consider a multi-pann party quantumn system composed of N subsystems, indexed by [ The joint state PaNN is separable if there exists Z*,, probubility distribution ( and density matrices
P1:N
(1)
such that
jE(K]
K
P1:N =
Σ
2 E
( &
8
2
PN
(
If there exists no such decomposition, P1:N called entangled.
Analogically, we define the Multi-agent Markov Entanglement, Definition 8 (Multi-agent Markov Entanglement). Consider Naagent Markov system M1:N and policy :: S (AA), the agents are separable under policy π if there exists K E Z*, measure (aybet satisfying Σnn Ij 1, and transition matrices
p(d)
such that jE[K]
1:N
PE I:N
EES
( 2... 2 P
If there exists no such decomposition, the agents are entangled under policy n
For clarity, we use superscript s' to denote the i-th element in state space and subscript to represent the state i-th arm. Furthermore, we denote S the profile of N-arms.
and $1:N = {$1, $ .N....... is
Given any global policy æ, for any agent i E [N].
(5 de si, ai)
Σ Σ
Pin ($i,,, oL suN, an.)) pi.N ( (s-ia a_i si,,,))
S-1,a-1
Definition (Measure of Multi-agent Markov Entanglement). Consider a N Nageent Markov system Mi.N with joint state space S = S and action space A = x N Given any policy
T: S + A(A), the measure of Markov entanglement of agents is
E(P(.N) min d(Pl. P), PEPST
(13)
where .l.,.) is some distance measure.
The following theorem generalizes the results of value-decompositton for two-agent Markov systems Theorem 3 to multi multi-agent Markov systems.
Theorem 7, Consider a N-agent MDP M1:N with joint state space S x and action space
A = N Ai. Given any policy π: S + (AA) with the measure of Markov entanglement Ex(P).)
w.r. ATV distance, it holds for any agent
P.P.T P.ll. 22,E(PEN)
where P, is the optimal solution of Eq. (13). Furthermore, the decomposition error is entry-wise bounded by the measure of Markov entanglement
47 (EN, E, E.(PE (r.TN
(s,(
(s,
S
(1 71
The proof mainly follows the following lemma, which generalizes the key technique used in Theo- rem 1.
Lemma 5. For any agent i, it holds
Σ
s, p()) 8 p() 8 ... p()) (((88) ((Be))- (60)--1
Σ 2f
p(i,,
(14)
23

---

The lemma follows from the property of tensor product. We can also extend Theorem 4 to multi-agen MDPs.
Theorem 8. Consider a N- N-agent MDP MI:N with joint state space S = x S and action space A = x Ai. Given any policy w: S + (AA) with the measure of Markov entanglement E, (PP.)) w.r. the Pi:N--eighht -weighed agent-wise total variation distance, holds for any agent
P pe
1u 100 (PE((
where P. is the optimal solution of Eq. (13) and μo the stationary distribution of the projected transition PT.. Furthermore, the ii weeighedd decomposition error is bounded by the measure of Markov entanglement,
N -
47 (Ei= Ei Ex(P (.NNrin max
O7 - (7
S
(1 1-7)²
14
I Proof of Theorem 6
We first provide an overview of the proof and introduce the technical assumptions.
To begin, we consider the system configuration m A |S| where m, 1/- +Agents in state s} is the proportion of agents in state When N - co, the transition between configurations will become deterministic under index policy and m will approach its mean-field limit m Furthermore, in the mean-field, each agent's ss local transition will only depend its local state. As result, the system will de-couple and become separable as N + oc.
To formalize this intuition, we introduce the following lemma that connects Markov entanglement measure with the mean-field analysis
Lemma 6. The measure of Markov entanglement w.r.t pl.x- ATV distance bounded by the deviation of mean-field configuration,
(m(T) S - m [loo]
where the expectation is taking over the stationary distribution m PT.N-
We thus focus the deviation from to m We extend the concentration analysis from [20, 21] to derive a new stability bound for the RHS. Specifically, we finishing the proof via demonstrating the deviation decays at the rate (I///N).
One caveat here is that we have to restrict chaotic behaviors in the mean mean-fiele field limit. We thus introduce two technical assumptions.
We first define the transition of configuration under index policy as o= A A such that 6" (m) = E [ma[ + 1] m it]] m, T].
For > O, we denote L = ( apply the transition mapping for rounds.
Assumption A (Uniform Global Attractor Property (UGAP)). There exists uniform global attractor
m" of dith (-), i.e. for all & > 0, there exists T(e) such that for all > T(e) and all m E 118), one has (1 m² ml E.
The UGAP assumption ensures the uniqueness of m and guarantees fast convergence from any initial to m..
Assumption B (Non-degenerate RMAB). There exists state E S such that 0 < π (s. < 1, where x² is the policy under m
The non-degenerate assumption further restricts cyclic behavior in the mean-field limit.
Non-degenerate and UGAP are two standard technical assumptions for the index policy, which restrict chaotic behavior in asymptotic regime and will be further introduced in subsequent sections. We note here these two assumptions are also used in almost all theoretical work on index policies [47, 41, 20, 21).
Proof of Theorem 6. the subsequent proof, we let 11 > 1/2 > V3 ... > D|s)- This does not lose generality in that we can always exchange state index. The proof consists of several steps
24

---

Step 1: Find m Recall the transition mapping for configurations Ø= A + A 8d (m) = E [m]t + 1] m [t] = m, π|
Notice that the definition of o= does not depend on N. We adapt from Lemma B. in [20] defined specially for Whittle Index.
Lemma 7 (Piecewise Affine), Given any index policy n, 6" a piecewise affine continuous function with S affine pieces.
When the context is clear, we abbreviate ot as Φ. For any m E A define s(m) E [|S]] be the state such that _i=1 E m; I a Ei(n) mi. Lemma characterizes for any 2, = (m& | (mm) = i}. there exists (())) (x(m) such that
Φ(m) K s(m) m + bs(m)-
By Brouwer fixed point theorem, there exists fixed point m such that d(m²) mm. The UGAP condition guarantees the uniqueness of m Our choice of n is the corresponding policy under m".
Step 2: Connecting policy entanglement with the deviation of stationary distribution Combine Proposition 9 with the RMAB model, we have
Lemma 8. The measure of Markov entunglement w.r.f PT.N wweigttt ATV distance bounded by the deviation of mean-field configuration,
(i(T) S | [[]m - m [loo]
where the expectation is taking over the stationary distribution Pi.N-
Proof. Given the homogeneity of agents, we first demonstrate for any two agent i, it holds
Σ ($1.N) (T(a;= = a 81:N) "t" (a: = a st)l = Σ 10 (81:N))) [T(a = a 81.8) - x x'(a = a sx))
$1.N
$1.N
To see this, we first notice by the definition of index policy
|T(a; s; =, m) (a 8) = I(a) ss-= x (a s)
then suffices to prove Σ En p($1:N) = E E (((1.N).
Σ - (($I:N) S E., = (($1:N), ) we can exchange the agent index of i and j. This
will result in the same stationary distribution and E. [(81:N) 2 E p(S1.))
and thus the equation. We then rewrite the bound in Proposition
BlT)) S 2 sup Σ 1a ($INN)
Σ [Ta
- 7" -1:N)-
(a; |s:)1
#1:N
a;
sup Σ
reth (SI.) |T(a;= = | - x= ==(a;,
8:)l
91NN
N Σ 10 (BEN)
|Ta;; 1|81 -x"(a, s;)
Σ 1e (m) Σ
me (T(a | x" s)l
SES
For any configuration m and state we have
my
(a 8, m) 7a 1 ||]
n" (a 8) s)m,,,N N his n (a
m
m + la
m N l.
ki l (a 1
N
N + Lo
<| m
m
1|,
where |ks1 < (15) m - m lo.. N representing the additional fraction of state s to be activated due to the deviation from m² and [,, < ||m m m= I representing the deviation of m. from m The results then hold by taking summation over and expectation over m.
25

---

Step 3: Concentrations and local stability To bound E [||m - m 3l we start with several
technical lemmas from previous RMAB literature. We use the same notation 9, o(
Lemma 9 (One-step Concentration, Lemma I in [21]. Let e[1] m|1] p(m (0)), it holds
S
E [||[[]]]| mm]]
N
Lemma 10 (Multi-ster Concentration, Lemma C.4 in [20]). There exists a positive constant K such that for all E N and O,
Pr [[]m[t]] 2. (m) 2 (1 (L+K+ K K2 + K m [0] m] S StSle-2Ne
Lemma 11 (Local Stability, Lemma C.5 [20]). Under non non-degenerate and UGAP:
(i) K () is a stable matrix, iee. its spectral radius is strictly less than 1.
(ii) For any there exists T(e) > 0 such that for all m E A ((Pree))))) - m 11.0 < c.
The first result implies there exists some matrix norm ll-ll such that || ( < 1. By the equivalence of norms, there exists constant C C3 > 0 such that for all æ E RIis
ا S | S C3
Combine the second result of Lemma 11 and non-degenerate condition, borhood N of m such that N = B(m", .c) n A E 2s(m²) where e > O and 3(mm"c) (m ||m - ml < }} is an open ball. We next show that m[[) under stationary distribution
construct a neigh-
will concentrate in M with high probability. Let T T(e/2) such that for all m e A (m)) - m m= </2. It holds
Pr [m[[]] ./] = Pr m [0] m
( Pr
mn[ m
2 E
m(0] = =m
< Pr
|m|
(m))
mm[0] m + Pr [.) - -m" -m=l0e 2 2.
IV 2
2
Pr
m (m)
m0 m < T 2uN
where (i)
follows from the stationarity m m[T] and m[(] are i.id and the constant u
does not depend on N.
2(1*K*K²
Step Put it together Finally, we are ready to bound [||m m" [lo Notice for all m 00] E N,
we have
m[1 m (0m(0)) + c[] m
= K <m) (m(0) - mmn) + <[1]
Taking |1-11, both side,
[m[]] mmml1 < K (m)) (m m m3) }11B + ||[[A]]|
K (m=) |1 ||m[0] m 1| ||||]]||
Taking expectation on both side,
E
[m|[]] m m='la
=E [[o(m((0)) - m [m[0] E vV3] + E [l)(m()) - ml {m/[0] o NN] + EE [|e{4]]]
K (m)))
|1 E [| m 1 (m] E v3] + [m] $ . sup (m mmm + [[e[A]]]]]
m|a
K
[|][0]] m= + [m[ M sup [|m(m(0)) m m0 E [|[[]]]| m 00]
26

---

By stationarity, one have E equality,
[[ m mmlla]]
1E [Im[0] m m=]1a]
This refines the above in-
3
sup Pr [m[0]] & & [l)(m(()) m l1s + E [
E [|] m
1
K (m |1g
m=
(Pr (m( W I. [[e]l
(1
K smm=)
11a))
C3
Tisse=2uu -uN vIs
C1
K (m 1l
VN
We combine Lemma and conclude the proof of Theorem
J Extensions of Markov entanglement
J.1 (Weakly-)coupled MDPs
Weakly-coupled MDPs (WCMDP) are rich class of multi-agent model that capture many real-worle applications such supply chain management, queuing network and resource allocations [2, 12, 36]. Compared to general multi-agent MDP, WCMDP further ensures each agent follow its local transition while the agents' actions are coupled with each other. Formally,
Definition 10 (Weakly-coupled MDPs). An N-agent MDP coupled MDP if
P,riN, is weakly-
Each agent has local transition kernel Pe such that Va, a, 8', S',PL P(s' s, = -1 P.(s Si, di).
At global state s, agents' joint actions subject coupling constraints E d(st, a4) < R.
We then demonstrate that this weakly-coupled structure can further refine the analysis of Markov entanglement measure.
Proposition 9, Consider a N-agent weakly-coupled MDP MI,((S, A, Given any policy x: S + A(A) with measure of Markov entanglement E((PP) (Tn)) w.n. the weightee agent-wise total variation distance, it holds for [N),
E, E.(PTN) S min EMIN(s)
IT(a; Elm(a: ()) T'(a; sx))
where &' :S; A, is any local policy for agent
Proof of Proposition 9, We demonstrate the proof for two-agent WCMDP and the generalization to
multi-agent WCMDP is straightforward. Consider PA be the transition of agent A under local policy
27

---

n.. We focus agent A
E (PAB)
a))
Σ
P dA (8,0) - -P (s'a ),
5,0
1 (An (8, a)
Σ
Σ
Pän(s' a4 8, - Px SA, s
8,0
8/B
(
1 WAB(S, (8, a)
Σ
Σ
Pa Pa 8,,)) - 1,,a)_ P(s'
8, a. (
2
8,0
8/B
"g
(A a)
T
Σ
E P(s' (s,) 80) n' r'(d' s'))
2
8,0
E'10's
8'1
P AAn (s, a)
P(s'\ s, .) Σ
I 1s) -- > s(a
8,0
d'A
(i))
Σ I<(d's = s'Ail (s
2
where (i) follows from the transition structure of weakly coupled MDP P(s') 8.0) = P(d' 8A, a.) P(s' 8n, an); and (ti) comes from the fact that pm (s' 8) Ea aa s(P 8,a) and E. 10 (8) pK (s' 8) 1ra (s').
Proposition establishes an upper bound for Markov entanglement in WCMDP. Intuitively, this bound characterizes how agent can be viewed as making independent decisions. It takes advantage of the weakly-coupled structure and shaves off the transition in Markov entanglement measure.
J.2 Coupled MDPs with exogenous information
In many practical scenarios, the agents' transitions and actions are coupled by a shared exogenous signal. For example, in ride-hailing platforms, the specific dispatch is related the exogenous order at the current moment [33, 24, 4]; in warehouse routing, the scheduling of robots is also related to the exogenous task revealed so far [15].
We will then enrich our framework by incorporating these exogenous information. each timestep there will an exogenous information revealed to the decision maker. 2; is assumed to evolve following a Markov chain independent of the action and transition of agents. We assume 2, 2 and Z is finite.
Given the current state and exogenous information z, the policy is given by π : 8 Z + A(Ā). where Á refers to the of feasible actions. We then have the global transition depending on exogenous information
( a'', 8, 2, P(s' ss,, x(aa) |2,2) P(x' 2).
and global Q-value QAB. E (RISMMAA
N
(xn(s, 0, = E
Σ
Σ
r(8i,,, Ci,t 21) 80 = 8,00 = a. 2g = 2
We assume the system is unichain and the stationary distribution is HABZ Then we can derive the local transition under new algorithm by
PA SA.GA.2)
Σ (AB. aB SA,
Σ
Px (x (s' (8,,,, s,
"/
Given the local transition, have the local value Q (I 7P (TAz) via Bellman Equation.
28

---

Combined with exogenous information, we consider the following value decomposition (A s, a, 2) = Q% (5 a, 2) + (s 2).
We start by introducing agent-wise Markov entanglement defined for each agent
P AR=
Σ 2 E
P
(15)
Proposition 10. If the system is agent-wise separable for all agents, then
QAB= = QA @SSIAA + @|S|A|| X QB=
Proof. The proof is basically the same as Theorem 1. One can first quickly show that PAz Σj=1 T;j P/ And then it holds
K
Σ
P
00
p(i)
(r^ 611
1-1
K
Σ
& p!
Σ Tyy
(0 @ (pLie) ))
3
/=1
/=1
1-1
K
K
Σ
(
& p!
Σ
pl))
(rA 8e
2z Az
/=1
Jz plf
(r (r) Øe.
We then provide the measure of Markov entanglement with exogenous information w.r.t agent-wise total variation distance.
K
EA PA 2) = min 2
PÂB: -
Σ
ayyPi 8 pU)
J=1
ATV,
min max PA. 8,a, 2
Σ
PP d' x' 18,, z)- dA (AA
s'A
(16)
Similar Theorem 3, we can connect this measure of Markov entanglement with the value decompo- sition error.
Theorem 11. Consider a N-agent Markov system MEN- Given any policy :: S + ((A) with the measure of Markov entanglement E, I.N Z) w.r. the agent-wise total variation distance, it holds for any agent i,
K
P
Σ
r
p() is
< (P Z).
j=1
Furthermore, the decomposition error is entry-wise bounded by the measure of Markov entanglement,
47 >> i-1 E.PPI.N Z)r
(
Σ
Uie
(st
(1
80
29

---

In practice, exogenous information is often discussed in the context of (weakly-)coupp MDPs, where each agent independent evolves by P((+111 8; a,, 2). Interestingly, we can derive a similar result to Proposition 9 that shaves off the transition in entanglement analysis.
Proposition 12. Consider N-agent Weakly Coupled Markov system MI:N- Given any policy :: S + ((A) and its measure of Markov entanglement E5 1., 2) w.T. the Weii-weighted agent-wise total variation distance, it holds
EAPTN. 2)5,))533
Ed (SINN)) #1:203
Σ1 Ia(a S1,N, - 7 (a; [(s
R2
for any policies n'.
Proof. We provide the proof for two-agent MDP, which can be easily generalized N-agent case.
EA 2)
1
Σ u(s, a,
Σ
PAB. ('
18, PA |8,, (A,
2
4,0,2
Σ a(s,a,2) Σ
Σ PAne(s'.aa:2'1 (s,
[s (s'A,²')
2
8,0,2
s'a aa 12
o'n
1
Σ
a(s.a,2)
Σ
Σ Pi (1.3,,,)2111,0,,))) - Σ 5
P(s', (8,0, 2)' 1'..
2
8,0,3
%/B
1
Σ
a,
Σ
Σ
| [s,a.)) 8,22 a d'(d's S s'
2 8,0,2
6BB
S 2
(1 a 2)
P(s' 2 0, 2) Σ
|a(d's 8',2') - <'a's s'A
8,0,2
8',2'
0/4
Σ
u(s',
Σ
ITaas 1 10'2²) - n 7'(d's (',1221)
2
8'
d'A
J.3 Factored MDPs
Another common class of multi-agent MDPs is Factored MDPs (FMDPs, [22, 23, 32]), which explicitly model the structured dependencies in state transitions. For instance, in server cluster, the state transition of each server depends only on its neighboring servers. Formally, we define
Definition 11 (Factored MDPs), An N-agent MDP (EN(S,AA A,P,, 7) is factored MDP if each agent has neighbor set Z, E [N] such that its transition is affected by all its neighbors, i.e. P(s 8, a) P(x $2, d.
The neighbor set IZ,] is often assumed to be much smaller compared to the number of agents N. This helps to encode exponentially large system very compactly. We show this idea can also be captured in Markov entanglement. Consider the measure of Markov entanglement w.r.t ATV distance in Eq. (7),
EA AB) min max Drv (P Px(s) 1 (A))
Pa (s.)
min max PA (8.A)ESxA
Drv (P 82,, a2,),
PA(s (s.,a)))
Thus conclude the agent-wise Markov entanglement will only depend on its neighbor set.
30

---

Meta Algorithm 2: Q-value Decomposition with Shared Reward
Require: Global policy æ; horizon length T.
1: Execute π for 7 epochs and obtain D = { (s'A a'm. A' 8 1+1
AB aBB 1=1
7-1
2: Each agent E {A, fits Q7 using local observations D; = af of , aatt)) 7-1 where the local reward (TA, is learned via solving
min Σ (rAB(s, ( tr(()),))))) PA
J.4 Fully cooperative Markov games
In fully cooperative settings, only global reward will be reviewed all agents, Unlike the modeling in section 2, this global reward may not necessarily be decomposed as the summation of local rewards. In this case, we propose meta algorithm as an extension of meta algorithm
This algorithm follows similar framework of meta algorithm I and differs at we now learn the closet local reward decomposition from data. When the reward completely decomposable, meta algorithm 2 recovers meta algorithm 1. Thus intuitively, the more accurate we can decompose the global reward, the less decomposition error we have. Formally, we define the measure of reward entanglement
e(rAB)
min ||AB (ra @ TA.BB
(17)
This measure characterizes how accurate we can decompose the global reward under stationary distribution. We then obtain extension of Theorem 4
Proposition 13. Consider a fully cooperative two-agent Markov system MAR. Given any policy :: (AA) with the measure of Markov entanglement F EA(PAB), EB (P(p) AA) wer the VAB weighted agent-wise total variation distance and the measure of reward entanglement e(rAB), holds
e(FAB) 1-7
47 (EA(AA)) max + EB((PA D m
QAB (Q) (27
AB
S
+
17B
7)2
where
T maxx max is the bound of optimal solution of Eq. (17).
Although Proposition offers a theoretical guarantee for general two-agent fully cooperative Markov games, its utility is greatest in systems with low reward and transition entanglement. Fully cooperative settings remain inherently challenging-for instance, even the asymptotically optimal Whittle Index may achieve only y appproximation ratio for RMABss with global rewards [34]. In practice, most research [38, 35] relies on sophisticated deep neural networks to learn decompositions in such settings. We thus defer more refined analysis of fully cooperative scenarios future work.
K Simulation environments
In this section, we empirically study the value decomposition for index policies. Our simulations build circulant RMAB benchmark, which is widely used in the literature [3, 52, 10, 18).
Circulant RMAB
A circulant RMAB has four states indexed by (0, 1, 2, Transition kernels P. = p(s, 0, 8') Je for action and 1 are given by
L/2
0
1/2
1/2
1/2
0
0
1/2
1/2
0
0
0
1/2
1/2
0
Po
P1 =
1/2
1/2
0
1/2
1/2
0
1/2
1/2
1/2
0
0
1/2
The reward solely depends on the state and unaffected by the action:
r(0, a) 11, r(1,a) 0, r(2, a) 0, r(3,a) 1; {0, 13.
31

---

We set the discount factor to y = 0.5 and require N/5 arms to be pulled per period. Initially, there are N/6 arms in state 0, N/3 arms in state and N/2 arms in state 2. the same [52]. We then test an index policy with priority: state 2 >> state 1 >> state 0 >> state 3.
K.1 Monte-Carlo estimation of Markov entanglement
For each RMAB instance, we simulate trajectory of length 7 = 6N and collect data for the later 5N epochs. Notice RMAB a special instance WCMDP, we thus apply the result Proposition
E (.N) S min Σ
PI
ITaas 8) (a: &x)
T
~
min x''
T
ITa 8) - T' r'a s:)1
(18)
02
Notice Eq. (18) is convex for x and r' only takes support of size | = 8. we thus apply efficient convex optimization solvers. We replicate this experiment for independent runs to obtain the mean estimation and standard error in the left panel of Figure 1.
K.2 Learning local Q-values
For each RMAB instance, we simulate trajectory of length T = 6N, reserving the later T = 5N epochs as training phase for each agent to fit local Q-value funetions. During testing, we estimate the yu-weighted decomposition error using 50 simulations sampled from the stationary distribution.
The ground-truth QI.v is approximated via Monte Carlo learning [39], with each estimate derived from 30-step simulations averaged over 3.V independent runs. Due to the high computational cost of Monte Carlo peehods-espeecillyy for very large RMABs-we limit the training phase to 10 independent runs and use the mean local Q-value as approximation. Error bars represent the standard error for both Monte Carlo estimates and je-weighted decomposition errors.
In addition to y-weighted error, we also introduce a concept of relative error, defined as ( a) Σ Q a.) pT. /1QQT.wI/T.. This relative error reflects the approximate
ratio of our value decomposition. We present our simulation results below.
Error Weighted by Stationary Distriaution
Relative Error
6.0
Local TD
Local
DU1//N
3.0
4.0%
4.0
3.0%
2.0%
1.0
0.0
300
630
500
1200
1500
1800
300
660
500
1200
1500
1800
Number Agents
Number of Agents
Figure 2: Value Decomposition error in circulant RMAB under index policy. Left: p-weighted decomposition error. Right: Relative error, ||decomposttion error]) /I.
immediately follows that the p-weighted error grows at a sublinear rate O(VN) and the relative error decays at rate ((//NN). This justifies our theoretical guarantees in Theorem Furthermore, we notice the relative error is no larger than 3% over all data points. As result, the meta algorithm 1 able provide very close approximation especially for large-scale MDPs even with small amount of training data T 5N while the global state space has size S
32

---

K.3 Sample Complexity and Computation
While each RMAB instance has an exponentially large state space ||| N. we show that our empiri- cal estimation of Markov entanglement along with the decomposition error converges quickly. Specifically, we illustrate these errors for an RMAB instance with with 900 agents in Figure 3. As exhibits in Figure 3, both errors decay and converges within 7 = 3N samples. Furthermore,
Estimation Error and Decomposiiio Errur
listmmtted Intonglomont Mozzure
Decomspooitin Ervoe (lam)
$0.0
Entangtement. Measire
Decompeettion Frrer (Smonthee;
30.0
20.0
300
600
1500 Sample Trajectory Lereth
900
1200
1800 2100 2000 2700
Figure 3: Different errors in RMAB with 900 agents: empirical estimation of Markov entanglement (bluc); weightee decomposition error (green); the true measure of Markov estimated with T = 10N samples (red dashed line).
empirical estimation of Markov entanglement converges in T < N samples, demonstrating its efficiency. Finally, we use standard convex optimization solvers to compute Markov entanglement, which can be run efficiently on single CPU.
33

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Yes. Our main contributions are also detailed in section 1.1. Also see Appendix J, H for more theoretical results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Yes, we discuss other possible value decompositions in section 3.1 and Appendix E, J.4.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
34

---

Answer: [Yes]
Justification: Theorem 1, 2, and 4 hold for general multi-agent as long as a stationary distribution exists (see section 2). Theorem relies standard assumptions for index polices, detailed in Appendix All proofs are included in main text or Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof's provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Our empirical results build on publicly RMAB benchmark in [3, 52, 10, 18], detailed in Appendix K. We upload the codes and instructions recover the results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
35

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: Our empirical results build nublicly-accessibe RMAB benchmark in [3, 52, 10, 18]. detailed in Appendix K. We upload the codes and instructions to recover the results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips..
wwwsssssssnniiiiiooo for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurlPS code and data submission guidelines (https: //n //ipp.cc. https/ccccpppcccaaeeceeecccccccc gww.//////////ege// /CodeSubmis ssi ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
See Appendix K.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[Yes]
Justification:
We detail the calculation error bars in Appendix K.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
36

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: See Appendix K.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https / //tner/insupppee cc cctppblic///ecccccccccccccclllll htteee/tthhsiiiieieeeeeeee
Answer: [Yes]
Justification:
We followed the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: This work focuses on establishing new mathematical foundation for MARL. This work is not related to any private or personal data, and there's 's no explicit negative social impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
37

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do foresee any high risk for misuse of this work.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best. faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: We do not existing assets and empirical simulations based on synthetic models, whose proposers have been appropriately cited.
Guidelines:
The answer NA means that the paper does
existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
38

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
39

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
We do not involve LLMMs as any important, original, or non-standard compo-
nents.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (uttps://neute) for what should or should not be described.
40


Reviews:
[{"review_id": "cbwtmmSkZW", "reviewer": "Reviewer_5Std", "summary": "This paper investigates the equivalent condition of the linear-decomposability of the value function in multi-agent MDPs. The authors introduces the concept of Markov entanglement, inspired by the entanglement in quantum mechanics, to characterize property of the dynamics of the multi-agent MDP. They prove that the linear-decomposability of the value function is equivalent to the Markov disentanglement of the dynamics (in non-trivial cases). Beyond this results, they define a quantitative measure of Markov entanglement, and relate it to the value decomposition error. The paper further shows that index policies exhibit low entanglement and thus enjoy a $O(\\sqrt N)$ scale of decomposition error. Finally, they show that the entanglement can be efficiently estimated, making it a useful tool for analyzing the linear decomposition error of the value function.", "questions": "See Weaknesses.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n\n- The paper is well-written and the presentation is clear.\n\n- The paper provides a new perspective to understand linear decomposition of the value function in multi-agent MDPs.\n\n- The theoretical results are comprehensive, and the paper also provides a method for estimating entanglement, making it applicable in practical settings.\n\n### Weaknesses\n\n- It would be better if the authors devote more discussion to the intuitive understanding of entanglement, and clarify how the proposed necessary and sufficient condition relates to other commonly used notions such as independence and Definition 3.1 in [1]. Discussion on the relationship between entanglement and coupling is also beneficial.\n\n- The paper does not provide the efficiency analysis of the entanglement estimation method.\n\n- (Minor) Linear decomposition of the value function is a fundamental problem in multi-agent RL, while it is not so effective in practice. Most of the existing empirical works focus on the monotonic decomposition[2]. It would be interesting to see the analysis of the monotonic decomposition.\n\n[1] Dou, Zehao, Jakub Grudzien Kuba and Yaodong Yang. “Understanding Value Decomposition Algorithms in Deep Cooperative Multi-Agent Reinforcement Learning.” ArXiv abs/2202.04868 (2022): n. pag.\n\n[2] Rashid, Tabish, Mikayel Samvelyan, C. S. D. Witt, Gregory Farquhar, Jakob N. Foerster and Shimon Whiteson. “QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning.” ArXiv abs/1803.11485 (2018): n. pag.", "was_revised": true, "final_justification": "A technically solid paper. It proposes an interesting theory, bringing new insights into the understanding of value decomposition in the MARL field.", "rebuttal": "Thank you for the helpful review! In response to your questions:\n\n# Intuition of Entanglement \nIn the introduction, we highlight that Markov entanglement intuitively captures whether an MDP can be viewed as a *linear combination of independent subsystems*. To further clarify this concept, we provide an illustrative example in Section 3 (Line 191) comparing entanglement with coupling. Specifically, we construct an MDP that is coupled but *not* entangled, highlighting the fundamental distinction between the two notions.\n\nAs a supplement, our example relies on a special MDP where two agents share the same randomness. This idea also has a direct parallel in quantum physics. Shared randomness plays a crucial role in characterizing the fundamental distinction between *classical correlation* and *quantum entanglement* in the quantum world, e.g. the famous Einstein-Podolsky-Rosen (EPR) paradox. When it comes to the Markov world, it delineates the difference between *coupling* and *Markov entanglement*. We plan to incorporate this perspective more explicitly in the next version of the paper.\n\n# Relations to Independence and Definition 3.1 in [1] \nOur notion of Markov entanglement strictly generalizes independence by allowing MDPs to be expressed as a *linear combination of independent subsystems*, allowing for coupled (non-independent) MDPs that are separable.\nDefinition 3.1 in [1] also assumes the global reward as the summation of local rewards. It further requires the transition to decompose into a sum of specific functions. While the authors show their definition is equivalent not only to exact value decomposition but also to the exact decomposition under the Bellman operator, they admit that MDPs satisfying their definition are \"rare in practice.\" Specifically, we find Definition 3.1 in [1] cannot accommodate certain independent cases.\n\n\n# Efficiency Analysis of the Entanglement Estimation \nWe briefly present the efficiency results here, with a detailed analysis to be included in the next version of the paper. First, note that the optimization problem can be abstracted as follows: $\\min_x F(x)=\\min_{\\\\|x\\\\|=1} \\mathbb E_y[\\\\|y-x\\\\|]=:L$ where $\\\\|\\cdot\\\\|$ refers to the L1-norm. Denote one optimal solution $m=arg\\min_x F(x)$. Similarly, let $L_n:=\\min_{\\\\|x\\\\|=1} F_n(x)=\\min_{\\\\|x\\\\|=1} \\frac{1}{n}\\sum_{i=1}^n\\\\|y_i-x\\\\|_1$ with one optimal solution $m_n=arg\\min_x F_n(x)$. We summarize the results in the table below\n\n|            | Efficiency                                                       |\n| ---------- | ---------------------------------------------------------------- |\n| Asymptotic | $\\sqrt n (L_n-L)\\xrightarrow{d} \\mathcal{N}(0,Var_y(\\\\\\|y-m\\\\\\|_1))$ |\n|     Non-asymptotic       |     $\\| L_n-L \\|\\leq O(\\sqrt\\frac{\\| S \\|\\| A \\|}{n})$  where $\\| S \\|\\| A \\|$ is the size of local state-action pairs.  |\n|||\n\nWe then briefly go through the proof sketch here\n- The asymptotic efficiency analysis is based on empirical process theory. Note that $L_n-L=F_n(m)-L+F_n(m_n)-F(m_n)+F(m_n)-F_n(m)$. For the first part, it's clear $\\sqrt n(F_n(m)-L)\\xrightarrow d \\mathcal{N}(0,Var_y(\\\\|y-m\\\\|_1))$ following standard CLT. For the later part, one can verify $F_n(m_n)-F(m_n)\\leq \\sup_x |F_n(x)-F(x)|$ and $F(m_n)-F_n(m)\\leq \\sup_x |F_n(x)-F(x)|$. Thus it suffices to bound $\\sup_x |F_n(x)-F(x)|$. We can verify the covering number of $F$ satisfies polynomial decay and thus apply standard analysis of uniform convergence (e.g. Theorem 37 in [2]). We have $\\sup_x |F_n(x)-F(x)|=o_p(n^{-1/2})$. Finally, we derive the asymptotic result via Slutsky’s theorem. For simplicity, the proof above assumes that transitions are sampled i.i.d. from the stationary distribution. When the data is drawn from a non-episodic Markov chain, standard Markov chain CLT (e.g. [4]) results can be applied to obtain analogous conclusions.\n- The non-asymptotic analysis is based on generalization theory. We note that $|L_n-L|\\leq R_n(F)+\\sqrt{\\frac{\\log (1/\\delta)}{n}}$ with probability at least $1-\\delta$ and $R_n(F)$ is the empirical Rademacher complexity. We can bound $R_n(F)$ via the covering number and conclude its order $O(\\sqrt\\frac{|S||A|}{n})$.\n\nIn summary, our entanglement estimation has efficiency that does not scale with the number of agents $N$.  In contrast, estimation of decomposition error without using Markov entanglement requires direct evaluation of global value functions, whose asymptotic efficiency has rate $\\Theta(1/\\mu_{\\min})$ where $\\mu_{\\min}=\\min \\mu(s_{1:N},a_{1:N})$ (e.g. see [3]). In other words, the rate of direct estimation is $\\Omega(|S|^N|A|^N)$. Thus the estimation of decomposition error via Markov entanglement is exponentially faster.  \n\n\n\n# Beyond Linear Decomposition (Minor)\nWe agree that linear value decomposition is a fundamental problem in MARL. We also acknowledge the rich body of work on non-linear decomposition methods (such as monotonic) that offer richer representations and enjoy greatempirical successes. Our work on linear decomposition and Markov entanglement can serve as a foundational framework for future analysis of such algorithms.\n\n\n[1] Dou, Zehao et.al, \"Understanding Value Decomposition Algorithms in Deep Cooperative Multi-Agent Reinforcement Learning.\" ArXiv 2022.\n\n[2] Polldard, David, \"Convegence of Stochastic Processes.\" Springer 1984 \n\n[3] Chen, Shuze, et.al, \"Experimenting on Markov Decision Processes with Local Treatments.\" Arxiv 2024\n\n[4] Galin L. Jones, \"On the Markov chain central limit theorem.\" Arxiv 2004"}, {"review_id": "Rlkmbd6LIM", "reviewer": "Reviewer_tNC3", "summary": "This paper establishes a rigorous theoretical foundation for value decomposition in multi-agent reinforcement learning. The authors introduce Markov entanglement—an analogue of quantum entanglement—to characterize when a joint transition probability is separable and thus admits exact value decomposition. They prove that exact decomposition holds if and only if the Markov entanglement is zero, and they derive upper bounds on the approximation error in terms of an agent-wise total variation entanglement measure.\n\nAs an application, they show that under standard index policies for Restless Multi-Armed Bandits, the Markov entanglement scales as $O(1/\\sqrt{N})$, and they confirm this rate via numerical experiments on circulant RMAB benchmarks. Additionally, they propose a simple Monte Carlo–based convex optimization procedure to efficiently estimate the entanglement, allowing practitioners to verify the feasibility of value decomposition without ever computing the full global Q-function.", "questions": "**Q1.**\n\nUnlike quantum entanglement, Markov entanglement allows the coefficients $x_j$ to be negative. What is the fundamental reason behind this difference? Could you elaborate on why the constraint $x_j \\ge 0$ is not imposed in the definition of Markov entanglement?\n\n\n**Q2.**\n\nI’m curious about the motivation for choosing the restless $N$-armed bandit setting for the experiments. Why was this particular environment selected?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\nThe paper establishes a rigorous theoretical foundation for value decomposition in MARL.\nIt provides a clean characterization of when value decomposition is possible, via the novel and well-defined concept of Markov entanglement.\nThe authors derive explicit upper bounds on the decomposition error in terms of an agent-wise TV entanglement measure, covering both worst-case and stationary distribution weighted scenarios.\nWhile the main text focuses on two agents for clarity, the framework is extended to the general $N$-agent settings in the appendix.\nThe paper includes appropriate numerical results using the restless multi-armed bandit benchmark, supporting the theory with empirical evidence.\n\nOverall, the paper is organized and well written.\n\n**Weaknesses**\n\n**W1.**\n\nWhile the theory is well-developed, its practical relevance to more complex MARL domains remains unclear, as the evaluation is limited to a syntheic circulant RMAB benchmark.\n\n**W2.**\n\nI think assuming the decomposition $r_{AB}(s_A,s_B,a_A,a_B)=r_A(s_A,a_A)+r_B(s_B,a_B)$ is restrictive when agents compete or cooperate to achieve a goal. In such case, the interaction should be modeled differently. I believe most multi-agent scenarios fall into this category, where reward decomposition is unnatural.", "was_revised": true, "final_justification": "The paper presents a novel theoretical foundation, well supported by a range of experiments. The authors have addressed my questions appropriately, and I have also benefited from discussions with other reviewers. Overall, I believe the paper has sufficient academic merit to warrant a final rating of 5.", "rebuttal": "Thank you for the helpful review! In response to your questions:\n\n# More Evaluations\nWe have conducted additional experiments to investigate how the performance of a value decomposition based algorithm [1] varies with different levels of system entanglement. Please see our response to Reviewer H55K for complete experimental details and results\n\n# Decomposition of Reward\nWe argue that many practical MARL settings fall into our modeling, especially in the field of operations research (OR). Typical examples include\n- Ride-hailing system (e.g. [1][2]) The platform's overall revenue is the summation of the revenue of each driver.\n- Warehouse Robot routing (e.g. [3]) The local reward is the indicator of whether the agent completes a task. The global objective is the overall number of task completed.\n- Inventory Control (e.g. [4]) The overall operational cost is the summation of the costs of each warehouse.\n- The well-established class of Weakly-coupled MDPs (e.g. [5]) and RMABs (e.g. [6]) in OR literature. These models have been widely applied in practice, including in resource allocation, revenue management, healthcare, and many other fields.\n    \nFurthermore, in Appendix J.2, we also provide a solution for scenarios where the global reward cannot be decomposed. We propose a concept called *reward entanglement* to characterize how well the global reward function can be approximated by a sum of local rewards. Building on this concept, we extend our analysis, demonstrating that the decomposition error can be bounded by considering both transition and reward entanglement.\n\n# Q1: Negative Coefficient in Markov Entanglement\nIn Appendix C we thoroughly discuss this difference between Markov entanglement and quantum entanglement. In short, we did find a separable two-agent MDPs that can only be represented by linear combinations but not convex combinations of independent subsystems. This result justifies the necessity of negative coefficients $x_j <0$ and highlights a structural difference between Markov entanglement and quantum entanglement. Specifically, we construct the following transition matrix in $\\mathbb R^{4\\times 4}$ $$\\left(\\begin{array}{cccc}\n0.5 & 0 & 0 & 0.5 \\\\\\\\\n0.5 & 0 & 0 & 0.5 \\\\\\\\\n0.5 & 0 & 0 & 0.5 \\\\\\\\\n0 & 0.5 & 0.5 & 0\n\\end{array}\\right)\\\\,.$$ One can verify this transition matrix can not be represented by the convex combination of tensor products of transition matrices in $\\mathbb R^{2\\times 2}$. \n\n\n\n\n# Q2: RMAB as Evaluation Environment\nWe choose RMAB out of the following reasons\n- RMAB forms the foundation for several award-winning industrial applications in operations research, including ride-hailing systems (DiDi, Lyft) [1,2] and Kenya's mobile healthcare platform [8]. We then adopt RMABs as our evaluation environment to empirically investigate why value decomposition based methods prove effective in large-scale systems and verify our theoretical justifications.\n- RMAB involves two major challenges in MARL \n   - *Scalability*: as demonstrated in our experiment, a RMAB instance usually contains thousands of agents. For example, the ride-hailing system in NYC contains thousands of active drivers.\n    -  *Action Constraint*: each agent's action is coupled with each other. For example, if one driver takes one order, other driver cannot fulfill the same order. \n        \nThese structures make RMAB an active research area in OR and MARL.\n\n\n\n[1] Qin, Z., et al. \"Ride-hailing order dispatching at didi via reinforcement learning.\" INFORMS Journal on Applied Analytics 50.5 (2020): 272-286.\n\n[2] Azagirre, Xabi, et al. \"A better match for drivers and riders: Reinforcement learning at lyft.\" INFORMS Journal on Applied Analytics 54.1 (2024): 71-83.\n\n[3] Chan, Shao-Hung, et al. \"The league of robot runners competition: Goals, designs, and implementation.\" ICAPS 2024 System's Demonstration track. 2024.\n\n[4] Alvo, Matias, Daniel Russo, and Yash Kanoria. \"Neural inventory control in networks via hindsight differentiable policy optimization.\" arXiv preprint arXiv:2306.11246 (2023).\n\n[5] Adelman, Daniel, and Adam J. Mersereau. \"Relaxations of weakly coupled stochastic dynamic programs.\" Operations Research 56.3 (2008): 712-727.\n\n[6] Whittle, Peter. \"Restless bandits: Activity allocation in a changing world.\" Journal of applied probability 25.A (1988): 287-298.\n\n[7] Sunehag, Peter, et al. \"Value-decomposition networks for cooperative multi-agent learning.\" arXiv preprint arXiv:1706.05296 (2017).\n\n[8] Baek, Jackie, et al. \"Policy optimization for personalized interventions in behavioral health.\" Manufacturing & Service Operations Management 27.3 (2025): 770-788."}, {"review_id": "bcJQCnJ1T0", "reviewer": "Reviewer_H55K", "summary": "This paper provides a theoretical analysis of the error introduced by approximating a joint value function (across multiple agents) as linear combination of individual value functions, referred to as value decomposition. In particular, they introduce a measure of Markov entanglement, which bounds the error of such decompositions. To estimate this entanglement, they propose to measure the total variation distance between the transition matrix of focal agent $A$’s local state (and its next action/policy) conditioned only on its own current local state and action, and the transition matrix and policy conditioned on the global state and actions.", "questions": "1. The proposed method to estimate Markov entanglement seems to be closely related to common counterfactual methods in MARL used to estimate influence. For example, [1] uses a similar measure of information-theoretic influence to encourage agents to explore highly entangled transitions $p^{\\boldsymbol{\\pi}}\\left(\\boldsymbol{s}, \\boldsymbol{a}, s_2^{\\prime}\\right)\\left[\\log p^{\\boldsymbol{\\pi}}\\left(s_2^{\\prime} \\mid \\boldsymbol{s}, \\boldsymbol{a}\\right)-\\log p^{\\boldsymbol{\\pi}}\\left(s_2^{\\prime} \\mid s_2, a_2\\right)\\right]$, and [2] proposes a similar mutual information-based method for entanglement of policies via the causal influence of one agent’s actions on another agent’s action. While this work uses it to bound value decomposition error rather than as intrinsic rewards for exploration, I would be interested to hear the authors discuss how their notion of Markov entanglement relates to these previous works.\n2. In J.4, Proposition 12 seems to be circular in some sense — bounding the error of value decomposition in terms of reward entanglement, which itself measures the accuracy of a global reward decomposition over the stationary state distribution. Can the authors clarify the contribution of this point?\n3. Apart from index policies, I would like to see more experiments to demonstrate the practical ramifications of using value decomposition in highly entangled MDPs with function approximation, e.g., a toy environment where the transition matrix/rewards can be altered to tune the level of entanglement, showing worse asymptotic performance with increasing entanglement for common decomposition methods such as VDNs [3] or QMIX [4]. I acknowledge that this would require a fair bit of engineering work, but might be useful for a camera-ready copy to make this more relevant to a wider body of MARL practitioners — I find that experiments only on index policies provide a rather narrow scope to demonstrate the utility of this approach.\n\n[1] Wang, T., Wang, J., Wu, Y. & Zhang, C. Influence-Based Multi-Agent Exploration. in *Eighth International Conference on Learning Representations* (2020).\n\n[2] Jaques, N. *et al.* Social Influence as Intrinsic Motivation for Multi-Agent Deep Reinforcement Learning. in *Proceedings of the 36th International Conference on Machine Learning* 3040–3049 (PMLR, 2019).\n\n[3] Sunehag, P. *et al.* Value-Decomposition Networks For Cooperative Multi-Agent Learning.\n\n[4] Rashid, T. *et al.* Monotonic value function factorisation for deep multi-agent reinforcement learning. *J. Mach. Learn. Res.* **21**, 178:7234-178:7284 (2020).", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n1. The idea of entanglement makes intuitive sense — it seems natural that value functions can be linearly decomposed into their component parts if their transition distributions are independent.\n2. The motivation for the work is clearly laid out, and I was able to follow the argument clearly throughout despite not being familiar with some of the experiment settings and index policies.\n\n**Weaknesses**\n\n1. The empirical evaluation is limited, being only a single demonstration for index policies that demonstrates sublinear decomposition error scaling. However, I would argue that this is not a significant weakness given the primarily theoretical nature of the paper.\n2. I believe that the paper’s notion of Markov entanglement is missing some key relevant work (expanded further upon in Questions).\n3. Small nit: typo in Meta Algorithm 1 “Leaning”", "was_revised": true, "final_justification": "The Inventory Simulator experiments clearly demonstrate the relationship between increased entanglement and the performance degradation of value decomposition-based methods, which addressed my concerns about the actual effects of Markov entanglement. They also addressed my questions about J.4.\n\nAs said in my response, while I believe that an alternative framing and experiments on more commonly used MARL environments would increase the impact of this work, I believe that it provides a valuable contribution to the community and a solid theoretical framework to investigate decomposition-based approximations. Therefore, I will raise my score to a 5 - with limited experimental evaluation being the primary flaw that precludes a 6 (however, I do not think this merits a 4 as this paper's contribution is primarily theoretical).", "rebuttal": "Thanks a lot for your review! Your suggestions are very insightful in helping us improve the paper and build strronger connections to the MARL literature.\n\n# New Empirical Evaluations \nWe have conducted additional empirical evaluations to examine how VDN's performance varies with different levels of system entanglement. These experiments utilize a synthetic inventory control environment, which we describe in detail below.\n\n## An Inventory Simulator\nA single-product inventory system consists of $k$ warehouses and 1 central factory. We denote the inventory level at each warehouse as $n_{1:k}$ and at factory as $n_f$. At each timestep,\n- Each warehouse $i\\in[k]$ observes an customer order of $o_i$ products. $o_i$ is drawn from $\\\\{\\underline{O_i},\\overline{O_i}\\\\}$ according to a Bernoulli distribution with parameter $p_i$.\n- Central factory's action is to decide how many new products to produce (an integer $a_f \\leq A_f$).\n- Each Warehouse's action is to decide how many products to order from the central factory (an integer $a_i \\leq A_i$)..\n- Allow backlogged order. An order not fulfilled this timestep can be fulfilled at future timesteps.\n- Local state of each warehouse is $(n_i, o_i)$, the current inventory level and the current order. The central factory has state $(n_f)$ as its inventory.\n- The transition for each warehouse follows $$n_{i}^{t+1}=n_{i}^t-o_{i}^t+a_{i}^t.$$Similarly, for the central factory, it transits as$$n_{f}^{t+1}=n_f^t+a_f^t-\\sum_{i=1}^ka_{i}^t.$$\n- Reward for local warehouse $r(n_i,o_i,a_i)=h_i\\min\\\\{n_i,0\\\\}-c_i\\max\\\\{n_i,0\\\\}$ where $h_i$ is the pentalty for the backlogged order and $c_i$ for the cost of storage. The reward for central factory is $r(n_f, a_f)=h_f\\min\\\\{n_f,0\\\\}-c_f\\max\\\\{n_f,0\\\\}$ where $h_f,c_f$ is the corresponding penalty.\n\nNote that the central factory's state transition depends not only on its local action but also on the actions of all warehouses. This interdependence creates potential system entanglement. Intuitively, entanglement increases with the number of warehouses. We therefore control the system's entanglement by adjusting $k$, the number of warehouses.\n\n## Benchmark\nWe implement VDN in [1] as the benchmark algorithm and test its performance under different levels of entanglement. More implementation details will be added in the next version of the paper. The optimal policy has access to the global information, thus it can fully avoid the cost. In this case, the factory supplies exactly the known order amount. Consequently, the optimal value function achieves zero cost. We then summarize the empirical results as follows\n\n\n|       | Estimated Entanglement | Global Optimal | VDN    |\n| ----- | ---------------------- | -------------- | ------ |\n| $k=1$ | 0.50                   | 0              | -9.72  |\n| $k=3$ | 0.81                   | 0              | -25.28 |\n| $k=5$ | 0.92                   | 0              | -36.94 |\n| $k=9$ | 0.98                   | 0              | -60.20 |\n|||||\n\nWe have the following observation\n- VDN's performance degrades as system entanglement increases. This aligns with VDN's reliance on local value functions for action selection: as entanglement grows, local state information becomes increasingly insufficient for optimal decision-making.\n \nHowever, we also note that entanglement may not always determine VDN's performance. Through its centralized training framework, VDN can encode global reward/state information in its local value functions. As shown in our Section 3.1 and Appendix E, certain entangled MDPs still permit exact decomposition when local values effectively capture global reward information.\n\n\n# Relations to Influenced-based MARL\nGreat question! It turns out the mutual information can be viewed as the measure of Markov entanglement under KL-divergence. Specifically, we can rewrite mutual information in [2] as $$\\begin{aligned}&I(S_2^\\prime, A_2^\\prime; S_2, A_2| S_1,A_1)\\\\\\\\=&\\sum_{s_{1:2},a_{1:2},s_2^\\prime,a_2^\\prime}p^\\pi(s_{1:2},a_{1:2},s_2^\\prime,a_2^\\prime)[\\log p^\\pi(s_2^\\prime,a^\\prime_2|s_{1:2},a_{1:2})-\\log p^\\pi(s_2^\\prime,a_2^\\prime|s_{2},a_{2})]\\\\\\\\\n =&\\sum_{s_{1:2},a_{1:2}}\\mu^\\pi(s_{1:2},a_{1:2}) D_{KL}(p^\\pi(\\cdot,\\cdot|s_{1:2},a_{1:2}) || p^\\pi(\\cdot,\\cdot|s_{2},a_{2}) ) \\\\,. \\end{aligned}$$\nThis is highly related to our measure of Markov entanglement under a $\\mu^\\pi$-weighted agent-wise KL-divergence, which we can define as\n$$E_2(P_{1:2})=\\min_{P_2} \\sum_{s_{1:2},a_{1:2}}\\mu^\\pi(s_{1:2},a_{1:2}) D_{KL}(p^\\pi(\\cdot,\\cdot|s_{1:2},a_{1:2}) || P_2(\\cdot,\\cdot|s_{2},a_{2}) )$$\nIntuitively, the measure of Markov entanglement can be viewed as how closely one agent can be approximated as an independent subsystem. This characterization aligns naturally with mutual information. Furthermore, since KL-divergence provides an upper bound for total variation distance, it consequently bounds our Markov entanglement measure relative to the ATV distance introduced in our paper. This connection demonstrates that influence-based MARL methods naturally fit within our theoretical framework, corresponding to a specialized distance measure.\n\n# Reward Entanglement in Appendix J.4\nThis section extends our analysis to scenarios where the global reward cannot be decomposed. In such cases, we propose learning an approximate local decomposition of the global reward, which is then used to derive local value functions. Our theoretical results demonstrate that when the global reward admits a good approximation via summed local rewards (under the stationary distribution), the decomposition error remains bounded (under the stationary distribution).\n\n\n\n\n\n\n\n[1] Sunehag, Peter, et al. \"Value-decomposition networks for cooperative multi-agent learning.\" arXiv preprint arXiv:1706.05296 (2017).\n\n[2] Wang, Tonghan, et al. \"Influence-based multi-agent exploration.\" arXiv preprint arXiv:1910.05512 (2019)."}, {"review_id": "0mUJgW8hGf", "reviewer": "Reviewer_bQ7W", "summary": "This paper shows that the concept of entanglement (analogous to the idea of quantum entanglement) can be used to mathematically justify the why value decomposition works in reinforcement learning.", "questions": "- Can you provide a clearer discussion on how your concept truly connects to quantum entanglement?\n- The analysis will only be valuable if you can scale it to more than two agents.\n- Can you expand the experimental results to more varied use cases?\n- Do your results still hold under non-stationarity?", "limitations": "Limitations are adequate", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n+ The theoretical results are very rigorous and the insights are important.\n+ The link between entanglement and value decomposition is novel and this is an important early work in this space.\n+ The two agent insights are useful.\n\nWeaknesses:\n- The experimental results are very limited.\n- Scalability with the number of agents is not discussed.\n- The linkage to quantum entanglement is rather tenuous.", "was_revised": true, "final_justification": "I maintain my review and I see this paper as a useful contribution. The authors should, however, revise the work to omit the analogy to quantum as it does not really stand and could mislead the community.", "rebuttal": "Thank you for the helpful review! In response to your questions:\n\n# More Experimental Results\nWe have conducted additional experiments to investigate how the performance of a value decomposition based algorithm [1] varies with different levels of system entanglement. Please see our response to Reviewer H55K for complete experimental details and results.\n\n# Generalize to Multi-agent\nOur framework naturally extends to multi-agent scenarios, as briefly introduced in Section 5 and comprehensively discussed in Appendix H. All concepts and results established for two-agent MDPs maintain their validity in the multi-agent setting. Specifically, we attach Theorem 7 (line 688) in Appendix H here for reference\n\n### Theorem 7\nConsider a $N$-agent MDP and policy $\\pi$ with the measure of Markov entanglement $E_i(P_{1:N})$ w.r.t the $\\mu^\\pi_{1:N}$-weighted agent-wise total variation distance, it holds the decomposition error in $\\mu^\\pi_{1:N}$-norm is bounded by the measure of Markov entanglement,\n$$\\\\| Q^\\pi_{1:N}(s_{1:N},a_{1:N})-\\sum_{i=1}^N Q^\\pi_i(s_i,a_i) \\\\| \\leq \\frac{4\\gamma (\\sum_{i=1}^NE_i(P_{1:N})r_{\\max}^i)}{(1-\\gamma)^2}\\\\,.$$\n\n# Relations to Quantum Entanglement\nSo far, the connection is primarily conceptual: we observe a mathematical structure in multi-agent Markov systems that parallels quantum entanglement, and our definition of the measure is inspired by its quantum counterpart. We also believe that additional concepts from quantum physics, such as information scrambling—the process by which initially localized information becomes delocalized throughout a quantum system—may have meaningful analogues in the multi-agent Markov context. Furthermore, this shared mathematical structure suggests that quantum computers could potentially accelerate computations in multi-agent reinforcement learning, helping to overcome the curse of dimensionality (it will be exciting if this speedup is exponential over the classical computers). The graphical frameworks such as 1D/2D chains developed for understanding entanglement (studied in quantum simulation through a lens of tensor networks) may also find novel applications in the Markov setting. Overall, we believe this work opens a door between two distinct fields, and we are excited to see how advances in quantum theory might benefit multi-agent RL—and perhaps vice versa.\n\n# Extension to Non-stationary MDPs\nGood question! We believe our results can be extended to finite-time and non-stationary MDPs. We note that to achieve an entry-wise error bound, our proof does not require the transition data to be sampled from the stationary distribution; it only requires that the sampling distribution has positive measure for all state-action pairs. We leave further extensions to future work.\n\n\n[1] Sunehag, Peter, et al. \"Value-decomposition networks for cooperative multi-agent learning.\" arXiv preprint arXiv:1706.05296 (2017)."}]

Author rebuttal:

Meta-review: Overall, the reviewers were quite favorable towards this paper. They had some questions which the authors easily addressed. I hope that the authors will review their manuscript in light of these questions and make edits aimed towards minimizing any ambiguities that might confuse future readers. In that vein, I hope that the authors will be careful to avoid leaning too heavily on the quantum entanglement motivation (per discussion with reviewer bQ7W) unless they can explain how the type of entanglement here is more like quantum entanglement than other cases of variable entanglement that are clearly understandable without resorting to quantum metaphors.
Decision: Accept (spotlight)