Lemma 4, p. 1130 — u ∈ V_B implies (I + A^k B)u ∈ V_B
ProvedModPolicyIter.Conv.lemma_4markov-decision-processmodified-policy-iterationp2o-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 .
Let . If and is a maximizer at , then for every
The condition is thus preserved by every step of modified policy iteration, which makes the iterates monotone (Theorem 1).
Preamble
import Mathlib import Definitions.Def_ModPolicyIter_Conv_Setting open MeasureTheory ProbabilityTheory
Formal statement
namespace ModPolicyIter.Conv
/-- Lemma 4 (Puterman–Shin 1978, p. 1130): if `u ∈ V_B` then `(I + A^k B)u ∈ V_B` for every
order `k`. -/
theorem lemma_4 {S : Type*} [MeasurableSpace S] {ι : Type*} (m : Model S ι)
(hmax : MaxAttained m) (k : ℕ) :
∀ u ∈ VB m, ∀ i, Attains m u i → (u + Apow m i k (B m u)) ∈ VB m := 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 4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.
Confirmed by the moderator at approval.