Proof of Theorem 6.3, p. 12 — on the chain of Figure 1 the value function is v*_i = λ^{i−1}/(1 − λ)
ProvedAccelVI.LowerBound.chain_value_functionlower-boundmarkov-decision-processp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1value-function
Let , , and let be the Bellman operator of the -state chain of Figure 1 (state 1 absorbing with reward 1, state moving to with reward 0, one action). The vector
is a fixed point of , and it is the only one: every with equals .
Since the paper defines the optimal value function as the unique fixed point of , this identifies it explicitly on the hard instance; the lower bound of Theorem 6.3 reads off its entries with .
Formalization Note. States are 0-based (Fin n): the paper's is lam ^ k / (1 - lam) at k = i − 1. The uniqueness clause states the page's "the value function is" for the fixed-point definition of on p. 3.
Preamble
import Mathlib import Definitions.Def_AccelVI_LowerBound_Setting
Formal statement
namespace AccelVI.LowerBound
theorem chain_value_function (n : ℕ) (lam : ℝ) (h0 : 0 < lam) (h1 : lam < 1) :
bellman (chainMDP n lam) (fun k : Fin n => lam ^ (k : ℕ) / (1 - lam)) =
(fun k : Fin n => lam ^ (k : ℕ) / (1 - lam)) ∧
∀ u : Fin n → ℝ, bellman (chainMDP n lam) u = u →
u = (fun k : Fin n => lam ^ (k : ℕ) / (1 - lam)) := by sorry
end AccelVI.LowerBound
Source
Goyal & Grand-Clément, A First-Order Approach to Accelerated Value Iteration, arXiv:1905.09963v7, p. 12, proof of Theorem 6.3, first sentence after Figure 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.