Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5 cost identity: a short prefix plus a repeated closed walk

Proved
MDPComplexity.StationaryHorizon.theorem5_structure

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

deterministicdynamic-programminggraph-theorymarkov-decision-processp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let MMM be a finite stationary deterministic process with nnn states, initial state s0s_0s0​, and horizon T>n2T>n^2T>n2. For l≤Tl\le Tl≤T and a state uuu, let wl,uw_{l,u}wl,u​ be the minimum cost of an lll-arc walk from s0s_0s0​ that visits uuu. Let rk,ur_{k,u}rk,u​ be the minimum cost of a closed kkk-arc walk at uuu. Then

JT∗(s0)=min⁡l≤T, l<n3, u∈S,1≤k≤n, k∣T−l(wl,u+T−lkrk,u),J_T^*(s_0)=\min_{\substack{l\le T,\ l<n^3,\ u\in S,\\1\le k\le n,\ k\mid T-l}}\left(w_{l,u}+\frac{T-l}{k}r_{k,u}\right),JT∗​(s0​)=l≤T, l<n3, u∈S,1≤k≤n, k∣T−l​min​(wl,u​+kT−l​rk,u​),

where a candidate is included only when both component walk sets are nonempty. This identity is the mathematical correctness claim behind the paper's parallel algorithm for Theorem 5.

Formalization Note The paper states that the finite-horizon stationary deterministic problem is in NC. This item formalizes its cost identity, not that complexity classification. The algorithm's “shortest cycle of length kkk” is represented as a cheapest closed kkk-arc walk, as computed by a min-plus matrix power. The structural milestone separately uses a simple cycle. The conditions l≤Tl\le Tl≤T and k∣T−lk\mid T-lk∣T−l make the natural-number quotient exact. No no-ties hypothesis is imposed. The optimum remains over all time-dependent policies, and TTT is the number of decision arcs.

Preamble
import Mathlib
import Definitions.Def_MDPComplexity_StationaryHorizon_Model
Formal statement
namespace MDPComplexity.StationaryHorizon

variable {S : Type} [Fintype S]

/-- §3, p. 447, identity underlying Theorem 5: minimize over a short prefix through
`u` and a repeated closed `k`-walk at `u`. The minima in each component are genuine
walk minima, and the outer optimum remains over all time-dependent policies. -/
theorem theorem5_structure (M : DetMDP S) (s₀ : S) (T : ℕ)
    (hT : (Fintype.card S) ^ 2 < T) :
    IsLeast
      {x : ℝ | ∃ (l k : ℕ) (u : S) (w r : ℝ),
        l ≤ T ∧ l < (Fintype.card S) ^ 3 ∧
        1 ≤ k ∧ k ≤ Fintype.card S ∧ k ∣ T - l ∧
        IsLeast {y : ℝ | ∃ W : M.Walk l,
          W.x 0 = s₀ ∧ (∃ t : Fin (l + 1), W.x t = u) ∧ y = W.cost} w ∧
        IsLeast {y : ℝ | ∃ C : M.Walk k,
          C.x 0 = u ∧ C.x ⟨k, Nat.lt_succ_self k⟩ = u ∧ y = C.cost} r ∧
        x = w + (((T - l) / k : ℕ) : ℝ) * r}
      (M.optHorizon s₀ T) := by sorry

end MDPComplexity.StationaryHorizon
Source
Papadimitriou and Tsitsiklis, The Complexity of Markov Decision Processes, Math. Oper. Res. 12(3) (1987), p. 447, §3 The finite horizon, stationary case, paragraph before Theorem 5, https://doi.org/10.1287/moor.12.3.441
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