Theorem 8.4.3 — the unichain optimality equation has a solution, with a unique gain
ProvedMarkovDecisionProcesses.average_optimality_equation_solvableConsider a stationary MDP with finite state and action sets that is unichain: the transition matrix of every deterministic stationary policy consists of a single recurrent class plus a possibly empty set of transient states. Then
- (a) there exist a scalar and a function solving the average reward optimality equation , that is, for every state ,
- (b) the scalar is unique: if is any other solution then .
This is Theorem 8.4.3. The source proves (a) by letting the discount factor tend to along a subsequence on which the same stationary policy is discount optimal (Theorem 6.2.10 of mission II), expanding the discounted value as , and passing to the limit in the discounted optimality equation; the solution obtained is the gain and bias of that policy. Part (b) is Theorem 8.4.1(c). The source notes that is not unique, since is again a solution.
Formalization Note Bounded rewards (Assumption 8.0.2) are automatic for a finite model and are not a separate hypothesis. Unichain is the source's Section 8.3.1 classification, stated through accessibility and recurrence on each as in the definition file. The state space is assumed nonempty, as every state space of the source is: on an empty every pair solves vacuously, and part (b) would be false.
import Definitions.Def_MarkovDecisionProcesses_AverageReward
namespace MarkovDecisionProcesses
theorem average_optimality_equation_solvable {S A : Type*} [Fintype S] [Nonempty S]
[Fintype A] (M : StationaryMDP S A) (hM : IsUnichain M) :
(∃ (g : ℝ) (h : S → ℝ), ∀ s, optimalityResidual M g h s = 0) ∧
∀ (g : ℝ) (h : S → ℝ) (g' : ℝ) (h' : S → ℝ),
(∀ s, optimalityResidual M g h s = 0) →
(∀ s, optimalityResidual M g' h' s = 0) → g = g' := by sorry
end MarkovDecisionProcesses
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.