Proof of Theorem 1 (p. 445): the expected cost of the circuit process cannot be less than zero
ProvedMDPComplexity.CircuitValue.expCost_nonnegmarkov-decision-processp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1reduction
Let be a circuit with triples and let be the Markov decision process built from in the proof of Theorem 1 (initial state: the last triple ; horizon ). Then for every policy ,
This is the remark "(it cannot be less)" in the proof of Theorem 1: every cost of is or , so the optimal expected cost is at most exactly when it equals .
Formalization Note The expected cost is the sum over trajectories of the model definition, with the paper's §2 horizon convention and .
Preamble
import Mathlib import Definitions.Def_MDPComplexity_CircuitValue_Model import Definitions.Def_MDPComplexity_CircuitValue_Circuit import Definitions.Def_MDPComplexity_CircuitValue_Reduction
Formal statement
namespace MDPComplexity.CircuitValue
theorem expCost_nonneg {k : ℕ} [NeZero k] (C : Circuit k) (δ : C.toMDP.Policy) :
0 ≤ C.toMDP.expCost (some (Circuit.lastIdx k)) δ k := by sorry
end MDPComplexity.CircuitValue
Source
Papadimitriou and Tsitsiklis, The Complexity of Markov Decision Processes, Math. Oper. Res. 12(3) (1987), p. 445, §3, proof of Theorem 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.