onlinePolicyValue
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)