Theorem 8.4.5 — existence of average optimal stationary policies in finite unichain models
ProvedMarkovDecisionProcesses.unichain_average_optimal_stationary_policyConsider a stationary MDP with finite state and action sets that is unichain. Then
- (a) there is a deterministic stationary policy that is average optimal: for every state and every ;
- (b) there are a scalar and a function with , and (d) this is the optimal gain under both remaining criteria: for every ;
- (c) for every solution of the optimality equation and every -improving decision rule , the stationary policy is average optimal.
This is Theorem 8.4.5, the chapter's existence theorem for unichain models, which the source assembles from Theorem 8.4.3 (existence of a solution), Theorem 8.4.4 (an improving rule is optimal) and Theorem 8.4.1 (the solution's scalar is the optimal gain). It is what justifies solving the single optimality equation — by policy iteration, value iteration or linear programming in Sections 8.5 to 8.8 — instead of searching over policies, and it is why the three average optimality criteria of Section 8.1.2 coincide in finite unichain models.
Formalization Note Bounded rewards are automatic in a finite model. Part (d) is stated together with (b), as the identity for the scalar of the solution exhibited there; by Theorem 8.4.3(b) that scalar is the same for every solution. Part (a) exhibits a deterministic stationary policy, which is what "stationary" means in the chapter's Section 8.3.1 classification and is what the proof produces. "Average optimal" is criterion (8.1.7), the strongest of the three, against every history-dependent randomized policy.
import Definitions.Def_MarkovDecisionProcesses_AverageReward
namespace MarkovDecisionProcesses
theorem unichain_average_optimal_stationary_policy {S A : Type*} [Fintype S] [Fintype A]
[DecidableEq A] (M : StationaryMDP S A) (hM : IsUnichain M) :
(∃ (d : S → A) (hd : ∀ s, d s ∈ M.admissible s),
IsAverageOptimal (stationaryPolicy M d hd)) ∧
(∃ (gstar : ℝ) (hstar : S → ℝ), (∀ s, optimalityResidual M gstar hstar s = 0) ∧
∀ s, optGainSup M s = gstar ∧ optGainInf M s = gstar) ∧
(∀ (gstar : ℝ) (hstar : S → ℝ), (∀ 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.
Confirmed by the moderator at approval.