Theorem 6 — least superharmonic gain
ProvedHordijkKallenbergLP.Correspondence.theorem_6average-rewardlinear-programmingmarkov-decision-processmultichainp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
For a finite Markov decision process, let be the supremum, over all history-dependent randomized policies, of the liminf average reward starting at . Then some makes superharmonic, and every superharmonic pair satisfies
This identifies the optimal gain vector as the componentwise least possible first component of a feasible primal pair.
Preamble
import Mathlib import Definitions.Def_HordijkKallenbergLP_Correspondence_Model
Formal statement
namespace HordijkKallenbergLP.Correspondence
open MarkovDecisionProcesses
/-- Hordijk and Kallenberg (1979), Theorem 6, p. 356.
The optimal average reward is the componentwise least first component of a
superharmonic pair. -/
theorem theorem_6 {S A : Type*} [Fintype S] [Fintype A] [Nonempty S]
(M : StationaryMDP S A) :
(∃ u : S → ℝ, HordijkKallenbergLP.SingleLP.Superharmonic M (optGainInf M) u) ∧
(∀ φ u : S → ℝ, HordijkKallenbergLP.SingleLP.Superharmonic M φ u → ∀ i, optGainInf M i ≤ φ i) := by sorry
end HordijkKallenbergLP.Correspondence
Source
Hordijk and Kallenberg, Linear Programming and Markov Decision Chains, Management Sci. 25(4):352–362 (1979), DOI 10.1287/mnsc.25.4.352, p. 356, Theorem 6
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.