AFTD Auto-Formalizing Theoretical Domains

IsValidPolicyAux

def

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_adaptive is false: The statement is false. IsValidPolicy only 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 policy AdaptivePolicy.stop satisfies…
  • 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)
See it in the graphDiscuss this resultChallenge it