Theorem 4.7.2 — L = X: the limit points of the expected state-action frequencies form the LP polytope
ProvedKallenbergLP.Constrained.limitPoints_eq_polytopeLet be an initial distribution (, ; zeros allowed) for a finite Markov decision model with stochastic transitions . Let be the set of all limit points of the expected state-action frequencies
over all policies (history-dependent and randomized), and let be the set of vectors for which some satisfies
Then
This characterizes the achievable long-run state-action frequencies of a multichain Markov decision problem as a polytope described by finitely many linear constraints, which is what makes constrained average-reward problems solvable by a single linear program.
Formalization Note ranges over all history-dependent randomized policies; restricting to stationary policies would give , which differs from in general (Example 4.7.1 of the book).
import Mathlib import Definitions.Def_MarkovDecisionProcesses_AverageReward import Definitions.Def_KallenbergLP_Constrained_Frequencies
namespace KallenbergLP.Constrained
open MarkovDecisionProcesses
/-- Kallenberg (1983), Theorem 4.7.2, p. 138: `L = X`. The set of all limit points of the expected
state-action frequencies, over all (history-dependent, randomized) policies, equals the polytope
`X` of (4.7.8). -/
theorem limitPoints_eq_polytope {S A : Type*} [Fintype S] [Fintype A] [DecidableEq S]
[DecidableEq A] (M : StationaryMDP S A) (β : S → ℝ) (hβ0 : ∀ j, 0 ≤ β j)
(hβ1 : ∑ j, β j = 1) :
Lset M β (fun _ => True) = polytopeX M β := by sorry
end KallenbergLP.Constrained
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.