Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1 (Blackwell) — exactly one: f^∞ is β-optimal with no one-step improvement, or some g has V_β(g, f^∞) > V_β(f^∞) and V_β(g^∞) > V_β(f^∞)

Proved
VeinottNoDiscount.Improve.theorem_1

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

discounted-mdpmarkov-decision-processp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1policy-improvement

Fix a decision rule f∈Ff\in Ff∈F and a discount factor 0≤β<10\le\beta<10≤β<1. Write Vβ(π)V_\beta(\pi)Vβ​(π) for the vector of expected total discounted returns of a policy π\piπ, f∞f^\inftyf∞ for the stationary policy using fff every period, and (g,f∞)(g,f^\infty)(g,f∞) for the policy that uses ggg in the first period and fff thereafter. For vectors, u≥vu\ge vu≥v means us≥vsu_s\ge v_sus​≥vs​ for all sss, and u>vu>vu>v means u≥vu\ge vu≥v and u≠vu\ne vu=v. Then exactly one of the following holds:

  1. Vβ(f∞)≥Vβ(g,f∞)V_\beta(f^\infty)\ge V_\beta(g,f^\infty)Vβ​(f∞)≥Vβ​(g,f∞) for all g∈Fg\in Fg∈F, and f∞f^\inftyf∞ is β\betaβ-optimal (Vβ(f∞)≥Vβ(π)V_\beta(f^\infty)\ge V_\beta(\pi)Vβ​(f∞)≥Vβ​(π) for every policy π\piπ);
  2. there is g∈Fg\in Fg∈F with
Vβ(g,f∞)>Vβ(f∞)andVβ(g∞)>Vβ(f∞).V_\beta(g,f^\infty)>V_\beta(f^\infty)\quad\text{and}\quad V_\beta(g^\infty)>V_\beta(f^\infty).Vβ​(g,f∞)>Vβ​(f∞)andVβ​(g∞)>Vβ​(f∞).

This is the policy improvement method for a fixed discount factor: either f∞f^\inftyf∞ cannot be improved in one step and is then optimal, or a one-step improvement yields a strictly better stationary policy.

Formalization Note One and the same ggg witnesses both inequalities in the second alternative. The strict order is not coordinatewise strict.

Preamble
import Mathlib
import Definitions.Def_BlackwellDiscreteDP_NearOne_LimitMatrix
import Definitions.Def_BlackwellDiscreteDP_NearOne_Model
import Definitions.Def_BlackwellDiscreteDP_NearOne_GainBias
import Definitions.Def_VeinottNoDiscount_Improve_Sets
open Filter Topology Matrix BlackwellDiscreteDP.NearOne
Formal statement
namespace VeinottNoDiscount.Improve

/-- **Theorem 1 (Blackwell).** Exactly one of the following must occur for each `f ε F` and
`0 ≦ β < 1`:
(a) `V_β(f^∞) ≧ V_β(g, f^∞)` for all `g ε F` and `f^∞` is β-optimal.
(b) `V_β(f^∞) < V_β(g, f^∞)` for some `g ε F` and `V_β(f^∞) < V_β(g^∞)`.

Veinott, On Finding Optimal Policies in Discrete Dynamic Programming with No Discounting,
Ann. Math. Statist. 37(5):1284–1294 (1966), DOI 10.1214/aoms/1177699272, p. 1285, Theorem 1.

**Formalization Note.** `u < v` is the paper's vector order (`v ≧ u` and `v ≠ u`), i.e.
`VecGt v u`, not coordinatewise strict. In (b) one `g` witnesses both inequalities (the
improving decision rule of the policy improvement method). `(g, f^∞)` is
`Policy.cons g (Policy.stationary f)`; β-optimal is the published `IsBetaOptimal` (comparison
with every policy). `Xor` expresses "exactly one". -/
theorem theorem_1 {St Act : Type*} [Fintype St] [DecidableEq St] [Nonempty St]
    [Fintype Act] [Nonempty Act] (M : Model St Act)
    (f : St → Act) (β : ℝ) (hβ0 : 0 ≤ β) (hβ1 : β < 1) :
    Xor
      ((∀ g : St → Act,
          M.V β (Policy.cons g (Policy.stationary f)) ≤ M.V β (Policy.stationary f)) ∧
        M.IsBetaOptimal β (Policy.stationary f))
      (∃ g : St → Act,
        VecGt (M.V β (Policy.cons g (Policy.stationary f))) (M.V β (Policy.stationary f)) ∧
          VecGt (M.V β (Policy.stationary g)) (M.V β (Policy.stationary f))) := by sorry

end VeinottNoDiscount.Improve
Source
Veinott, On Finding Optimal Policies in Discrete Dynamic Programming with No Discounting, Ann. Math. Statist. 37(5):1284–1294 (1966), DOI 10.1214/aoms/1177699272, p. 1285, Theorem 1
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