Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 3.1 (N) — the n-stage returns decrease to the total return, Iₙ(π) ↓ I(π)

Proved
NegativeDP.Stationary.lemma31

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

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

In the negative dynamic programming problem, let π\piπ be any policy and sss any initial state. Let In(π)=In(π,0)I_n(\pi)=I_n(\pi,0)In​(π)=In​(π,0) be the expected return of the first nnn stages (terminal reward 000) and I(π)I(\pi)I(π) the expected total return. Then

In(π)(s) ↓ I(π)(s)(n→∞),I_n(\pi)(s)\ \downarrow\ I(\pi)(s)\qquad (n\to\infty),In​(π)(s) ↓ I(π)(s)(n→∞),

that is, n↦In(π)(s)n\mapsto I_n(\pi)(s)n↦In​(π)(s) is non-increasing and converges to I(π)(s)I(\pi)(s)I(π)(s) in [−∞,0][-\infty,0][−∞,0].

The paper states Lemma 3.1 for the discounted, positive and negative cases; this item is the negative case. The lemma is the basic approximation of total returns by finite-horizon returns and is used in Theorems 4.1, 4.2 and 5.1.

Formalization Note. Returns lie in [−∞,0][-\infty,0][−∞,0] and are minus sums of stage losses in [0,∞][0,\infty][0,∞]; convergence is in the order topology of the extended reals.

Preamble
import Mathlib
import Definitions.Def_DiscountedDP_Stationary_Model
import Definitions.Def_DiscountedDP_Stationary_Return
import Definitions.Def_NegativeDP_Stationary_Model
open MeasureTheory ProbabilityTheory Filter Topology
open DiscountedDP.Stationary (Hist Plan MarkovPlan MarkovPlan.toPlan stationary)
Formal statement
namespace NegativeDP.Stationary

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

/-- Lemma 3.1, case N (p. 875): `Iₙ(π) ↓ I(π)`, where `Iₙ(π) = Iₙ(π, 0)`. -/
theorem lemma31 (P : Problem S A) (π : Plan (S := S) (A := A)) (s : S) :
    Antitone (fun n => In P π n 0 s) ∧
      Tendsto (fun n => In P π n 0 s) atTop (𝓝 (I P π s)) := by sorry

end NegativeDP.Stationary
Source
Strauch, Negative Dynamic Programming, Ann. Math. Statist. 37 (1966), p. 875, Lemma 3.1 (N)
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