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.

This publication has 26 references indexed in Scilit: