optDP
For resource weights w : Fin n → ℝ, fuel : ℕ, available resources S : Finset (Fin n), and arrival states arrs : Fin m → OfflineArrival n, optDP is the dynamic programming value function: 0 when fuel is 0, and otherwise the maximum of 0 and the supremum over valid probes of arrival t and available resource i of p * (w i + optDP w fuel (S.erase i) arrs_succ) + (1 - p) * optDP w fuel S arrs_fail.
Statement
noncomputable def optDP {n m : ℕ} (w : Fin n → ℝ) : ℕ → Finset (Fin n) → (Fin m → OfflineArrival n) → ℝ
- Defined in
- scout/2611-03598-online-matching-with-arbitrary-stochastic-rewards.md:420
- Verified
- 04 Nov 2026
- Axioms
- none listed
- Built on 2
- OMSRArrivalAn arrival in online bipartite matching with stochastic rewards and patience facing n offline resources, consisting of a patience budget…
- OfflineArrivalThe state of an arrival in the offline benchmark, tracking its arrival data, the set of resources already probed for it, and whether it…
- Used by 3
- 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…
- offlineOptValueThe expected reward of the adaptive offline benchmark OPT on a list of arrivals arrs with resource weights w, defined by running optDP…
Read back from the Lean
optDP is a noncomputable function that defines the optimal dynamic programming value for a stochastic matching / probing problem with n items and m arrivals.
Given:
- (implicit) natural numbers n and m,
- a weight function w : Fin n → ℝ on items,
- a recursion bound fuel : ℕ,
- a set of available items S : Finset (Fin n),
- an arrival state function arrs : Fin m → OfflineArrival n,
optDP w fuel S arrs returns a real number defined recursively on fuel:
1. Base case (fuel = 0): returns 0.
2. Recursive step (fuel + 1, S, arrs):
Returns max 0 continue_val, where continue_val is the supremum (⨆) over all arrivals t : Fin m and items i : Fin n satisfying:
- i ∈ S (item i is currently available),
- ¬ (arrs t).matched (arrival t is not yet matched),
- i ∉ (arrs t).probed (item i has not already been probed by arrival t), and
- (arrs t).probed.card < (arrs t).arrival.patience (the number of items arrival t has probed is strictly less than its patience parameter),
of the expected reward of probing item i for arrival t:
p * (w i + optDP w fuel (S.erase i) arrs_succ) + (1 - p) * optDP w fuel S arrs_fail
where:
- p = (arrs t).arrival.prob i,
- arrs_succ : Fin m → OfflineArrival n is the function identical to arrs except at t, where (arrs t).matched is set to true,
- arrs_fail : Fin m → OfflineArrival n is the function identical to arrs except at t, where i is inserted into (arrs t).probed.
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
/-- Dynamic programming value of the adaptive offline benchmark. -/ noncomputable def optDP {n m : ℕ} (w : Fin n → ℝ) : ℕ → Finset (Fin n) → (Fin m → OfflineArrival n) → ℝ | 0, _, _ => 0 | fuel + 1, S, arrs => let continue_val := ⨆ (t : Fin m) (i : Fin n) (_ : i ∈ S ∧ ¬ (arrs t).matched ∧ i ∉ (arrs t).probed ∧ (arrs t).probed.card < (arrs t).arrival.patience), let p := (arrs t).arrival.prob i let arrs_succ : Fin m → OfflineArrival n := fun j => if j = t then { (arrs t) with matched := true } else arrs j let arrs_fail : Fin m → OfflineArrival n := fun j => if j = t then { (arrs t) with probed := insert i (arrs t).probed } else arrs j p * (w i + optDP w fuel (S.erase i) arrs_succ) + (1 - p) * optDP w fuel S arrs_fail max 0 continue_val