§3.2 — normalization of a feasible dual solution
ProvedHordijkKallenbergLP.Correspondence.dual_policy_well_definedaverage-rewardlinear-programmingmarkov-decision-processmultichainp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let with , and let satisfy the dual constraints (3)–(5). For every state ,
Consequently the normalized rule , using when its row sum is positive and otherwise, is a stationary randomized policy supported on available actions. This supplies the denominator and policy facts used in both parts of Theorem 8. Formalization Note The Lean inequality states the comparison with ; strict positivity follows from the separately stated assumption .
Preamble
import Mathlib import Definitions.Def_HordijkKallenbergLP_Correspondence_Model
Formal statement
namespace HordijkKallenbergLP.Correspondence
open MarkovDecisionProcesses
/-- Hordijk and Kallenberg (1979), §3.2, proof of Theorem 7, p. 357:
equations (4) and (5) make the normalization of §3.3 a policy.
Formalization Note: the existence clause certifies both cases of the printed
definition, including the positive y-denominator outside E_x. -/
theorem dual_policy_well_defined {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) :
(∀ i, β i ≤ stateMass M x i + stateMass M y i) ∧
∃ π : RandomizedPolicy M, ∀ i a, π.weight i a = dualPolicyWeight M x y i a := 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. 357, §3.2, proof of Theorem 7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.