Corollary (p. 721) — for each β ∈ [0, 1) some stationary policy is β-optimal
ProvedBlackwellDiscreteDP.Stationary.corollarydynamic-programmingmarkov-decision-processp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1stationary-policy
Fix . There is a decision rule such that the stationary policy is -optimal:
where the comparison is coordinatewise and ranges over all policies, stationary or not.
Here "optimal" is meant at the fixed discount factor (the sense of §3). The same sentence in §4, with "optimal" meaning optimal for all near , is Theorem 5.
Preamble
import Mathlib import Definitions.Def_BlackwellDiscreteDP_Stationary_Model
Formal statement
namespace BlackwellDiscreteDP.Stationary
/-- Corollary, p. 721 (Blackwell, *Discrete Dynamic Programming*, Ann. Math. Statist. 33(2):719–726 (1962),
DOI 10.1214/aoms/1177704593):
"There is an optimal policy which is stationary."
Here "optimal" is the §3 notion at a fixed `β ∈ [0, 1)`: there is a decision rule `f` whose
stationary policy `f^(∞)` satisfies `V_β(f^(∞)) ≧ V_β(π)` for every policy `π` (deterministic,
Markov, possibly time-dependent). The §4 statement with the same words is Theorem 5. -/
theorem corollary {St Act : Type} [Fintype St] [DecidableEq St] [Nonempty St] [Fintype Act] [Nonempty Act]
(M : Model St Act)
(β : ℝ) (hβ0 : 0 ≤ β) (hβ1 : β < 1) :
∃ f : St → Act, M.IsBetaOptimal β (stationary f) := by sorry
end BlackwellDiscreteDP.Stationary
Source
Blackwell, Discrete Dynamic Programming, Ann. Math. Statist. 33(2):719–726 (1962), DOI 10.1214/aoms/1177704593, p. 721, Corollary (to Theorem 3)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.