Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 7.1.1 — Markov policies suffice for total reward

Proved
PutermanMDP.TotalReward.markov_reduction

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

dynamic-programmingmdpp2o-gran-per-chapterp2o-plan-bookp2o-v1total-reward

Let SSS and each nonempty action set AsA_sAs​ be finite or countably infinite, with real rewards and stochastic transition rows. Suppose Assumption 7.1.1 holds: for every history-dependent randomized policy π\piπ and initial state sss, at least one of the expected accumulated positive and negative rewards is finite. Then for every state,

v∗(s)=sup⁡π∈ΠHRvπ(s)=sup⁡π∈ΠMRvπ(s).v^*(s)=\sup_{\pi\in\Pi^{HR}}v^\pi(s)=\sup_{\pi\in\Pi^{MR}}v^\pi(s).v∗(s)=π∈ΠHRsup​vπ(s)=π∈ΠMRsup​vπ(s).

Here ΠHR\Pi^{HR}ΠHR consists of all admissible history-dependent randomized policies, and ΠMR\Pi^{MR}ΠMR 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.

Preamble
import Mathlib
import Definitions.Def_PutermanMDP_TotalReward_Model
Formal statement
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
Source
Puterman, Markov Decision Processes, Wiley, 1994, p. 280 (PDF 296), Proposition 7.1.1
Read-back

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

Setting. SSS is a countable, nonempty set of states. Each state sss has a countable, nonempty set of actions AsA_sAs​. The model MMM consists of real rewards r(s,a)r(s,a)r(s,a) and discrete transition distributions p(⋅∣s,a)p(\cdot\mid s,a)p(⋅∣s,a) on SSS.

A history hhh is a finite list of past pairs (si,ai)(s_i,a_i)(si​,ai​) with ai∈Asia_i\in A_{s_i}ai​∈Asi​​, together with a current state shs_hsh​; its length ∣h∣|h|∣h∣ is the number of pairs. A history-dependent randomized policy π\piπ assigns a distribution π(⋅∣h)\pi(\cdot\mid h)π(⋅∣h) on AshA_{s_h}Ash​​ to every history, including histories of probability zero.

The history laws are defined recursively:

  • P0π,sP^{\pi,s}_0P0π,s​ is the point mass on the history with an empty list and current state sss.
  • Pn+1π,sP^{\pi,s}_{n+1}Pn+1π,s​ draws h∼Pnπ,sh\sim P^{\pi,s}_nh∼Pnπ,s​, then a∼π(⋅∣h)a\sim\pi(\cdot\mid h)a∼π(⋅∣h), then t∼p(⋅∣sh,a)t\sim p(\cdot\mid s_h,a)t∼p(⋅∣sh​,a), and outputs hhh extended by (sh,a)(s_h,a)(sh​,a) with current state ttt.

The reward parts are

Vπ±(s)=∑n≥0∑h∑a∈AshPnπ,s(h) π(a∣h) r(sh,a)±∈[0,∞],V^\pm_\pi(s)=\sum_{n\ge0}\sum_h\sum_{a\in A_{s_h}}P^{\pi,s}_n(h)\,\pi(a\mid h)\,r(s_h,a)^\pm\in[0,\infty],Vπ±​(s)=n≥0∑​h∑​a∈Ash​​∑​Pnπ,s​(h)π(a∣h)r(sh​,a)±∈[0,∞],

where x+=max⁡(x,0)x^+=\max(x,0)x+=max(x,0), x−=max⁡(−x,0)x^-=\max(-x,0)x−=max(−x,0), and divergent sums equal +∞+\infty+∞. The policy value is Vπ(s)=Vπ+(s)−Vπ−(s)V_\pi(s)=V^+_\pi(s)-V^-_\pi(s)Vπ​(s)=Vπ+​(s)−Vπ−​(s) in [−∞,+∞][-\infty,+\infty][−∞,+∞], and the optimal value is v∗(s)=sup⁡πVπ(s)v^*(s)=\sup_\pi V_\pi(s)v∗(s)=supπ​Vπ​(s) over all history-dependent randomized policies.

Hypothesis. "WellDefined" holds: for every history-dependent randomized policy π\piπ and every state sss, Vπ+(s)<∞V^+_\pi(s)<\inftyVπ+​(s)<∞ or Vπ−(s)<∞V^-_\pi(s)<\inftyVπ−​(s)<∞.

Conclusion. For every state sss, both of the following equalities hold:

v∗(s)=sup⁡π history-dependentVπ(s)v^*(s)=\sup_{\pi\ \text{history-dependent}}V_\pi(s)v∗(s)=π history-dependentsup​Vπ​(s)

and

v∗(s)=sup⁡(πn)n≥0 MarkovVπ^(s).v^*(s)=\sup_{(\pi_n)_{n\ge0}\ \text{Markov}}V_{\hat\pi}(s).v∗(s)=(πn​)n≥0​ Markovsup​Vπ^​(s).
  • The first equality restates the definition of v∗v^*v∗.
  • In the second, the supremum runs over all sequences (πn)(\pi_n)(πn​) where each πn(⋅∣s′)\pi_n(\cdot\mid s')πn​(⋅∣s′) is a distribution on As′A_{s'}As′​. The policy π^\hat\piπ^ is defined by π^(⋅∣h)=π∣h∣(⋅∣sh)\hat\pi(\cdot\mid h)=\pi_{|h|}(\cdot\mid s_h)π^(⋅∣h)=π∣h∣​(⋅∣sh​), 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 +∞+\infty+∞ or −∞-\infty−∞.
  • The statement is made separately for each sss. 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 AsA_sAs​ 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 (+∞)−(+∞)(+\infty)-(+\infty)(+∞)−(+∞); without it, that case would be given the value −∞-\infty−∞. The n=0n=0n=0 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 MMM.

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