Lemma 2 — along policy improvement the gaps ε_i^{R_n} tend to 0 at every state
ProvedDermanDenumerable.AvgCost.lemma2average-costdynamic-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1policy-improvement
Assume (A), (B), (C), (E) and (F). Let be the uniformly bounded family of (E), and let be a sequence of policy improvement iterations starting from an arbitrary : for every , the decisions of minimize at every state. With
we have, for each ,
The lemma says that the improvement step eventually stops finding improvements at each fixed state; it is the key step of Theorem 4.
Formalization Note. The improvement step is taken against the family of (E), as in the paper's definition of ; ties among minimizing decisions are broken arbitrarily. Condition (D) is implied by (E) and is not a separate hypothesis. The sequence is indexed from in Lean.
Preamble
import Mathlib import Definitions.Def_DermanDenumerable_AvgCost_Model open scoped Topology open Filter SennottDP.AvgFinite
Formal statement
namespace DermanDenumerable.AvgCost
/-- Derman (1966), Lemma 2, pp. 1551–1552: under (A), (B), (C), (E) (hence (D)) and (F), for any
sequence `R_1, R_2, ⋯` of policy improvement iterations (relative to the family `{g^R, v^R}` of (E))
starting from an arbitrary rule of `C''`, `lim_{n→∞} ε_i^{R_n} = 0` for every state `i`. -/
theorem lemma2 {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) :
∀ i : S, Tendsto (fun n : ℕ => gap M w gR vR (R n) (R (n + 1)) i) atTop (𝓝 0) := by sorry
end DermanDenumerable.AvgCost
Source
Derman, Denumerable State Markovian Decision Processes—Average Cost Criterion, Ann. Math. Statist. 37(6) (1966), pp. 1551–1552, Lemma 2 (ε_i^R and the procedure on p. 1551)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.