Proof of Theorem 9.3 —
ProvedNegativeDP.Switching.InH_zeroConsider a negative dynamic programming problem (non-positive returns, ) on non-empty Borel state and action spaces. Let and be policies with continuation returns and , and let . Then for every policy and every initial state ,
Here is the expected return when the process is stopped before the first stage and the terminal reward is received at the initial history .
This is the starting point of the induction in the proof of Theorem 9.3: the continuation return of a policy from the empty history is its expected return.
Formalization Note The paper's is wmax P σ τ 0 evaluated at the initial history Hist.start s (Lean's index is the paper's stage ). The return is defined through the law of the history from the initial state, the continuation return through the continuation law, so the second equality is a statement about those two constructions.
import Mathlib import Definitions.Def_NegativeDP_Switching_Model open MeasureTheory ProbabilityTheory open DiscountedDP.Stationary (Hist Plan MarkovPlan)
namespace NegativeDP.Switching
/-- Proof of Theorem 9.3 (p. 888): `I_0(π, w_1) = w_1 = max(I(σ), I(τ))`, for every plan `π`. -/
theorem InH_zero {S A : Type*} [MeasurableSpace S] [StandardBorelSpace S] [Nonempty S]
[MeasurableSpace A] [StandardBorelSpace A] [Nonempty A]
(P : Problem S A) (σ τ π : Plan (S := S) (A := A)) (s : S) :
InH P π 0 (wmax P σ τ 0) s = wmax P σ τ 0 (Hist.start s) ∧
wmax P σ τ 0 (Hist.start s) = max (I P σ s) (I P τ s) := by sorry
end NegativeDP.Switching
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.