Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5.5.1 — Markovization preserves state-action marginals

Proved
PutermanMDP.MarkovPolicies.markovization

by Shuze Chen · Oct 29, 2026 · Mathlib 0df444a (Lean v4.33.1)

markovizationmdpp2o-gran-per-chapterp2o-plan-bookp2o-v1state-action-marginals

Let π\piπ be an admissible randomized history-dependent policy in a stationary model on a nonempty finite or countable state space. For each initial state sss, there exists a randomized Markov policy π′\pi'π′ such that, for every epoch t≥1t\ge1t≥1, state jjj, and action a∈Aja\in A_ja∈Aj​,

Pr⁡π′(Xt=j,Yt=a∣X1=s)=Pr⁡π(Xt=j,Yt=a∣X1=s).\Pr^{\pi'}(X_t=j,Y_t=a\mid X_1=s) =\Pr^\pi(X_t=j,Y_t=a\mid X_1=s).Prπ′(Xt​=j,Yt​=a∣X1​=s)=Prπ(Xt​=j,Yt​=a∣X1​=s).

One replacement policy preserves all the time marginals simultaneously. It may depend on the specified initial state. This is the distributional foundation for comparing expected reward criteria under history-dependent and Markov policies.

Formalization Note Lean starts the process from the point mass at sss, which represents the conditional notation on the page without conditioning an arbitrary initial law on a null event. Time n=0n=0n=0 represents epoch 111. No boundedness or integrability of rewards is assumed, because the conclusion concerns only probability distributions. The replacement need not be deterministic or stationary.

Preamble
import Mathlib
import Definitions.Def_PutermanMDP_MarkovPolicies_Model
Formal statement
namespace PutermanMDP.MarkovPolicies

/-- Theorem 5.5.1: one Markov replacement matches every time marginal. -/
theorem markovization {S A : Type*} [Countable S] [Nonempty S]
    (M : Model S A) (π : HistoryPolicy M) :
    ∀ s : S, ∃ π' : MarkovPolicy M, ∀ (n : ℕ) (j : S) (a : A),
      a ∈ M.actions j →
      stateActionLaw M π'.toHistory (PMF.pure s) n (j, a) =
        stateActionLaw M π (PMF.pure s) n (j, a) := by sorry

end PutermanMDP.MarkovPolicies
Source
Puterman, Markov Decision Processes, Wiley, 1994, p. 134 (PDF 150), Theorem 5.5.1, Eq. (5.5.1)
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Setting. Let SSS and AAA be arbitrary types. SSS is the state space and must be countable and nonempty. AAA is the action space and has no assumptions on it: it need not be countable or nonempty. The following are fixed:

  • MMM, an object of type Model over SSS and AAA. It provides, among other data, a set M.actions(j)⊆AM.\mathrm{actions}(j) \subseteq AM.actions(j)⊆A for each state j∈Sj \in Sj∈S.
  • π\piπ, an object of type HistoryPolicy relative to MMM.

Model, HistoryPolicy, MarkovPolicy, the conversion π′↦πhist′\pi' \mapsto \pi'_{\mathrm{hist}}π′↦πhist′​ (toHistory) and stateActionLaw all come from the imported module Definitions.Def_PutermanMDP_MarkovPolicies_Model. That module is not shown here, so this read-back treats them as opaque. It cannot confirm what they compute, for example whether stateActionLaw really is a probability, or what restrictions a MarkovPolicy carries beyond its type. For a policy σ\sigmaσ of type HistoryPolicy relative to MMM, an initial distribution μ\muμ on SSS, a natural number nnn and a pair (j,a)∈S×A(j,a) \in S \times A(j,a)∈S×A, the quantity

LM(σ,μ,n)(j,a)L_M(\sigma, \mu, n)(j,a)LM​(σ,μ,n)(j,a)

denotes the value of stateActionLaw on these arguments. In this statement μ\muμ is always δs\delta_sδs​, the point-mass (Dirac) probability distribution at a state sss.

Assertion. For every initial state s∈Ss \in Ss∈S there is an object π′\pi'π′ of type MarkovPolicy relative to MMM with the following property. Let πhist′\pi'_{\mathrm{hist}}πhist′​ be π′\pi'π′ converted to a history policy. Then for every n∈Nn \in \mathbb{N}n∈N, every state j∈Sj \in Sj∈S and every action a∈Aa \in Aa∈A with a∈M.actions(j)a \in M.\mathrm{actions}(j)a∈M.actions(j),

LM(πhist′,δs,n)(j,a)  =  LM(π,δs,n)(j,a).L_M(\pi'_{\mathrm{hist}}, \delta_s, n)(j,a) \;=\; L_M(\pi, \delta_s, n)(j,a).LM​(πhist′​,δs​,n)(j,a)=LM​(π,δs​,n)(j,a).

The quantifiers come in the order "for every sss, there exists π′\pi'π′". So the Markov policy π′\pi'π′ may depend on the initial state sss; the statement does not claim that one π′\pi'π′ works for all initial states at once. It also does not claim that π′\pi'π′ is unique.

Scope of the equality. The equality is claimed only at the points listed, and nothing else is said:

  • It covers only pairs (j,a)(j,a)(j,a) with a∈M.actions(j)a \in M.\mathrm{actions}(j)a∈M.actions(j). Pairs where aaa is not an admissible action at jjj are unconstrained, and the two sides may differ there.
  • It is an equality of values point by point, not a stated equality of measures or distributions.
  • It concerns only initial distributions that are point masses δs\delta_sδs​, not general initial distributions.
  • Nothing is said about any other quantity attached to the policies, such as joint laws across several time indices, rewards or histories.

Degenerate cases.

  • Time index n=0n = 0n=0. This case is included, so the equality must already hold at index 000, whatever LML_MLM​ means there.
  • One-element SSS. The assertion still says the same thing, now about a single initial state sss, and jjj is forced to equal sss.
  • Empty admissible action sets. If M.actions(j)M.\mathrm{actions}(j)M.actions(j) is empty for some jjj, nothing is required at that jjj.
  • Empty AAA, or all admissible action sets empty. If every set M.actions(j)M.\mathrm{actions}(j)M.actions(j) is empty, which happens in particular when AAA is empty, the equality part holds vacuously. The statement then only asserts that for each sss at least one object of type MarkovPolicy relative to MMM exists.
  • Whether AAA can be empty at all. Whether such a policy, or such a model, can exist when AAA is empty depends on the imported definitions, which are not shown.
  • Junk values. Whether LML_MLM​ can return default or junk values, for example from a division by zero or an ill-defined probability, also depends on the unseen definition of stateActionLaw. If it can, the equality is asserted for those values just the same.
Human review
  • Endorsed by Community (Bot) · Oct 29, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Oct 29, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me