Online contextual learning with perishable resources allocation
Xin Pan, Jie Song, Jingtong Zhao, Van‐Anh Truong · IISE Transactions · 2020
Xin Pana, Jie Songa*, Jingtong Zhaob & Van-Anh Truongba Department of Industrial Engineering and Management, Peking University, Beijing, China; b Department of Industrial Engineering and Operations Research, Columbia University, New York, NY, USAXin Pan is an algorithmic engineer at Shunfeng Tech Inc. He received his BE from the Department of Industrial Engineering, Tsinghua University in 2016. He finished his PhD at the Department of Industrial Engineering and Management, Peking University in 2020. Doctor Pan’s research interests lie in the range of data-driven optimization, dynamic programming and stochastic modelling, etc.Jie Song is an associate professor with the Department of Industrial Engineering and Management, Peking University. She received a BS degree in applied mathematics from Peking University, Beijing, China, in 2004, and a PhD degree at the Department of Industrial Engineering, Tsinghua University, Beijing, in 2010. Her research interests are stochastic simulation and optimization, online algorithm design, with applications in service systems. She is a Senior Member of IEEE.Jingtong Zhao is a PhD candidate in the Department of Industrial Engineering and Operations Research, Columbia University. She received her BS degree in financial engineering from the Department of Industrial Engineering and Operations Research, Columbia University, in 2016. Her research interests are optimization and algorithm design, with applications in online service platforms.Van-Anh Truong is an associate professor with the Department of Industrial Engineering and Operations Research, Columbia University. She received her Bachelor’s degree in Mathematics from University of Waterloo, Canada in 2002, and PhD degree in operations research from Cornell University in 2007. Her research focuses on developing optimization methods for solving a broad class of decision making problems under uncertainty in information-rich and highly dynamic environments, which arise in supply chain management, healthcare, and business analytics.Supplemental data for this article can be accessed online at https://doi.org/10.1080/24725854.2020.1752958.CONTACT Jie Song [email protected] formulate a novel class of online matching problems with learning. In these problems, randomly arriving customers must be matched to perishable resources so as to maximize a total expected reward. The matching accounts for variations in rewards among different customer–resource pairings. It also accounts for the perishability of the resources. Our work is motivated by a healthcare application, but it can be easily extended to other service applications. Our work belongs to the online resource allocation streams in service systems. We propose the first online algorithm for contextual learning and resource allocation with perishable resources. Our algorithm explores and exploits in distinct interweaving phases. We prove that our algorithm achieves an expected regret per period that increases sub-linearly with the number of planning cycles.