# Best of Many Worlds Guarantees for Online Learning with Knapsacks

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 65 references that are in the map.
- First posted on arXiv 28 Feb 2022.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Stochastic bandits robust to adversarial corruptions](https://mlsanity.com/paper/1803.09353/) (2018)
- [Bandits with concave rewards and convex knapsacks](https://mlsanity.com/paper/1402.5758/) (2014)
- [Adversarial Bandits with Knapsacks](https://mlsanity.com/paper/1811.11881/) (2018)
- [The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems](https://mlsanity.com/paper/2011.10124/) (2020)
- [Online Convex Optimization with Time-Varying Constraints](https://mlsanity.com/paper/1702.04783/) (2017)
- [Dual Mirror Descent for Online Allocation Problems](https://mlsanity.com/paper/2002.10421/) (2020)
- [An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits](https://mlsanity.com/paper/1605.08722/) (2016)
- [Resourceful Contextual Bandits](https://mlsanity.com/paper/1402.6779/) (2014)
- [An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives](https://mlsanity.com/paper/1506.03374/) (2015)
- [An Online Convex Optimization Approach to Dynamic Network Resource Allocation](https://mlsanity.com/paper/1701.03974/) (2017)
- [Learning to Bid Optimally and Efficiently in Adversarial First-price Auctions](https://mlsanity.com/paper/2007.04568/) (2020)
- [Algorithms with Logarithmic or Sublinear Regret for Constrained Contextual Bandits](https://mlsanity.com/paper/1504.06937/) (2015)
- [Bandit Convex Optimization for Scalable and Dynamic IoT Management](https://mlsanity.com/paper/1707.09060/) (2017)
- [Combinatorial Semi-Bandits with Knapsacks](https://mlsanity.com/paper/1705.08110/) (2017)
- [Online Learning with Vector Costs and Bandits with Knapsacks](https://mlsanity.com/paper/2010.07346/) (2020)
- [Learning to Bid in Contextual First Price Auctions](https://mlsanity.com/paper/2109.03173/) (2021)
- [Multiplicative Pacing Equilibria in Auction Markets](https://mlsanity.com/paper/1706.07151/) (2017)
- [Better Regularization for Sequential Decision Spaces: Fast Convergence Rates for Nash, Correlated, and Team Equilibria](https://mlsanity.com/paper/2105.12954/) (2021)
- [Unifying the stochastic and the adversarial Bandits with Knapsack](https://mlsanity.com/paper/1811.12253/) (2018)
- [Robust Dynamic Assortment Optimization in the Presence of Outlier Customers](https://mlsanity.com/paper/1910.04183/) (2019)
- [Dynamic Ad Allocation: Bandits with Budgets](https://mlsanity.com/paper/1306.0155/) (2013)
- [Bandits with Knapsacks beyond the Worst-Case](https://mlsanity.com/paper/2002.00253/) (2020)

## Built on by (most cited first, 4 of 4)

- [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)
- [Contextual Decision-Making with Knapsacks Beyond the Worst Case](https://mlsanity.com/paper/2211.13952/) (2022)
- [Constrained Online Two-stage Stochastic Optimization: Algorithm with (and without) Predictions](https://mlsanity.com/paper/2401.01077/) (2024)

## Abstract (arXiv)

We study online learning problems in which a decision maker wants to maximize their expected reward without violating a finite set of m resource constraints. By casting the learning process over a suitably defined space of strategy mixtures, we recover strong duality on a Lagrangian relaxation of the underlying optimization problem, even for general settings with non-convex reward and resource-consumption functions. Then, we provide the first best-of-many-worlds type framework for this setting, with no-regret guarantees under stochastic, adversarial, and non-stationary inputs. Our framework yields the same regret guarantees of prior work in the stochastic case. On the other hand, when budgets grow at least linearly in the time horizon, it allows us to provide a constant competitive ratio in the adversarial case, which improves over the best known upper bound bound of O(log m log T). Moreover, our framework allows the decision maker to handle non-convex reward and cost functions. We provide two game-theoretic applications of our framework to give further evidence of its flexibility. In doing so, we show that it can be employed to implement budget-pacing mechanisms in repeated first-price auctions.