Theorem 1, last display, p.9 —
ProvedMarkovEntanglementExact.local_values_decompose_of_separablemarkov-chainp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1reinforcement-learningvalue-decomposition
Let be a separable transition matrix on , , a distribution with positive agent marginals, and the local transition matrices of Eq. (2). Then for all local rewards ,
where , , are the Bellman solutions for , and .
This is Eq. (1) of the paper for the local Q-values and , which are the limits of local TD learning.
Formalization Note is included, since Theorem 1 does not assume .
Differences from the source:
- generalization: P^π_AB of a two-agent MDP and policy → an arbitrary transition matrix P on a product of two finite sets; reason: the argument uses only the stochasticity of P; P^π_AB is an instance by M12
- generalization: μ is the stationary occupancy measure of a unichain, unique and strictly positive on states → μ is any distribution on joint pairs with μ ≥ 0, Σμ = 1 and positive agent marginals; reason: the derivation uses only the positivity of the conditioning marginals (footnote 1); the paper's occupancy measure is an instance, proved in the verification file OccupancyInstance
- encoding: Eq. (2) with the conditional μ(s_B, a_B | s_A, a_A) → IsLocalTransitionA/B, Eq. (2) multiplied through by the marginal; reason: equivalent under positive marginals; the quotient form is proved in M2
- encoding: Q-values as the printed expectation, and Q^π_A = (I − γP^π_A)⁻¹ r_A → Q-values as the solutions of IsBellmanQ; reason: M1 proves the solution exists, is unique, and equals the series and the inverse formula
Preamble
import Mathlib import Definitions.Def_markov_entanglement import Definitions.Def_MarkovEntanglementExact_LocalValuesDecompose import Definitions.Def_MarkovEntanglementExact_IsOccupancy open scoped BigOperators open MarkovEntanglement
Formal statement
namespace MarkovEntanglementExact
/-- Theorem 1, last display: if the agents are separable, then Eq. (1) holds with the local
Q-values of the marginalized chains, `Q^π_AB = Q^π_A ⊗ e + e ⊗ Q^π_B`, for every reward pair and
every `0 ≤ γ < 1`.
Source: Chen & Peng, Multi-agent Markov Entanglement, arXiv:2506.02385v3, Theorem 1, p.9.
**Formalization Note.** `γ = 0` is included, since Theorem 1 has no `γ > 0`. -/
theorem local_values_decompose_of_separable
{SA SB : Type*} [Fintype SA] [Fintype SB] [DecidableEq SA] [DecidableEq SB]
(P : Matrix (SA × SB) (SA × SB) ℝ) (hP : IsTransitionMatrix P)
(hsep : IsSeparable P)
(γ : ℝ) (hγ0 : 0 ≤ γ) (hγ1 : γ < 1)
(μ : SA × SB → ℝ) (hμ : IsOccupancy μ)
(PA : Matrix SA SA ℝ) (PB : Matrix SB SB ℝ)
(hA : IsLocalTransitionA P μ PA) (hB : IsLocalTransitionB P μ PB) :
LocalValuesDecompose P PA PB γ := by sorry
end MarkovEntanglementExact
Source
Chen & Peng, Multi-agent Markov Entanglement, arXiv:2506.02385v3, Theorem 1, p.9
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.