Corollary 1 — g ∈ G(f) ⇒ x(g) > x(f), or x(g) = x(f) and y(g) > y(f)
ProvedVeinottNoDiscount.Improve.corollary_1average-rewardmarkov-decision-processp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1policy-improvement
Let and . Then either
where is the gain, the bias, and means coordinatewise with .
Each step of the policy improvement method therefore raises the pair (gain, bias) lexicographically.
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
/-- **Corollary 1.** Suppose `f ε F` and `g ε G(f)`. Then either `x(g) > x(f)`, or
`x(g) = x(f)` and `y(g) > y(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. 1287, Corollary 1.
**Formalization Note.** `>` is `VecGt` (`≧` and `≠`, not coordinatewise strict). `x`, `y` are
Blackwell's closed forms `Q*(f)r(f)`, `H(f)r(f)`, the unique solutions of (2), (3). -/
theorem corollary_1 {St Act : Type*} [Fintype St] [DecidableEq St] [Nonempty St]
[Fintype Act] [Nonempty Act] (M : Model St Act)
(f g : St → Act) (hg : g ∈ GSet M f) :
VecGt (M.x g) (M.x f) ∨ (M.x g = M.x f ∧ VecGt (M.y g) (M.y 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, Corollary 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.