Proposition 7.1.1 — costs over finitely many initial transitions do not affect the average cost
ProvedSennottDP.SEN.prop_7_1_1_average_cost_tailaverage-costp2o-batch-b23ap2o-gran-per-chapterp2o-plan-bookp2o-v1
Let be a positive integer, an initial state and a policy such that the -horizon cost is finite. Then the average cost can be computed from the costs incurred from time on:
The costs accumulated over any fixed finite number of transitions do not change the average cost, provided they are finite; the finiteness hypothesis cannot be dropped (Example 7.1.2).
Formalization Note The expectation of the sum is the sum over of the expected costs, in ℝ≥0∞. For the natural-number difference is and the quotient is a junk value; the limit supremum along is unaffected.
Preamble
import Mathlib import Definitions.Def_SennottDP_SEN_Criteria open scoped ENNReal NNReal open Filter
Formal statement
namespace SennottDP.SEN
/-- Sennott (1999), Proposition 7.1.1, p. 128: let `K` be a positive integer, `i` an initial
state and `θ` a policy with `v_{θ,K}(i) < ∞`. Then
`J_θ(i) = limsup_{n→∞} (1/(n − K)) E_θ[∑_{t=K}^{n-1} C(X_t,A_t) | X_0 = i]` (7.1).
The expectation of the sum is the sum of the expected costs `E_θ[C(X_t,A_t) | X_0 = i]`,
`K ≤ t < n`; the terms with `n ≤ K` (where `n − K = 0` in `ℕ`) do not affect the limit supremum. -/
theorem prop_7_1_1_average_cost_tail {S : Type} [Countable S] {Act : Type} (M : SennottDP.Discounted.MDC S Act)
(K : ℕ) (hK : 0 < K) (i : S) (θ : SennottDP.Discounted.Policy M) (hfin : horizonCost M θ K i < ⊤) :
avgCost M θ i =
limsup (fun n : ℕ => (∑ t ∈ Finset.Ico K n, SennottDP.Discounted.expCost M θ i t) / ((n - K : ℕ) : ℝ≥0∞))
atTop := by sorry
end SennottDP.SEN
Source
Sennott, Stochastic Dynamic Programming and the Control of Queueing Systems (Wiley, 1999), p. 128, Proposition 7.1.1, (7.1)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.