Local transition deviates in -norm by at most twice the -weighted measure of entanglement
ProvedMarkovEntanglement.local_transition_deviation_mu_le_two_entanglementTheorem 5, first part (Chen and Peng, p. 19), -agent form — the -weighted row of Table 1.
Consider an -agent MDP with joint transition and occupancy measure strictly positive and stationary. Fix an agent , let be the local (marginalized) transition induced by and via Eq. (2), and let attain the measure of Markov entanglement of agent with respect to the -weighted agent-wise total variation distance.
Then the local transition deviates from that optimal independent approximation by at most twice the entanglement, measured in the -weighted norm:
where is agent 's local stationary distribution. By Lemma 5 that distribution is exactly the marginal of the global occupancy measure onto agent 's coordinate, which is how it is written here.
This is the -weighted counterpart of the first part of Theorem 8, and the weighting on both sides is what makes it true: the same statement with a uniform conclusion fails, because a rarely visited local state contributes almost nothing to the -average defining the entanglement while its conditional deviation can remain of constant order. Weighting the conclusion by the same marginal exactly compensates. In fact the sharp form of the argument gives the bound with constant rather than , and is tight; the factor stated here is the source's.
import Mathlib import Definitions.Def_markov_entanglement_multi open scoped BigOperators open MarkovEntanglement
namespace MarkovEntanglement
theorem local_transition_deviation_mu_le_two_entanglement
{N : ℕ} {S : Fin N → Type*} [∀ i, Fintype (S i)] [∀ i, DecidableEq (S i)]
(P : Matrix (Joint S) (Joint S) ℝ) (hP : IsTransitionMatrix P)
(μ : Joint S → ℝ) (hμ : IsPositiveDist μ) (hstat : IsStationary P μ) (i : Fin N)
(Pi Ptrue : Matrix (S i) (S i) ℝ)
(hPi : IsTransitionMatrix Pi)
(hopt : muAgentTVDistN i μ P Pi = entanglementN i μ P)
(hPtrue : IsTransitionMatrix Ptrue) (htrue : IsLocalTransitionN i P μ Ptrue) :
muTVDist (marginalDist i μ) Ptrue Pi ≤ 2 * entanglementN i μ P := by
sorry
end MarkovEntanglement