Corollary 1, p. 1131 — value iteration below, U^k-iteration above modified policy iteration: u⁰ₙ ≤ vₙᵏ ≤ uₙᵏ
ProvedModPolicyIter.Conv.corollary_1Throughout, is a set of states with a -algebra; each policy is a Markov transition kernel on with a measurable one-period reward , ; ; is the space of bounded measurable functions with ; and the maximum in is attained for every , a maximizer being written .
Let and let be generated by modified policy iteration of order , recursion (4): with , where attains the maximum in (1) at . Assume and . Assume also that maps into . Then for every , pointwise on ,
The iterates of value iteration and of -iteration from the same start bracket those of modified policy iteration of order .
Formalization Note The hypothesis that maps into is the paper's implicit premise (see Lemma 2); for it follows from the attainment assumption. The paragraph before the corollary speaks of ""; the corollary and its proof use , which is what is stated.
import Mathlib import Definitions.Def_ModPolicyIter_Conv_Setting open MeasureTheory ProbabilityTheory
namespace ModPolicyIter.Conv
/-- Corollary 1 (Puterman–Shin 1978, p. 1131): if `Bv₀ ≥ 0` and `u^0_0 = u^k_0 = v_0`, then
`u^0_n ≤ v_n ≤ u^k_n` for every `n`, where `u^j_n = (U^j)^n v_0` and `v_n` is the run (4) of
order `k`. `hUV` (`U^k` maps `V` into `V`) is the paper's implicit premise. -/
theorem corollary_1 {S : Type*} [MeasurableSpace S] {ι : Type*} (m : Model S ι)
(hmax : MaxAttained m) (k : ℕ) (hUV : ∀ w : S → ℝ, IsBM w → IsBM (U m k w))
(v : ℕ → S → ℝ) (pol : ℕ → ι)
(hrun : IsRun m k v pol) (hv0 : IsBM (v 0)) (hB0 : ∀ s, 0 ≤ B m (v 0) s) :
∀ n s, (U m 0)^[n] (v 0) s ≤ v n s ∧ v n s ≤ (U m k)^[n] (v 0) s := by sorry
end ModPolicyIter.Conv
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.