Lemma 4.7.1 — for R in C_1 the frequency limit equals the Abel limit of discounted frequencies
ProvedKallenbergLP.Constrained.freq_eq_abel_limitdynamic-programmingmarkov-decision-processp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1state-action-frequencies
Let be an initial distribution and a policy whose expected state-action frequencies have exactly one limit point (that is, ). Then for every state and action ,
The lemma links the average-reward frequencies to normalized discounted frequencies, so that results for discounted problems can be transferred to the average case as the discount factor tends to one.
Formalization Note The limit is taken along the left neighbourhood filter 𝓝[<] 1; the Lean summation index is the book's .
Preamble
import Mathlib import Definitions.Def_MarkovDecisionProcesses_AverageReward import Definitions.Def_KallenbergLP_Constrained_Frequencies
Formal statement
namespace KallenbergLP.Constrained
open MarkovDecisionProcesses Filter Topology
/-- Kallenberg (1983), Lemma 4.7.1, pp. 153–154: for `R ∈ C_1` with unique limit point `x(R)` and
every pair `(j, a)`,
`x_{ja}(R) = lim_{α↑1} (1−α) ∑_{t=1}^∞ α^{t−1} ∑_i β_i ℙ_R(X_t = j, Y_t = a | X_1 = i)`. -/
theorem freq_eq_abel_limit {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) (R : AvgHRPolicy M) (hR : IsC1 β R)
(x : KallenbergLP.AverageLP.Pair M → ℝ) (hx : x ∈ limitPoints β R) (p : KallenbergLP.AverageLP.Pair M) :
Tendsto (fun α : ℝ => (1 - α) * ∑' k : ℕ, α ^ k * ∑ i, β i * prob R k i p)
(𝓝[<] 1) (𝓝 (x p)) := by sorry
end KallenbergLP.Constrained
Source
Kallenberg, Linear Programming and Finite Markovian Control Problems, Mathematical Centre Tracts 148, Mathematisch Centrum, Amsterdam 1983, pp. 153–154, Lemma 4.7.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.