Theorem 4 — every limit point of policy improvement is a rule of C'' optimal over C
ProvedDermanDenumerable.AvgCost.theorem4Assume conditions (A), (B), (C), (E) and (F) for a Markovian decision process on a denumerable state space with finitely many decisions per state and bounded costs. Let be the uniformly bounded solutions of (2) given by (E), and let be any sequence of policy improvement iterations starting from an arbitrary : the decisions of minimize
at every state . Then:
- the sequence has a limit point , i.e. a subsequence whose decision at each state equals that of for all large ;
- every limit point is optimal over : for every rule and every ;
- for every limit point and every , as .
This is the paper's main theorem: on a denumerable state space, the policy improvement procedure "converges to a rule which is optimal over ".
Formalization Note. The paper's "converges" is read as items 1–2: its proof chooses a subsequence converging to and never shows that the whole sequence converges, which can fail when the minimization has ties. Item 3 records the convergence of the values that the proof establishes (). Condition (D) is implied by (E) and is not a separate hypothesis. The sequence is indexed from : R 0 is the paper's .
import Mathlib import Definitions.Def_DermanDenumerable_AvgCost_Model open scoped Topology open Filter SennottDP.AvgFinite
namespace DermanDenumerable.AvgCost
/-- Derman (1966), Theorem 4, p. 1552: under (A), (B), (C), (E) (hence (D)) and (F), let `R_1, R_2, ⋯`
be any sequence of policy improvement iterations (relative to the family `{g^R, v^R}` of (E)) from an
arbitrary initial rule of `C''`. Then (i) the sequence has a limit point `R*` in `C''`; (ii) every
limit point `R*` is optimal over the class `C` of all rules; and (iii) `g^{R_n}` converges to the
optimal average cost `Q_{R*}(i)`. -/
theorem theorem4 {S Act : Type} [Countable S] (M : MDC S Act)
(w : S → Act → ℝ) (hB : CostBounded M w) (hC : CondC M) (gR : StationaryPolicy M → ℝ)
(vR : StationaryPolicy M → S → ℝ) (hE : IsUniformEvaluation M w gR vR) (hF : CondF M)
(R : ℕ → StationaryPolicy M) (hR : IsPISequence M w vR R) :
(∃ e : StationaryPolicy M, IsLimitPoint R e) ∧
∀ e : StationaryPolicy M, IsLimitPoint R e →
OptimalOverC w e.toPolicy ∧
∀ i : S, Tendsto (fun n : ℕ => gR (R n)) atTop (𝓝 (avgCostR e.toPolicy w i)) := by sorry
end DermanDenumerable.AvgCost
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.