(5.3), p. 8 — every eigenvalue ω of B_π solves ω² − (μ+1)(1 − √(1/κ))ω + ½(μ+1)(1 − √(1/κ))² = 0 for some μ ∈ Sp(L_π)
ProvedAccelVI.AVC.eq_5_3accelerationblock-matrixp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1spectrum
Let be a finite MDP with , a policy with transition matrix , , and the matrix (5.1). For every complex eigenvalue of there is a complex eigenvalue of such that
The equation ties the spectrum of to that of ; its two roots are the candidates for the leading eigenvalue of . No reversibility is needed.
Formalization Note. Both spectra are taken over (the matrices are real, their eigenvalues need not be).
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]
/-- (5.3), p. 8 (proof of Lemma 5.3): every complex eigenvalue `ω` of `B_π` satisfies
`ω² − (μ + 1)(1 − √(1/κ))ω + ½(μ + 1)(1 − √(1/κ))² = 0` for some eigenvalue `μ` of `L_π`. -/
theorem eq_5_3 (M : MDP S A) (hM : M.Valid) (pol : S → A → ℝ) (hpol : FoundationsML.ReinforcementLearning.IsPolicy pol) :
∀ ω ∈ spectrum ℂ ((Bpol M pol).map (algebraMap ℝ ℂ)),
∃ μ ∈ spectrum ℂ ((LPol M pol).map (algebraMap ℝ ℂ)),
ω ^ 2 - (μ + 1) * (theta M.lam : ℂ) * ω + 1 / 2 * (μ + 1) * (theta M.lam : ℂ) ^ 2 = 0 := by sorry
end AccelVI.AVC
Source
Goyal & Grand-Clément, A First-Order Approach to Accelerated Value Iteration, arXiv:1905.09963v7, p. 8, proof of Lemma 5.3, display (5.3)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.