Theorem 4 (Blackwell) — F″ is the nonempty set of f for which f^∞ is 1-optimal
ProvedVeinottNoDiscount.Improve.theorem_4bias-optimalityblackwell-optimalitymarkov-decision-processp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
In the finite decision model, let be the set of decision rules of maximal gain that, among those, have maximal bias . A policy is 1-optimal if
where is the value of a -optimal policy. Then is nonempty, and for every ,
The theorem reduces the search for a 1-optimal stationary policy to lexicographic maximization of gain and then bias.
Formalization Note 1-optimality is the published Blackwell notion "nearly optimal", encoded without : for every and all close enough to , coordinatewise for every policy (not only stationary ones).
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 4 (Blackwell).** `F″` is the (nonempty) set of all `f ε F` for which `f^∞` is
1-optimal.
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. 1286, Theorem 4.
**Formalization Note.** 1-optimal (p. 1285: `lim_{β↗1}[V_β(π*) − U(β)] = 0` with `U(β)` the
value of a β-optimal policy) is the published `IsNearlyOptimal` (Veinott's footnote 2: Blackwell's
"nearly optimal"), encoded without `U` and comparing against every policy, not only stationary
ones. `F″` is `Fdprime M`. -/
theorem theorem_4 {St Act : Type*} [Fintype St] [DecidableEq St] [Nonempty St]
[Fintype Act] [Nonempty Act] (M : Model St Act) :
(Fdprime M).Nonempty ∧
∀ f : St → Act, f ∈ Fdprime M ↔ M.IsNearlyOptimal (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. 1286, Theorem 4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.