expected_utility_dus_le_opt_dus
For any Pandora's problem instance with deadlines inst and any valid policy π, expectedUtilityDUS inst π ≤ optDUS inst.
Statement
theorem expected_utility_dus_le_opt_dus (inst : PandoraDeadlineInstance) (π : AdaptivePolicy inst.n)
(hπ : IsValidPolicy inst π) :
expectedUtilityDUS inst π ≤ optDUS inst- Source
- step towards op182_deferred_to_deadline_beyond_half_against_stopping
- Verified
- 19 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- optDUSThe optimal expected net utility
optDUS instunder deferred-until-stopping commitment for a Pandora's problem instance with deadlines… - expectedUtilityDUSThe expected net utility of an adaptive policy
π : AdaptivePolicy inst.nunder deferred-until-stopping commitment on a Pandora's problem… - IsValidPolicyA policy is valid for a Pandora's problem instance with deadlines if it respects opening deadlines and never opens any box more than once.
- 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…
- 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…
- supportThe support $\mathrm{supp}(p) \subseteq \mathrm{Fin}\,n$ consists of coordinates where $p(i) \neq I$; the weight is…
- optDUSThe optimal expected net utility
- Used by 3
- opt_dus_nonnegFor any Pandora deadline instance
inst,0 ≤ optDUS inst. - op182_deferred_to_deadline_beyond_half_against_stoppingRefutation of Open Problem OP-182 against the deferred-until-stopping benchmark: there does not exist any constant
c > 1/2such that for… - two_box_counterexample_familyFor any integer
M > 1, there exists a 2-box Pandora deadline instance such that2 - 1 / M ≤ optDUS instand every valid policyπ…
- opt_dus_nonnegFor any Pandora deadline instance
The proof, explained
The theorem proves that the expected utility of any valid adaptive policy $\pi$ under deferred-until-stopping commitment is at most $\text{optDUS}(inst)$, the supremum of expected utilities over all valid policies. First, structural induction on policies establishes that the expected utility of any policy is bounded above by the total sum of all possible prize values across all boxes. This bound guarantees that the sets of utilities are bounded above in the conditionally complete lattice $\mathbb{R}$. Finally, applying the definition of supremum twice—first over the validity proofs for $\pi$, and then over all policies—yields the desired inequality.
For any list of pairs whose second components are bounded by $M$, folding $\max$ over the list starting from initial value $x$ is at most $\max(x, M)$.
We proceed by induction on the list. For the empty list, folding returns $x$, which is bounded by $\max(x, M)$. For a non-empty list `hd :: tl`, folding over `hd :: tl` with accumulator $x$ is equivalent to folding over `tl` with accumulator $\max(x, hd.2)$. By the induction hypothesis, this is at most $\max(\max(x, hd.2), M)$. By associativity of $\max$ and the assumption that $hd.2 \le M$, we rewrite $\max(hd.2, M) = M$, yielding $\max(x, M)$.
uses
List.foldl_cons,expected_utility_dus_le_opt_dus_foldl_max_le,List.mem_cons_of_mem,le_trans,max_assoc,max_eq_right| [], x, M, _ => by simp | hd :: tl, x, M, h => by have h1 : hd.2 ≤ M := h hd (by simp) simp only [List.foldl_cons] refine le_trans (expected_utility_dus_le_opt_dus_foldl_max_le tl (max x hd.2) M (fun bv hbv => h bv (List.mem_cons_of_mem _ hbv))) ?_ rw [max_assoc, max_eq_right h1]
For the stopping policy `AdaptivePolicy.stop`, the auxiliary expected utility for any history bounded by $M \ge 0$ is at most $M$.
We induct on the adaptive policy. When the policy is `stop`, the auxiliary utility definition simplifies to folding $\max$ over the recorded history starting at accumulator 0. By the fold lemma, this is bounded by $\max(0, M)$, which equals $M$ because $0 \le M$.
uses
le_trans,expected_utility_dus_le_opt_dus_foldl_max_le,max_eq_rightintro a induction a using AdaptivePolicy.rec with | stop => intro hist hh rw [show expectedUtilityDUS.aux inst hist (AdaptivePolicy.stop : AdaptivePolicy inst.n) = List.foldl (fun acc bv => max acc bv.2) 0 hist from rfl] exact le_trans (expected_utility_dus_le_opt_dus_foldl_max_le hist 0 M hh) (by rw [max_eq_right hM0])
For an `openBox b cont` policy, the auxiliary expected utility is at most $M$, completing the induction that all policies have auxiliary utility bounded by $M$.
When opening box $b$, the auxiliary utility is the expected continuation utility minus the inspection cost $\text{cost}(b)$. For every prize $v$ in the support of box $b$, the augmented history $(b, v) :: hist$ has all prizes bounded by $M$. By the induction hypothesis, each continuation's auxiliary utility is at most $M$. Since probabilities are non-negative, each term is at most $\text{prob}(v) \cdot M$. Summing over the support and factoring out $M$ yields $(\sum_v \text{prob}(v)) \cdot M = 1 \cdot M = M$. Because $\text{cost}(b) \ge 0$, linear arithmetic shows the expected utility minus cost is at most $M$.
uses
Finset.sum_le_sum,mul_le_mul_of_nonneg_left,List.mem_cons.mp,Finset.sum_mul,one_mul| openBox b cont ih => intro hist hh rw [show expectedUtilityDUS.aux inst hist (AdaptivePolicy.openBox b cont) = ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v * expectedUtilityDUS.aux inst ((b, v) :: hist) (cont v) - inst.cost b from rfl] have hsum : ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v * expectedUtilityDUS.aux inst ((b, v) :: hist) (cont v) ≤ M := by have h1 : ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v * expectedUtilityDUS.aux inst ((b, v) :: hist) (cont v) ≤ ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v * M := by apply Finset.sum_le_sum intro v hv apply mul_le_mul_of_nonneg_left _ ((inst.dist b).prob_nonneg v hv) exact ih v ((b, v) :: hist) (fun bv hbv => by rcases List.mem_cons.mp hbv with hmem | hmem · rw [hmem]; exact hMv b v hv · exact hh bv hmem) calc ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v * expectedUtilityDUS.aux inst ((b, v) :: hist) (cont v) ≤ ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v * M := h1 _ = (∑ v ∈ (inst.dist b).support, (inst.dist b).prob v) * M := by rw [Finset.sum_mul] _ = M := by rw [(inst.dist b).sum_prob_one, one_mul] linarith [inst.cost_nonneg b]The set of expected utilities of all adaptive policies is bounded above by the total sum of all possible prize values.
Let $B = \sum_i \sum_{v \in \text{support}(\text{dist}(i))} v$ be the sum of all prize values across all boxes. Because all prizes are non-negative, $B \ge 0$. Furthermore, every individual prize $v$ in the support of any box $i$ is bounded by $B$, since a single term in a non-negative double sum is at most the total sum. Applying the auxiliary bound lemma with bound $B$ and an empty history shows that every policy's expected utility is at most $B$.
uses
expected_utility_dus_le_opt_dus_aux_bound,Finset.sum_nonneg,le_trans,Finset.single_le_sum,Finset.mem_univrefine ⟨∑ i : Fin inst.n, ∑ v ∈ (inst.dist i).support, v, ?_⟩ rintro _ ⟨π, rfl⟩ apply expected_utility_dus_le_opt_dus_aux_bound inst _ ?_ ?_ π [] (by simp) · exact Finset.sum_nonneg fun i _ => Finset.sum_nonneg fun v hv => (inst.dist i).val_nonneg v hv · intro i v hv refine le_trans (Finset.single_le_sum (f := fun v => v) (fun v hv => (inst.dist i).val_nonneg v hv) hv) ?_ exact Finset.single_le_sum (f := fun i => ∑ v ∈ (inst.dist i).support, v) (fun i _ => Finset.sum_nonneg fun v hv => (inst.dist i).val_nonneg v hv) (Finset.mem_univ i)
The indexed suprema of expected utilities over valid policies are bounded above across all policies.
To show that the range of $\lambda \pi', \bigsqcup_{(h : \text{IsValidPolicy}(inst, \pi'))} \text{expectedUtilityDUS}(inst, \pi')$ is bounded above, it suffices by `BddAbove.range_iSup_of_iUnion_range` to bound the union of the ranges of the inner constant families. By the previous lemma, every expected utility is bounded above by the total prize sum $B$, which therefore bounds this union.
uses
BddAbove.range_iSup_of_iUnion_range,expected_utility_dus_le_opt_dus_bddAbove,Set.mem_iUnion,Set.mem_range,Set.mem_range_selfhave hbdd : BddAbove (Set.range fun π : AdaptivePolicy inst.n => ⨆ (_ : IsValidPolicy inst π), expectedUtilityDUS inst π) := by refine BddAbove.range_iSup_of_iUnion_range ?_ obtain ⟨B, hB⟩ := expected_utility_dus_le_opt_dus_bddAbove inst refine ⟨B, ?_⟩ intro x hx simp only [Set.mem_iUnion, Set.mem_range] at hx obtain ⟨π', -, rfl⟩ := hx exact hB (Set.mem_range_self π')
For the given valid policy $\pi$, its expected utility is at most the supremum over validity proofs for $\pi$.
We unfold $\text{optDUS}$. For the fixed policy $\pi$, its expected utility belongs to the singleton range indexed by proofs of validity. Since the hypothesis $h\pi$ provides a validity witness, `le_ciSup` implies that the utility of $\pi$ is at most the supremum over all such validity witnesses.
uses
le_ciSup,le_rflunfold optDUS have h1 : expectedUtilityDUS inst π ≤ ⨆ (_ : IsValidPolicy inst π), expectedUtilityDUS inst π := by exact le_ciSup ⟨expectedUtilityDUS inst π, by rintro _ ⟨_, rfl⟩; exact le_rfl⟩ hπ
The supremum over validity proofs for $\pi$ is at most $\text{optDUS}(inst)$, and therefore $\text{expectedUtilityDUS}(inst, \pi) \le \text{optDUS}(inst)$.
Using the upper bound established for the outer family (`hbdd`), `le_ciSup` bounds the inner supremum for policy $\pi$ by the full supremum over all policies $\pi'$, which is $\text{optDUS}(inst)$. Transitivity combining this with the previous step proves that the expected utility of $\pi$ is at most $\text{optDUS}(inst)$.
uses
le_ciSup,le_transhave h2 : (⨆ (_ : IsValidPolicy inst π), expectedUtilityDUS inst π) ≤ ⨆ (π' : AdaptivePolicy inst.n), ⨆ (_ : IsValidPolicy inst π'), expectedUtilityDUS inst π' := by exact le_ciSup hbdd π exact le_trans h1 h2
List.foldl_cons- Folding a function over a non-empty list `a :: l` with accumulator `b` equals folding over `l` with updated accumulator `f b a`.
expected_utility_dus_le_opt_dus_foldl_max_le- If all second components of pairs in a list `l` are bounded by `M`, then folding the `max` operation over `l` starting from `x` is bounded by `max x M`.
List.mem_cons_of_mem- An element belonging to a list also belongs to that list prepended with any element `y`.
le_trans- Inequality is transitive: if `a ≤ b` and `b ≤ c`, then `a ≤ c`.
max_assoc- The maximum operation on a linear order is associative: `max (max a b) c = max a (max b c)`.
max_eq_right- If `a ≤ b`, then `max a b = b`.
Finset.sum_le_sum- If `f i ≤ g i` for all indices `i ∈ s`, then the sum of `f` over `s` is at most the sum of `g` over `s`.
mul_le_mul_of_nonneg_left- Multiplying an inequality `b ≤ c` on the left by a non-negative value `a` preserves the inequality: `a * b ≤ a * c`.
List.mem_cons.mp- Membership in a prepended list `a :: l` implies being the head `a` or being in the tail `l`.
Finset.sum_mul- Multiplication distributes over finite summation from the right: `(∑ i ∈ s, f i) * a = ∑ i ∈ s, f i * a`.
one_mul- Multiplying any value by 1 on the left leaves it unchanged: `1 * a = a`.
expected_utility_dus_le_opt_dus_aux_bound- For any non-negative bound `M` exceeding all box prize values, and any history bounded by `M`, the auxiliary expected utility of any adaptive policy is at most `M`.
Finset.sum_nonneg- A finite sum of non-negative real numbers is non-negative.
Finset.single_le_sum- Any single term in a finite sum of non-negative elements is at most the total sum.
Finset.mem_univ- Every element of a finite type belongs to its universal finset `Finset.univ`.
BddAbove.range_iSup_of_iUnion_range- If the union of ranges of a family of functions is bounded above, then the range of their pointwise suprema is also bounded above.
expected_utility_dus_le_opt_dus_bddAbove- The set of expected utilities of all adaptive policies for a Pandora's problem instance is bounded above.
Set.mem_iUnion- An element belongs to an indexed union of sets if and only if it belongs to at least one set in the family.
Set.mem_range- An element belongs to the range of a function if and only if it is the image of some input.
Set.mem_range_self- Every value of a function belongs to the range of that function.
le_ciSup- In a conditionally complete lattice, any element in the range of a function is bounded above by the supremum of that function, provided the range is bounded above.
le_rfl- Inequality is reflexive: `a ≤ a`.
- In Lean's conditionally complete lattice ℝ, applying `le_ciSup` (that a term is at most the supremum) requires proving that the range is bounded above (`BddAbove`). On paper, such boundedness is usually implicit because all prize distributions have finite support.
- The definition of `optDUS` is formalized as a nested supremum: an outer supremum over all adaptive policies `π'`, and an inner supremum indexed by proofs that `π'` is a valid policy (`IsValidPolicy inst π'`).
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.
lemma expected_utility_dus_le_opt_dus_foldl_max_le {α : Type*} : ∀ (l : List (α × ℝ)) (x M : ℝ), (∀ bv ∈ l, bv.2 ≤ M) → List.foldl (fun acc bv => max acc bv.2) x l ≤ max x M | [], x, M, _ => by simp | hd :: tl, x, M, h => by have h1 : hd.2 ≤ M := h hd (by simp) simp only [List.foldl_cons] refine le_trans (expected_utility_dus_le_opt_dus_foldl_max_le tl (max x hd.2) M (fun bv hbv => h bv (List.mem_cons_of_mem _ hbv))) ?_ rw [max_assoc, max_eq_right h1]lemma expected_utility_dus_le_opt_dus_aux_bound (inst : PandoraDeadlineInstance) (M : ℝ) (hM0 : 0 ≤ M) (hMv : ∀ (i : Fin inst.n) (v : ℝ), v ∈ (inst.dist i).support → v ≤ M) : ∀ (a : AdaptivePolicy inst.n) (hist : List (Fin inst.n × ℝ)), (∀ bv ∈ hist, bv.2 ≤ M) → expectedUtilityDUS.aux inst hist a ≤ M := by intro a induction a using AdaptivePolicy.rec with | stop => intro hist hh rw [show expectedUtilityDUS.aux inst hist (AdaptivePolicy.stop : AdaptivePolicy inst.n) = List.foldl (fun acc bv => max acc bv.2) 0 hist from rfl] exact le_trans (expected_utility_dus_le_opt_dus_foldl_max_le hist 0 M hh) (by rw [max_eq_right hM0]) | openBox b cont ih => intro hist hh rw [show expectedUtilityDUS.aux inst hist (AdaptivePolicy.openBox b cont) = ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v * expectedUtilityDUS.aux inst ((b, v) :: hist) (cont v) - inst.cost b from rfl] have hsum : ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v * expectedUtilityDUS.aux inst ((b, v) :: hist) (cont v) ≤ M := by have h1 : ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v * expectedUtilityDUS.aux inst ((b, v) :: hist) (cont v) ≤ ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v * M := by apply Finset.sum_le_sum intro v hv apply mul_le_mul_of_nonneg_left _ ((inst.dist b).prob_nonneg v hv) exact ih v ((b, v) :: hist) (fun bv hbv => by rcases List.mem_cons.mp hbv with hmem | hmem · rw [hmem]; exact hMv b v hv · exact hh bv hmem) calc ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v * expectedUtilityDUS.aux inst ((b, v) :: hist) (cont v) ≤ ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v * M := h1 _ = (∑ v ∈ (inst.dist b).support, (inst.dist b).prob v) * M := by rw [Finset.sum_mul] _ = M := by rw [(inst.dist b).sum_prob_one, one_mul] linarith [inst.cost_nonneg b]lemma expected_utility_dus_le_opt_dus_bddAbove (inst : PandoraDeadlineInstance) : BddAbove (Set.range fun π : AdaptivePolicy inst.n => expectedUtilityDUS inst π) := by refine ⟨∑ i : Fin inst.n, ∑ v ∈ (inst.dist i).support, v, ?_⟩ rintro _ ⟨π, rfl⟩ apply expected_utility_dus_le_opt_dus_aux_bound inst _ ?_ ?_ π [] (by simp) · exact Finset.sum_nonneg fun i _ => Finset.sum_nonneg fun v hv => (inst.dist i).val_nonneg v hv · intro i v hv refine le_trans (Finset.single_le_sum (f := fun v => v) (fun v hv => (inst.dist i).val_nonneg v hv) hv) ?_ exact Finset.single_le_sum (f := fun i => ∑ v ∈ (inst.dist i).support, v) (fun i _ => Finset.sum_nonneg fun v hv => (inst.dist i).val_nonneg v hv) (Finset.mem_univ i)/-- For any Pandora's problem instance with deadlines and any valid adaptive policy, its expected utility under deferred-until-stopping commitment is at most optDUS. -/theorem expected_utility_dus_le_opt_dus (inst : PandoraDeadlineInstance) (π : AdaptivePolicy inst.n) (hπ : IsValidPolicy inst π) : expectedUtilityDUS inst π ≤ optDUS inst := by have hbdd : BddAbove (Set.range fun π : AdaptivePolicy inst.n => ⨆ (_ : IsValidPolicy inst π), expectedUtilityDUS inst π) := by refine BddAbove.range_iSup_of_iUnion_range ?_ obtain ⟨B, hB⟩ := expected_utility_dus_le_opt_dus_bddAbove inst refine ⟨B, ?_⟩ intro x hx simp only [Set.mem_iUnion, Set.mem_range] at hx obtain ⟨π', -, rfl⟩ := hx exact hB (Set.mem_range_self π') unfold optDUS have h1 : expectedUtilityDUS inst π ≤ ⨆ (_ : IsValidPolicy inst π), expectedUtilityDUS inst π := by exact le_ciSup ⟨expectedUtilityDUS inst π, by rintro _ ⟨_, rfl⟩; exact le_rfl⟩ hπ have h2 : (⨆ (_ : IsValidPolicy inst π), expectedUtilityDUS inst π) ≤ ⨆ (π' : AdaptivePolicy inst.n), ⨆ (_ : IsValidPolicy inst π'), expectedUtilityDUS inst π' := by exact le_ciSup hbdd π exact le_trans h1 h2