Lemma A1 (p. 632) — a bounded-below supersolution of (A1) bounds g_f above by g; a bounded subsolution bounds it below
ProvedSennott1989.AvgCost.lemma_A1average-costmarkov-decision-processp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a stationary policy, a real constant, and a real function on the states.
- If for every and
then for every . 2. If the inequality in (A1) is reversed and for all , then for every .
Here is the lim sup average cost of from . The first statement is the verification step that turns the optimality inequality (5) into an upper bound on average cost.
Formalization Note is compared with in the extended reals; may be any real number. The sum is the extended-real positive-part-minus-negative-part sum. Its negative part is finite in the first case, and its positive part is finite in the second.
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 A1, p. 632. Let `g` be a real constant, `h` a real function,
and `f` a stationary policy.
1. If `−N ≤ h(i)` and `g + h(i) ≥ C(i, f) + ∑_j P_{ij}(f) h(j)` for all `i ≥ 0` (A1), then
`g_f(i) ≤ g` for every `i`.
2. If the inequality in (A1) is reversed and `h(i) ≤ N` for all `i`, then `g_f(i) ≥ g` for all `i`.
**Formalization Note** `g_f(i)` is the lim sup average cost `SennottDP.SEN.avgCost` in `[0, ∞]`,
compared with the real `g` in `EReal`; `g` may be any real number. The sum `∑_j P_{ij}(f) h(j)` is
the extended-real `SennottDP.SEN.wsum`: its negative part is finite in the first case, and its
positive part is finite in the second. -/
theorem lemma_A1 {Act : Type} (M : MDC ℕ Act) (f : StationaryPolicy M) (g : ℝ) (h : ℕ → ℝ)
(N : ℝ) :
((∀ i, -N ≤ h i) →
(∀ i, acoiTerm M h i (f.1 i) ≤ ((g + h i : ℝ) : EReal)) →
∀ i, (SennottDP.SEN.avgCost M f.toPolicy i : EReal) ≤ (g : EReal)) ∧
((∀ i, h i ≤ N) → (∀ i, ((g + h i : ℝ) : EReal) ≤ acoiTerm M h i (f.1 i)) →
∀ i, (g : EReal) ≤ (SennottDP.SEN.avgCost M f.toPolicy i : EReal)) := 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 A1, (A1), p. 632
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.