Theorem 4 (Markov optimality) — V*_λ(s) = sup over deterministic Markov policies of V^π_λ(s)
ProvedRobustDP.Discounted.theorem4_markov_optimalitydynamic-programmingmarkov-policiesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1robust-optimization
Let be a discounted ambiguous MDP. For every state ,
where is the set of all history dependent randomized policies and the set of deterministic Markov policies.
The decision maker loses nothing by restricting to deterministic Markov policies, even though the adversary is history dependent.
Formalization Note is parametrized by sequences of deterministic Markov decision rules. The page gives only a proof by citation (robust extensions of Theorems 5.5.1, 5.5.3 and Proposition 6.2.1 of Puterman 1994).
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 theorem4_markov_optimality {S A : Type*} [Countable S] [Countable A]
(M : Model S A) (s : S) :
Vstar M s = ⨆ f : ℕ → DecisionRule M, V M (markovPolicy M f) s := by sorry
end RobustDP.Discounted
Source
Iyengar, Robust dynamic programming, CORC Tech Report TR-2002-07 (rev. May 4, 2004), p. 9, Theorem 4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.