Theorem 5 (Blackwell) — G(f) empty ⇒ f ∈ F′; g ∈ G(f) ⇒ V_β(g^∞) > V_β(f^∞) for β near 1
ProvedVeinottNoDiscount.Improve.theorem_5average-rewardmarkov-decision-processp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1policy-improvement
Let , and let be Veinott's set of improving decision rules (defined from the inequalities (i), (ii) on gain and bias). Then:
- if is empty, then , i.e. for every ;
- if , then there is such that
where means coordinatewise and .
This is Howard's policy improvement method for maximal average return per unit time.
Preamble
import Mathlib import Definitions.Def_BlackwellDiscreteDP_NearOne_LimitMatrix import Definitions.Def_BlackwellDiscreteDP_NearOne_Model import Definitions.Def_BlackwellDiscreteDP_NearOne_GainBias import Definitions.Def_VeinottNoDiscount_Improve_Sets open Filter Topology Matrix BlackwellDiscreteDP.NearOne
Formal statement
namespace VeinottNoDiscount.Improve
/-- **Theorem 5 (Blackwell).** Suppose `f ε F`.
(a) If `G(f)` is empty, then `f ε F′`.
(b) If `g ε G(f)`, then `V_β(g^∞) > V_β(f^∞)` for all `β (< 1)` sufficiently near 1.
Veinott, On Finding Optimal Policies in Discrete Dynamic Programming with No Discounting,
Ann. Math. Statist. 37(5):1284–1294 (1966), DOI 10.1214/aoms/1177699272, p. 1287, Theorem 5.
**Formalization Note.** `G(f)` is Veinott's set `GSet M f` (four clauses, p. 1287), not
Blackwell's per-state `G(s, f)`. `>` is `VecGt` (`≧` and `≠`). "For all β (< 1) sufficiently
near 1" is: there is `β₀ < 1` with the conclusion for every `β ∈ (β₀, 1)`. -/
theorem theorem_5 {St Act : Type*} [Fintype St] [DecidableEq St] [Nonempty St]
[Fintype Act] [Nonempty Act] (M : Model St Act)
(f : St → Act) :
(GSet M f = ∅ → f ∈ Fprime M) ∧
∀ g ∈ GSet M f, ∃ β₀ < (1 : ℝ), ∀ β : ℝ, β₀ < β → β < 1 →
VecGt (M.V β (Policy.stationary g)) (M.V β (Policy.stationary f)) := by sorry
end VeinottNoDiscount.Improve
Source
Veinott, On Finding Optimal Policies in Discrete Dynamic Programming with No Discounting, Ann. Math. Statist. 37(5):1284–1294 (1966), DOI 10.1214/aoms/1177699272, p. 1287, Theorem 5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.