Proof of Theorem 8.4, p. 887 — the optimal return is the supremum over Markov policies
ProvedNegativeDP.EssFinite.vstar_eq_sup_markovIn Strauch's negative dynamic programming problem (non-empty Borel , , law of motion , Borel return with ), the optimal return , taken over all randomized history-dependent policies, equals the supremum over non-random Markov policies: for every state ,
The paper derives this identity from Theorem 8.1 in the proof of Theorem 8.4, and the proof of Theorem 9.1 uses it in the form "we have shown that ". It reduces the search for good policies from history-dependent randomized rules to sequences of measurable maps .
Formalization Note The identity is stated pointwise in , in EReal. A Markov policy is a sequence of measurable maps (MarkovPlan), turned into a plan with deterministic kernels by MarkovPlan.toPlan; the left side is the model's , the supremum over every Plan.
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]
/-- Proof of Theorem 8.4, Strauch (1966), p. 887: `sup_π NegativeDP.Stationary.I(π) = sup {NegativeDP.Stationary.I(π̂) | π̂ Markov}`,
pointwise, the left supremum over every randomized history-dependent policy and the right one
over non-random Markov policies. -/
theorem vstar_eq_sup_markov (P : NegativeDP.Stationary.Problem S A) (s : S) :
NegativeDP.Stationary.vstar P s = ⨆ m : MarkovPlan S A, NegativeDP.Stationary.I P m.toPlan s := by sorry
end NegativeDP.EssFinite
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.