Lemma 5 — G(f) empty and y(f) ≥ y(g) for all g ∈ E(f) ⇒ f ∈ F″
ProvedVeinottNoDiscount.Improve.lemma_5bias-optimalitymarkov-decision-processp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1policy-improvement
Let . If is empty and
then : has maximal gain and, among the decision rules of maximal gain, maximal bias.
The lemma is the certificate that lets the algorithm stop: it suffices to maximize the bias over the explicitly available set instead of over , which is hard to describe.
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
/-- **Lemma 5.** If `f ε F`, if `G(f)` is empty, and if `y(f) ≧ y(g)` for all `g ε E(f)`, then
`f ε 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. 1289, Lemma 5.
**Formalization Note.** `G(f)`, `E(f)`, `F″` are `GSet`, `ESet`, `Fdprime`; `≧` is pointwise. -/
theorem lemma_5 {St Act : Type*} [Fintype St] [DecidableEq St] [Nonempty St]
[Fintype Act] [Nonempty Act] (M : Model St Act)
(f : St → Act) (hG : GSet M f = ∅) (hy : ∀ g ∈ ESet M f, M.y g ≤ M.y f) :
f ∈ Fdprime M := 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. 1289, Lemma 5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.