(7), p. 1131 — support inequality Bw ≥ Bv + (λP_v − I)(w − v)
ProvedModPolicyIter.Conv.support_inequalityLet 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 .
Let and let attain the maximum in (1) at . Then, pointwise on ,
This support inequality, due to Puterman and Brumelle and quoted in the proof of Lemma 4, says that the convex operator lies above its "tangent" at ; it is what makes policy iteration a Newton method, and it drives Lemma 4 and the rate bound (9).
Formalization Note The attainment of the maximum is needed only at and is given as the hypothesis that the policy is a maximizer there; the standing assumption for all is not used.
import Mathlib import Definitions.Def_ModPolicyIter_Conv_Model open MeasureTheory ProbabilityTheory
namespace ModPolicyIter.Conv
/-- The support inequality (7) (Puterman–Shin 1978, proof of Lemma 4, p. 1131, quoting
Puterman–Brumelle, Proposition 1): for `v, w ∈ V` and a maximizer `P_v` at `v`,
`Bw ≥ Bv + (λP_v − I)(w − v)`. -/
theorem support_inequality {S : Type*} [MeasurableSpace S] {ι : Type*} (m : Model S ι) :
∀ v w : S → ℝ, IsBM v → IsBM w → ∀ i, Attains m v i →
∀ s, B m v s + (m.lam * Pop m i (w - v) s - (w - v) s) ≤ B m w s := by sorry
end ModPolicyIter.Conv
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.
Confirmed by the moderator at approval.