# The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems

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

## Key facts

- Cited by 58 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Nov 2020.

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

- [A Unifying Framework for Online Optimization with Long-Term Constraints](https://mlsanity.com/paper/2209.07454/) (2022)
- [Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regression](https://mlsanity.com/paper/2211.07484/) (2022)
- [Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics](https://mlsanity.com/paper/2301.13306/) (2023)
- [Multi-channel Autobidding with Budget and ROI Constraints](https://mlsanity.com/paper/2302.01523/) (2023)
- [Degeneracy is OK: Logarithmic Regret for Network Revenue Management with Indiscrete Distributions](https://mlsanity.com/paper/2210.07996/) (2022)
- [Online Contextual Decision-Making with a Smart Predict-then-Optimize Method](https://mlsanity.com/paper/2206.07316/) (2022)
- [Optimal Contextual Bandits with Knapsacks under Realizability via Regression Oracles](https://mlsanity.com/paper/2210.11834/) (2022)
- [Towards Environmentally Equitable AI via Geographical Load Balancing](https://mlsanity.com/paper/2307.05494/) (2023)
- [Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints](https://mlsanity.com/paper/2405.16118/) (2024)
- [Online Resource Allocation under Horizon Uncertainty](https://mlsanity.com/paper/2206.13606/) (2022)
- [Joint Online Learning and Decision-making via Dual Mirror Descent](https://mlsanity.com/paper/2104.09750/) (2021)
- [Optimal Regularized Online Allocation by Adaptive Re-Solving](https://mlsanity.com/paper/2209.00399/) (2022)
- [Infrequent Resolving Algorithm for Online Linear Programming](https://mlsanity.com/paper/2408.00465/) (2024)
- [Bidding Agent Design in the LinkedIn Ad Marketplace](https://mlsanity.com/paper/2202.12472/) (2022)
- [Approximately Stationary Bandits with Knapsacks](https://mlsanity.com/paper/2302.14686/) (2023)
- [Bandits with Replenishable Knapsacks: the Best of both Worlds](https://mlsanity.com/paper/2306.08470/) (2023)
- [No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization](https://mlsanity.com/paper/2405.06575/) (2024)
- [No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need!](https://mlsanity.com/paper/2506.13244/) (2025)
- [Best of Many Worlds Guarantees for Online Learning with Knapsacks](https://mlsanity.com/paper/2202.13710/) (2022)
- [Robust Budget Pacing with a Single Sample](https://mlsanity.com/paper/2302.02006/) (2023)
- [Coordinated Dynamic Bidding in Repeated Second-Price Auctions with Budgets](https://mlsanity.com/paper/2306.07709/) (2023)
- [Online Learning in Contextual Second-Price Pay-Per-Click Auctions](https://mlsanity.com/paper/2310.05047/) (2023)
- [Beyond O(√T) Regret: Decoupling Learning and Decision-making in Online Linear Programming](https://mlsanity.com/paper/2501.02761/) (2025)
- [Analysis of Dual-Based PID Controllers through Convolutional Mirror Descent](https://mlsanity.com/paper/2202.06152/) (2022)
- [Network Revenue Management with Demand Learning and Fair Resource-Consumption Balancing](https://mlsanity.com/paper/2207.11159/) (2022)
- [Interpolating Item and User Fairness in Multi-Sided Recommendations](https://mlsanity.com/paper/2306.10050/) (2023)
- [High-dimensional Linear Bandits with Knapsacks](https://mlsanity.com/paper/2311.01327/) (2023)
- [Decoupling Learning and Decision-Making: Breaking the O(√T) Barrier in Online Resource Allocation with First-Order Methods](https://mlsanity.com/paper/2402.07108/) (2024)
- [Best of Many in Both Worlds: Online Resource Allocation with Predictions under Unknown Arrival Model](https://mlsanity.com/paper/2402.13530/) (2024)
- [Single-Sample and Robust Online Resource Allocation](https://mlsanity.com/paper/2505.02963/) (2025)

## Abstract (arXiv)

Online allocation problems with resource constraints are central problems in revenue management and online advertising. In these problems, requests arrive sequentially during a finite horizon and, for each request, a decision maker needs to choose an action that consumes a certain amount of resources and generates reward. The objective is to maximize cumulative rewards subject to a constraint on the total consumption of resources. In this paper, we consider a data-driven setting in which the reward and resource consumption of each request are generated using an input model that is unknown to the decision maker. We design a general class of algorithms that attain good performance in various input models without knowing which type of input they are facing. In particular, our algorithms are asymptotically optimal under independent and identically distributed inputs as well as various non-stationary stochastic input models, and they attain an asymptotically optimal fixed competitive ratio when the input is adversarial. Our algorithms operate in the Lagrangian dual space: they maintain a dual multiplier for each resource that is updated using online mirror descent. By choosing the reference function accordingly, we recover the dual sub-gradient descent and dual multiplicative weights update algorithm. The resulting algorithms are simple, fast, and do not require convexity in the revenue function, consumption function and action space, in contrast to existing methods for online allocation problems. We discuss applications to network revenue management, online bidding in repeated auctions with budget constraints, online proportional matching with high entropy, and personalized assortment optimization with limited inventory.