Lemma 6.1 (N) — lim U^n0 ≥ sup over π̂-generated policies ≥ sup over π̂-generated stationary policies
ProvedNegativeDP.EssFinite.lemma61Consider Strauch's negative dynamic programming problem: non-empty Borel state and action spaces , , a law of motion , and a Borel return with . Let be any Markov policy, i.e. any countable sequence of measurable maps , and let be its operator, . A measurable is -generated if there is a partition of into Borel sets with on ; a Markov policy is -generated if each of its maps is. Let be the set of -generated policies.
Then the pointwise limit exists (with ), and at every state
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 -generated policies, the optimal infinite-horizon return among them, and the optimal return among -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 with pointwise in EReal. consists of non-random Markov plans whose every rule is -generated (IsGeneratedPlan of the published Operators module, with a measurable, pairwise disjoint, covering partition indexed from , the piece n carrying π̂ n); the stationary are those with -generated (IsGenerated). Suprema are in EReal.
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)
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.