AFTD Auto-Formalizing Theoretical Domains

expected_utility_dus_le_opt_dus

theoremverified

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 inst under deferred-until-stopping commitment for a Pandora's problem instance with deadlines…
  • expectedUtilityDUSThe expected net utility of an adaptive policy π : AdaptivePolicy inst.n under 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…
Used by 3

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.

  1. 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)$.

    lines 4–10

    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]
  2. 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$.

    lines 16–22

    uses le_trans, expected_utility_dus_le_opt_dus_foldl_max_le, max_eq_right

      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])
  3. 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$.

    lines 23–46

    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]
  4. 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$.

    lines 50–58

    uses expected_utility_dus_le_opt_dus_aux_bound, Finset.sum_nonneg, le_trans, Finset.single_le_sum, Finset.mem_univ

      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)
  5. 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.

    lines 64–72

    uses BddAbove.range_iSup_of_iUnion_range, expected_utility_dus_le_opt_dus_bddAbove, Set.mem_iUnion, Set.mem_range, Set.mem_range_self

      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 π')
  6. 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.

    lines 73–75

    uses le_ciSup, le_rfl

      unfold optDUS
      have h1 : expectedUtilityDUS inst π ≤ ⨆ (_ : IsValidPolicy inst π), expectedUtilityDUS inst π := by
        exact le_ciSup ⟨expectedUtilityDUS inst π, by rintro _ ⟨_, rfl⟩; exact le_rfl⟩ hπ
  7. 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)$.

    lines 76–79

    uses le_ciSup, le_trans

      have 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`.

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

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
See it in the graphDiscuss this resultChallenge it