Theorem 8.4.1 — sub- and supersolutions of the optimality equation bound the optimal gain
ProvedMarkovDecisionProcesses.average_optimality_boundsConsider a stationary MDP with finite state and action sets, a scalar and a function , and let .
- (a) If at every state, then for every : no policy has lim sup average reward above .
- (b) If at every state, then for every , : some deterministic stationary policy has lim inf average reward at least .
- (c) If at every state, then and for every .
This is Theorem 8.4.1, the average reward analogue of Theorem 6.2.2 (mission II) and, in the source's words, "one of the most important results for average reward models; part (c) gives the main result". Part (a) follows by iterating the inequality along any policy and averaging, the telescoping term vanishing after division by ; part (b) uses the decision rule attaining the maximum; (c) is (a) and (b) together.
Formalization Note The source states the theorem for countable ; the model of this mission is finite, as the chapter's Assumption 8.0.3, so the statement is the finite case. In (b) the source writes , the gain of a stationary policy, which exists as a limit on a finite chain; it is formalized as the lim inf gain, which equals it. In (c) the source's chain is stated through its two computable members and , since is defined only where the limits exist. The suprema over policies and over deterministic decision rules are real suprema of nonempty families bounded by .
import Definitions.Def_MarkovDecisionProcesses_AverageReward
namespace MarkovDecisionProcesses
theorem average_optimality_bounds {S A : Type*} [Fintype S] [Fintype A] [DecidableEq A]
(M : StationaryMDP S A) (g : ℝ) (h : S → ℝ) :
((∀ s, optimalityResidual M g h s ≤ 0) → ∀ s, optGainSup M s ≤ g) ∧
((∀ s, 0 ≤ optimalityResidual M g h s) →
∀ s, g ≤ (⨆ d : {d : S → A // ∀ s, d s ∈ M.admissible s},
gainInf (stationaryPolicy M d.1 d.2) s) ∧
(⨆ d : {d : S → A // ∀ s, d s ∈ M.admissible s},
gainInf (stationaryPolicy M d.1 d.2) s) ≤ optGainInf M s) ∧
((∀ s, optimalityResidual M g h s = 0) →
∀ s, optGainSup M s = g ∧ optGainInf M s = g) := by sorry
end MarkovDecisionProcesses
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.