Proof of Theorem 6(b), p. 1290 — w(f) = 0, and H(f) empty ⇒ y(g) ≤ y(f) for all g ∈ E(f)
ProvedVeinottNoDiscount.Improve.proof_theorem_6bbias-optimalitymarkov-decision-processp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1policy-improvement
Let and, for , let be the unique solution of (10). Then , and if is empty,
This is the step of the proof of Theorem 6(b) that combines Lemma 4 with Theorem 5 applied to the reduced problem with action sets and reward , whose improving set is ; Lemma 5 then gives .
Formalization Note The reduced problem is not instantiated: the published model has one action set for all states. The statement records the consequence in the original model. In Lean is written , so is .
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
/-- **Proof of Theorem 6(b), first step.** "First note from (11) that `w(f) = 0`. Thus since `H(f)`
is empty, it follows from Theorem 5 and Lemma 4 that `y(g) ≦ y(f)` for all `g ε E(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, §3, proof of Theorem 6(b).
The reason is the paragraph after Lemma 4 (p. 1289): "Notice from (2), (8), and Lemma 4 that the
problem of maximizing w(g) over g ε E(f) has the same form as that of maximizing x(g) over g ε F
where we replace A_s by E(s, f), F by E(f), and r(g) by −y(f) for s = 1, ⋯ , S and all g ε E(f).
Thus the policy improvement method of Theorem 5 can be used to find an h that maximizes w(g)—and
hence y(g) in view of (11)—over g ε E(f)."
**Formalization Note.** Stated in the original model (Blackwell's `Model` has one action set for
all states, so the reduced problem with action sets `E(s, f)` is not instantiated). `w M f f` is
the paper's `w(f)` (with the paper's `f` fixed). Only `H(f) = ∅` is assumed, as in the
sentence; `G(f) = ∅` is used afterwards, through Lemma 5. -/
theorem proof_theorem_6b {St Act : Type*} [Fintype St] [DecidableEq St] [Nonempty St]
[Fintype Act] [Nonempty Act] (M : Model St Act)
(f : St → Act) :
w M f f = 0 ∧ (HSet M f = ∅ → ∀ g ∈ ESet M f, 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. 1290, §3, proof of Theorem 6(b) (with the paragraph after Lemma 4, p. 1289)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.