Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 5.4 — a stationary policy is optimal iff T_μ*(J*) = T(J*); pointwise-optimal policies give a stationary optimal one

Proved
BertsekasShreve.Monotone.prop5_4_optimal_stationary_criterion

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

dynamic-programmingoptimality-equationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1stationary-policy

Consider the abstract monotone dynamic programming model (S,C,U,H,J0)(S,C,U,H,J_0)(S,C,U,H,J0​): state space SSS, control space CCC, nonempty constraint sets U(x)⊆CU(x)\subseteq CU(x)⊆C, a mapping HHH that is monotone in its function argument, and a terminal function J0>−∞J_0 > -\inftyJ0​>−∞. For a selector μ\muμ (μ(x)∈U(x)\mu(x)\in U(x)μ(x)∈U(x)) let Tμ(J)(x)=H(x,μ(x),J)T_\mu(J)(x)=H(x,\mu(x),J)Tμ​(J)(x)=H(x,μ(x),J) and T(J)(x)=inf⁡u∈U(x)H(x,u,J)T(J)(x)=\inf_{u\in U(x)}H(x,u,J)T(J)(x)=infu∈U(x)​H(x,u,J); for a policy π=(μ0,μ1,… )\pi=(\mu_0,\mu_1,\dots)π=(μ0​,μ1​,…) let Jπ=lim⁡N→∞(Tμ0⋯TμN−1)(J0)J_\pi=\lim_{N\to\infty}(T_{\mu_0}\cdots T_{\mu_{N-1}})(J_0)Jπ​=limN→∞​(Tμ0​​⋯TμN−1​​)(J0​), let JμJ_\muJμ​ be the cost of the stationary policy (μ,μ,… )(\mu,\mu,\dots)(μ,μ,…), and let J∗=inf⁡πJπJ^*=\inf_\pi J_\piJ∗=infπ​Jπ​.

Assume Assumptions I, I.1 and I.2 hold. Then:

  1. A stationary policy (μ∗,μ∗,… )(\mu^*,\mu^*,\dots)(μ∗,μ∗,…) is optimal, i.e. Jμ∗=J∗J_{\mu^*}=J^*Jμ∗​=J∗, if and only if
Tμ∗(J∗)=T(J∗).T_{\mu^*}(J^*) = T(J^*).Tμ∗​(J∗)=T(J∗).
  1. If for each x∈Sx\in Sx∈S there exists a policy πx\pi_xπx​ which is optimal at xxx, i.e. Jπx(x)=J∗(x)J_{\pi_x}(x)=J^*(x)Jπx​​(x)=J∗(x), then there exists a stationary optimal policy.

Part 1 reduces the existence of an optimal stationary policy to attainment of the infimum in Bellman's equation J∗(x)=inf⁡u∈U(x)H(x,u,J∗)J^*(x)=\inf_{u\in U(x)}H(x,u,J^*)J∗(x)=infu∈U(x)​H(x,u,J∗) at every state. Part 2 shows that the optimal policies, possibly different from state to state, can always be merged into a single stationary one.

Formalization Note The model and the assumptions are the published MonotoneDP.Increase definitions; "I.2 holds" is the existence of a scalar α\alphaα with AssumptionI2 α. Part 2 is the book's formulation (a policy optimal at each state); a policy optimal at all states at once is a special case.

Preamble
import Mathlib
import Definitions.Def_MonotoneDP_Increase_Model
import Definitions.Def_MonotoneDP_Increase_Assumptions
Formal statement
namespace BertsekasShreve.Monotone

/-- Bertsekas & Shreve (1996), p. 78, Proposition 5.4: let I, I.1 and I.2 hold. A stationary policy
`(μ*, μ*, …)` is optimal (`J_{μ*} = J*`) if and only if `T_{μ*}(J*) = T(J*)` (eq. (18)).
Furthermore, if for each `x ∈ S` there exists a policy which is optimal at `x`
(`J_π(x) = J*(x)`), then there exists a stationary optimal policy. -/
theorem prop5_4_optimal_stationary_criterion {S C : Type*} (m : MonotoneDP.Increase.Model S C)
    (hI : m.AssumptionI) (hI1 : m.AssumptionI1) (hI2 : ∃ α : ℝ, m.AssumptionI2 α) :
    (∀ μ : m.Selector, m.Jmu μ = m.Jstar ↔ m.Tmu μ m.Jstar = m.T m.Jstar) ∧
      ((∀ x : S, ∃ π : m.Policy, m.Jpi π x = m.Jstar x) →
        ∃ μ : m.Selector, m.Jmu μ = m.Jstar) := by sorry

end BertsekasShreve.Monotone
Source
Bertsekas & Shreve, Stochastic Optimal Control: The Discrete-Time Case, Athena Scientific 1996, p. 78, Proposition 5.4, Eq. (18) of Chapter 5
Human review
  • Endorsed by Shuze Chen · Oct 5, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 5, 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