Corollary 2(b) — V*_λ is the unique bounded solution of the robust optimality equation (30), and ε-optimal stationary policies exist
ProvedRobustDP.Discounted.corollary2b_value_unique_fixed_pointbellman-equationdynamic-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1robust-optimization
Let be a discounted ambiguous MDP with robust value function , the supremum over all history dependent randomized policies. Then
- is bounded and solves
- every bounded solution of (30) equals ;
- for every there is a deterministic Markov decision rule whose stationary policy satisfies for every .
This is the robust Bellman equation of discounted dynamic programming: the robust value function is computed by a fixed point of a state-wise max–min operator, and nearly optimal policies can be taken stationary.
Formalization Note "Unique solution" is uniqueness among bounded functions (the space of the page). The -optimal stationary policy is deterministic, as the page's construction (28) gives. is the value against the dynamic (rectangular) adversary.
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 corollary2b_value_unique_fixed_point {S A : Type*} [Countable S] [Countable A]
(M : Model S A) :
IsBounded (Vstar M) ∧ (∀ s, Vstar M s = T M (Vstar M) s) ∧
(∀ U : S → ℝ, IsBounded U → (∀ s, U s = T M U s) → U = Vstar M) ∧
∀ ε : ℝ, 0 < ε → ∃ d : DecisionRule M, ∀ s, Vstar M s - ε ≤ V M (stationary M d) s := by sorry
end RobustDP.Discounted
Source
Iyengar, Robust dynamic programming, CORC Tech Report TR-2002-07 (rev. May 4, 2004), p. 11, Corollary 2(b), eq. (30)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.