Proposition 7.7.2 — the conclusions of Theorem 7.2.3 hold under the weaker (H) assumptions
ProvedSennottDP.SEN.prop_7_7_2_h_acoiacoiaverage-costp2o-batch-b23ap2o-gran-per-chapterp2o-plan-bookp2o-v1
Let be an MDC for which the (H) assumptions hold for the distinguished state , with function in (H2) and function in (H3). Then the conclusions of Theorem 7.2.3 are valid, with the function from (H3):
- there is a finite constant for every ;
- a limit function exists; every limit function satisfies and
every stationary policy realizing this minimum is average cost optimal with , and ; 3. every limit point of stationary policies realizing the discount optimality equation is average cost optimal, has an associated limit function, and every associated satisfies (7.11) and (7.12); 4. for every average cost optimal policy and every , .
Formalization Note The statement is Theorem 7.2.3's, with the (H) assumptions in place of (SEN) and in place of ; conventions are as there.
Preamble
import Mathlib import Definitions.Def_SennottDP_SEN_Assumptions open scoped ENNReal NNReal open Filter Topology
Formal statement
namespace SennottDP.SEN
/-- Sennott (1999), Proposition 7.7.2, p. 158: let `Δ` be an SennottDP.Discounted.MDC for which the (H) assumptions
hold for the distinguished state `z`, with function `Mf` in (H2) and function `Lf` in (H3). Then
the conclusions of Theorem 7.2.3 are valid, where `L` is the function `Lf` from (H3):
(i) there is a finite constant `J = lim_{α→1⁻} (1 − α) V_α(i)` for all `i`;
(ii) a limit function exists; every limit function `h` satisfies `−Lf ≤ h ≤ Mf` and the average
cost optimality inequality (7.9); every stationary policy `e` realizing the minimum in (7.9) is
average cost optimal with average cost `J`, and (7.10) holds;
(iii) every limit point `f` of discount optimal stationary policies is average cost optimal, has
an associated limit function, and every associated `h` satisfies (7.11) and (7.12);
(iv) the average cost under any average cost optimal policy is obtained as a limit. -/
theorem prop_7_7_2_h_acoi {S : Type} [Countable S] {Act : Type} (M : SennottDP.Discounted.MDC S Act) (z : S)
(Mf Lf : S → ℝ) (hH : HAssumptions M z Mf Lf) :
∃ J : ℝ≥0,
-- (i)
(∀ i, Tendsto (fun α : ℝ => ENNReal.ofReal (1 - α) * discValue M α i) (𝓝[<] 1)
(𝓝 (J : ℝ≥0∞))) ∧
-- (ii)
(∃ h : S → ℝ, IsLimitFunction M z h) ∧
(∀ h : S → ℝ, IsLimitFunction M z h →
(∀ i, -Lf i ≤ h i ∧ h i ≤ Mf i) ∧
(∀ i, acoiMin M h i ≤ (((J : ℝ) + h i : ℝ) : EReal)) ∧
∀ e : StationaryPolicy M, RealizesACOI M h e →
IsAverageOptimal M e.toPolicy ∧ (∀ i, avgCost M e.toPolicy i = (J : ℝ≥0∞)) ∧
∀ i, Tendsto (fun n : ℕ => (((n : ℝ)⁻¹ : ℝ) : EReal) * expReal M e.toPolicy i n h)
atTop (𝓝 0)) ∧
-- (iii)
(∀ fam : ℝ → StationaryPolicy M, (∀ α ∈ Set.Ioo (0 : ℝ) 1, RealizesDOE M α (fam α)) →
∀ f : StationaryPolicy M, IsLimitPoint M fam f →
IsAverageOptimal M f.toPolicy ∧
(∃ h : S → ℝ, IsAssociated M z fam f h) ∧
∀ h : S → ℝ, IsAssociated M z fam f h →
(∀ i, ((M.C i (f.1 i) : ℝ) : EReal) + wsum (M.P i (f.1 i)) h ≤
(((J : ℝ) + h i : ℝ) : EReal)) ∧
∀ i, Tendsto (fun n : ℕ => (((n : ℝ)⁻¹ : ℝ) : EReal) * expReal M f.toPolicy i n h)
atTop (𝓝 0)) ∧
-- (iv)
(∀ ψ : SennottDP.Discounted.Policy M, IsAverageOptimal M ψ → ∀ i,
Tendsto (fun n : ℕ => horizonCost M ψ n i / (n : ℝ≥0∞)) atTop (𝓝 (avgCost M ψ i))) := by sorry
end SennottDP.SEN
Source
Sennott, Stochastic Dynamic Programming and the Control of Queueing Systems (Wiley, 1999), p. 158, Proposition 7.7.2 (conclusions of Theorem 7.2.3, pp. 134–135)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.