Lemma A2 (p. 632) — lim sup_{α↑1} (1 − α)V_α(i) ≤ g_θ(i) for every policy θ
ProvedSennott1989.AvgCost.lemma_A2average-costdiscounted-costmarkov-decision-processp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Consider a Markov decision chain on the states with nonnegative costs. For every policy (history-dependent and randomized allowed) and every state ,
where is the optimal -discounted cost and the lim sup average cost of from .
This Tauberian-type comparison gives the lower bound in the proof of the Theorem.
Formalization Note No assumption is made; both sides are in and may be infinite. The lim sup is taken as with .
Preamble
import Mathlib import Definitions.Def_Sennott1989_AvgCost_Assumptions open scoped ENNReal NNReal open Filter Topology
Formal statement
namespace Sennott1989.AvgCost
open SennottDP.Discounted
/-- Sennott (1989), Appendix, Lemma A2, p. 632. If `θ` is any policy, then
`lim sup_{α↑1} (1 − α) V_α(i) ≤ g_θ(i)` for every state `i ≥ 0` (A5).
**Formalization Note** No assumption is made: `V_α(i)` and `g_θ(i)` lie in `[0, ∞]` and may be
infinite. `θ` ranges over all (history-dependent, randomized) policies. The lim sup is taken as
`α → 1` with `α < 1` (the filter `𝓝[<] 1` on `ℝ≥0`), in the complete lattice `[0, ∞]`. -/
theorem lemma_A2 {Act : Type} (M : MDC ℕ Act) (θ : Policy M) (i : ℕ) :
limsup (fun α : ℝ≥0 => ((1 - α : ℝ≥0) : ℝ≥0∞) * valueFn M α i) (𝓝[<] 1) ≤
SennottDP.SEN.avgCost M θ i := by sorry
end Sennott1989.AvgCost
Source
Sennott, Average Cost Optimal Stationary Policies in Infinite State Markov Decision Processes with Unbounded Costs, Oper. Res. 37(4):626–633 (1989), DOI 10.1287/opre.37.4.626, Appendix, Lemma A2, (A5), p. 632
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.