Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

(4) — a rule of C'' solving (2) with bounded v has average cost g

Proved
DermanDenumerable.AvgCost.eq4_avg_cost_of_evaluation

by mikedeng1 · Oct 5, 2026 · Mathlib 0df444a (Lean v4.33.1)

average-costdynamic-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let III be a denumerable state space with finite decision sets and bounded costs wikw_{ik}wik​ (conditions (A) and (B)). Let R∈C′′R \in C''R∈C′′ be a stationary deterministic rule making decision kik_iki​ at state iii, write pij=qij(ki)p_{ij} = q_{ij}(k_i)pij​=qij​(ki​), and suppose that a number ggg and a bounded set of numbers {vj}j∈I\{v_j\}_{j \in I}{vj​}j∈I​ satisfy equation (2):

g+vi=wiki+∑j∈Ipijvj,i∈I.g + v_i = w_{ik_i} + \sum_{j \in I} p_{ij} v_j, \qquad i \in I.g+vi​=wiki​​+j∈I∑​pij​vj​,i∈I.

Then for every initial state i′i'i′ the expected average cost converges to ggg:

lim⁡T→∞1T+1∑t=0TERWt=g,in particularQR(i′)=g.\lim_{T\to\infty} \frac{1}{T+1}\sum_{t=0}^{T} E_R W_t = g, \qquad \text{in particular} \quad Q_R(i') = g .T→∞lim​T+11​t=0∑T​ER​Wt​=g,in particularQR​(i′)=g.

This is display (4) of the paper: ggg is the expected average cost per unit time under RRR. It holds for every rule of C′′C''C′′ that solves (2) with a bounded vvv, and no recurrence condition is needed. It is used in the proof of Theorem 1 for the minimizing rule R∗R^*R∗, and in Lemma 1 as g=QR(l)g = Q_R(l)g=QR​(l).

Formalization Note. The statement asserts both that the limit exists and that it equals ggg; QR(i′)Q_R(i')QR​(i′) is the limsup of the averages. The bounded vvv is part of the hypothesis, as in the paper (the interchange of summation in (3) relies on it).

Preamble
import Mathlib
import Definitions.Def_DermanDenumerable_AvgCost_Model
open scoped Topology
open Filter SennottDP.AvgFinite
Formal statement
namespace DermanDenumerable.AvgCost

/-- Derman (1966), §3, display (4), p. 1549: if the rule `e ∈ C''` (decision `k_i = e.f i`) and a
bounded `{v_j}` satisfy (2) with the number `g`, then for every initial state `i` the expected
average cost `(T + 1)^{-1} Σ_{t=0}^{T} E_e W_t` converges to `g`; in particular `Q_e(i) = g`. -/
theorem eq4_avg_cost_of_evaluation {S Act : Type} [Countable S] (M : MDC S Act)
    (w : S → Act → ℝ) (hB : CostBounded M w) (e : StationaryPolicy M) (g : ℝ) (v : S → ℝ)
    (hv : BddFun v) (hD : IsEvaluation M w e g v) :
    ∀ i : S,
      Tendsto (fun T : ℕ => ((T : ℝ) + 1)⁻¹ *
          ∑ t ∈ Finset.range (T + 1), expCostR e.toPolicy w i t) atTop (𝓝 g) ∧
        avgCostR e.toPolicy w i = g := by sorry

end DermanDenumerable.AvgCost
Source
Derman, Denumerable State Markovian Decision Processes—Average Cost Criterion, Ann. Math. Statist. 37(6) (1966), p. 1549, §3, display (4) (from (2), (3) on p. 1548)
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me