§3.2, p.11 — the absorbing step
ProvedMarkovEntanglementExact.absorbing_stepmarkov-chainp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1reinforcement-learningvalue-decomposition
Let be as in Definition 1. Then for every , every on and every on ,
This is the step that turns the global discounted series into the local one, and it rests on .
Formalization Note is written fun q => y q.1.
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: the display is for the reward vector r_A, and "similar results" for B → an arbitrary vector y for each agent, both stated; reason: r_A is an instance
Preamble
import Mathlib import Definitions.Def_markov_entanglement import Definitions.Def_MarkovEntanglementExact_IsSeparableWitness open scoped BigOperators open MarkovEntanglement
Formal statement
namespace MarkovEntanglementExact
/-- The absorbing step: if `P = Σ_j x_j P^(j)_A ⊗ P^(j)_B`, then for every `t`,
`P^t (y ⊗ e) = ((Σ_j x_j P^(j)_A)^t y) ⊗ e`, and symmetrically
`P^t (e ⊗ y) = e ⊗ ((Σ_j x_j P^(j)_B)^t y)`.
Source: Chen & Peng, Multi-agent Markov Entanglement, arXiv:2506.02385v3, §3.2, p.11. The
`N`-agent, one-step form is Lemma 6, p.40, published as
`MarkovEntanglement.separable_apply_local_reward`. -/
theorem absorbing_step
{SA SB : Type*} [Fintype SA] [Fintype SB] [DecidableEq SA] [DecidableEq SB]
(P : Matrix (SA × SB) (SA × SB) ℝ)
{K : ℕ} {x : Fin K → ℝ} {PAj : Fin K → Matrix SA SA ℝ} {PBj : Fin K → Matrix SB SB ℝ}
(hw : IsSeparableWitness P K x PAj PBj) (t : ℕ) :
(∀ (y : SA → ℝ) (p : SA × SB),
(P ^ t).mulVec (fun q => y q.1) p = ((∑ k, x k • PAj k) ^ t).mulVec y p.1) ∧
(∀ (y : SB → ℝ) (p : SA × SB),
(P ^ t).mulVec (fun q => y q.2) p = ((∑ k, x k • PBj k) ^ t).mulVec y p.2) := by sorry
end MarkovEntanglementExact
Source
Chen & Peng, Multi-agent Markov Entanglement, arXiv:2506.02385v3, §3.2, p.11
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.