Lemma 4 — and as maxima over and
ProvedBoundedParamMDP.IntervalEval.lemma4_restricted_maxdynamic-programmingmarkov-decision-processesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1robust-mdp
Let be a bounded-parameter MDP with finite state set and finite nonempty action set , and let , and be as in the definitions of interval value iteration.
Lemma 4. For any value functions and state ,
It isolates how the action choice of (respectively ) is driven by the fixed bound , and is the form used to show that these operators contract.
Formalization Note. The paper prints the inner operator of the second line as . Since is an upper bound, eq. (29) and the proof of Theorem 13(b) (p. 47) make it , which is what is stated here. Each "" is stated as: the value is the greatest element of the set .
Preamble
import Mathlib import Definitions.Def_BoundedParamMDP_Optimal_MDP import Definitions.Def_BoundedParamMDP_Optimal_BMDP import Definitions.Def_BoundedParamMDP_IntervalEval_IntervalValueIteration
Formal statement
namespace BoundedParamMDP.IntervalEval
/-- Lemma 4 (Givan–Leach–Dean 2000, p. 25, eq. (32)), with the misprinted `min` of the second
line read as `max`: for any value functions `V, V'` and state `p`,
`IVI↓_{opt,V}(V')(p) = max_{α ∈ ρ_V(p)} min_{M ∈ M↕} VI_{M,α}(V')(p)` and
`IVI↑_{pes,V}(V')(p) = max_{α ∈ σ_V(p)} max_{M ∈ M↕} VI_{M,α}(V')(p)`; each maximum over a set
of actions is stated as "the greatest element of the set of values". -/
theorem lemma4_restricted_max {Q A : Type*} [Fintype Q] [Fintype A] [Nonempty A]
(B : BoundedParamMDP.Optimal.BMDP Q A) (V V' : Q → ℝ) (p : Q) :
IsGreatest ((fun α => ⨅ M : BoundedParamMDP.Optimal.Member B, BoundedParamMDP.Optimal.VIact M.1 α V' p) '' rho B V p)
(IVIloOptV B V V' p) ∧
IsGreatest ((fun α => ⨆ M : BoundedParamMDP.Optimal.Member B, BoundedParamMDP.Optimal.VIact M.1 α V' p) '' sigma B V p)
(IVIhiPesV B V V' p) := by sorry
end BoundedParamMDP.IntervalEval
Source
Givan, Leach, Dean, Bounded-parameter Markov decision processes, Artificial Intelligence (2000), DOI 10.1016/S0004-3702(00)00047-3, manuscript of May 22, 2000, p. 25, Lemma 4, eq. (32) (second line misprinted min corrected to max)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.