Learning for Edge-Weighted Online Bipartite Matching with Robustness
  Guarantees
Pengfei Li Jianyi Yang Shaolei Ren
Many problems, such as online ad display, can be formulated as online
bipartite matching. The crucial challenge lies in the nature of
sequentially-revealed online item information, based on which we make
irreversible matching decisions at each step. While numerous expert online
algorithms have been proposed with bounded worst-case competitive ratios, they
may not offer satisfactory performance in average cases. On the other hand,
reinforcement learning (RL) has been applied to improve the average
performance, but it lacks robustness and can perform arbitrarily poorly. In
this paper, we propose a novel RL-based approach to edge-weighted online
bipartite matching with robustness guarantees (LOMAR), achieving both good
average-case and worst-case performance. The key novelty of LOMAR is a new
online switching operation which, based on a judicious condition to hedge
against future uncertainties, decides whether to follow the expert's decision
or the RL decision for each online item. We prove that for any $\rho\in[0,1]$,
LOMAR is $\rho$-competitive against any given expert online algorithm. To
improve the average performance, we train the RL policy by explicitly
considering the online switching operation. Finally, we run empirical
experiments to demonstrate the advantages of LOMAR compared to existing
baselines. Our code is available at: https://github.com/Ren-Research/LOMAR