Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma A1 (p. 632) — a bounded-below supersolution of (A1) bounds g_f above by g; a bounded subsolution bounds it below

Proved
Sennott1989.AvgCost.lemma_A1

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

average-costmarkov-decision-processp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Let fff be a stationary policy, ggg a real constant, and hhh a real function on the states.

  1. If −N≤h(i)-N\le h(i)−N≤h(i) for every iii and
g+h(i) ≥ C(i,f)+∑jPij(f)h(j),i≥0,(A1)g+h(i)\ \ge\ C(i,f)+\sum_jP_{ij}(f)h(j),\qquad i\ge0,\tag{A1}g+h(i) ≥ C(i,f)+j∑​Pij​(f)h(j),i≥0,(A1)

then gf(i)≤gg_f(i)\le ggf​(i)≤g for every iii. 2. If the inequality in (A1) is reversed and h(i)≤Nh(i)\le Nh(i)≤N for all iii, then gf(i)≥gg_f(i)\ge ggf​(i)≥g for every iii.

Here gf(i)g_f(i)gf​(i) is the lim sup average cost of fff from iii. The first statement is the verification step that turns the optimality inequality (5) into an upper bound on average cost.

Formalization Note gf(i)∈[0,∞]g_f(i)\in[0,\infty]gf​(i)∈[0,∞] is compared with ggg in the extended reals; ggg may be any real number. The sum ∑jPij(f)h(j)\sum_jP_{ij}(f)h(j)∑j​Pij​(f)h(j) is the extended-real positive-part-minus-negative-part sum. Its negative part is finite in the first case, and its positive part is finite in the second.

Preamble
import Mathlib
import Definitions.Def_Sennott1989_AvgCost_Assumptions

open scoped ENNReal NNReal
open Filter Topology
Formal statement
namespace Sennott1989.AvgCost

open SennottDP.Discounted

/-- Sennott (1989), Appendix, Lemma A1, p. 632. Let `g` be a real constant, `h` a real function,
and `f` a stationary policy.

1. If `−N ≤ h(i)` and `g + h(i) ≥ C(i, f) + ∑_j P_{ij}(f) h(j)` for all `i ≥ 0` (A1), then
   `g_f(i) ≤ g` for every `i`.
2. If the inequality in (A1) is reversed and `h(i) ≤ N` for all `i`, then `g_f(i) ≥ g` for all `i`.

**Formalization Note** `g_f(i)` is the lim sup average cost `SennottDP.SEN.avgCost` in `[0, ∞]`,
compared with the real `g` in `EReal`; `g` may be any real number. The sum `∑_j P_{ij}(f) h(j)` is
the extended-real `SennottDP.SEN.wsum`: its negative part is finite in the first case, and its
positive part is finite in the second. -/
theorem lemma_A1 {Act : Type} (M : MDC ℕ Act) (f : StationaryPolicy M) (g : ℝ) (h : ℕ → ℝ)
    (N : ℝ) :
    ((∀ i, -N ≤ h i) →
      (∀ i, acoiTerm M h i (f.1 i) ≤ ((g + h i : ℝ) : EReal)) →
        ∀ i, (SennottDP.SEN.avgCost M f.toPolicy i : EReal) ≤ (g : EReal)) ∧
      ((∀ i, h i ≤ N) → (∀ i, ((g + h i : ℝ) : EReal) ≤ acoiTerm M h i (f.1 i)) →
        ∀ i, (g : EReal) ≤ (SennottDP.SEN.avgCost M f.toPolicy i : EReal)) := 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, Appendix, Lemma A1, (A1), p. 632
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