Proof of Theorem 9.1, p. 887 — the limit of value iteration is conserved by U
ProvedNegativeDP.EssFinite.lim_le_U_limdynamic-programmingnegative-dynamic-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
In Strauch's negative dynamic programming problem (non-empty Borel , , law of motion , Borel return with ), suppose that is essentially finite by the Markov policy , and let be the operator associated with . Let
(the sequence is non-increasing). Then
In the paper this limit is called inside the proof of Theorem 9.1. Together with the bound it is one of the two steps of the proof of Theorem 9.1.
Formalization Note is written as the pointwise infimum of in EReal; it is non-positive, so is applied to an element of .
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]
/-- Proof of Theorem 9.1 (N), Strauch (1966), p. 887, second paragraph. If `A` is essentially
finite by `π*` and `U` is its operator, the limit `v^∞ = lim_n NegativeDP.OptEq.U^n 0 = inf_n NegativeDP.OptEq.U^n 0` (the
paper's "v*" inside this proof) satisfies `U v^∞ ≧ v^∞`. -/
theorem lim_le_U_lim (P : NegativeDP.Stationary.Problem S A) (πstar : MarkovPlan S A)
(h : EssentiallyFinite P πstar) :
∀ s, (⨅ n, (NegativeDP.OptEq.U P πstar)^[n] 0 s) ≤ NegativeDP.OptEq.U P πstar (fun t => ⨅ n, (NegativeDP.OptEq.U P πstar)^[n] 0 t) s := by sorry
end NegativeDP.EssFinite
Source
Strauch, Negative Dynamic Programming, Ann. Math. Statist. 37 (1966), p. 887, proof of Theorem 9.1 (second paragraph)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.