Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization
Abstract
Motivated by online decision-making in time-varying combinatorial environments, we study the problem of transforming offline algorithms to their online counterparts. We focus on offline combinatorial problems that are amenable to a constant factor approximation using a greedy algorithm that is robust to local errors. For such problems, we provide a general framework that efficiently transforms offline robust greedy algorithms to online ones using Blackwell approachability. We show that the resulting online algorithms have $O(\sqrt{T})$ (approximate) regret under the full information setting. We further introduce a bandit extension of Blackwell approachability that we call Bandit Blackwell approachability. We leverage this notion to transform greedy robust offline algorithms into a $O(T^{2/3})$ (approximate) regret in the bandit setting. Demonstrating the flexibility of our framework, we apply our offline-to-online transformation to several problems at the intersection of revenue management, market design, and online optimization, including product ranking optimization in online platforms, reserve price optimization in auctions, and submodular maximization. We also extend our reduction to greedy-like first-order methods used in continuous optimization, such as those used for maximizing continuous strong DR monotone submodular functions subject to convex constraints. We show that our transformation, when applied to these applications, leads to new regret bounds or improves the current known bounds. We complement our theoretical studies by conducting numerical simulations for two of our applications, in both of which we observe that the numerical performance of our transformations outperforms the theoretical guarantees in practical instances.
Paper: https://arxiv.org/abs/2102.11050
Bio
Negin Golrezaei is an Assistant Professor of Operations Management at the MIT Sloan School of Management and the KDD Career Development Professor in Communications and Technology. Her research focuses on machine learning, statistical learning theory, mechanism design, and optimization algorithms, with applications to revenue management, pricing, and online markets.
Prior to joining MIT, Negin worked as a postdoctoral fellow at Google Research in New York, where she collaborated with the Market Algorithm team to create, design, and test new mechanisms and algorithms for online marketplaces. She received her BSc and MSc degrees in electrical engineering from the Sharif University of Technology, Iran, and a PhD in operations research from USC. Negin is an associate editor for the Production and Operations Management journal and Operations Research Letters journal. She has received several awards, including the 2021 Young Investigator Award at ONR, the 2018 Google Faculty Research Award, the 2017 George B. Dantzig Dissertation Award, and the INFORMS Revenue Management and Pricing Section Dissertation Prize.
