Theorem 8(a) proof — objective of the representative
ProvedHordijkKallenbergLP.Correspondence.representative_objectiveaverage-rewardlinear-programmingmarkov-decision-processmultichainp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
For any positive normalized state weights and stationary randomized policy , the dual objective at its representative equals the -weighted average reward of the policy:
This is the objective identity used to compare an optimal policy with the primal optimum in Theorem 8(a). It makes no optimality assumption on .
Preamble
import Mathlib import Definitions.Def_HordijkKallenbergLP_Correspondence_Representative
Formal statement
namespace HordijkKallenbergLP.Correspondence
open MarkovDecisionProcesses
/-- Hordijk and Kallenberg (1979), proof of Theorem 8(a), p. 360:
the representative's dual objective is the β-weighted gain of its policy. -/
theorem representative_objective {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) :
dualObjective M (representativeX M β π) =
∑ i, β i * gainInf π.toHR 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. 360, proof of Theorem 8(a)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.