Theorem 13(b) — and are contraction mappings
ProvedBoundedParamMDP.IntervalEval.theorem13b_contractionLet be a bounded-parameter MDP with finite state set and finite nonempty action set . For a value function , and are maps from value functions to value functions; their action choices are governed by the sets and .
Theorem 13(b). For any value function (with its associated action set selection functions and ), and are contraction mappings: each of them has some with
This is what makes the lower bounds of optimistic (upper bounds of pessimistic) interval value iteration converge once the other bound has converged.
Formalization Note. No relation between and the argument is assumed, so may be an improper interval, as on the page. The modulus may depend on (the paper's statement is per ).
import Mathlib import Definitions.Def_BoundedParamMDP_Optimal_MDP import Definitions.Def_BoundedParamMDP_Optimal_BMDP import Definitions.Def_BoundedParamMDP_IntervalEval_IntervalPolicyEvaluation import Definitions.Def_BoundedParamMDP_IntervalEval_IntervalValueIteration
namespace BoundedParamMDP.IntervalEval
/-- Theorem 13(b) (Givan–Leach–Dean 2000, p. 25; proof p. 47): for any value function `V`
(with its action selection sets `ρ_V`, `σ_V`), the maps `IVI↓_{opt,V}` and `IVI↑_{pes,V}`
from value functions to value functions are contraction mappings. -/
theorem theorem13b_contraction {Q A : Type*} [Fintype Q] [Fintype A] [Nonempty A]
(B : BoundedParamMDP.Optimal.BMDP Q A) (V : Q → ℝ) :
IsContraction (IVIloOptV B V) ∧ IsContraction (IVIhiPesV B V) := by sorry
end BoundedParamMDP.IntervalEval
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.