Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Lemma 5.3, p. 9 — for a reversible policy chain, Sp(L_π) ⊂ [−1, 1]

Proved
AccelVI.AVC.spectrum_LPol_Icc

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

markov-decision-processp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1reversible-markov-chainspectrum

Let (S,A,P,r,λ)(\mathbb S,\mathbb A,P,r,\lambda)(S,A,P,r,λ) be a finite MDP and π\piπ a policy whose transition matrix LπL_\piLπ​ (with Lπ,ij=∑aπiaPiajL_{\pi,ij}=\sum_a\pi_{ia}P_{iaj}Lπ,ij​=∑a​πia​Piaj​) defines an irreducible, reversible Markov chain (Definition 2.1). Then every complex eigenvalue of LπL_\piLπ​ is a real number of absolute value at most one:

Sp⁡(Lπ)⊂[−1,1].\operatorname{Sp}(L_\pi)\subset[-1,1].Sp(Lπ​)⊂[−1,1].

This is the location of the spectrum on which the computation of ρ(Bπ)\rho(B_\pi)ρ(Bπ​) in Lemma 5.3 rests: ∣μ∣≤1|\mu|\le1∣μ∣≤1 because LπL_\piLπ​ is stochastic, and μ∈R\mu\in\mathbb Rμ∈R because the chain is reversible.

Formalization Note. The spectrum is that of LπL_\piLπ​ as a complex matrix; the conclusion says each of its elements equals a real number t∈[−1,1]t\in[-1,1]t∈[−1,1].

Preamble
import Mathlib
import Definitions.Def_mm_basic
import Definitions.Def_AccelVI_AVC_Setting
Formal statement
namespace AccelVI.AVC

variable {S A : Type*} [Fintype S] [DecidableEq S] [Fintype A]

/-- Proof of Lemma 5.3, p. 9: if the chain of `π` is irreducible and reversible, then
`Sp(L_π) ⊂ [−1, 1]`: every complex eigenvalue of `L_π` is a real number in `[−1, 1]`. -/
theorem spectrum_LPol_Icc (M : MDP S A) (hM : M.Valid) (pol : S → A → ℝ) (hpol : FoundationsML.ReinforcementLearning.IsPolicy pol)
    (hrev : IsReversible (LPol M pol)) :
    ∀ μ ∈ spectrum ℂ ((LPol M pol).map (algebraMap ℝ ℂ)),
      ∃ t : ℝ, t ∈ Set.Icc (-1 : ℝ) 1 ∧ μ = (t : ℂ) := by sorry

end AccelVI.AVC
Source
Goyal & Grand-Clément, A First-Order Approach to Accelerated Value Iteration, arXiv:1905.09963v7, p. 9, proof of Lemma 5.3, paragraph 'First, since L_π is a stochastic matrix'
Human review
  • Endorsed by Shuze Chen · Oct 15, 2026

    Confirmed by the moderator at approval.

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