Corollary 5.5.2 — Markovization for an initial distribution
ProvedPutermanMDP.MarkovPolicies.initial_distributionLet be any initial-state distribution on a nonempty finite or countable state space, and let be any admissible randomized history-dependent policy. There exists one randomized Markov policy such that, for every epoch , state , and available action ,
The replacement may depend on and , but the same replacement works at all epochs. The result extends marginal preservation from a fixed starting state to a given initial distribution.
Formalization Note Lean uses zero-based time . The statement compares one-time marginals and does not assert equality of whole path laws.
import Mathlib import Definitions.Def_PutermanMDP_MarkovPolicies_Model
namespace PutermanMDP.MarkovPolicies
/-- Corollary 5.5.2: the Markov replacement may depend on the initial law. -/
theorem initial_distribution {S A : Type*} [Countable S] [Nonempty S]
(M : Model S A) :
∀ μ : PMF S, ∀ π : HistoryPolicy M, ∃ π' : MarkovPolicy M,
∀ (n : ℕ) (j : S) (a : A), a ∈ M.actions j →
stateActionLaw M π'.toHistory μ n (j, a) =
stateActionLaw M π μ n (j, a) := by sorry
end PutermanMDP.MarkovPolicies
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setting and hypotheses.
- is a countable, nonempty type of states. is an arbitrary type of actions.
- is any model: nonempty admissible action sets , transition PMFs for , and real rewards .
- There is no assumption on the rewards; they do not appear in the statement.
Conclusion. Take every initial PMF on and every history policy , that is, every PMF on for each history . Then there exists a Markov policy , which may depend on both and . A Markov policy gives a PMF on for each time and state . As a history policy, acts on a history by using , where is the number of past pairs.
The existence claim is that for every , every state and every admissible action :
Here is the state–action law generated by a policy from :
- Draw and start from history .
- Repeat times: draw an action from given the current history, draw the next state from , and prepend the (state, action) pair to the history list.
- Draw one more action from given the resulting history .
is the probability that the pair equals . The equality is between probabilities in .
Scope of the equality. Only the one-epoch joint marginals of (current state, chosen action) are asserted equal, separately for each . The full laws of histories, and joint laws across different epochs, are not claimed equal. Pairs with are not covered by the statement.
Degenerate cases. At the claim reads
This places no constraint on at states with . may have a single element, and is necessarily nonempty. may be any PMF, including a point mass.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.