Theorem 8.4.4 — an h*-improving decision rule gives an average optimal stationary policy
ProvedMarkovDecisionProcesses.improving_rule_average_optimalConsider a stationary MDP with finite state and action sets. Suppose a scalar and a function satisfy the optimality equation , and let be an -improving decision rule: at every state , attains . Then the stationary policy is average optimal: its lim inf average reward dominates the lim sup average reward of every history-dependent randomized policy at every state.
This is Theorem 8.4.4, the identification of an optimal policy from a solution of the optimality equation. Since attains the maximum, , so by Corollary 8.2.7 the gain of is , and Theorem 8.4.1(c) says is the optimal gain. The source's Example 8.4.3 shows the converse fails: a policy can be average optimal without being -improving.
Formalization Note No unichain hypothesis is imposed, matching the printed statement: the constant solution is the hypothesis, and on a finite chain the identity forces the gain of to be whatever the chain structure. Admissibility of is part of being improving.
import Definitions.Def_MarkovDecisionProcesses_AverageReward
namespace MarkovDecisionProcesses
theorem improving_rule_average_optimal {S A : Type*} [Fintype S] [Fintype A] [DecidableEq A]
(M : StationaryMDP S A) (gstar : ℝ) (hstar : S → ℝ)
(hB : ∀ s, optimalityResidual M gstar hstar s = 0)
(d : S → A) (hd : IsImproving M hstar d) :
IsAverageOptimal (stationaryPolicy M d (fun s => (hd s).1)) := by sorry
end MarkovDecisionProcesses
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.