expected_utility_dtd_le_dus
For every Pandora's problem instance with deadlines inst : PandoraDeadlineInstance and every adaptive policy π : AdaptivePolicy inst.n, the expected net utility under deferred-to-deadline commitment expectedUtilityDTD inst π is at most the expected net utility under deferred-until-stopping commitment expectedUtilityDUS inst π.
Statement
theorem expected_utility_dtd_le_dus (inst : PandoraDeadlineInstance) (π : AdaptivePolicy inst.n) :
expectedUtilityDTD inst π ≤ expectedUtilityDUS inst π- Source
- arXiv:2610.13775 Sec. 2.1
- Verified
- 19 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- expectedUtilityDTDThe expected net utility of an adaptive policy
π : AdaptivePolicy inst.nunder deferred-to-deadline commitment on a Pandora's problem… - expectedUtilityDUSThe expected net utility of an adaptive policy
π : AdaptivePolicy inst.nunder deferred-until-stopping commitment on a Pandora's problem… - PandoraDeadlineInstanceAn instance of Pandora's problem with deadlines consisting of n boxes, each with a non-negative opening cost, a positive integer deadline,…
- DiscreteDistA discrete probability distribution with finite support on non-negative real values, defined by a finite support set, non-negative…
- AdaptivePolicyA fully adaptive search policy for Pandora's problem with n boxes, represented as a decision tree that at each step either stops or opens…
- expectedUtilityDTDThe expected net utility of an adaptive policy
- Used by 1
- opt_dtd_le_opt_dusFor every Pandora's problem instance with deadlines
inst : PandoraDeadlineInstance, the optimal expected utility under…
- opt_dtd_le_opt_dusFor every Pandora's problem instance with deadlines
Read back from the Lean
For any Pandora's deadline instance inst and any adaptive policy π on inst.n boxes, the expected utility of π under the deadline-constrained model (expectedUtilityDTD inst π) is less than or equal to the expected utility of π under the unconstrained model (expectedUtilityDUS inst π).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof proceeds by structural induction on the adaptive policy π, generalized to an arbitrary history of inspected boxes. Under deferred-to-deadline (DTD) commitment, an opened box can only be selected upon stopping if the total stopping time does not exceed the box's deadline, whereas under deferred-until-stopping (DUS) commitment, any opened box may be chosen regardless of deadlines. For the base case where the policy stops, a helper lemma shows by list induction that filtering opened boxes by their deadlines can only decrease or preserve the maximum value obtained. For the inductive step where a box is opened, the cost incurred is identical in both models, and the expected continuation utility is bounded by the induction hypothesis because outcome probabilities are non-negative.
The goal reduces to proving the inequality for the recursive auxiliary functions starting with an empty history.
We unfold the definitions of `expectedUtilityDTD` and `expectedUtilityDUS`, both of which are defined by evaluating their auxiliary recursive functions `aux` on the initial empty history `[]`.
unfold expectedUtilityDTD expectedUtilityDUSTo show that the deadline-filtered maximum over a history is bounded by the unfiltered maximum, it suffices to prove the stronger claim for any two initial accumulators acc1 ≤ acc2.
We formulate the lemma `hfold` and generalize it using `suffices`: for arbitrary initial values acc1 ≤ acc2, the left fold with deadline filtering starting at acc1 is at most the unfiltered fold starting at acc2. Specializing to acc1 = acc2 = 0 via `le_rfl` immediately yields the desired inequality.
uses
le_rflhave hfold : ∀ (t : ℕ) (history : List (Fin inst.n × ℝ)), List.foldl (fun acc bv => if t ≤ inst.deadline bv.1 then max acc bv.2 else acc) 0 history ≤ List.foldl (fun acc bv => max acc bv.2) 0 history := by intro t history suffices h : ∀ (acc1 acc2 : ℝ) (l : List (Fin inst.n × ℝ)), acc1 ≤ acc2 → List.foldl (fun acc bv => if t ≤ inst.deadline bv.1 then max acc bv.2 else acc) acc1 l ≤ List.foldl (fun acc bv => max acc bv.2) acc2 l from h 0 0 history le_rfl
For any list of inspected boxes and any acc1 ≤ acc2, the accumulator inequality is preserved through the fold.
We argue by induction on the list of inspected boxes. The base case of an empty list holds directly from the assumption acc1 ≤ acc2. In the inductive step for an added box bv, we case-split on whether the current time t meets the box deadline (t ≤ inst.deadline bv.1). If it does, the filter condition is true (`if_true`) and the new accumulators max acc1 bv.2 ≤ max acc2 bv.2 preserve the order by monotonicity of max (`max_le_max`). If the deadline is not met, the filter condition is false (`if_false`) so the left accumulator remains acc1, which is at most acc2 ≤ max acc2 bv.2 by transitivity (`le_trans`) and `le_max_left`. In both cases, the induction hypothesis applies.
uses
if_true,max_le_max,le_rfl,if_false,le_trans,le_max_leftintro acc1 acc2 l induction l generalizing acc1 acc2 with | nil => intro h; exact h | cons bv rest ih => intro hle apply ih by_cases hc : t ≤ inst.deadline bv.1 · simp only [hc, if_true] exact max_le_max hle le_rfl · simp only [hc, if_false] exact le_trans hle (le_max_left _ _)
Under the stopping policy `AdaptivePolicy.stop`, the expected utility under DTD is at most that under DUS, for any history.
We introduce `key`, which asserts the inequality `expectedUtilityDTD.aux inst history a ≤ expectedUtilityDUS.aux inst history a` for all policies a and histories. We proceed by induction on a using `AdaptivePolicy.rec`. For the stopping policy a = stop, the stopping time is t = history.length; the DTD utility is the deadline-filtered fold and the DUS utility is the unfiltered fold, so the inequality holds directly by `hfold`.
uses
AdaptivePolicy.rechave key : ∀ (a : AdaptivePolicy inst.n) (history : List (Fin inst.n × ℝ)), expectedUtilityDTD.aux inst history a ≤ expectedUtilityDUS.aux inst history a := by intro a induction a using AdaptivePolicy.rec with | stop => intro history exact hfold history.length history
When opening a box b with continuation policy cont, the DTD expected utility is bounded by the DUS expected utility.
In the inductive step `AdaptivePolicy.openBox b cont`, both utility functions expand to an expected continuation utility minus the inspection cost cost(b). The cost is identical on both sides, so subtracting it preserves the inequality by `sub_le_sub_right`. By `Finset.sum_le_sum`, it suffices to bound the expected values term by term. For each outcome value v in the support of box b, the continuation utility under DTD is at most that under DUS by the induction hypothesis; since the probability of outcome v is non-negative, multiplying by it preserves the inequality via `mul_le_mul_of_nonneg_left`.
uses
sub_le_sub_right,Finset.sum_le_sum,mul_le_mul_of_nonneg_left| openBox b cont ih => intro history rw [show expectedUtilityDTD.aux inst history (AdaptivePolicy.openBox b cont) = _ from rfl, show expectedUtilityDUS.aux inst history (AdaptivePolicy.openBox b cont) = _ from rfl] apply sub_le_sub_right apply Finset.sum_le_sum intro v hv exact mul_le_mul_of_nonneg_left (ih v ((b, v) :: history)) ((inst.dist b).prob_nonneg v hv)The expected utility under DTD for policy π is at most that under DUS, concluding the proof.
We instantiate the generalized induction result `key` with policy π and the empty history `[]`.
exact key π []
le_rfl- Inequality is reflexive: every element is less than or equal to itself (a ≤ a).
if_true- A conditional expression whose condition is true simplifies to the 'then' branch.
if_false- A conditional expression whose condition is false simplifies to the 'else' branch.
max_le_max- Taking the maximum is monotonic: a ≤ c and b ≤ d imply max a b ≤ max c d.
le_trans- Inequality is transitive: a ≤ b and b ≤ c imply a ≤ c.
le_max_left- Any element is at most the maximum of itself and another element (a ≤ max a b).
AdaptivePolicy.rec- The structural induction principle for adaptive policies: a property holds for all policies if it holds for `stop` and is preserved by `openBox`.
sub_le_sub_right- Subtracting a common term from both sides preserves the inequality (a ≤ b implies a - c ≤ b - c).
Finset.sum_le_sum- If f(i) ≤ g(i) for all elements i in a finite set, then the sum of f is at most the sum of g.
mul_le_mul_of_nonneg_left- Multiplying an inequality by a non-negative number on the left preserves the inequality (b ≤ c implies a * b ≤ a * c for a ≥ 0).
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Expected net utility under deferred-to-deadline commitment is at most that under deferred-until-stopping commitment. -/theorem expected_utility_dtd_le_dus (inst : PandoraDeadlineInstance) (π : AdaptivePolicy inst.n) : expectedUtilityDTD inst π ≤ expectedUtilityDUS inst π := by unfold expectedUtilityDTD expectedUtilityDUS have hfold : ∀ (t : ℕ) (history : List (Fin inst.n × ℝ)), List.foldl (fun acc bv => if t ≤ inst.deadline bv.1 then max acc bv.2 else acc) 0 history ≤ List.foldl (fun acc bv => max acc bv.2) 0 history := by intro t history suffices h : ∀ (acc1 acc2 : ℝ) (l : List (Fin inst.n × ℝ)), acc1 ≤ acc2 → List.foldl (fun acc bv => if t ≤ inst.deadline bv.1 then max acc bv.2 else acc) acc1 l ≤ List.foldl (fun acc bv => max acc bv.2) acc2 l from h 0 0 history le_rfl intro acc1 acc2 l induction l generalizing acc1 acc2 with | nil => intro h; exact h | cons bv rest ih => intro hle apply ih by_cases hc : t ≤ inst.deadline bv.1 · simp only [hc, if_true] exact max_le_max hle le_rfl · simp only [hc, if_false] exact le_trans hle (le_max_left _ _) have key : ∀ (a : AdaptivePolicy inst.n) (history : List (Fin inst.n × ℝ)), expectedUtilityDTD.aux inst history a ≤ expectedUtilityDUS.aux inst history a := by intro a induction a using AdaptivePolicy.rec with | stop => intro history exact hfold history.length history | openBox b cont ih => intro history rw [show expectedUtilityDTD.aux inst history (AdaptivePolicy.openBox b cont) = _ from rfl, show expectedUtilityDUS.aux inst history (AdaptivePolicy.openBox b cont) = _ from rfl] apply sub_le_sub_right apply Finset.sum_le_sum intro v hv exact mul_le_mul_of_nonneg_left (ih v ((b, v) :: history)) ((inst.dist b).prob_nonneg v hv) exact key π []