Theorem 4 — no improvement of order n+1 implies n^± discount optimality, which rules out improvement of order n
ProvedVeinottSensitiveDP.Sensitive.theorem_4discount-optimalitymarkov-decision-processp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1policy-improvement
In the model of §4, where every is substochastic (and, for the sign , every stationary policy is transient), let be the number of states, and .
- If is empty, then .
- If , then is empty.
Here is the set of decision rules whose stationary policy satisfies for all policies (), and is the set of improvements of of order .
The theorem gives a test for discount optimality that only inspects the finitely many one-step switches , and it lets the policy improvement method stop as soon as no improvement of order is left.
Formalization Note The two signs are one real parameter : is and is . The liminf is encoded per state as "for every , eventually "; the lexicographic order is applied row by row.
Preamble
import Mathlib import Definitions.Def_BlackwellDiscreteDP_NearOne_LimitMatrix import Definitions.Def_VeinottSensitiveDP_Sensitive_Matrix import Definitions.Def_VeinottSensitiveDP_Sensitive_Model import Definitions.Def_VeinottSensitiveDP_Sensitive_Optimality open Filter Topology Matrix BlackwellDiscreteDP.NearOne
Formal statement
namespace VeinottSensitiveDP.Sensitive
/-- Theorem 4: suppose `f ε F` and `n = −2, −1, ⋯, S − 1`.
1°. If `G_{n+1}^±(f)` is empty, then `f ε D_n^±`.
2°. If `f ε D_n^±`, then `G_n^±(f)` is empty.
Veinott, Discrete Dynamic Programming with Sensitive Discount Optimality Criteria,
Ann. Math. Statist. 40(5):1635–1660 (1969), DOI 10.1214/aoms/1177697379, p. 1648, §4, Theorem 4.
**Formalization Note.** `σ = 1` is the sign `+` and `σ = −1` the sign `−`; the `−` case assumes the transient case, where alone `n⁻`
discount optimality is defined (p. 1644). `S = Fintype.card St`. `D_n^±` is the set of `f` whose
stationary policy `f^∞` is `n^±` discount optimal against **all** policies (27), with `D_{−2} = F`;
`G_n^±(f) = {g : Ψ_n^±(g, f) ≻ 0}` (lexicographic, columns `−1, …, n`), empty for `n < −1`. -/
theorem theorem_4 {St : Type} [Fintype St] [DecidableEq St] [Nonempty St]
{A : St → Type} [∀ s, Fintype (A s)] [∀ s, DecidableEq (A s)] [∀ s, Nonempty (A s)]
(M : Model St A)
(σ : ℝ) (hσ : σ = 1 ∨ σ = -1) (htr : σ = -1 → M.TransientCase) (n : ℤ) (hn1 : -2 ≤ n)
(hn2 : n ≤ (Fintype.card St : ℤ) - 1) (f : DecisionRule A) :
(M.G σ (n + 1) f = ∅ → f ∈ M.D σ n) ∧ (f ∈ M.D σ n → M.G σ n f = ∅) := by sorry
end VeinottSensitiveDP.Sensitive
Source
Veinott, Discrete Dynamic Programming with Sensitive Discount Optimality Criteria, Ann. Math. Statist. 40(5):1635–1660 (1969), DOI 10.1214/aoms/1177697379, p. 1648, §4, Theorem 4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.