Theorem 1 — a bounded solution of (1) makes the minimizing rule of C'' optimal over C, with average cost g
ProvedDermanDenumerable.AvgCost.theorem1Assume conditions (A) and (B): the state space is denumerable, each state has finitely many decisions, and the costs are bounded. Suppose a number and a bounded set of numbers satisfy
Then a rule prescribing at each state a decision that minimizes the right side of (1) exists, and every such rule satisfies
for every initial state and every rule (history-dependent and randomized).
This is the verification theorem of the paper: a bounded solution of the average-cost optimality equation identifies the optimal average cost and an optimal stationary deterministic rule. Theorems 2, 3 and 4 all conclude by reducing to it.
Formalization Note. "R* is the rule which prescribes the decision that minimizes" is stated for every choice of minimizing decisions, as the proof allows ("if there are several minimizing decisions, let be any one of them"). The bounded is essential: on an infinite state space unbounded solutions of (1) do not certify optimality.
import Mathlib import Definitions.Def_DermanDenumerable_AvgCost_Model open scoped Topology open Filter SennottDP.AvgFinite
namespace DermanDenumerable.AvgCost
/-- Derman (1966), Theorem 1, p. 1548: under (A) and (B), if a bounded `{g, v_j}` solves (1), then a
rule `R* ∈ C''` prescribing at each state a decision minimizing the right side of (1) exists, and
every such rule satisfies `g = Q_{R*}(i) ≤ Q_R(i)` for every initial state `i` and every rule
`R ∈ C`. -/
theorem theorem1 {S Act : Type} [Countable S] (M : MDC S Act)
(w : S → Act → ℝ) (hB : CostBounded M w) (g : ℝ) (v : S → ℝ) (hv : BddFun v)
(h1 : IsACOE M w g v) :
(∃ e : StationaryPolicy M, IsMinimizer M w v e) ∧
∀ e : StationaryPolicy M, IsMinimizer M w v e →
∀ i : S, avgCostR e.toPolicy w i = g ∧ ∀ R : Policy M, g ≤ avgCostR R w i := by sorry
end DermanDenumerable.AvgCost
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.