Theorem 8 — correspondence preserves average optimality
ProvedHordijkKallenbergLP.Correspondence.theorem_8average-rewardlinear-programmingmarkov-decision-processmultichainp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let with in a finite Markov decision process. There are two directions.
- If a stationary randomized policy is average optimal among all history-dependent randomized policies, then its representative from equation (6) is an optimal solution of the dual linear program.
- If is any optimal dual solution, then its normalized stationary randomized policy exists and is average optimal.
The theorem relates policy performance to every dual optimum in a multichain model. Formalization Note The second direction explicitly constructs a randomized policy with the printed weights; no extreme-point or pure-action hypothesis is imposed.
Preamble
import Mathlib import Definitions.Def_HordijkKallenbergLP_Correspondence_Representative
Formal statement
namespace HordijkKallenbergLP.Correspondence
open MarkovDecisionProcesses
/-- Hordijk and Kallenberg (1979), Theorem 8(a) and (b), p. 360.
Formalization Note: part (b) asserts existence of the normalized randomized
policy with the exact printed weights and its average optimality. It ranges over
all dual optima, not only extreme points. -/
theorem theorem_8 {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, HordijkKallenbergLP.SingleLP.IsAvgOptimal M π.toHR →
DualOptimal M β (representativeX M β π) (representativeY M β π)) ∧
(∀ x y : HordijkKallenbergLP.SingleLP.Pair M → ℝ, DualOptimal M β x y →
∃ π : RandomizedPolicy M,
(∀ i a, π.weight i a = dualPolicyWeight M x y i a) ∧
HordijkKallenbergLP.SingleLP.IsAvgOptimal M π.toHR) := 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, Theorem 8
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.