Thursday, October 7, 2021
12:00pm-1:00pm
*ONLINE*
October 7, 2021
Registration: Link (Zoom link will be provided after the registration form is submitted)
Professor Elias Khalil – University of Toronto (MIE)
Deep Reinforcement Learning for Online Combinatorial Optimization: The Case of Bipartite Matching
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. Joint work with Mohammad Ali Alomrani (UofT ECE) and Reza Morajev (UofT MIE). Manuscript available at https://arxiv.org/abs/2109.10380.
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.
