Proposition 7.1.1 — Markov policies suffice for total reward
ProvedPutermanMDP.TotalReward.markov_reductionLet and each nonempty action set be finite or countably infinite, with real rewards and stochastic transition rows. Suppose Assumption 7.1.1 holds: for every history-dependent randomized policy and initial state , at least one of the expected accumulated positive and negative rewards is finite. Then for every state,
Here consists of all admissible history-dependent randomized policies, and consists of all time-dependent randomized Markov policies. This allows pointwise total-reward optimization to be restricted to Markov policies.
Formalization Note Both suprema are extended-real suprema. The statement permits infinite values and asserts neither attainment nor the existence of one policy attaining the supremum at every state.
import Mathlib import Definitions.Def_PutermanMDP_TotalReward_Model
namespace PutermanMDP.TotalReward
/-- Proposition 7.1.1. Equality of pointwise suprema does not assert that
one Markov policy attains them simultaneously at all states. -/
theorem markov_reduction {S : Type*} {A : S → Type*}
[Countable S] [Nonempty S] [∀ s, Countable (A s)] [∀ s, Nonempty (A s)]
(M : Model S A) (hM : WellDefined M) (s : S) :
optimalValue M s = (⨆ π : HRPolicy S A, policyValue M π s) ∧
optimalValue M s = (⨆ π : MRPolicy S A, policyValue M (markovPolicy π) s) := by sorry
end PutermanMDP.TotalReward
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setting. is a countable, nonempty set of states. Each state has a countable, nonempty set of actions . The model consists of real rewards and discrete transition distributions on .
A history is a finite list of past pairs with , together with a current state ; its length is the number of pairs. A history-dependent randomized policy assigns a distribution on to every history, including histories of probability zero.
The history laws are defined recursively:
- is the point mass on the history with an empty list and current state .
- draws , then , then , and outputs extended by with current state .
The reward parts are
where , , and divergent sums equal . The policy value is in , and the optimal value is over all history-dependent randomized policies.
Hypothesis. "WellDefined" holds: for every history-dependent randomized policy and every state , or .
Conclusion. For every state , both of the following equalities hold:
and
- The first equality restates the definition of .
- In the second, the supremum runs over all sequences where each is a distribution on . The policy is defined by , so the decision depends only on the length of the history and its current state.
- Both equalities are between extended reals, so they may hold with value or .
- The statement is made separately for each . It does not assert that one Markov policy attains or approaches the supremum at all states at once, and it does not assert that any supremum is attained.
Degenerate cases. Nonemptiness of every ensures that both policy classes are nonempty, so neither supremum is over an empty set. Because of the WellDefined hypothesis, no policy value in either supremum arises from the case ; without it, that case would be given the value . The term, the reward at the initial state, is included in all sums. WellDefined is a hypothesis about all policies and can fail for a given model, for example when some policy has both reward parts infinite. In that case the statement says nothing about .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.