Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 6.1 (N) — lim U^n0 ≥ sup over π̂-generated policies ≥ sup over π̂-generated stationary policies

Proved
NegativeDP.EssFinite.lemma61

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

dynamic-programmingnegative-dynamic-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Consider Strauch's negative dynamic programming problem: non-empty Borel state and action spaces SSS, AAA, a law of motion qqq, and a Borel return r≤0r\le 0r≤0 with ∫r(s,a,t) dq(t∣s,a)>−∞\int r(s,a,t)\,dq(t\mid s,a)>-\infty∫r(s,a,t)dq(t∣s,a)>−∞. Let π^=(f1,f2,… )\hat\pi=(f_1,f_2,\dots)π^=(f1​,f2​,…) be any Markov policy, i.e. any countable sequence of measurable maps S→AS\to AS→A, and let UUU be its operator, Uu=sup⁡nTnuUu=\sup_n T_n uUu=supn​Tn​u. A measurable f:S→Af:S\to Af:S→A is π^\hat\piπ^-generated if there is a partition of SSS into Borel sets S1,S2,…S_1,S_2,\dotsS1​,S2​,… with f=fnf=f_nf=fn​ on SnS_nSn​; a Markov policy is π^\hat\piπ^-generated if each of its maps is. Let G(π^)G(\hat\pi)G(π^) be the set of π^\hat\piπ^-generated policies.

Then the pointwise limit lim⁡n→∞Un0\lim_{n\to\infty}U^n0limn→∞​Un0 exists (with U00=0U^0 0=0U00=0), and at every state

lim⁡n→∞Un0  ≥  sup⁡π∈G(π^)I(π)  ≥  sup⁡f(∞)∈G(π^)I(f(∞)).\lim_{n\to\infty}U^n0\;\ge\;\sup_{\pi\in G(\hat\pi)}I(\pi)\;\ge\;\sup_{f^{(\infty)}\in G(\hat\pi)}I(f^{(\infty)}).n→∞lim​Un0≥π∈G(π^)sup​I(π)≥f(∞)∈G(π^)sup​I(f(∞)).

The paper states this for the discounted, positive and negative cases; this item is the negative case. No finiteness assumption on the actions is made. The three quantities are the limit of the optimal finite-horizon returns among π^\hat\piπ^-generated policies, the optimal infinite-horizon return among them, and the optimal return among π^\hat\piπ^-generated stationary policies; Example 6.1 of the paper shows that in the negative case all three may differ.

Formalization Note The existence of the limit is part of the statement (the paper takes it from Theorem 5.2 (e)), so the statement provides a function www with Un0→wU^n0\to wUn0→w pointwise in EReal. G(π^)G(\hat\pi)G(π^) consists of non-random Markov plans whose every rule is π^\hat\piπ^-generated (IsGeneratedPlan of the published Operators module, with a measurable, pairwise disjoint, covering partition indexed from 000, the piece n carrying π̂ n); the stationary f(∞)∈G(π^)f^{(\infty)}\in G(\hat\pi)f(∞)∈G(π^) are those with fff π^\hat\piπ^-generated (IsGenerated). Suprema are in EReal.

Preamble
import Mathlib
import Definitions.Def_DiscountedDP_Stationary_Operators
import Definitions.Def_NegativeDP_EssFinite_Model

open MeasureTheory ProbabilityTheory Filter Topology
open DiscountedDP.Stationary (Hist Plan MarkovPlan MarkovPlan.toPlan stationary IsGenerated IsGeneratedPlan)
Formal statement
namespace NegativeDP.EssFinite

variable {S A : Type*} [MeasurableSpace S] [StandardBorelSpace S] [Nonempty S]
  [MeasurableSpace A] [StandardBorelSpace A] [Nonempty A]

/-- Lemma 6.1 (N), Strauch (1966), p. 880. For any Markov policy `π̂` with operator `U`,
`lim NegativeDP.OptEq.U^n 0` exists and `lim NegativeDP.OptEq.U^n 0 ≧ sup_{π ∈ G(π̂)} NegativeDP.Stationary.I(π) ≧ sup_{f^(∞) ∈ G(π̂)} NegativeDP.Stationary.I(f^(∞))`,
where `G(π̂)` is the set of `π̂`-generated (Markov) policies. -/
theorem lemma61 (P : NegativeDP.Stationary.Problem S A) (πhat : MarkovPlan S A) :
    ∃ w : S → EReal,
      (∀ s, Tendsto (fun n => (NegativeDP.OptEq.U P πhat)^[n] 0 s) atTop (𝓝 (w s))) ∧
      (∀ s, (⨆ σ : {σ : MarkovPlan S A // IsGeneratedPlan πhat σ}, NegativeDP.Stationary.I P σ.1.toPlan s) ≤ w s) ∧
      ∀ s, (⨆ f : {f : {g : S → A // Measurable g} // IsGenerated πhat f},
              NegativeDP.Stationary.I P (stationary f.1).toPlan s) ≤
            ⨆ σ : {σ : MarkovPlan S A // IsGeneratedPlan πhat σ}, NegativeDP.Stationary.I P σ.1.toPlan s := by sorry

end NegativeDP.EssFinite
Source
Strauch, Negative Dynamic Programming, Ann. Math. Statist. 37 (1966), p. 880, Lemma 6.1
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 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