Proof of Lemma 5.3, p. 9 — for a reversible policy chain, Sp(L_π) ⊂ [−1, 1]
ProvedAccelVI.AVC.spectrum_LPol_Iccmarkov-decision-processp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1reversible-markov-chainspectrum
Let be a finite MDP and a policy whose transition matrix (with ) defines an irreducible, reversible Markov chain (Definition 2.1). Then every complex eigenvalue of is a real number of absolute value at most one:
This is the location of the spectrum on which the computation of in Lemma 5.3 rests: because is stochastic, and because the chain is reversible.
Formalization Note. The spectrum is that of as a complex matrix; the conclusion says each of its elements equals a real number .
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.