Proposition 5.4 — a stationary policy is optimal iff T_μ*(J*) = T(J*); pointwise-optimal policies give a stationary optimal one
ProvedBertsekasShreve.Monotone.prop5_4_optimal_stationary_criterionConsider the abstract monotone dynamic programming model : state space , control space , nonempty constraint sets , a mapping that is monotone in its function argument, and a terminal function . For a selector () let and ; for a policy let , let be the cost of the stationary policy , and let .
Assume Assumptions I, I.1 and I.2 hold. Then:
- A stationary policy is optimal, i.e. , if and only if
- If for each there exists a policy which is optimal at , i.e. , then there exists a stationary optimal policy.
Part 1 reduces the existence of an optimal stationary policy to attainment of the infimum in Bellman's equation at every state. Part 2 shows that the optimal policies, possibly different from state to state, can always be merged into a single stationary one.
Formalization Note The model and the assumptions are the published MonotoneDP.Increase definitions; "I.2 holds" is the existence of a scalar with AssumptionI2 α. Part 2 is the book's formulation (a policy optimal at each state); a policy optimal at all states at once is a special case.
import Mathlib import Definitions.Def_MonotoneDP_Increase_Model import Definitions.Def_MonotoneDP_Increase_Assumptions
namespace BertsekasShreve.Monotone
/-- Bertsekas & Shreve (1996), p. 78, Proposition 5.4: let I, I.1 and I.2 hold. A stationary policy
`(μ*, μ*, …)` is optimal (`J_{μ*} = J*`) if and only if `T_{μ*}(J*) = T(J*)` (eq. (18)).
Furthermore, if for each `x ∈ S` there exists a policy which is optimal at `x`
(`J_π(x) = J*(x)`), then there exists a stationary optimal policy. -/
theorem prop5_4_optimal_stationary_criterion {S C : Type*} (m : MonotoneDP.Increase.Model S C)
(hI : m.AssumptionI) (hI1 : m.AssumptionI1) (hI2 : ∃ α : ℝ, m.AssumptionI2 α) :
(∀ μ : m.Selector, m.Jmu μ = m.Jstar ↔ m.Tmu μ m.Jstar = m.T m.Jstar) ∧
((∀ x : S, ∃ π : m.Policy, m.Jpi π x = m.Jstar x) →
∃ μ : m.Selector, m.Jmu μ = m.Jstar) := by sorry
end BertsekasShreve.Monotone
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.