(5.6), p. 9 — λ = 1 − √(1/κ) + √(1−λ)(1 − √(1−λ²))/√(1+λ), with the last term positive
ProvedAccelVI.AVC.eq_5_6accelerationinequalityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1value-iteration
Let and . Then
and
Hence : the rate of A-VC is strictly better than the rate of plain value computation.
Preamble
import Mathlib import Definitions.Def_mm_basic import Definitions.Def_AccelVI_AVC_Setting
Formal statement
namespace AccelVI.AVC
/-- (5.6), p. 9: for λ ∈ (0, 1),
`λ = 1 − √(1/κ) + √(1 − λ)(1 − √(1 − λ²))/√(1 + λ)` and `√(1 − λ)(1 − √(1 − λ²)) > 0`. -/
theorem eq_5_6 (lam : ℝ) (h0 : 0 < lam) (h1 : lam < 1) :
lam = theta lam + Real.sqrt (1 - lam) * (1 - Real.sqrt (1 - lam ^ 2)) / Real.sqrt (1 + lam) ∧
0 < Real.sqrt (1 - lam) * (1 - Real.sqrt (1 - lam ^ 2)) := 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 Theorem 5.1, display (5.6) and the line after it
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.