Theorem 5.5.1 — Markovization preserves state-action marginals
ProvedPutermanMDP.MarkovPolicies.markovizationLet be an admissible randomized history-dependent policy in a stationary model on a nonempty finite or countable state space. For each initial state , there exists a randomized Markov policy such that, for every epoch , state , and action ,
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 , which represents the conditional notation on the page without conditioning an arbitrary initial law on a null event. Time represents epoch . No boundedness or integrability of rewards is assumed, because the conclusion concerns only probability distributions. The replacement need not be deterministic or stationary.
import Mathlib import Definitions.Def_PutermanMDP_MarkovPolicies_Model
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
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setting. Let and be arbitrary types. is the state space and must be countable and nonempty. is the action space and has no assumptions on it: it need not be countable or nonempty. The following are fixed:
- , an object of type
Modelover and . It provides, among other data, a set for each state . - , an object of type
HistoryPolicyrelative to .
Model, HistoryPolicy, MarkovPolicy, the conversion (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 of type HistoryPolicy relative to , an initial distribution on , a natural number and a pair , the quantity
denotes the value of stateActionLaw on these arguments. In this statement is always , the point-mass (Dirac) probability distribution at a state .
Assertion. For every initial state there is an object of type MarkovPolicy relative to with the following property. Let be converted to a history policy. Then for every , every state and every action with ,
The quantifiers come in the order "for every , there exists ". So the Markov policy may depend on the initial state ; the statement does not claim that one works for all initial states at once. It also does not claim that is unique.
Scope of the equality. The equality is claimed only at the points listed, and nothing else is said:
- It covers only pairs with . Pairs where is not an admissible action at 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 , 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 . This case is included, so the equality must already hold at index , whatever means there.
- One-element . The assertion still says the same thing, now about a single initial state , and is forced to equal .
- Empty admissible action sets. If is empty for some , nothing is required at that .
- Empty , or all admissible action sets empty. If every set is empty, which happens in particular when is empty, the equality part holds vacuously. The statement then only asserts that for each at least one object of type
MarkovPolicyrelative to exists. - Whether can be empty at all. Whether such a policy, or such a model, can exist when is empty depends on the imported definitions, which are not shown.
- Junk values. Whether 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.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.