Lemma 3, p. 1130 — U^k u ≥ (I + A^k B)v for u ≥ v; (I + A^k B)u ≥ U^0 v if also Bu ≥ 0
ProvedModPolicyIter.Conv.lemma_3markov-decision-processmodified-policy-iterationmonotonicityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Throughout, 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 .
Write , with and a maximizer at . Let and with pointwise. Then
- for every maximizer at ,
- if moreover , then for every maximizer at ,
So one step of modified policy iteration of order is sandwiched between one step of value iteration and one step of -iteration; this is the comparison behind Theorem 1 and Corollary 1.
Preamble
import Mathlib import Definitions.Def_ModPolicyIter_Conv_Setting open MeasureTheory ProbabilityTheory
Formal statement
namespace ModPolicyIter.Conv
/-- Lemma 3 (Puterman–Shin 1978, p. 1130): for `u ≥ v` in `V`, `U^k u ≥ (I + A^k B)v`; if in
addition `u ∈ V_B`, then `(I + A^k B)u ≥ U^0 v`. Here `(I + A^k B)x = x + A^k_x Bx` with `A^k_x`
the truncated series of a maximizer at `x`. -/
theorem lemma_3 {S : Type*} [MeasurableSpace S] {ι : Type*} (m : Model S ι)
(hmax : MaxAttained m) (k : ℕ) :
∀ u v : S → ℝ, IsBM u → IsBM v → (∀ s, v s ≤ u s) →
(∀ i, Attains m v i → ∀ s, v s + Apow m i k (B m v) s ≤ U m k u s) ∧
((∀ s, 0 ≤ B m u s) → ∀ i, Attains m u i →
∀ s, U m 0 v s ≤ u s + Apow m i k (B m u) s) := by sorry
end ModPolicyIter.Conv
Source
Puterman and Shin, Modified policy iteration algorithms for discounted Markov decision problems, Management Science 24 (1978), DOI 10.1287/mnsc.24.11.1127, p. 1130, Lemma 3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.
Confirmed by the moderator at approval.