optDTD
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.nunder 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…
- expectedUtilityDTDThe expected net utility of an adaptive policy
- Used by 2
- opt_dtd_le_opt_dusFor every Pandora's problem instance with deadlines
inst : PandoraDeadlineInstance, the optimal expected utility under… - op182_deferred_to_deadline_beyond_half_self_benchmarkOpen Problem OP-182 against the deferred-to-deadline benchmark: there exists a constant
c > 1/2such that for every Pandora's problem…
- opt_dtd_le_opt_dusFor every Pandora's problem instance with deadlines
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 π