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

arXiv: https://arxiv.org/abs/2102.11050 · HTML: https://mlsanity.com/paper/2102.11050/

## Key facts

- Cited by 40 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 79 references that are in the map.
- First posted on arXiv 18 Feb 2021.

## Builds on (most cited first, 23 of 23)

- [Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously](https://mlsanity.com/paper/1901.08779/) (2019)
- [MNL-Bandit: A Dynamic Learning Approach to Assortment Selection](https://mlsanity.com/paper/1706.03880/) (2017)
- [Stochastic Conditional Gradient Methods: From Convex Minimization to Submodular Maximization](https://mlsanity.com/paper/1804.09554/) (2018)
- [The Computational Power of Optimization in Online Learning](https://mlsanity.com/paper/1504.02089/) (2015)
- [Dynamic Incentive-aware Learning: Robust Pricing in Contextual Auctions](https://mlsanity.com/paper/2002.11137/) (2020)
- [Oracle-Efficient Online Learning and Auction Design](https://mlsanity.com/paper/1611.01688/) (2016)
- [Gradient Methods for Submodular Maximization](https://mlsanity.com/paper/1708.03949/) (2017)
- [Online Continuous Submodular Maximization: From Full-Information to Bandit Feedback](https://mlsanity.com/paper/1910.12424/) (2019)
- [One Sample Stochastic Frank-Wolfe](https://mlsanity.com/paper/1910.04322/) (2019)
- [Guaranteed Non-convex Optimization: Submodular Maximization over Continuous Domains](https://mlsanity.com/paper/1606.05615/) (2016)
- [Projection-Free Online Optimization with Stochastic Gradient: From Convexity to Submodularity](https://mlsanity.com/paper/1802.08183/) (2018)
- [Volumetric Spanners: an Efficient Exploration Basis for Learning](https://mlsanity.com/paper/1312.6214/) (2013)
- [Efficient Online Linear Optimization with Approximation Algorithms](https://mlsanity.com/paper/1709.03093/) (2017)
- [Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximization](https://mlsanity.com/paper/1805.09480/) (2018)
- [Deterministic Algorithms for Submodular Maximization Problems](https://mlsanity.com/paper/1508.02157/) (2015)
- [Online Non-Monotone DR-submodular Maximization](https://mlsanity.com/paper/1909.11426/) (2019)
- [Black Box Submodular Maximization: Discrete and Continuous Settings](https://mlsanity.com/paper/1901.09515/) (2019)
- [Stochastic Conditional Gradient++](https://mlsanity.com/paper/1902.06992/) (2019)
- [Maximizing Monotone Submodular Functions over the Integer Lattice](https://mlsanity.com/paper/1503.01218/) (2015)
- [Improved Revenue Bounds for Posted-Price and Second-Price Mechanisms](https://mlsanity.com/paper/1807.03435/) (2018)
- [LP-based Approximation for Personalized Reserve Prices](https://mlsanity.com/paper/1905.01526/) (2019)
- [Response-Based Approachability and its Application to Generalized No-Regret Algorithms](https://mlsanity.com/paper/1312.7658/) (2013)
- [Optimal Auctions vs. Anonymous Pricing](https://mlsanity.com/paper/1507.02615/) (2015)

## Built on by (most cited first, 30 of 40)

- [A Framework for Adapting Offline Algorithms to Solve Combinatorial Multi-Armed Bandit Problems with Bandit Feedback](https://mlsanity.com/paper/2301.13326/) (2023)
- [Combinatorial Stochastic-Greedy Bandit](https://mlsanity.com/paper/2312.08057/) (2023)
- [An α-regret analysis of Adversarial Bilateral Trade](https://mlsanity.com/paper/2210.06846/) (2022)
- [Bandit Multi-linear DR-Submodular Maximization and Its Applications on Adversarial Submodular Bandits](https://mlsanity.com/paper/2305.12402/) (2023)
- [A CMDP-within-online framework for Meta-Safe Reinforcement Learning](https://mlsanity.com/paper/2405.16601/) (2024)
- [Federated Combinatorial Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2405.05950/) (2024)
- [A Unified Approach for Maximizing Continuous DR-submodular Functions](https://mlsanity.com/paper/2305.16671/) (2023)
- [From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-stationary DR-submodular Optimization](https://mlsanity.com/paper/2405.00065/) (2024)
- [Semi-Bandit Learning for Monotone Stochastic Optimization](https://mlsanity.com/paper/2312.15427/) (2023)
- [Adaptive Oracle-Efficient Online Learning](https://mlsanity.com/paper/2210.09385/) (2022)
- [Nearly Minimax Optimal Submodular Maximization with Bandit Feedback](https://mlsanity.com/paper/2310.18465/) (2023)
- [Online Submodular Maximization via Online Convex Optimization](https://mlsanity.com/paper/2309.04339/) (2023)
- [Learning and Collusion in Multi-unit Auctions](https://mlsanity.com/paper/2305.17402/) (2023)
- [Bandit Sequential Posted Pricing via Half-Concavity](https://mlsanity.com/paper/2312.12794/) (2023)
- [Unified Projection-Free Algorithms for Adversarial DR-Submodular Optimization](https://mlsanity.com/paper/2403.10063/) (2024)
- [Offline Learning for Combinatorial Multi-armed Bandits](https://mlsanity.com/paper/2501.19300/) (2025)
- [Product Ranking for Revenue Maximization with Multiple Purchases](https://mlsanity.com/paper/2210.08268/) (2022)
- [Learning in Repeated Multi-Unit Pay-As-Bid Auctions](https://mlsanity.com/paper/2307.15193/) (2023)
- [Sum-max Submodular Bandits](https://mlsanity.com/paper/2311.05975/) (2023)
- [Stochastic k-Submodular Bandits with Full Bandit Feedback](https://mlsanity.com/paper/2412.10682/) (2024)
- [On Submodular Contextual Bandits](https://mlsanity.com/paper/2112.02165/) (2021)
- [Active Learning for Non-Parametric Choice Models](https://mlsanity.com/paper/2208.03346/) (2022)
- [Stochastic Submodular Bandits with Delayed Composite Anonymous Bandit Feedback](https://mlsanity.com/paper/2303.13604/) (2023)
- [Online Mixture of Experts: No-Regret Learning for Optimal Collective Decision-Making](https://mlsanity.com/paper/2510.21788/) (2025)
- [Misalignment, Learning, and Ranking: Harnessing Users Limited Attention](https://mlsanity.com/paper/2402.14013/) (2024)
- [Preparing for Black Swans: The Antifragility Imperative for Machine Learning](https://mlsanity.com/paper/2405.11397/) (2024)
- [No-Regret Mnatural-Concave Function Maximization: Stochastic Bandit Algorithms and Hardness of Adversarial Full-Information Setting](https://mlsanity.com/paper/2405.12439/) (2024)
- [Wasserstein gradient flow for optimal probability measure decomposition](https://mlsanity.com/paper/2406.00914/) (2024)
- [A Unified Approach to Submodular Maximization Under Noise](https://mlsanity.com/paper/2510.21128/) (2025)
- [Improved Approximate Regret for Decentralized Online Continuous Submodular Maximization via Reductions](https://mlsanity.com/paper/2602.09502/) (2026)

## Abstract (arXiv)

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