AFTD Auto-Formalizing Theoretical Domains

onlinePolicyValue

def

The expected total reward of a deterministic online policy π on an arrival list arrs starting from available resources S with resource weights w, defined by folding probeValue along arrs.

Statement

def onlinePolicyValue {n : ℕ} (w : Fin n → ℝ)
    (π : OMSRArrival n → Finset (Fin n) → List (Fin n)) :
    List (OMSRArrival n) → Finset (Fin n) → ℝ
Defined in
scout/2611-03598-online-matching-with-arbitrary-stochastic-rewards.md:416
Verified
04 Nov 2026
Axioms
none listed
Built on 2
  • probeValueGiven arrival arr with success probabilities arr.prob, resource weights w, continuation value function V on subsets of resources, and…
  • OMSRArrivalAn arrival in online bipartite matching with stochastic rewards and patience facing n offline resources, consisting of a patience budget…
Used by 2
  • omsr_patience_single_arrival_optimalFor all n and all non-negative weights w, there exists a randomized online policy R for n resources such that on every arrival list arrs…
  • expectedOnlineValueThe expected total reward of a randomized online policy R on a list of arrivals arrs with weights w, defined as the integral over Ω of…

Read back from the Lean

onlinePolicyValue defines a function by recursion on a list of arrivals. Given a number of items n : ℕ, an item weight function w : Fin n → ℝ, and a policy π : OMSRArrival n → Finset (Fin n) → List (Fin n) (which maps an arrival and a set of available items to a sequence of items to probe), onlinePolicyValue w π takes a list of arrivals List (OMSRArrival n) and a set of available items S : Finset (Fin n) and returns a real number: 1. Base case: If the list of arrivals is empty [], it returns 0 for any set S. 2. Recursive step: If the list of arrivals is arr :: rest, it returns probeValue arr w (fun S' => onlinePolicyValue w π rest S') S (π arr S).

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

/-- Expected reward of a deterministic online policy on a list of arrivals. -/
def onlinePolicyValue {n : ℕ} (w : Fin n → ℝ)
    (π : OMSRArrival n → Finset (Fin n) → List (Fin n)) :
    List (OMSRArrival n) → Finset (Fin n) → ℝ
  | [], _ => 0
  | arr :: rest, S =>
    probeValue arr w (fun S' => onlinePolicyValue w π rest S') S (π arr S)
See it in the graphDiscuss this resultChallenge it