Proposition 4 — equalities on supported actions
ProvedHordijkKallenbergLP.Correspondence.proposition_4average-rewardlinear-programmingmarkov-decision-processmultichainp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix positive normalized state weights , an optimal dual solution and an optimal primal solution . Let be the actions with . For every ,
These equalities identify which superharmonic constraints become tight on the actions used by an optimal dual point. Formalization Note The primal first component is any optimal ; its identification with the optimal gain follows from Theorem 6 and positive , rather than being added as an assumption.
Preamble
import Mathlib import Definitions.Def_HordijkKallenbergLP_Correspondence_Model
Formal statement
namespace HordijkKallenbergLP.Correspondence
open MarkovDecisionProcesses
/-- Hordijk and Kallenberg (1979), Proposition 4, pp. 360–361.
The complementary-slackness identities hold for every action given positive
probability by the policy of any optimal dual solution. -/
theorem proposition_4 {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 : DualOptimal M β x y)
(φ u : S → ℝ) (hφu : PrimalOptimal M β φ u) :
∀ i a, 0 < dualPolicyWeight M x y i a →
(∑ j, M.trans i a j * φ j = φ i) ∧
(i ∈ Ex M x → φ i + u i = M.reward i a + ∑ j, M.trans i a j * u j) := 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. 360–361, Proposition 4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.