Theorem 1 (Blackwell) — exactly one: f^∞ is β-optimal with no one-step improvement, or some g has V_β(g, f^∞) > V_β(f^∞) and V_β(g^∞) > V_β(f^∞)
ProvedVeinottNoDiscount.Improve.theorem_1discounted-mdpmarkov-decision-processp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1policy-improvement
Fix a decision rule and a discount factor . Write for the vector of expected total discounted returns of a policy , for the stationary policy using every period, and for the policy that uses in the first period and thereafter. For vectors, means for all , and means and . Then exactly one of the following holds:
- for all , and is -optimal ( for every policy );
- there is with
This is the policy improvement method for a fixed discount factor: either cannot be improved in one step and is then optimal, or a one-step improvement yields a strictly better stationary policy.
Formalization Note One and the same witnesses both inequalities in the second alternative. The strict order is not coordinatewise strict.
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 1 (Blackwell).** Exactly one of the following must occur for each `f ε F` and
`0 ≦ β < 1`:
(a) `V_β(f^∞) ≧ V_β(g, f^∞)` for all `g ε F` and `f^∞` is β-optimal.
(b) `V_β(f^∞) < V_β(g, f^∞)` for some `g ε F` and `V_β(f^∞) < V_β(g^∞)`.
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. 1285, Theorem 1.
**Formalization Note.** `u < v` is the paper's vector order (`v ≧ u` and `v ≠ u`), i.e.
`VecGt v u`, not coordinatewise strict. In (b) one `g` witnesses both inequalities (the
improving decision rule of the policy improvement method). `(g, f^∞)` is
`Policy.cons g (Policy.stationary f)`; β-optimal is the published `IsBetaOptimal` (comparison
with every policy). `Xor` expresses "exactly one". -/
theorem theorem_1 {St Act : Type*} [Fintype St] [DecidableEq St] [Nonempty St]
[Fintype Act] [Nonempty Act] (M : Model St Act)
(f : St → Act) (β : ℝ) (hβ0 : 0 ≤ β) (hβ1 : β < 1) :
Xor
((∀ g : St → Act,
M.V β (Policy.cons g (Policy.stationary f)) ≤ M.V β (Policy.stationary f)) ∧
M.IsBetaOptimal β (Policy.stationary f))
(∃ g : St → Act,
VecGt (M.V β (Policy.cons g (Policy.stationary f))) (M.V β (Policy.stationary f)) ∧
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. 1285, Theorem 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.