(6) — a bounded solution of (1) keeps g_n(i) within a constant of ng + v_i
ProvedDermanDenumerable.AvgCost.eq6_value_iteration_boundaverage-costdynamic-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1value-iteration
Under conditions (A) and (B), suppose a number and a bounded set of numbers satisfy the optimality equation (1),
Let be the value iteration of (5): and . Then there is a constant such that
This is display (6) of the paper. Together with the finite-horizon optimality of it yields the lower bound for every rule in the proof of Theorem 1.
Formalization Note. The paper calls the constant ; it is renamed because M names the model. The series converges absolutely since .
Preamble
import Mathlib import Definitions.Def_DermanDenumerable_AvgCost_Model open scoped Topology open Filter SennottDP.AvgFinite
Formal statement
namespace DermanDenumerable.AvgCost
/-- Derman (1966), §3, display (6), p. 1549: if `{g, v_j}` with `v` bounded solves (1), there is a
constant `C` (the paper's `M`) with `n g + v_i − C ≤ g_n(i) ≤ n g + v_i + C` for all `n` and `i`,
where `g_n` is defined by (5). -/
theorem eq6_value_iteration_bound {S Act : Type} [Countable S] (M : MDC S Act)
(w : S → Act → ℝ) (hB : CostBounded M w) (g : ℝ) (v : S → ℝ) (hv : BddFun v)
(h1 : IsACOE M w g v) :
∃ C : ℝ, ∀ (n : ℕ) (i : S),
(n : ℝ) * g + v i - C ≤ valueIter M w n i ∧ valueIter M w n i ≤ (n : ℝ) * g + v i + C := by sorry
end DermanDenumerable.AvgCost
Source
Derman, Denumerable State Markovian Decision Processes—Average Cost Criterion, Ann. Math. Statist. 37(6) (1966), p. 1549, §3, displays (5) and (6)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.