Lemma 2 (Policy evaluation) — V^π of a stationary policy is the optimal solution of the robust program (31)
ProvedRobustDP.Discounted.lemma2_policy_evaluationdynamic-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1policy-evaluationrobust-optimization
Let be a discounted ambiguous MDP, let be a deterministic Markov decision rule, , and let with for all and . Consider the robust program
over bounded , where . Then
- is feasible for (31);
- every feasible has ;
- every feasible attaining equals .
So robust policy evaluation is a (convex) robust optimization problem, the first step of robust policy iteration.
Formalization Note With a countable state space the objective needs and bounded ; both are added and restrict the page's program to bounded . "The optimal solution" is rendered as feasibility, optimality and uniqueness of the maximizer.
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 lemma2_policy_evaluation {S A : Type*} [Countable S] [Countable A] (M : Model S A)
(d : DecisionRule M) (α : S → ℝ) (hα : ∀ s, 0 < α s) (hαs : Summable α) :
let feasible : (S → ℝ) → Prop := fun U =>
IsBounded U ∧ ∀ s, ∀ p ∈ M.P s (d.1 s),
U s ≤ RobustDP.FiniteHorizon.expect p (fun s' => M.r s (d.1 s) s' + M.lam * U s')
feasible (V M (stationary M d)) ∧
(∀ U, feasible U → ∑' s, α s * U s ≤ ∑' s, α s * V M (stationary M d) s) ∧
∀ U, feasible U → ∑' s, α s * U s = ∑' s, α s * V M (stationary M d) s →
U = V M (stationary M d) := by sorry
end RobustDP.Discounted
Source
Iyengar, Robust dynamic programming, CORC Tech Report TR-2002-07 (rev. May 4, 2004), p. 12, Lemma 2, eq. (31)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.