Display (5.8) — first-return bound J*_β(i) ≤ M E[τ] + J*_β(0) E[β^τ]
ProvedArapostathisAC.RossRecurrence.eq_5_8Consider the countable-state controlled Markov process of §5. Assume the cost is bounded: there is with for every state and every , as §5.1 assumes. Let and let be -discount optimal. Let be the return time to state , with on . Then for every state ,
This is the last line of display (5.8) in the proof of Theorem 5.3. It splits the discounted cost of at the first return to : before the cost is at most per step, and after the process restarts from under the optimal policy .
Formalization Note. The paper's intermediate line writes the first sum as . The exponent should be (a typo), and only the final inequality is stated here. All quantities are in ; is times the mean return time, possibly . The bound on is the standing hypothesis of §5.1.
import Mathlib import Definitions.Def_ArapostathisAC_RossRecurrence_CMP import Definitions.Def_ArapostathisAC_RossRecurrence_ReturnTime open MeasureTheory ProbabilityTheory open scoped ENNReal
namespace ArapostathisAC.RossRecurrence
/-- Display (5.8) (proof of Theorem 5.3, p. 302): if `c ≤ M₀` on the admissible pairs and
`f ∈ Π_SD` is `β`-discount optimal, then `J*_β(i) ≤ M₀ E^f_i[τ] + J*_β(0) E^f_i[β^τ]`. -/
theorem eq_5_8 {A : Type*} [MetricSpace A] [MeasurableSpace A] [BorelSpace A]
(M : CMP A) (M₀ : ℝ) (hc : ∀ i, ∀ a ∈ M.U i, M.c i a ≤ M₀)
(β : ℝ) (hβ : β ∈ Set.Ioo (0 : ℝ) 1) (f : StationaryPolicy M) (hf : IsDiscOptimal M f β)
(i : ℕ) :
discValue M β i ≤
ENNReal.ofReal M₀ * meanReturnTime M f i + discValue M β 0 * expDiscAtReturn M f β i := by sorry
end ArapostathisAC.RossRecurrence
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.