Theorem 13(a) — and are contraction mappings
ProvedBoundedParamMDP.IntervalEval.theorem13a_contractionLet be a bounded-parameter MDP with finite state set and finite nonempty action set . is the upper bound returned by optimistic interval value iteration ; it depends only on the upper bound of its input, and is regarded as a map . Likewise , the lower bound returned by , depends only on .
Theorem 13(a). and are contraction mappings. Precisely, there are such that for all interval inputs and ,
With Theorem 9 this yields convergence of the upper bounds of optimistic (lower bounds of pessimistic) interval value iteration.
Formalization Note. The inequalities are taken over arbitrary pairs of input functions with arbitrary values of the other bound. Taking equal other bounds gives the contraction property of the map on ; taking equal relevant bounds gives the independence from the other bound (p. 23) that makes the map on well defined. Inputs are not required to be proper intervals ().
import Mathlib import Definitions.Def_BoundedParamMDP_Optimal_MDP import Definitions.Def_BoundedParamMDP_Optimal_BMDP import Definitions.Def_BoundedParamMDP_IntervalEval_IntervalValueIteration
namespace BoundedParamMDP.IntervalEval
/-- Theorem 13(a) (Givan–Leach–Dean 2000, p. 25; proof pp. 45–47): `IVI↑opt` and `IVI↓pes` are
contraction mappings. `IVI↑opt` is the upper bound returned by `IVI↕opt`, regarded as a map
`V̄ → V̄` of the upper input `V↑` (it does not depend on the lower input, p. 23); `IVI↓pes`
likewise is the lower bound returned by `IVI↕pes` as a map of the lower input `V↓`. The
statement bounds the outputs for two arbitrary interval inputs by `λ` times the distance of
the relevant input bounds only: this is the contraction property together with the
independence from the other bound that makes the maps well defined on `V̄`. -/
theorem theorem13a_contraction {Q A : Type*} [Fintype Q] [Fintype A] [Nonempty A]
(B : BoundedParamMDP.Optimal.BMDP Q A) :
(∃ c : ℝ, 0 ≤ c ∧ c < 1 ∧ ∀ L L' U U' : Q → ℝ,
‖(fun p => (IVIopt B (L', U') p).2) - (fun p => (IVIopt B (L, U) p).2)‖ ≤
c * ‖U' - U‖) ∧
(∃ c : ℝ, 0 ≤ c ∧ c < 1 ∧ ∀ L L' U U' : Q → ℝ,
‖(fun p => (IVIpes B (L', U') p).1) - (fun p => (IVIpes B (L, U) p).1)‖ ≤
c * ‖L' - L‖) := by sorry
end BoundedParamMDP.IntervalEval
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.