Feature-based Dynamic Matching in the Dark
Author:
Preprint
- 11 June 2026
- preprint
- Published by Elsevier in SSRN Electronic Journal
Abstract
We study a distribution-agnostic variant of the feature-based dynamic matching problem, where a set of supply units must be matched immediately and irrevocably to sequentially arriving demand units. Both sides are drawn i.i.d. from possibly different distributions over high-dimensional feature vectors, and the value of a match is a function of the two vectors. We measure performance by regret, the additive loss relative to the limiting hindsight-optimal match value. State-of-the-art algorithms for this problem require accurate knowledge of the demand distribution; we show that under model misspecification their performance can be highly sub-optimal. We develop ROAR, a completely distribution-agnostic algorithm that uses only the realized demand stream itself to make forward-looking assignment decisions. ROAR requires neither knowledge of the demand distribution nor any historical demand traces. We prove an exact identity expressing the average match value under ROAR as a folded average of hindsight-optimal values. As a consequence, ROAR obtains the same near-optimal regret scalings as the state-of-the-art algorithms that know the demand distribution exactly, across broad classes of quality functions and distributions.Keywords
This publication has 26 references indexed in Scilit:
- Dynamic Matching: Characterizing and Achieving Constant RegretManagement Science, 2024
- Constant Regret Primal-Dual Policy for Multi-way Dynamic Matching2023
- The Bayesian Prophet: A Low-Regret Framework for Online Decision MakingManagement Science, 2021
- A Re-Solving Heuristic with Uniformly Bounded Loss for Network Revenue ManagementManagement Science, 2020
- On Optimal Matching of Gaussian SamplesJournal of Mathematical Sciences, 2019
- Online Stochastic Matching: New Algorithms with Better BoundsMathematics of Operations Research, 2014
- Online Stochastic Matching: Online Actions Based on Offline StatisticsMathematics of Operations Research, 2012
- Online Stochastic Weighted Matching: Improved Approximation Algorithms2011
- Online Stochastic Matching: Beating 1-1/e2009
- On optimal matchingsCombinatorica, 1984