Theorem 4 — under monotonicity and N-stage contraction, f is the unique fixed point of E and of A, and ρ(A^N v, f) ≤ cρ(v, f) for v ≤ f
ProvedDenardoDP.NStage.theorem4Let be a set, a decision set at each , the policies, the bounded real functions on with the sup metric , the return, the policy operators and the maximization operator , both mapping into . Suppose:
- the monotonicity assumption: implies for every ;
- the N-stage contraction assumption: for a positive integer and , independent of , each has modulus or less and each has modulus or less.
Let be the fixed point of , let be the operator , and let be the optimal return. Then:
- (a) is the unique fixed point of ;
- (b) for every ;
- (c) is a contraction mapping of modulus or less;
- (d) , and is the unique fixed point of and the unique fixed point of :
- (e) if , then
This is the main result of §5: even when no single is a contraction, the optimality equation has exactly one bounded solution, and it is the optimal return. Part (e) gives geometric convergence of successive approximations from below.
Formalization Note The family is supplied with (the paper's definition of in §5; such a family exists and is unique because is a contraction on the complete space ); part (a) is a conclusion. is taken as an operator with IsNStageSupOperator H N E (its value at each point is the least upper bound of ); such an operator exists, which is the milestone Theorem 4 (a)–(c), and is then unique. is not defined as a fixed point: part (d) asserts that some is the pointwise least upper bound of (which determines ) and that this satisfies , , is the only fixed point of either operator, and satisfies (e). is pointwise, and is the -fold composition.
import Mathlib import Definitions.Def_DenardoDP_NStage_Model
namespace DenardoDP.NStage
theorem theorem4 {Ω : Type*} {D : Ω → Type*}
(h : (x : Ω) → D x → DenardoDP.Contraction.BFun Ω → ℝ) (H : ((x : Ω) → D x) → DenardoDP.Contraction.BFun Ω → DenardoDP.Contraction.BFun Ω)
(A : DenardoDP.Contraction.BFun Ω → DenardoDP.Contraction.BFun Ω) (v : ((x : Ω) → D x) → DenardoDP.Contraction.BFun Ω) (N : ℕ) (c : ℝ)
(hH : DenardoDP.Contraction.IsPolicyOperator h H) (hA : DenardoDP.Contraction.IsMaxOperator h A)
(hmono : DenardoDP.Contraction.MonotonicityAssumption H) (hN : NStageContractionAssumption H N c)
(hv : ∀ δ, (H δ)^[N] (v δ) = v δ)
(E : DenardoDP.Contraction.BFun Ω → DenardoDP.Contraction.BFun Ω) (hE : IsNStageSupOperator H N E) :
(∀ δ, H δ (v δ) = v δ ∧ ∀ w, H δ w = w → w = v δ) ∧
(∀ δ w, dist (v δ) w ≤ dist (H δ w) w * N / (1 - c)) ∧
DenardoDP.Contraction.ModulusLE E c ∧
∃ f : DenardoDP.Contraction.BFun Ω, DenardoDP.Contraction.IsOptimalReturn v f ∧
E f = f ∧ A f = f ∧ (∀ w, E w = w → w = f) ∧ (∀ w, A w = w → w = f) ∧
(∀ w, DenardoDP.Contraction.PLe w f → dist (A^[N] w) f ≤ c * dist w f) := by sorry
end DenardoDP.NStage
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.