Theorem 6 — G(f) ∪ H(f) empty ⇒ f ∈ F″; improvement steps raise (x, y, z) lexicographically
ProvedVeinottNoDiscount.Improve.theorem_6bias-optimalitymarkov-decision-processp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1policy-improvement
In Blackwell's finite decision model without discounting, let and be the gain and bias of the stationary policy , let be the unique solution of , , and let , be Veinott's improvement sets. For vectors, means coordinatewise and . Suppose . Then
- if is empty, then ;
- if is empty, then ;
- if , then either , or and ;
- if , then , and either , or and .
In short,
and every step raises the triple lexicographically, so the extended policy improvement method cannot cycle and stops, after finitely many steps, at a decision rule with 1-optimal (Theorem 4).
Formalization Note Every action is available in every state. , , , are sets of decision rules defined literally from the paper's inequalities (i)–(iii); is the closed form with Blackwell's deviation matrix.
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 6.** Suppose `f ε F`.
(a) If `G(f)` is empty, then `f ε F′`.
(b) If `G(f) ∪ H(f)` is empty, then `f ε F″`.
(c) If `g ε G(f)`, then either `x(g) > x(f)`, or `x(g) = x(f)` and `y(g) > y(f)`.
(d) If `g ε H(f)`, then `x(g) = x(f)`; and either `y(g) > y(f)`, or `y(g) = y(f)` and
`z(g) > z(f)`.
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. 1290, Theorem 6.
**Formalization Note.** `F = St → Act` (`A_s = Act` for every state). `G(f)`, `H(f)`, `F′`,
`F″` are `GSet`, `HSet`, `Fprime`, `Fdprime` (sets of decision rules; `HSet` is not Blackwell's
deviation matrix `Hf`). `x`, `y` are Blackwell's gain and bias `Q*(f)r(f)`, `H(f)r(f)`; `z` is
`H(f)(−y(f))`, the unique solution of (12). `>` is `VecGt` (`≧` and `≠`). -/
theorem theorem_6 {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) ∧
(GSet M f ∪ HSet M f = ∅ → f ∈ Fdprime M) ∧
(∀ g ∈ GSet M f, VecGt (M.x g) (M.x f) ∨ (M.x g = M.x f ∧ VecGt (M.y g) (M.y f))) ∧
(∀ g ∈ HSet M f, M.x g = M.x f ∧
(VecGt (M.y g) (M.y f) ∨ (M.y g = M.y f ∧ VecGt (z M g) (z M 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. 1290, Theorem 6
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.