offlineOptValue
The expected reward of the adaptive offline benchmark OPT on a list of arrivals arrs with resource weights w, defined by running optDP with fuel equal to arrs.length * n starting from the full resource set univ and initial unprobed, unmatched arrival states.
Statement
noncomputable def offlineOptValue {n : ℕ} (w : Fin n → ℝ) (arrs : List (OMSRArrival n)) : ℝ
- Defined in
- scout/2611-03598-online-matching-with-arbitrary-stochastic-rewards.md:420
- Verified
- 04 Nov 2026
- Axioms
- none listed
- Built on 3
- optDPFor resource weights w : Fin n → ℝ, fuel : ℕ, available resources S : Finset (Fin n), and arrival states arrs : Fin m → OfflineArrival n,…
- OfflineArrivalThe state of an arrival in the offline benchmark, tracking its arrival data, the set of resources already probed for it, and whether it…
- 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…
- omsr_single_arrival_optimal_probeSeq_existsFor any resource weights w ≥ 0 and single arrival arr, there exists a valid probe sequence L from the full resource set univ whose probe…
Read back from the Lean
offlineOptValue defines a real number representing the offline optimal expected value for an online matching with stochastic rewards (OMSR) problem. Given an implicit dimension n : ℕ, a weight vector w : Fin n → ℝ on items Fin n, and a list arrs : List (OMSRArrival n) of arrival specifications, it sets m = arrs.length and initializes an array init_arrs : Fin m → OfflineArrival n where each index idx : Fin m has arrival := arrs.get idx, probed := ∅, and matched := false. It then evaluates the dynamic program optDP w (m * n) Finset.univ init_arrs.
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 the adaptive offline benchmark OPT. -/ noncomputable def offlineOptValue {n : ℕ} (w : Fin n → ℝ) (arrs : List (OMSRArrival n)) : ℝ := let m := arrs.length let init_arrs : Fin m → OfflineArrival n := fun idx => { arrival := arrs.get idx, probed := ∅, matched := false } optDP w (m * n) Finset.univ init_arrs