Lemma 1 (first claim) — robust value iteration stops, and its output is within ε/4 of V*_λ
ProvedRobustDP.Discounted.lemma1_value_iterationdynamic-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1robust-optimizationvalue-iteration
Let be a discounted ambiguous MDP, let be the operator of (30), let be bounded and , and let . The robust value iteration algorithm of Figure 1 returns , where is the first index with
Then such a exists (the algorithm stops), and for the first such ,
This is the approximation guarantee of robust value iteration.
Formalization Note The algorithm is encoded by its iterates: the stopping index is characterized by the stopping test holding at and failing at every . Only the first sentence of Lemma 1 is stated. Its second claim (an -greedy rule against is -optimal) is false as printed and is not part of the mission. Figure 1's header says ; the Lemma's is used.
Preamble
import Mathlib import Definitions.Def_RobustDP_Discounted_Model import Definitions.Def_RobustDP_Discounted_Value import Definitions.Def_RobustDP_Discounted_Bellman
Formal statement
namespace RobustDP.Discounted
theorem lemma1_value_iteration {S A : Type*} [Countable S] [Countable A] (M : Model S A)
(V₀ : S → ℝ) (hV₀ : IsBounded V₀) (ε : ℝ) (hε : 0 < ε) :
let Vk : ℕ → S → ℝ := fun k => (T M)^[k] V₀
let c : ℝ := (1 - M.lam) / (4 * M.lam) * ε
(∃ K, supNorm (fun s => Vk (K + 1) s - Vk K s) < c) ∧
∀ K, supNorm (fun s => Vk (K + 1) s - Vk K s) < c →
(∀ k < K, c ≤ supNorm (fun s => Vk (k + 1) s - Vk k s)) →
supNorm (fun s => Vk (K + 1) s - Vstar M s) ≤ ε / 4 := by sorry
end RobustDP.Discounted
Source
Iyengar, Robust dynamic programming, CORC Tech Report TR-2002-07 (rev. May 4, 2004), p. 12, Lemma 1 (first sentence); algorithm in Figure 1, p. 11
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.