Proposition 8.7.1 (corrected: uniform lower bound in (WAC3)) — under (WAC) the conclusions of Theorem 8.1.1 hold
ProvedSennottDP.AvgASM.wac_limit_optimal_v2Corrected version (v2) of Proposition 8.7.1 (p. 194) of Sennott, Stochastic Dynamic Programming and the Control of Queueing Systems.
Let be an approximating sequence for the MDC on a countable state space, and let the constants and functions satisfy the (WAC) assumptions: (WAC1), (WAC2), (WAC4) are (AC1), (AC2), (AC4) — the optimality equations
and with — and (WAC3): there is a nonnegative function on with for all such that, for every stationary policy and initial state , (i) , (ii) for , and (iii) . Assume in addition that the lower bound of (WAC3) holds uniformly: for a nonnegative function satisfying (i), for all and all . Then the conclusions of Theorem 8.1.1 are valid:
- the limit exists and is the minimum average cost in , i.e. for all ;
- any limit point of a sequence of stationary policies realizing the minimum in (8.1) is average cost optimal for .
Since (AC) implies (WAC) (take ), this is a strengthening of Theorem 8.1.1 that allows the lower bound on the relative values to depend on the state.
Formalization Note. The book states (WAC3) only through the pointwise bound for each , and the retired version followed it; its proof, however, passes to the limit in (8.1) by a Fatou-type argument that applies to every and every together with (WAC3₂)(i) for the same . With only the pointwise bound the statement is false: the counterexample accepted on prove2.me (every state absorbing, very negative at the newest state of ) satisfies (WAC) and refutes conclusion 1; the same example refuted Theorem 8.1.1 as first stated, which has been replaced by SennottDP.AvgASM.ac_limit_optimal_v2. Consistently with that replacement, this version keeps AS.WAC JN rN as in the original definition module Def_SennottDP_AvgASM_Assumptions and adds the uniform bound as the explicit hypothesis hQ, for a nonnegative that also satisfies the convergence and finiteness condition (WAC3₂)(i); the conclusions are unchanged. The minimum average cost is an infimum over all general policies, valued in ; its equality with the real number is stated in EReal.
import Mathlib import Definitions.Def_SennottDP_AvgASM_Assumptions open scoped ENNReal NNReal Topology open Filter
namespace SennottDP.AvgASM
/-- **Proposition 8.7.1** (Sennott 1999, p. 194), corrected: (WAC3) is used **uniformly**. The
book states (WAC3₁) as `−Q(i) ≤ liminf_{N→∞} r^N(i)` for each fixed `i`, but the proof passes
to the limit in (8.1) by a Fatou argument that uses the bound `r^N(j) ≥ −Q(j)` for all `j ∈ S_N`
and all `N ≥ N₀`, together with (WAC3₂)(i) for the same `Q`; with only the pointwise `liminf`
bound the statement is false (the counterexample accepted on prove2.me against
`SennottDP.AvgASM.wac_limit_optimal`, which also refuted Theorem 8.1.1 as first stated; see
`ac_limit_optimal_v2`). The hypothesis `hQ` adds that uniform bound, for a nonnegative function
`Q` satisfying (WAC3₂)(i); the conclusions are unchanged:
`lim_{N→∞} J^N` exists and equals the (constant) minimum average cost `J(i)` of `Δ`, and any
limit point of a sequence of stationary policies realizing the minimum in (8.1) is average cost
optimal for `Δ`. -/
theorem wac_limit_optimal_v2 {S : Type*} {Act : Type*} [Countable S] {M : MDC S Act}
(AS : ApproxSeq M) (JN : ℕ → ℝ) (rN : ℕ → S → ℝ) (hWAC : AS.WAC JN rN)
(hQ : ∃ Q : S → ℝ≥0,
(∀ N, AS.N₀ ≤ N → ∀ i ∈ AS.SN N, -(Q i : ℝ) ≤ rN N i) ∧
∀ e : StationaryPolicy M, ∀ i,
Tendsto (fun N => ∑ j ∈ AS.SN N, AS.PN N i (e.f i) j * (Q j : ℝ≥0∞)) atTop
(𝓝 (∑' j, M.P i (e.f i) j * (Q j : ℝ≥0∞))) ∧
∑' j, M.P i (e.f i) j * (Q j : ℝ≥0∞) < ⊤) :
(∃ Jstar : ℝ, Tendsto JN atTop (𝓝 Jstar) ∧
∀ i, ((avgValue M i : ℝ≥0∞) : EReal) = (Jstar : EReal)) ∧
∀ e : ℕ → S → Act, AS.IsStationarySeq e →
(∀ N, AS.N₀ ≤ N → ∀ i ∈ AS.SN N, JN N + rN N i = AS.acoeTerm rN N i (e N i)) →
∀ f : StationaryPolicy M, AS.IsLimitPoint e f → IsAverageOptimal f.toPolicy := by sorry
end SennottDP.AvgASM