Theorem 6.3, p. 12 — on the n-state chain MDP every first-order method has ‖v_s − v*‖∞ ≥ λ^s/(1 + λ) for s = 1, …, n − 1
ProvedAccelVI.LowerBound.theorem_6_3Let and , and consider the -state chain MDP of Figure 1: one action, state 1 absorbing with reward , and for a deterministic transition from to with reward . Let be its Bellman operator (2.1) and its fixed point, . Let be any sequence of iterates with
Then for every step ,
So no first-order method, in the sense of iterates built from linear combinations of past iterates and their Bellman images, can converge faster than at rate uniformly over MDPs, which is the rate of plain value iteration. Acceleration as in convex optimization, which improves to roughly , is therefore impossible for general MDPs.
Formalization Note. The paper states "there exists an MDP instance" with its number of states; its proof fixes an arbitrary and an arbitrary and uses the chain of Figure 1. The statement here is that proof's claim, for every and on the explicit chain; the printed existential follows from it. States are 0-based (Fin n), "span" is the real linear span, enters through the fixed-point equation , is the sup norm, and is natural-number subtraction (so the statement has content for ).
import Mathlib import Definitions.Def_AccelVI_LowerBound_Setting
namespace AccelVI.LowerBound
theorem theorem_6_3 (n : ℕ) (lam : ℝ) (h0 : 0 < lam) (h1 : lam < 1) (vstar : Fin n → ℝ)
(hfix : bellman (chainMDP n lam) vstar = vstar) (v : ℕ → Fin n → ℝ)
(hv : IsFirstOrder (bellman (chainMDP n lam)) v) (s : ℕ) (hs1 : 1 ≤ s) (hs2 : s ≤ n - 1) :
lam ^ s / (1 + lam) ≤ ‖v s - vstar‖ := by sorry
end AccelVI.LowerBound
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.