Theorem 5 cost identity: a short prefix plus a repeated closed walk
ProvedMDPComplexity.StationaryHorizon.theorem5_structureLet be a finite stationary deterministic process with states, initial state , and horizon . For and a state , let be the minimum cost of an -arc walk from that visits . Let be the minimum cost of a closed -arc walk at . Then
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 ” is represented as a cheapest closed -arc walk, as computed by a min-plus matrix power. The structural milestone separately uses a simple cycle. The conditions and make the natural-number quotient exact. No no-ties hypothesis is imposed. The optimum remains over all time-dependent policies, and is the number of decision arcs.
import Mathlib import Definitions.Def_MDPComplexity_StationaryHorizon_Model
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.