Lemma 3.1 (N) — the n-stage returns decrease to the total return, Iₙ(π) ↓ I(π)
ProvedNegativeDP.Stationary.lemma31dynamic-programmingnegative-dynamic-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
In the negative dynamic programming problem, let be any policy and any initial state. Let be the expected return of the first stages (terminal reward ) and the expected total return. Then
that is, is non-increasing and converges to in .
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 and are minus sums of stage losses in ; 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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.