Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization

Rad Niazadeh (), Negin Golrezaei (), Joshua Wang (), Fransisca Susan () and Ashwinkumar Badanidiyuru ()
Additional contact information
Rad Niazadeh: Operations Management, Chicago Booth School of Business, Chicago, Illinois 60637
Negin Golrezaei: Operations Management, MIT Sloan School of Management, Cambridge, Massachusetts 02142
Joshua Wang: Google Research Mountain View, Mountain View, California 94043
Fransisca Susan: Operations Management, MIT Sloan School of Management, Cambridge, Massachusetts 02142
Ashwinkumar Badanidiyuru: Google Research Mountain View, Mountain View, California 94043

Management Science, 2023, vol. 69, issue 7, 3797-3817

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 ( 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.

Keywords: Blackwell approachability; offline-to-online; no regret; submodular maximization; product ranking; reserve price optimization (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.2022.4558 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:69:y:2023:i:7:p:3797-3817

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().