Robust Online Matching with User Arrival Distribution Drift

Authors

  • Yu-Hang Zhou Alibaba Group
  • Chen Liang Alibaba Group
  • Nan Li Alibaba Group
  • Cheng Yang Alibaba Group
  • Shenghuo Zhu Alibaba Group
  • Rong Jin Alibaba Group

DOI:

https://doi.org/10.1609/aaai.v33i01.3301459

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.

Downloads

Published

2019-07-17

How to Cite

Zhou, Y.-H., Liang, C., Li, N., Yang, C., Zhu, S., & Jin, R. (2019). Robust Online Matching with User Arrival Distribution Drift. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 459-466. https://doi.org/10.1609/aaai.v33i01.3301459

Issue

Section

AAAI Technical Track: AI and the Web