Online Algorithms for Correlated Arrivals
This is a joint seminar organized by Department of Computer Science , Faculty of Engineering and HKU Business School’s IIM Area.
Prof. Will Ma
Associate Professor | Decision, Risk, and Operations
Graduate School of Business and Data Science Institute
Columbia University
Online algorithms are ubiquitous in e-commerce systems, where inventory, fulfillment, and assortment decisions must be committed to in real-time without knowing future demand. For many of these problems, there is a lack of decision-making approaches that are aware of correlations in demand over time. This is partly due to the challenge of model selection, but even given an explicit model of correlated demand, it is unclear how online decisions should be prescribed.
We present two new approaches that overcome these challenges by implicitly capturing the correlations in demand arrivals over time. First, we present a non-parametric framework that models only the distribution of the total arrivals of each “type”, and then by making assumptions on how these arrivals are interleaved, leads to correlation-aware online decisions. Second, we discuss a model-free “reinforcement learning” approach that directly optimizes for average performance over a collection of past (correlated) arrival sequences, while restricting to a carefully curated class of policies. We discuss the benefits of each approach, and the assumptions that they make on the data. Finally, we discuss details of the first approach specifically for the online matching (fulfillment) problem. Based primarily on joint work with Ali Aouad (London Business School -> MIT).
Will Ma is an Associate Professor of Decision, Risk, and Operations at Columbia Business School. His research centers around online algorithms in e-commerce systems, both for supply-side problems like inventory and fulfillment, and revenue management problems like dynamic assortment optimization. He specializes in designing simple online algorithms with performance guarantees, that can be tuned to historical data. Will also has miscellaneous experience as a professional poker player, video-game startup founder, and karaoke bar pianist.
