Proposition 5.11 — accumulation points of DP-minimizing controls form an optimal stationary policy
ProvedBertsekasShreve.Monotone.prop5_11_accumulation_points_optimalConsider the abstract monotone dynamic programming model (state space , control space , nonempty constraint sets , monotone mapping , terminal function ), with operators and , policy costs , stationary costs and optimal cost . Assume:
- Assumptions I, I.1 and I.2 hold;
- is a Hausdorff topological space;
- there is a nonnegative integer such that for each , and the set
is compact.
Then:
(a) There exists a policy attaining the infimum in the DP algorithm for all :
(b) For every policy satisfying (43), the sequence has at least one accumulation point in for each with .
(c) Let satisfy (43). If is such that is an accumulation point of for every with , and for every with , then for all and the stationary policy is optimal:
The proposition makes the value-iteration algorithm constructive: the controls that attain the minimum at each stage of the DP recursion, followed to an accumulation point state by state, yield an optimal stationary policy.
Formalization Note The model and assumptions are the published MonotoneDP.Increase definitions; "I.2 holds" is , AssumptionI2 α. An accumulation point of is a cluster point of the sequence (MapClusterPt u atTop), not a limit. In (c) the admissibility of is part of the conclusion, as the existence of a proof that for all .
import Mathlib import Definitions.Def_MonotoneDP_Increase_Model import Definitions.Def_MonotoneDP_Increase_Assumptions
namespace BertsekasShreve.Monotone
open Filter Topology
/-- Bertsekas & Shreve (1996), p. 87, Proposition 5.11, under the assumptions of Proposition 5.10
(p. 86): I, I.1 and I.2 hold, the control space `C` is a Hausdorff space, and for a nonnegative
integer `k̄` the sets `U_k(x, λ) = {u ∈ U(x) | H[x, u, T^k(J₀)] ≤ λ}` (eq. (40)) are compact for all
`x ∈ S`, `λ ∈ ℝ`, `k ≥ k̄`. Then
(a) some policy `π* = (μ₀*, μ₁*, …)` satisfies `(T_{μ_k*} T^k)(J₀) = T^{k+1}(J₀)` for all `k ≥ k̄`
(eq. (43));
(b) for every policy satisfying (43), `{μ_k*(x)}` has an accumulation point whenever
`J*(x) < ∞`;
(c) if `μ* : S → C` takes an accumulation point of `{μ_k*(x)}` at every `x` with `J*(x) < ∞` and a
value in `U(x)` at every `x` with `J*(x) = ∞`, then `μ*` is admissible and the stationary policy
`(μ*, μ*, …)` is optimal. -/
theorem prop5_11_accumulation_points_optimal {S C : Type*} [TopologicalSpace C] [T2Space C]
(m : MonotoneDP.Increase.Model S C)
(hI : m.AssumptionI) (hI1 : m.AssumptionI1) (hI2 : ∃ α : ℝ, m.AssumptionI2 α)
(kbar : ℕ)
(hcpt : ∀ x : S, ∀ lam : ℝ, ∀ k : ℕ, kbar ≤ k →
IsCompact {u | u ∈ m.U x ∧ m.H x u ((m.T)^[k] m.Jbar) ≤ (lam : EReal)}) :
(∃ π : m.Policy, ∀ k : ℕ, kbar ≤ k →
m.Tmu (π k) ((m.T)^[k] m.Jbar) = (m.T)^[k + 1] m.Jbar) ∧
(∀ π : m.Policy, (∀ k : ℕ, kbar ≤ k →
m.Tmu (π k) ((m.T)^[k] m.Jbar) = (m.T)^[k + 1] m.Jbar) →
∀ x : S, m.Jstar x < ⊤ → ∃ u : C, MapClusterPt u atTop (fun k => (π k).1 x)) ∧
(∀ π : m.Policy, (∀ k : ℕ, kbar ≤ k →
m.Tmu (π k) ((m.T)^[k] m.Jbar) = (m.T)^[k + 1] m.Jbar) →
∀ μ : S → C,
(∀ x : S, m.Jstar x < ⊤ → MapClusterPt (μ x) atTop (fun k => (π k).1 x)) →
(∀ x : S, m.Jstar x = ⊤ → μ x ∈ m.U x) →
∃ hμ : ∀ x, μ x ∈ m.U x, m.Jmu ⟨μ, hμ⟩ = m.Jstar) := by sorry
end BertsekasShreve.Monotone
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.