Theorem 9.1 (N) — essentially finite actions: U^n0 → v* and a stationary optimal policy exists
ProvedNegativeDP.EssFinite.theorem91Consider Strauch's negative dynamic programming problem: non-empty Borel state and action spaces , , a law of motion , and a Borel return with , without discounting. Suppose that is essentially finite by the Markov policy : there is a partition of into Borel sets such that for every with one of is equivalent to at (same return function and same transition law). Let be the operator associated with , with . Then
- value iteration from zero converges to the optimal return: for every state ,
- there exists a stationary optimal policy , i.e. a measurable with for every .
The paper states this for the discounted and negative cases; this item is the negative case. In particular, when is finite there is an optimal policy (§1). Without such a hypothesis, Example 6.1 of the paper shows that in the negative case , the supremum of over the policies generated by the rules of , and the supremum over the corresponding stationary policies may all differ.
Formalization Note The convergence in (1) is pointwise in EReal, so the limit is allowed; . is the supremum over every randomized history-dependent plan, and optimality is against every plan at every state. Essential finiteness is zero-based: Lean's piece n is the paper's and allows ; the pieces are measurable, pairwise disjoint and cover , and may be empty.
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]
/-- Theorem 9.1 (N), Strauch (1966), p. 887. If `A` is essentially finite by
`π* = (f_1, f_2, …)` and `U` is the operator associated with `π*`, then
(a) `U^n 0 → v* = sup_π NegativeDP.Stationary.I(π)` pointwise, and
(b) there exists a stationary optimal policy `f^(∞)`. -/
theorem theorem91 (P : NegativeDP.Stationary.Problem S A) (πstar : MarkovPlan S A)
(h : EssentiallyFinite P πstar) :
(∀ s, Tendsto (fun n => (NegativeDP.OptEq.U P πstar)^[n] 0 s) atTop (𝓝 (NegativeDP.Stationary.vstar P s))) ∧
∃ f : {g : S → A // Measurable g}, NegativeDP.Stationary.IsOptimal P (stationary f).toPlan := by sorry
end NegativeDP.EssFinite
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.