Proposition 5 — recurrent states are exactly E_x
ProvedHordijkKallenbergLP.Correspondence.proposition_5average-rewardlinear-programmingmarkov-decision-processmultichainp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix positive normalized state weights and any feasible dual solution . Construct the stationary randomized policy by row normalization, and let be its transition matrix. Then
This identifies the support of the flow with the recurrent part of the induced finite Markov chain. Feasibility alone suffices; the dual point need not be optimal or extreme.
Preamble
import Mathlib import Definitions.Def_HordijkKallenbergLP_Correspondence_Model
Formal statement
namespace HordijkKallenbergLP.Correspondence
open MarkovDecisionProcesses
/-- Hordijk and Kallenberg (1979), Proposition 5, p. 361.
Formalization Note: the transition matrix uses the normalized policy attached
to the feasible pair, with no extremality or optimality hypothesis. -/
theorem proposition_5 {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)
(x y : HordijkKallenbergLP.SingleLP.Pair M → ℝ) (hxy : DualFeasible M β x y)
(π : RandomizedPolicy M)
(hπ : ∀ i a, π.weight i a = dualPolicyWeight M x y i a) :
∀ i, i ∈ Ex M x ↔ IsRecurrent (policyMatrix 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. 361, Proposition 5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.