§3.3 — stationary gain from the Cesàro limit
ProvedHordijkKallenbergLP.Correspondence.stationary_gainaverage-rewardlinear-programmingmarkov-decision-processmultichainp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be any stationary randomized policy of a finite Markov decision process, with transition matrix , one-step reward vector and Cesàro limit matrix . Its liminf average reward is
This converts the policy's long-run performance into the matrix expression used by its representative. Formalization Note The other identities stated in the same paragraph of the paper belong to Blackwell's existing limit and deviation matrix results.
Preamble
import Mathlib import Definitions.Def_HordijkKallenbergLP_Correspondence_Representative
Formal statement
namespace HordijkKallenbergLP.Correspondence
open MarkovDecisionProcesses Matrix
/-- Hordijk and Kallenberg (1979), §3.3, p. 359, the final clause after
the limit and deviation matrix identities. -/
theorem stationary_gain {S A : Type*} [Fintype S] [Fintype A]
[DecidableEq S] [DecidableEq A] [Nonempty S]
(M : StationaryMDP S A) (π : RandomizedPolicy M) (i : S) :
gainInf π.toHR i = (Pstar M π).mulVec (policyReward M π) 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. 359, §3.3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.