Deep Reinforcement Learning for Online Combinatorial Optimization: The Case of Bipartite Matching

Speaker: Elias Khalil

Affiliation: University of Toronto

Abstract: From assigning computing tasks to servers and advertisements to users, sequential online matching problems arise in a wide variety of domains. The challenge in online matching lies in making irrevocable assignments while there is uncertainty about future inputs. In the theoretical computer science literature, most 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. I will 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 significantly better than classical greedy algorithms on four synthetic and real-world datasets.

Bio: Elias B. Khalil [] is the Scale AI Research Chair in Data-Driven Algorithms for Modern Supply Chains, an Assistant Professor of Industrial Engineering at the University of Toronto, and a Faculty Affiliate of the Vector Institute. Prior to that, he was the IVADO Postdoctoral Scholar at Polytechnique Montréal. Elias obtained his Ph.D. from the College of Computing at Georgia Tech where he was an IBM Ph.D. Fellow in 2016. His research interests are in the integration of machine learning and discrete optimization to enable fast and optimal decision-making for supply chain planning and healthcare resource management.
Be the first to comment