§3, discounted case (p. 446) — the discounted cost of a sigma in closed form (indices corrected)
ProvedMDPComplexity.Discounted.sigma_cost_closed_formLet and let be a sigma from in a deterministic Markov decision process: a walk along decisions with distinct nodes and for some . Write for the cost of its -th arc and for the length of its cycle. Then the discounted cost of the infinite walk that follows and repeats the cycle forever is
This is the formula the paper uses to evaluate a sigma; it turns the infinite discounted sum into a finite expression in the prefix cost and the cycle cost.
Formalization Note The paper prints , with mixed summation indices and a factor in the cycle sum that is one power of too many for the sentence that follows it ("the discounted cost of a sigma coincides with the discounted cost of an infinite path that follows the sigma and repeats the cycle forever"). We state the corrected identity, which agrees with that sentence: with the paper's , the cycle's -th arc () carries , i.e. the paper's for , and . The left side is the definition of the sigma's cost (an infinite series); is the paper's .
import Mathlib import Definitions.Def_MDPComplexity_Discounted_Model
namespace MDPComplexity.Discounted
open Finset
theorem sigma_cost_closed_form {S : Type} [Fintype S] [DecidableEq S] (M : DetMDP S) (s₀ : S)
(P : M.Sigma s₀) (β : ℝ) (hβ : 0 < β ∧ β < 1) :
P.cost β = ∑ t ∈ range P.j, β ^ t * P.arcCost t +
β ^ P.j / (1 - β ^ (P.N - P.j)) * ∑ t ∈ range (P.N - P.j), β ^ t * P.arcCost (P.j + t) := by sorry
end MDPComplexity.Discounted
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.