Proof of Theorem 9.1, p. 887 — under essential finiteness every policy's return is at most lim U^n0
ProvedNegativeDP.EssFinite.return_le_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 . Put . Then:
- for every and every state , so exists;
- every policy satisfies, at every state ,
In the paper this limit is called inside the proof of Theorem 9.1; it is a different object from until the theorem identifies the two. This inequality is one half of Theorem 9.1 (a).
Formalization Note Monotonicity is stated as Antitone in for each state, and the limit of the non-increasing sequence is written as its infimum in EReal. The policy ranges over every randomized history-dependent plan.
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, first paragraph. If `A` is essentially
finite by `π*` and `U` is its operator, then `v_n = NegativeDP.OptEq.U^n 0` is non-increasing in `n`, and
every policy satisfies `I(π) ≦ lim_n v_n = inf_n v_n`. -/
theorem return_le_lim (P : NegativeDP.Stationary.Problem S A) (πstar : MarkovPlan S A)
(h : EssentiallyFinite P πstar) :
(∀ s, Antitone (fun n => (NegativeDP.OptEq.U P πstar)^[n] 0 s)) ∧
∀ (σ : Plan (S := S) (A := A)) (s : S), NegativeDP.Stationary.I P σ s ≤ ⨅ n, (NegativeDP.OptEq.U P πstar)^[n] 0 s := by sorry
end NegativeDP.EssFinite
Source
Strauch, Negative Dynamic Programming, Ann. Math. Statist. 37 (1966), p. 887, proof of Theorem 9.1 (first paragraph)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.