§3 — g_n(i) is the optimal expected cost over periods 0, …, n among all rules
ProvedDermanDenumerable.AvgCost.finite_horizon_optimaldynamic-programmingfinite-horizonp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Under conditions (A) and (B), let be the value iteration of (5) and, for a rule , let be the total expected cost incurred over the periods under when . Then for every :
- every rule does at least as badly: for every rule and every ;
- the bound is attained: some rule has for every .
This is the paper's statement that " is the result of an optimal rule for those periods" (proof of Theorem 1). Part 1 is the inequality used there to conclude .
Formalization Note. The paper's phrase reads "over the periods under ", with the final missing in print; the meaning, from the gloss of (5), is the periods . No optimality equation is assumed. The minimum is over all history-dependent randomized rules.
Preamble
import Mathlib import Definitions.Def_DermanDenumerable_AvgCost_Model open scoped Topology open Filter SennottDP.AvgFinite
Formal statement
namespace DermanDenumerable.AvgCost
/-- Derman (1966), §3, proof of Theorem 1, p. 1549: `g_n(i)` of (5) is the result of an optimal rule
for the periods `0, 1, ⋯, n`. For every `n`: (a) no rule `R ∈ C` has total expected cost
`h_n(i)` over the periods `0, ⋯, n` below `g_n(i)`, at any initial state `i`; and (b) some rule
`R ∈ C` attains `g_n(i)` at every initial state. -/
theorem finite_horizon_optimal {S Act : Type} [Countable S] (M : MDC S Act)
(w : S → Act → ℝ) (hB : CostBounded M w) (n : ℕ) :
(∀ (R : Policy M) (i : S), valueIter M w n i ≤ horizonCostR R w i n) ∧
∃ R : Policy M, ∀ i : S, horizonCostR R w i n = valueIter M w n i := by sorry
end DermanDenumerable.AvgCost
Source
Derman, Denumerable State Markovian Decision Processes—Average Cost Criterion, Ann. Math. Statist. 37(6) (1966), p. 1549, §3, gloss of (5) and proof of Theorem 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.