(12) — z(f) is the unique solution of [I − Q(f)]z = −y(f), Q*(f)z = 0
ProvedVeinottNoDiscount.Improve.display_12bias-optimalitymarkov-chainmarkov-decision-processp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
For each decision rule , the system
has exactly one solution, .
The vector is the third coordinate of the triple that Veinott's extended improvement method increases lexicographically; it plays for the bias the role that the bias plays for the gain.
Formalization Note is defined as with ; the statement asserts that this vector is the one and only solution of (12).
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
/-- **(12).** For each `f ε F` let `z(f)` be the unique solution (by Theorem 3) to
(12) `[I − Q(f)]z(f) = −y(f), Q*(f)z(f) = 0`.
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, (12).
**Formalization Note.** `z M f` is the closed form `H(f)(−y(f))` with Blackwell's deviation
matrix `H(f)`; the statement says it is the one and only solution of (12). -/
theorem display_12 {St Act : Type*} [Fintype St] [DecidableEq St] [Nonempty St]
[Fintype Act] [Nonempty Act] (M : Model St Act)
(f : St → Act) :
∀ v : St → ℝ, ((1 - M.Q f) *ᵥ v = -(M.y f) ∧ M.Qstar f *ᵥ v = 0) ↔ v = z M 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, (12)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.