§3, proof of Proposition 8, p. 631 — V_α(i) is increasing in i, hence Assumption 2 holds
ProvedSennott1989.AvgCost.queue_value_monotonemarkov-decision-processmonotone-value-functionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1queueing-control
For the queueing model with variable service rates of Example 2 under the cost structure of p. 631 (so that is increasing in for every ), and for every discount factor :
- the -horizon discounted value (terminal cost ) is increasing in for every ;
- the discounted value is increasing in ;
- consequently, under Assumption 1, Assumption 2 holds with : for all and .
This is the step of the proof of Proposition 8 that supplies Assumption 2.
Formalization Note Values are in ; items 1–2 need no moment assumption. is the -horizon value of the Sennott (1999) development, which equals the paper's value iteration iterate. Since is defined only when the values are finite, item 3 is stated under Assumption 1.
Preamble
import Mathlib import Definitions.Def_Sennott1989_AvgCost_Assumptions import Definitions.Def_Sennott1989_AvgCost_Queue open scoped ENNReal NNReal open Filter Topology
Formal statement
namespace Sennott1989.AvgCost
open SennottDP.Discounted
/-- Sennott (1989), §3, proof of Proposition 8, p. 631 (unnumbered). For the queueing model with
variable service rates of Example 2 under the cost structure of p. 631 (`C(i, a)` increasing in
`i` for every `a`), the structure of (13) gives that `V_{α,n}(i)` is increasing in `i` for every
`n`, and hence (Proposition 3) `V_α(i)` is increasing in `i`, for every discount factor
`α ∈ (0, 1)`. Therefore Assumption 2 holds (with `N = 0`).
**Formalization Note** `V_{α,n}` is `SennottDP.Discounted.finiteValueFn` (the `n`-horizon
discounted value with terminal cost `0`, which equals the paper's value iteration iterate) and
`V_α` is `SennottDP.Discounted.valueFn`, both in `[0, ∞]`; monotonicity holds there without any
moment assumption. Since `h_α(i) = V_α(i) − V_α(0)` is defined only under Assumption 1 (see
`relValue`), the conclusion "Assumption 2 holds" is stated under Assumption 1. -/
theorem queue_value_monotone {Act : Type} [Fintype Act] [Nonempty Act] (q : QueueData Act) :
(∀ α : ℝ≥0, 0 < α → α < 1 → ∀ n : ℕ, Monotone fun i : ℕ => finiteValueFn q.toMDC α n i) ∧
(∀ α : ℝ≥0, 0 < α → α < 1 → Monotone fun i : ℕ => valueFn q.toMDC α i) ∧
(Assumption1 q.toMDC → Assumption2 q.toMDC 0) := 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, §3, proof of Proposition 8, first paragraph, p. 631
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.