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 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's approachability. We show that the resulting online algorithms have O(T^{1/2}) (approximate) regret under the full information setting. We further introduce a bandit extension of Blackwell's approachability and leverage this notion to transform greedy robust offline algorithms into an 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 show that our transformation leads to new regret bounds or improves the current known bounds when applied to these applications. If time permits, I will elaborate on some open problems and future directions from this work.
The talk is based on the following paper (with Negin Golrezaei, Joshua Wang, Fransisca Susan, and Ashwinkumar Badanidiyuru):
"Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization",
Management Science, 2022 (the conference version has appeared in ACM EC'21)