Lemma 1, p. 1129 — U^k is a contraction with constant λ^{k+1}
ProvedModPolicyIter.Conv.lemma_1Let be a set of states with a -algebra. Each policy is a Markov transition kernel on with a measurable one-period reward , where and . Let be the space of bounded measurable functions with .
For let . Then for all
That is, is a contraction with modulus ; for this is the classical contraction property of the value-iteration operator.
Formalization Note The conclusion includes both that maps into and the Lipschitz inequality. Since the pointwise supremum defining need not be measurable for an arbitrary policy family, the mapping property is an explicit hypothesis, as it is for Lemma 2 and Corollary 1. The paper treats it as implicit in calling an operator on . The standing attainment assumption for is not needed for this contraction estimate.
import Mathlib import Definitions.Def_ModPolicyIter_Conv_Setting open MeasureTheory ProbabilityTheory
namespace ModPolicyIter.Conv
/-- Lemma 1 (Puterman–Shin 1978, p. 1129): `U^k` is a contraction mapping of `V` with
constant `λ^{k+1}`. The explicit `hUV` supplies the paper's implicit assertion that the
pointwise maximum defining `U^k` is measurable and therefore maps `V` into `V`. -/
theorem lemma_1 {S : Type*} [MeasurableSpace S] {ι : Type*} (m : Model S ι) (k : ℕ)
(hUV : ∀ w : S → ℝ, IsBM w → IsBM (U m k w)) :
(∀ w : S → ℝ, IsBM w → IsBM (U m k w)) ∧
∀ u w : S → ℝ, IsBM u → IsBM w →
supNorm (U m k u - U m k w) ≤ m.lam ^ (k + 1) * supNorm (u - w) := by sorry
end ModPolicyIter.Conv
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.