§3.3 — representative satisfies the dual LP
ProvedHordijkKallenbergLP.Correspondence.representative_feasibleaverage-rewardlinear-programmingmarkov-decision-processmultichainp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and . For every stationary randomized policy , form the representative by equation (6), including the class-wise choice of . Then
Thus each stationary policy determines a feasible dual point, even when its Markov chain has several recurrent classes. The dual coordinates are indexed only by admissible state-action pairs.
Preamble
import Mathlib import Definitions.Def_HordijkKallenbergLP_Correspondence_Representative
Formal statement
namespace HordijkKallenbergLP.Correspondence
open MarkovDecisionProcesses
/-- Hordijk and Kallenberg (1979), §3.3, pp. 359–360, equation (6) and
properties 1–4: the representative is dual feasible. -/
theorem representative_feasible {S A : Type*} [Fintype S] [Fintype A]
[DecidableEq S] [DecidableEq A] [Nonempty S]
(M : StationaryMDP S A) (β : S → ℝ)
(hβpos : ∀ i, 0 < β i) (hβsum : ∑ i, β i = 1)
(π : RandomizedPolicy M) :
DualFeasible M β (representativeX M β π) (representativeY M β π) := 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, pp. 359–360, §3.3, equation (6) and properties 1–4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.