AFTD Auto-Formalizing Theoretical Domains

optDTD

def

The optimal expected net utility optDTD inst under deferred-to-deadline commitment for a Pandora's problem instance with deadlines inst : PandoraDeadlineInstance, defined as the supremum of expectedUtilityDTD inst π over all valid adaptive policies π : AdaptivePolicy inst.n satisfying IsValidPolicy inst π.

Statement

noncomputable def optDTD (inst : PandoraDeadlineInstance) : ℝ
Defined in
arXiv:2610.13775 Sec. 2.1
Verified
18 Oct 2026
Axioms
none listed
Built on 4
  • expectedUtilityDTDThe expected net utility of an adaptive policy π : AdaptivePolicy inst.n under deferred-to-deadline 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.
  • PandoraDeadlineInstanceAn instance of Pandora's problem with deadlines consisting of n boxes, each with a non-negative opening cost, a positive integer deadline,…
  • 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…
Used by 2

Read back from the Lean

optDTD inst defines the optimal expected utility (as a real number) for a given instance inst : PandoraDeadlineInstance of Pandora's Box with deadlines. It is defined as the supremum (⨆) over all adaptive policies π : AdaptivePolicy inst.n satisfying IsValidPolicy inst π of the expected utility expectedUtilityDTD inst π. Specifically: 1. **Instance (PandoraDeadlineInstance)**: - n : ℕ: the number of boxes, indexed by Fin n. - cost : Fin n → ℝ: a non-negative inspection cost for each box (0 ≤ cost i). - deadline : Fin n → ℕ: a strictly positive deadline for each box (1 ≤ deadline i). - dist : Fin n → DiscreteDist: a discrete probability distribution for each box, having finite support in $[0, \infty)$ with probabilities summing to 1. 2. **Policy (AdaptivePolicy inst.n)**: An inductive decision tree where at each step the agent either: - stop: stops opening boxes. - openBox b cont: opens box b : Fin inst.n, observes a value v : ℝ, and proceeds according to a continuation policy cont v : AdaptivePolicy inst.n. 3. **Validity (IsValidPolicy inst π)**: A policy π is valid (starting from an empty list of opened boxes) if along every execution path: - Stopping (stop) is always valid. - Opening box b after having already opened the sequence opened requires: 1. b ∉ opened (no box is opened more than once); 2. opened.length + 1 ≤ inst.deadline b (box b is opened at or before its deadline); 3. For every value v in the support of inst.dist b, the continuation policy cont v is valid with b added to opened. 4. **Expected Utility (expectedUtilityDTD inst π)**: Computed recursively starting with an empty history: - At stop with history of opened box-value pairs of total length t: the terminal payoff is the maximum value observed among all boxes b in the history whose deadline satisfies t ≤ inst.deadline b, or 0 if no such box exists. - At openBox b cont: the expected utility is the expectation (weighted by (inst.dist b).prob v over v ∈ (inst.dist b).support) of the utility of cont v with (b, v) prepended to the history, minus inst.cost b. 5. **optDTD inst**: The supremum over all valid policies π of expectedUtilityDTD inst π.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- Optimal expected net utility over all valid adaptive policies under deferred-to-deadline commitment. -/
noncomputable def optDTD (inst : PandoraDeadlineInstance) : ℝ := ⨆ (π : AdaptivePolicy inst.n) (_ : IsValidPolicy inst π), expectedUtilityDTD inst π
See it in the graphDiscuss this resultChallenge it