IsValidPolicyAux
A 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 realization branches.
Statement
def IsValidPolicyAux {n : ℕ} (inst : PandoraDeadlineInstance) (hn : inst.n = n) (opened : List (Fin n)) : AdaptivePolicy n → Prop
- Defined in
- arXiv:2610.13775, Sec. 2.1
- Verified
- 18 Oct 2026
- Axioms
- none listed
- Built on 3
- 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…
- Used by 10
- two_box_pi01_validThe policy "open box 0, then box 1, then stop" is valid for the two-box instance.
- 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.
- two_box_dtd_le_oneUnder deferred-to-deadline commitment, every valid policy on the two-box instance gets expected utility at most 1.
- two_box_valid_stop_of_mem_oneIf a valid policy execution has box 1 in its already-opened list and at least one round has elapsed, then the remaining policy is
stop. - not_single_box_valid_is_partially_adaptiveThe statement
single_box_valid_is_partially_adaptiveis false: The statement is false.IsValidPolicyonly constrains the continuation… - two_box_dtd_after_box_zeroWith the history
[(0, 1)], any valid policy has deferred-to-deadline expected utility at most 1. - is_valid_policy_stopFor every Pandora's problem instance with deadlines
inst : PandoraDeadlineInstance, the policyAdaptivePolicy.stopsatisfies… - op184_partially_adaptive_half_approximationFor every Pandora's problem instance with deadlines
inst : PandoraDeadlineInstance, there exists a valid partially adaptive policy… - pandora_adaptive_surplus_upper_boundLemma 1: for reservation values r and any threshold t >= 0, every valid adaptive policy has expected DUS utility at most t plus the total…
- pandora_threshold_policy_validA threshold policy on a duplicate-free list whose j-th box has deadline at least j is a valid policy and is partially adaptive.
Read back from the Lean
A recursive predicate IsValidPolicyAux stating whether an adaptive policy p : AdaptivePolicy n is valid for a Pandora's box instance with deadlines inst : PandoraDeadlineInstance (where inst.n = n via hypothesis hn), given a list opened : List (Fin n) of boxes already opened.
The definition proceeds by structural recursion on p:
1. If p is AdaptivePolicy.stop: it is always valid (True).
2. If p is AdaptivePolicy.openBox b cont (opening box b : Fin n and then executing continuation policy cont v : AdaptivePolicy n depending on the observed value v : ℝ): it is valid if and only if all three of the following hold:
- b ∉ opened: box b has not already been opened.
- opened.length + 1 ≤ inst.deadline (hn ▸ b): the round at which box b is opened (namely, the count of previously opened boxes plus 1) does not exceed the deadline of box b.
- ∀ v ∈ (inst.dist (hn ▸ b)).support, IsValidPolicyAux inst hn (b :: opened) (cont v): for every reward value v in the support of the discrete distribution of box b, the continuation policy cont v is valid with b added to the list of opened boxes.
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
/-- Auxiliary validity condition ensuring deadlines and no re-opening along branches. -/ def IsValidPolicyAux {n : ℕ} (inst : PandoraDeadlineInstance) (hn : inst.n = n) (opened : List (Fin n)) : AdaptivePolicy n → Prop | .stop => True | .openBox b cont => b ∉ opened ∧ (opened.length + 1 ≤ inst.deadline (hn ▸ b)) ∧ ∀ v ∈ (inst.dist (hn ▸ b)).support, IsValidPolicyAux inst hn (b :: opened) (cont v)