Proof of Theorem 1 (p. 445): with nonnegative costs, zero expected cost iff no positive cost is incurred on a reachable trajectory
ProvedMDPComplexity.CircuitValue.expCost_eq_zero_iffLet be a finite Markov decision process (states , decisions , costs , transition probabilities ) whose costs are all nonnegative: . Fix an initial state , a policy and a horizon . Then
if and only if, for every trajectory that has positive probability under from , every cost incurred along it is zero: for all .
In the proof of Theorem 1 this is the step "there are decisions so that the states with positive costs are impossible to reach": a zero expected cost means that the policy never reaches, with positive probability, a state where it pays a positive cost.
Formalization Note Stated for an arbitrary finite, possibly nonstationary process with nonnegative costs, since the step does not use the circuit. "Impossible to reach" is read as "no trajectory of positive probability incurs a positive cost".
import Mathlib import Definitions.Def_MDPComplexity_CircuitValue_Model
namespace MDPComplexity.CircuitValue
open Finset BigOperators
theorem expCost_eq_zero_iff {S : Type} [Fintype S] [DecidableEq S] (M : MDP S)
(hc : ∀ s i t, 0 ≤ M.c s i t) (s₀ : S) (δ : M.Policy) (T : ℕ) :
M.expCost s₀ δ T = 0 ↔
∀ x : Fin (T + 1) → S, 0 < M.trajProb s₀ δ T x →
∀ t : Fin (T + 1), M.c (x t) (δ (x t) (t : ℕ)) (t : ℕ) = 0 := by sorry
end MDPComplexity.CircuitValue
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.