Proof of Lemma 5.2, p. 8 — the step sizes (4.1) give 1 + 1/κ − 2α = 0, (1−α)(1+γ) = αλ(1+γ) = 1 − √(1/κ), αγλ = (1−α)γ = α − √(1/κ) = ½(1 − √(1/κ))²
ProvedAccelVI.AVC.step_size_identitiesaccelerationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1step-sizevalue-iteration
Let , and take the step sizes (4.1) of Accelerated Value Computation,
together with . Then
- ;
- ;
- .
These identities collapse the two-step recursion of A-VC into the block matrix of (5.1): the coefficient of becomes and that of becomes .
Preamble
import Mathlib import Definitions.Def_mm_basic import Definitions.Def_AccelVI_AVC_Setting
Formal statement
namespace AccelVI.AVC
/-- Proof of Lemma 5.2, p. 8: for λ ∈ (0, 1), with α = 1/(1 + λ), γ = (1 − √(1 − λ²))/λ and
κ = (1 + λ)/(1 − λ): `1 + 1/κ − 2α = 0`, `(1 − α)(1 + γ) = αλ(1 + γ) = 1 − √(1/κ)` and
`αγλ = (1 − α)γ = α − √(1/κ) = ½(1 − √(1/κ))²`. -/
theorem step_size_identities (lam : ℝ) (h0 : 0 < lam) (h1 : lam < 1) :
1 + 1 / kappa lam - 2 * alphaAVC lam = 0 ∧
(1 - alphaAVC lam) * (1 + gammaAVC lam) = alphaAVC lam * lam * (1 + gammaAVC lam) ∧
alphaAVC lam * lam * (1 + gammaAVC lam) = 1 - Real.sqrt (1 / kappa lam) ∧
alphaAVC lam * gammaAVC lam * lam = (1 - alphaAVC lam) * gammaAVC lam ∧
(1 - alphaAVC lam) * gammaAVC lam = alphaAVC lam - Real.sqrt (1 / kappa lam) ∧
alphaAVC lam - Real.sqrt (1 / kappa lam) = 1 / 2 * (1 - Real.sqrt (1 / kappa lam)) ^ 2 := 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.2, displays after 'Recall that α = 1/(1 + λ)'
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.