Robust Online Matching with User Arrival Distribution Drift

Yu-Hang Zhou, Chen Liang, Nan Li, Cheng Yang, Shenghuo Zhu, Rong Jin

Introduction

Online matching is a fundamental component of the digital economy, particularly within display advertising. In a typical bipartite matching scenario, the system must assign arriving users (queries) to bidders (advertisers) in real-time to maximize revenue while respecting budget constraints. Traditional approaches generally categorize user behavior as either purely stochastic (predictable and stationary) or adversarial (worst-case). However, real-world traffic often exhibits "distribution drift"—patterns that are somewhat predictable but shift over time, such as the variance between weekday and weekend search behavior.

The Challenge of Distribution Drift

Standard stochastic models often fail when the underlying user distribution changes, leading to suboptimal resource allocation. Conversely, adversarial models tend to be overly pessimistic, sacrificing potential revenue for safety. The core difficulty lies in handling the "hybrid" nature of real-world data, where user arrivals are neither perfectly stable nor intentionally malicious.

Fluctuations in mean top-3 bids and candidate bidder numbers over 70 time intervals, demonstrating the significant distribution drift present in real-world advertising data.

As shown in the figure above, metrics such as bid intensity and competition levels fluctuate significantly across time intervals. A robust system must adapt to these shifts without overreacting to temporary noise.

The Robust Dynamic Learning Algorithm (RDLA)

To address these challenges, this paper introduces the Robust Dynamic Learning Algorithm (RDLA). RDLA leverages Distributionally Robust Optimization (DRO) to manage uncertainty. Instead of relying on a single empirical distribution from historical data, RDLA optimizes against an ambiguity set—a collection of potential distributions within a defined Kullback-Leibler (KL) divergence from the observed data.

The algorithm employs a Max-Min formulation, effectively playing a game against an imaginary adversary that selects the least favorable distribution from the ambiguity set. This approach results in more stable "dual variables" (internal opportunity costs for bidders). Furthermore, RDLA utilizes an Equal Period Updating scheme, ensuring that the model parameters are refreshed at regular intervals to capture the most recent trends, rather than relying on geometric intervals that may become stale.

Key Insights: The "Fall Sample" Filter

A significant advantage of the RDLA framework is its inherent ability to filter "Fall Samples"—queries characterized by unusually high bids or an abnormally high number of bidders. In a standard model, these outliers might skew the dual variables, leading to poor future performance.

Weight assignment across samples in the RDLA framework. The algorithm assigns lower weights to early high-bid 'Fall Samples' to prevent model overreaction.

The max-min optimization naturally assigns lower weights to these anomalous samples, as seen in the figure above. By discounting these spikes, the algorithm maintains a "drift-proof" model that focuses on sustainable trends rather than transient noise.

Experimental Results

The authors evaluated RDLA using a massive dataset from Alibaba Group, involving 245 bidders and millions of queries over seven days. The results demonstrate the clear superiority of the robust approach:

  • Revenue Increase: RDLA achieved a 5.5% revenue boost over the classical One-Time Primal-Dual (OT-PD) method.
  • Consistency: RDLA consistently outperformed standard Dynamic Learning Algorithms (DLA), proving that the DRO component adds value beyond simple frequent model updates.
  • Reliability: Across various test days, the algorithm maintained high mean revenue with competitive stability, particularly when the ambiguity set radius ($\delta$) was tuned to approximately $1e-3$.

Conclusion

RDLA bridges the gap between optimistic stochastic models and conservative adversarial ones. By explicitly accounting for distribution drift through robust optimization and frequent, equal-interval updates, it provides a practical and high-performing solution for large-scale online matching problems. Future work may explore alternative distance metrics, such as Wasserstein distance, to further refine the ambiguity sets and enhance robustness.

Summary updated

Abstract

Recently, online matching problems have attracted much attention due to its emerging applications in internet advertising. Most existing online matching methods have adopted either adversarial or stochastic user arrival assumption, while on both of them significant limitation exists. The adversarial model does not exploit existing knowledge of the user sequence, and thus can be pessimistic in practice. On other hands, the stochastic model assumes that users are drawn from a stationary distribution, which may not be true in real applications. In this paper, we consider a novel user arrival model where users are drawn from drifting distribution, which is a hybrid case between the adversarial and stochastic model, and propose a new approach RDLA to deal with such assumption. Instead of maximizing empirical total revenues on the revealed users, RDLA leverages distributionally robust optimization techniques to learn dual variables via a worst-case consideration over an ambiguity set on the underlying user distribution. Experiments on a real-world dataset exhibit the superiority of our approach.
BibTeX
@inproceedings{zhou2019robust,
  author = {Yu-Hang Zhou and Chen Liang and Nan Li and Cheng Yang and Shenghuo Zhu and Rong Jin},
  title = {{Robust Online Matching with User Arrival Distribution Drift}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.3301459},
}
Figure