AFTD Auto-Formalizing Theoretical Domains

pandora_adaptive_surplus_upper_bound

theoremverified

Lemma 1: for reservation values r and any threshold t >= 0, every valid adaptive policy has expected DUS utility at most t plus the total capped surplus of some deadline-feasible set.

Statement

theorem pandora_adaptive_surplus_upper_bound (inst : PandoraDeadlineInstance)
    (r : Fin inst.n → ℝ) (hr : pandora_is_reservation inst r) (t : ℝ) (ht : 0 ≤ t)
    (π : AdaptivePolicy inst.n) (hπ : IsValidPolicy inst π) :
    ∃ S : Finset (Fin inst.n), pandora_deadline_feasible inst S ∧
      expectedUtilityDUS inst π ≤ t + ∑ i ∈ S, pandora_capped_surplus inst r i t
Source
Helper for op184_partially_adaptive_half_approximation: arXiv:2610.13775 Section 3, Lemma 1 (adaptive-surplus upper bound)
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 11
  • 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…
  • 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.
  • IsPartiallyAdaptiveA search policy π : AdaptivePolicy n for Pandora's problem is partially adaptive if there exists a predetermined ordered list of boxes…
  • expectedUtilityDUSThe expected net utility of an adaptive policy π : AdaptivePolicy inst.n under deferred-until-stopping commitment on a Pandora's problem…
  • pandora_is_reservationr is a vector of reservation values: for every box i, the expected excess E[(v_i - r_i)^+] of its value over r_i equals its opening cost…
  • pandora_capped_surplusThe reservation-capped threshold surplus of box i at threshold t: w_i(t) = E[(min(v_i, r_i) - t)^+].
  • pandora_deadline_feasibleA set S of boxes is deadline-feasible if for every j at most j of its boxes have deadline at most j (equivalently, by Lemma 2, its boxes…
  • IsValidPolicyAuxA policy execution is valid if it never re-opens an already opened box, respects the deadline of each opened box, and remains valid on all…
  • supportThe support $\mathrm{supp}(p) \subseteq \mathrm{Fin}\,n$ consists of coordinates where $p(i) \neq I$; the weight is…

The proof, explained

The proof establishes an upper bound on the expected utility of any valid adaptive policy π by analyzing an intermediate quantity, the policy's expected opened capped surplus W(π). First, by structural induction on π, the expected utility from any history is bounded by t, plus the realized capped and excess surplus in the history, plus W(π); the reservation value condition E[(v - r(b))⁺] = cost(b) cancels the box opening cost against the expected excess reward at each step. Second, a separate structural induction on π bounds W(π) by the total capped surplus of a single deadline-feasible set of boxes S, constructed along the worst-case path that maximizes continuation surplus. Specializing both bounds to an empty initial history completes the proof.

  1. Folding the maximum over a list of pairs leaves the accumulator bounded by A, provided both the initial accumulator and all second components in the list are bounded by A.

    We proceed by structural induction on the list `h`. The base case `h = []` holds immediately since the initial accumulator satisfies `acc ≤ A`. In the inductive step `h = a :: h'`, the updated accumulator is `max acc a.2`. Because `acc ≤ A` and `a.2 ≤ A`, their maximum is bounded by `A` (`max_le`), so the inductive hypothesis applies to the tail `h'`.

    lines 12–18

    uses List.foldl_cons, max_le

      intro h
      induction h with
      | nil => intro acc hacc _; simpa using hacc
      | cons a h ih =>
        intro acc hacc hall
        simp only [List.foldl_cons]
        exact ih _ (max_le hacc (hall a (by simp))) (fun bv hbv => hall bv (by simp [hbv]))
  2. When the policy terminates (the `stop` case), the maximum value observed in the history is bounded by t plus the history's total capped and excess surplus.

    By structural induction on `π`. When `π = stop`, utility is computed by folding `max` over the history with initial accumulator 0, and the policy opens no further boxes (surplus 0). Each summand in the history surplus is a sum of two maximums with 0, hence non-negative (`add_nonneg`, `le_max_right`), which implies the sum over the history is non-negative (`List.sum_nonneg`) and bounds 0 ≤ t + sum. Furthermore, for each pair `(b, v)` in the history, a case split on whether `v ≤ r(b)` or `r(b) ≤ v` (`le_total`, `min_eq_left`, `min_eq_right`, `le_max_left`, `le_max_right`) proves `v ≤ t + (min v (r b) - t)⁺ + (v - r b)⁺`. As each term is non-negative, this single term is at most the total history sum (`List.single_le_sum`). Applying `pandora_adaptive_surplus_upper_bound_foldl` bounds the stopping utility.

    lines 26–52

    uses add_zero, List.mem_map, add_nonneg, le_max_right, pandora_adaptive_surplus_upper_bound_foldl, List.sum_nonneg, List.single_le_sum, le_total, min_eq_left, le_max_left, min_eq_right

      intro π
      induction π with
      | stop =>
        intro hist
        simp only [expectedUtilityDUS.aux, pandora_adaptive_surplus_upper_bound_opened, add_zero]
        have hnn : ∀ x ∈ hist.map (fun bv => max (min bv.2 (r bv.1) - t) 0 + max (bv.2 - r bv.1) 0),
            0 ≤ x := by
          intro x hx
          simp only [List.mem_map] at hx
          obtain ⟨bv, -, rfl⟩ := hx
          exact add_nonneg (le_max_right _ _) (le_max_right _ _)
        apply pandora_adaptive_surplus_upper_bound_foldl
        · have := List.sum_nonneg hnn
          linarith
        · intro bv hbv
          have h1 := List.single_le_sum hnn _ (List.mem_map.2 ⟨bv, hbv, rfl⟩)
          have h2 : bv.2 ≤ t + (max (min bv.2 (r bv.1) - t) 0 + max (bv.2 - r bv.1) 0) := by
            rcases le_total bv.2 (r bv.1) with h | h
            · rw [min_eq_left h]
              have := le_max_left (bv.2 - t) 0
              have := le_max_right (bv.2 - r bv.1) 0
              linarith
            · rw [min_eq_right h]
              have := le_max_left (r bv.1 - t) 0
              have := le_max_left (bv.2 - r bv.1) 0
              linarith
          linarith
  3. In the `openBox` case, the expected utility of the policy is bounded by the expectation over outcomes of the induction hypothesis applied to each continuation.

    For `π = openBox b cont`, the utility is the expected utility of `cont v` with `(b, v)` prepended to the history, minus the opening cost `inst.cost b`. Applying the inductive hypothesis to each outcome `v` with the extended history `(b, v) :: hist`, simplifying the prepended history sum via `List.map_cons` and `List.sum_cons`, and summing over the distribution using `Finset.sum_le_sum` and non-negativity of probabilities (`mul_le_mul_of_nonneg_left`) establishes the intermediate inequality `hle`.

    lines 53–66

    uses Finset.sum_le_sum, mul_le_mul_of_nonneg_left, List.map_cons, List.sum_cons

      | openBox b cont ih =>
        intro hist
        simp only [expectedUtilityDUS.aux, pandora_adaptive_surplus_upper_bound_opened]
        have hle : ∑ 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 * (t +
              (hist.map (fun bv => max (min bv.2 (r bv.1) - t) 0 + max (bv.2 - r bv.1) 0)).sum +
              (max (min v (r b) - t) 0 + max (v - r b) 0) +
              pandora_adaptive_surplus_upper_bound_opened inst r t (cont v)) := by
          apply Finset.sum_le_sum
          intro v hv
          apply mul_le_mul_of_nonneg_left _ ((inst.dist b).prob_nonneg v hv)
          have := ih v ((b, v) :: hist)
          simp only [List.map_cons, List.sum_cons] at this
          linarith
  4. The expected continuation bound simplifies to t plus the history surplus, the capped surplus of box b, and the expected opened surplus of the policy.

    We evaluate the expectation by expanding `pandora_capped_surplus` and distributing sums (`Finset.sum_add_distrib`, `Finset.mul_sum`). Under the reservation value definition `hr b`, the expected excess reward `(v - r b)⁺` equals `inst.cost b`, exactly canceling the opening cost. The probabilities sum to 1, allowing the history sum term to factor out with coefficient 1. Linear arithmetic and ring rewriting (`Finset.sum_congr`) complete the inductive step.

    lines 67–81

    uses Finset.mul_sum, Finset.sum_add_distrib, Finset.sum_congr

        have hsum : ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v * (t +
              (hist.map (fun bv => max (min bv.2 (r bv.1) - t) 0 + max (bv.2 - r bv.1) 0)).sum +
              (max (min v (r b) - t) 0 + max (v - r b) 0) +
              pandora_adaptive_surplus_upper_bound_opened inst r t (cont v)) =
            (t + (hist.map (fun bv => max (min bv.2 (r bv.1) - t) 0 + max (bv.2 - r bv.1) 0)).sum) *
                ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v +
              pandora_capped_surplus inst r b t + inst.cost b +
              ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v * pandora_adaptive_surplus_upper_bound_opened inst r t (cont v) := by
          rw [← hr b]
          simp only [pandora_capped_surplus, Finset.mul_sum]
          rw [← Finset.sum_add_distrib, ← Finset.sum_add_distrib, ← Finset.sum_add_distrib]
          refine Finset.sum_congr rfl (fun v _ => ?_)
          ring
        rw [(inst.dist b).sum_prob_one] at hsum
        linarith
  5. The stopping policy satisfies the path surplus bound using the empty set of boxes.

    By induction on `π`. For `π = stop`, we choose `S = ∅`. The empty set is trivially disjoint from `O`, has 0 elements with deadline ≤ j (satisfying `0 ≤ j - O.length`), and has total capped surplus 0, matching the opened surplus of `stop`.

    lines 90–94

      intro π
      induction π with
      | stop =>
        intro O _
        exact ⟨∅, by simp, by simp, by simp [pandora_adaptive_surplus_upper_bound_opened]⟩
  6. For `openBox b cont`, there exists an outcome maximizing continuation surplus, from which the inductive hypothesis produces a valid box set for the continuation.

    From validity of `openBox b cont`, we have `b ∉ O`, `O.length + 1 ≤ inst.deadline b`, and each continuation `cont v` is valid given `b :: O`. Because the support of the distribution on box `b` is non-empty (`Finset.nonempty_iff_ne_empty`), there exists an outcome `v0` maximizing the continuation surplus (`Finset.exists_max_image`). Applying the inductive hypothesis to `cont v0` with opened list `b :: O` yields a set `S` disjoint from `b :: O` satisfying the deadline constraints relative to `b :: O`, which in particular implies `b ∉ S`.

    lines 95–109

    uses Finset.nonempty_iff_ne_empty, Finset.exists_max_image

      | openBox b cont ih =>
        intro O hv
        obtain ⟨hbO, hdl, hcont⟩ := hv
        have hdl' : O.length + 1 ≤ inst.deadline b := hdl
        set D := inst.dist b
        have hne : D.support.Nonempty := by
          rw [Finset.nonempty_iff_ne_empty]
          intro he
          have := D.sum_prob_one
          rw [he, Finset.sum_empty] at this
          norm_num at this
        obtain ⟨v0, hv0, hmax⟩ := Finset.exists_max_image D.support
          (fun v => pandora_adaptive_surplus_upper_bound_opened inst r t (cont v)) hne
        obtain ⟨S, hSO, hSf, hSW⟩ := ih v0 (b :: O) (hcont v0 hv0)
        have hbS : b ∉ S := fun h => hSO b h (by simp)
  7. The augmented set {b} ∪ S is disjoint from O and satisfies the deadline constraints relative to O. automation

    Any element in `insert b S` is either `b` (not in `O` by policy validity) or in `S` (disjoint from `b :: O`, hence not in `O` by `List.mem_cons_of_mem`). For any deadline `j`, filtering `insert b S` splits on whether `inst.deadline b ≤ j` (`Finset.filter_insert`). If `deadline b ≤ j`, using `O.length + 1 ≤ deadline b ≤ j` and `Finset.card_insert_le`, the count is at most `1 + (j - (O.length + 1)) = j - O.length`. If `deadline b > j`, `b` is omitted from the filter and the bound holds directly. Both arithmetic cases are resolved by `omega`.

    lines 110–123

    uses Finset.mem_insert, List.mem_cons_of_mem, Finset.filter_insert, Finset.card_insert_le

        refine ⟨insert b S, ?_, ?_, ?_⟩
        · intro i hi
          rw [Finset.mem_insert] at hi
          rcases hi with rfl | hi
          · exact hbO
          · exact fun h => hSO i hi (List.mem_cons_of_mem _ h)
        · intro j
          have h1 := hSf j
          simp only [List.length_cons] at h1
          rw [Finset.filter_insert]
          split_ifs with hb
          · have := Finset.card_insert_le b (S.filter (fun i => inst.deadline i ≤ j))
            omega
          · omega
  8. The expected opened surplus of `openBox b cont` is bounded by the total capped surplus of {b} ∪ S.

    The opened surplus of `openBox b cont` is the capped surplus of `b` plus the expected continuation surplus. Because `v0` maximizes continuation surplus across all outcomes in the support, the expectation is bounded by the surplus at `v0` (`Finset.sum_le_sum`, `mul_le_mul_of_nonneg_left`, `Finset.sum_mul`). The induction hypothesis bounds this by the sum of capped surpluses over `S`. Since `b ∉ S`, adding the capped surplus of `b` yields the sum over `insert b S` (`Finset.sum_insert`).

    lines 124–132

    uses Finset.sum_insert, Finset.sum_le_sum, mul_le_mul_of_nonneg_left, Finset.sum_mul

        · simp only [pandora_adaptive_surplus_upper_bound_opened]
          rw [Finset.sum_insert hbS]
          have : ∑ v ∈ D.support, D.prob v *
                pandora_adaptive_surplus_upper_bound_opened inst r t (cont v) ≤
              ∑ v ∈ D.support, D.prob v *
                pandora_adaptive_surplus_upper_bound_opened inst r t (cont v0) :=
            Finset.sum_le_sum (fun v hv => mul_le_mul_of_nonneg_left (hmax v hv) (D.prob_nonneg v hv))
          rw [← Finset.sum_mul, D.sum_prob_one, one_mul] at this
          linarith
  9. Every valid adaptive policy has expected DUS utility bounded by t plus the capped surplus of some deadline-feasible set.

    Applying `pandora_adaptive_surplus_upper_bound_path` with an empty opened list `O = []` yields a set `S` satisfying `∀ j, card ≤ j`, which is the definition of deadline feasibility, bounding the policy's opened surplus. Specializing `pandora_adaptive_surplus_upper_bound_utility` with an empty history `hist = []` eliminates the history sum (`List.map_nil`, `List.sum_nil`, `add_zero`). Unfolding `expectedUtilityDUS` and combining the two inequalities via `linarith` yields the final bound.

    lines 139–144

    uses pandora_adaptive_surplus_upper_bound_path, pandora_adaptive_surplus_upper_bound_utility, List.map_nil, List.sum_nil, add_zero

      obtain ⟨S, -, hSf, hSW⟩ := pandora_adaptive_surplus_upper_bound_path inst r t π [] hπ
      refine ⟨S, fun j => by simpa using hSf j, ?_⟩
      have := pandora_adaptive_surplus_upper_bound_utility inst r hr t ht π []
      simp only [List.map_nil, List.sum_nil, add_zero] at this
      unfold expectedUtilityDUS
      linarith
add_zero
Adding zero to any element leaves it unchanged.
add_nonneg
The sum of two non-negative real numbers is non-negative.
le_max_right
Any element b is less than or equal to max a b.
le_max_left
Any element a is less than or equal to max a b.
le_total
Any two real numbers are comparable: either a ≤ b or b ≤ a.
min_eq_left
If a ≤ b, then min a b = a.
min_eq_right
If b ≤ a, then min a b = b.
max_le
If both a ≤ c and b ≤ c, then max a b ≤ c.
List.foldl_cons
Folding over a non-empty list a :: l with accumulator b equals folding over l with updated accumulator f b a.
List.mem_map
An element belongs to the image of a list under f if and only if it is the image of some element in the list.
List.sum_nonneg
If every element in a list is non-negative, then the sum of the list is non-negative.
List.single_le_sum
In a list of non-negative elements, each individual element is at most the sum of the list.
List.map_cons
Mapping a function over a non-empty list a :: l yields f a prepended to the mapped tail.
List.sum_cons
The sum of a non-empty list a :: l is a plus the sum of l.
List.map_nil
Mapping a function over the empty list produces the empty list.
List.sum_nil
The sum of the empty list is zero.
List.mem_cons_of_mem
If an element belongs to l, it belongs to y :: l.
Finset.sum_le_sum
If f(i) ≤ g(i) for all elements i in a finite set 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 by a non-negative scalar a preserves the inequality: a * b ≤ a * c.
Finset.mul_sum
Multiplication distributes over finite sums from the left: a * ∑ i ∈ s, f i = ∑ i ∈ s, a * f i.
Finset.sum_mul
Multiplication distributes over finite sums from the right: (∑ i ∈ s, f i) * a = ∑ i ∈ s, f i * a.
Finset.sum_add_distrib
The sum of a pointwise sum of two functions over a finite set equals the sum of their individual sums.
Finset.sum_congr
Two finite sums are equal if their index sets are identical and their summands agree on every element.
Finset.nonempty_iff_ne_empty
A finite set is non-empty if and only if it is not the empty set.
Finset.exists_max_image
Any non-empty finite set contains an element maximizing a given real-valued function.
Finset.mem_insert
An element belongs to insert b s if and only if it equals b or belongs to s.
Finset.filter_insert
Filtering insert a s by predicate p yields insert a (filter p s) if p a holds, and filter p s otherwise.
Finset.card_insert_le
Inserting an element into a finite set increases its cardinality by at most 1.
Finset.sum_insert
If a is not in s, the sum of f over insert a s equals f a plus the sum of f over s.
pandora_adaptive_surplus_upper_bound_foldl
If an initial accumulator and the second components of all pairs in list h are bounded by A, folding max over h leaves the accumulator bounded by A.
pandora_adaptive_surplus_upper_bound_utility
For reservation values r and t ≥ 0, the expected utility of policy π from history hist is bounded by t plus the realized capped and excess surplus in hist and the opened surplus of π.
pandora_adaptive_surplus_upper_bound_path
For any valid policy π with opened boxes O, there exists a set S disjoint from O and deadline-feasible relative to O bounding the expected opened surplus of π.

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

/-- Expected total capped surplus of the boxes a policy opens. -/noncomputable def pandora_adaptive_surplus_upper_bound_opened (inst : PandoraDeadlineInstance)    (r : Fin inst.n → ℝ) (t : ℝ) : AdaptivePolicy inst.n → ℝ  | .stop => 0  | .openBox b cont => pandora_capped_surplus inst r b t +      ∑ v ∈ (inst.dist b).support,        (inst.dist b).prob v * pandora_adaptive_surplus_upper_bound_opened inst r t (cont v)theorem pandora_adaptive_surplus_upper_bound_foldl {α : Type*} (A : ℝ) :    ∀ (h : List (α × ℝ)) (acc : ℝ), acc ≤ A → (∀ bv ∈ h, bv.2 ≤ A) →      h.foldl (fun acc bv => max acc bv.2) acc ≤ A := by  intro h  induction h with  | nil => intro acc hacc _; simpa using hacc  | cons a h ih =>    intro acc hacc hall    simp only [List.foldl_cons]    exact ih _ (max_le hacc (hall a (by simp))) (fun bv hbv => hall bv (by simp [hbv]))theorem pandora_adaptive_surplus_upper_bound_utility (inst : PandoraDeadlineInstance)    (r : Fin inst.n → ℝ) (hr : pandora_is_reservation inst r) (t : ℝ) (ht : 0 ≤ t) :    ∀ (π : AdaptivePolicy inst.n) (hist : List (Fin inst.n × ℝ)),      expectedUtilityDUS.aux inst hist π ≤ t +        (hist.map (fun bv => max (min bv.2 (r bv.1) - t) 0 + max (bv.2 - r bv.1) 0)).sum +        pandora_adaptive_surplus_upper_bound_opened inst r t π := by  intro π  induction π with  | stop =>    intro hist    simp only [expectedUtilityDUS.aux, pandora_adaptive_surplus_upper_bound_opened, add_zero]    have hnn : ∀ x ∈ hist.map (fun bv => max (min bv.2 (r bv.1) - t) 0 + max (bv.2 - r bv.1) 0),        0 ≤ x := by      intro x hx      simp only [List.mem_map] at hx      obtain ⟨bv, -, rfl⟩ := hx      exact add_nonneg (le_max_right _ _) (le_max_right _ _)    apply pandora_adaptive_surplus_upper_bound_foldl    · have := List.sum_nonneg hnn      linarith    · intro bv hbv      have h1 := List.single_le_sum hnn _ (List.mem_map.2 ⟨bv, hbv, rfl⟩)      have h2 : bv.2 ≤ t + (max (min bv.2 (r bv.1) - t) 0 + max (bv.2 - r bv.1) 0) := by        rcases le_total bv.2 (r bv.1) with h | h        · rw [min_eq_left h]          have := le_max_left (bv.2 - t) 0          have := le_max_right (bv.2 - r bv.1) 0          linarith        · rw [min_eq_right h]          have := le_max_left (r bv.1 - t) 0          have := le_max_left (bv.2 - r bv.1) 0          linarith      linarith  | openBox b cont ih =>    intro hist    simp only [expectedUtilityDUS.aux, pandora_adaptive_surplus_upper_bound_opened]    have hle : ∑ 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 * (t +          (hist.map (fun bv => max (min bv.2 (r bv.1) - t) 0 + max (bv.2 - r bv.1) 0)).sum +          (max (min v (r b) - t) 0 + max (v - r b) 0) +          pandora_adaptive_surplus_upper_bound_opened inst r t (cont v)) := by      apply Finset.sum_le_sum      intro v hv      apply mul_le_mul_of_nonneg_left _ ((inst.dist b).prob_nonneg v hv)      have := ih v ((b, v) :: hist)      simp only [List.map_cons, List.sum_cons] at this      linarith    have hsum : ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v * (t +          (hist.map (fun bv => max (min bv.2 (r bv.1) - t) 0 + max (bv.2 - r bv.1) 0)).sum +          (max (min v (r b) - t) 0 + max (v - r b) 0) +          pandora_adaptive_surplus_upper_bound_opened inst r t (cont v)) =        (t + (hist.map (fun bv => max (min bv.2 (r bv.1) - t) 0 + max (bv.2 - r bv.1) 0)).sum) *            ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v +          pandora_capped_surplus inst r b t + inst.cost b +          ∑ v ∈ (inst.dist b).support, (inst.dist b).prob v * pandora_adaptive_surplus_upper_bound_opened inst r t (cont v) := by      rw [← hr b]      simp only [pandora_capped_surplus, Finset.mul_sum]      rw [← Finset.sum_add_distrib, ← Finset.sum_add_distrib, ← Finset.sum_add_distrib]      refine Finset.sum_congr rfl (fun v _ => ?_)      ring    rw [(inst.dist b).sum_prob_one] at hsum    linariththeorem pandora_adaptive_surplus_upper_bound_path (inst : PandoraDeadlineInstance)    (r : Fin inst.n → ℝ) (t : ℝ) :    ∀ (π : AdaptivePolicy inst.n) (O : List (Fin inst.n)), IsValidPolicyAux inst rfl O π →      ∃ S : Finset (Fin inst.n), (∀ i ∈ S, i ∉ O) ∧        (∀ j : ℕ, (S.filter (fun i => inst.deadline i ≤ j)).card ≤ j - O.length) ∧        pandora_adaptive_surplus_upper_bound_opened inst r t π ≤          ∑ i ∈ S, pandora_capped_surplus inst r i t := by  intro π  induction π with  | stop =>    intro O _    exact ⟨∅, by simp, by simp, by simp [pandora_adaptive_surplus_upper_bound_opened]⟩  | openBox b cont ih =>    intro O hv    obtain ⟨hbO, hdl, hcont⟩ := hv    have hdl' : O.length + 1 ≤ inst.deadline b := hdl    set D := inst.dist b    have hne : D.support.Nonempty := by      rw [Finset.nonempty_iff_ne_empty]      intro he      have := D.sum_prob_one      rw [he, Finset.sum_empty] at this      norm_num at this    obtain ⟨v0, hv0, hmax⟩ := Finset.exists_max_image D.support      (fun v => pandora_adaptive_surplus_upper_bound_opened inst r t (cont v)) hne    obtain ⟨S, hSO, hSf, hSW⟩ := ih v0 (b :: O) (hcont v0 hv0)    have hbS : b ∉ S := fun h => hSO b h (by simp)    refine ⟨insert b S, ?_, ?_, ?_⟩    · intro i hi      rw [Finset.mem_insert] at hi      rcases hi with rfl | hi      · exact hbO      · exact fun h => hSO i hi (List.mem_cons_of_mem _ h)    · intro j      have h1 := hSf j      simp only [List.length_cons] at h1      rw [Finset.filter_insert]      split_ifs with hb      · have := Finset.card_insert_le b (S.filter (fun i => inst.deadline i ≤ j))        omega      · omega    · simp only [pandora_adaptive_surplus_upper_bound_opened]      rw [Finset.sum_insert hbS]      have : ∑ v ∈ D.support, D.prob v *            pandora_adaptive_surplus_upper_bound_opened inst r t (cont v) ≤          ∑ v ∈ D.support, D.prob v *            pandora_adaptive_surplus_upper_bound_opened inst r t (cont v0) :=        Finset.sum_le_sum (fun v hv => mul_le_mul_of_nonneg_left (hmax v hv) (D.prob_nonneg v hv))      rw [← Finset.sum_mul, D.sum_prob_one, one_mul] at this      linariththeorem pandora_adaptive_surplus_upper_bound (inst : PandoraDeadlineInstance)    (r : Fin inst.n → ℝ) (hr : pandora_is_reservation inst r) (t : ℝ) (ht : 0 ≤ t)    (π : AdaptivePolicy inst.n) (hπ : IsValidPolicy inst π) :    ∃ S : Finset (Fin inst.n), pandora_deadline_feasible inst S ∧      expectedUtilityDUS inst π ≤ t + ∑ i ∈ S, pandora_capped_surplus inst r i t := by  obtain ⟨S, -, hSf, hSW⟩ := pandora_adaptive_surplus_upper_bound_path inst r t π [] hπ  refine ⟨S, fun j => by simpa using hSf j, ?_⟩  have := pandora_adaptive_surplus_upper_bound_utility inst r hr t ht π []  simp only [List.map_nil, List.sum_nil, add_zero] at this  unfold expectedUtilityDUS  linarith
See it in the graphDiscuss this resultChallenge it