# Deep Policies for Online Bipartite Matching: A Reinforcement Learning Approach

arXiv: https://arxiv.org/abs/2109.10380 · HTML: https://mlsanity.com/paper/2109.10380/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 42 references that are in the map.
- First posted on arXiv 21 Sep 2021.

## Builds on (most cited first, 17 of 17)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Learning to learn by gradient descent by gradient descent](https://mlsanity.com/paper/1606.04474/) (2016)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Representation Learning for Dynamic Graphs: A Survey](https://mlsanity.com/paper/1905.11485/) (2019)
- [Reinforcement Learning for Combinatorial Optimization: A Survey](https://mlsanity.com/paper/2003.03600/) (2020)
- [Learning to Perform Local Rewriting for Combinatorial Optimization](https://mlsanity.com/paper/1810.00337/) (2018)
- [Exploratory Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1909.04063/) (2019)
- [Secretary and Online Matching Problems with Machine Learned Advice](https://mlsanity.com/paper/2006.01026/) (2020)
- [An Experimental Study of Algorithms for Online Bipartite Matching](https://mlsanity.com/paper/1808.04863/) (2018)
- [Balancing Relevance and Diversity in Online Bipartite Matching via Submodularity](https://mlsanity.com/paper/1811.05100/) (2018)
- [Learning Robust Algorithms for Online Allocation Problems Using Adversarial Training](https://mlsanity.com/paper/2010.08418/) (2020)

## Built on by (most cited first, 10 of 10)

- [Online bipartite matching with imperfect advice](https://mlsanity.com/paper/2405.09784/) (2024)
- [Learning for Edge-Weighted Online Bipartite Matching with Robustness Guarantees](https://mlsanity.com/paper/2306.00172/) (2023)
- [Robustified Learning for Online Optimization with Memory Costs](https://mlsanity.com/paper/2305.00677/) (2023)
- [Robust Learning for Smoothed Online Convex Optimization with Feedback Delay](https://mlsanity.com/paper/2310.20098/) (2023)
- [Learning Potentials for Dynamic Matching and Application to Heart Transplantation](https://mlsanity.com/paper/2602.08878/) (2026)
- [Understanding Curriculum Learning in Policy Optimization for Online Combinatorial Optimization](https://mlsanity.com/paper/2202.05423/) (2022)
- [MAGNOLIA: Matching Algorithms via GNNs for Online Value-to-go Approximation](https://mlsanity.com/paper/2406.05959/) (2024)
- [Learning-Assisted Algorithm Unrolling for Online Optimization with Budget Constraints](https://mlsanity.com/paper/2212.01689/) (2022)
- [Learning Efficient and Fair Policies for Uncertainty-Aware Collaborative Human-Robot Order Picking](https://mlsanity.com/paper/2404.08006/) (2024)
- [Online Budgeted Matching with General Bids](https://mlsanity.com/paper/2411.04204/) (2024)

## Abstract (arXiv)

The challenge in the widely applicable online matching problem lies in making irrevocable assignments while there is uncertainty about future inputs. Most theoretically-grounded policies are myopic or greedy in nature. In real-world applications where the matching process is repeated on a regular basis, the underlying data distribution can be leveraged for better decision-making. We present an end-to-end Reinforcement Learning framework for deriving better matching policies based on trial-and-error on historical data. We devise a set of neural network architectures, design feature representations, and empirically evaluate them across two online matching problems: Edge-Weighted Online Bipartite Matching and Online Submodular Bipartite Matching. We show that most of the learning approaches perform consistently better than classical baseline algorithms on four synthetic and real-world datasets. On average, our proposed models improve the matching quality by 3--10% on a variety of synthetic and real-world datasets. Our code is publicly available at https://github.com/lyeskhalil/CORL.