(4) — a rule of C'' solving (2) with bounded v has average cost g
ProvedDermanDenumerable.AvgCost.eq4_avg_cost_of_evaluationLet be a denumerable state space with finite decision sets and bounded costs (conditions (A) and (B)). Let be a stationary deterministic rule making decision at state , write , and suppose that a number and a bounded set of numbers satisfy equation (2):
Then for every initial state the expected average cost converges to :
This is display (4) of the paper: is the expected average cost per unit time under . It holds for every rule of that solves (2) with a bounded , and no recurrence condition is needed. It is used in the proof of Theorem 1 for the minimizing rule , and in Lemma 1 as .
Formalization Note. The statement asserts both that the limit exists and that it equals ; is the limsup of the averages. The bounded is part of the hypothesis, as in the paper (the interchange of summation in (3) relies on it).
import Mathlib import Definitions.Def_DermanDenumerable_AvgCost_Model open scoped Topology open Filter SennottDP.AvgFinite
namespace DermanDenumerable.AvgCost
/-- Derman (1966), §3, display (4), p. 1549: if the rule `e ∈ C''` (decision `k_i = e.f i`) and a
bounded `{v_j}` satisfy (2) with the number `g`, then for every initial state `i` the expected
average cost `(T + 1)^{-1} Σ_{t=0}^{T} E_e W_t` converges to `g`; in particular `Q_e(i) = g`. -/
theorem eq4_avg_cost_of_evaluation {S Act : Type} [Countable S] (M : MDC S Act)
(w : S → Act → ℝ) (hB : CostBounded M w) (e : StationaryPolicy M) (g : ℝ) (v : S → ℝ)
(hv : BddFun v) (hD : IsEvaluation M w e g v) :
∀ i : S,
Tendsto (fun T : ℕ => ((T : ℝ) + 1)⁻¹ *
∑ t ∈ Finset.range (T + 1), expCostR e.toPolicy w i t) atTop (𝓝 g) ∧
avgCostR e.toPolicy w i = g := by sorry
end DermanDenumerable.AvgCost
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.