# No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 42 references that are in the map.
- First posted on arXiv 10 May 2024.

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

- [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)
- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [Explore no more: Improved high-probability regret bounds for non-stochastic bandits](https://mlsanity.com/paper/1506.03271/) (2015)
- [Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability](https://mlsanity.com/paper/2003.12699/) (2020)
- [Online Convex Optimization with Stochastic Constraints](https://mlsanity.com/paper/1708.03741/) (2017)
- [Practical Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/1803.01088/) (2018)
- [Scale-Free Online Learning](https://mlsanity.com/paper/1601.01974/) (2016)
- [Bandits with concave rewards and convex knapsacks](https://mlsanity.com/paper/1402.5758/) (2014)
- [Linear Contextual Bandits with Knapsacks](https://mlsanity.com/paper/1507.06738/) (2015)
- [Adversarial Bandits with Knapsacks](https://mlsanity.com/paper/1811.11881/) (2018)
- [A Contextual Bandit Bake-off](https://mlsanity.com/paper/1802.04064/) (2018)
- [Relative Loss Bounds for On-line Density Estimation with the Exponential Family of Distributions](https://mlsanity.com/paper/1301.6677/) (2013)
- [The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems](https://mlsanity.com/paper/2011.10124/) (2020)
- [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)
- [A Unifying Framework for Online Optimization with Long-Term Constraints](https://mlsanity.com/paper/2209.07454/) (2022)
- [Online Primal-Dual Mirror Descent under Stochastic Constraints](https://mlsanity.com/paper/1908.00305/) (2019)
- [Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regression](https://mlsanity.com/paper/2211.07484/) (2022)
- [Non-stationary Bandits with Knapsacks](https://mlsanity.com/paper/2205.12427/) (2022)
- [Online Learning with Vector Costs and Bandits with Knapsacks](https://mlsanity.com/paper/2010.07346/) (2020)
- [Budget Pacing in Repeated Auctions: Regret and Efficiency without Convergence](https://mlsanity.com/paper/2205.08674/) (2022)
- [Online Bidding Algorithms for Return-on-Spend Constrained Advertisers](https://mlsanity.com/paper/2208.13713/) (2022)
- [No-Regret Learning in Bilateral Trade via Global Budget Balance](https://mlsanity.com/paper/2310.12370/) (2023)
- [Learning to Bid in Repeated First-Price Auctions with Budgets](https://mlsanity.com/paper/2304.13477/) (2023)
- [Non-monotonic Resource Utilization in the Bandits with Knapsacks Problem](https://mlsanity.com/paper/2209.12013/) (2022)
- [Optimal Contextual Bandits with Knapsacks under Realizability via Regression Oracles](https://mlsanity.com/paper/2210.11834/) (2022)
- [Online Resource Allocation under Horizon Uncertainty](https://mlsanity.com/paper/2206.13606/) (2022)
- [Approximately Stationary Bandits with Knapsacks](https://mlsanity.com/paper/2302.14686/) (2023)
- [Best of Many Worlds Guarantees for Online Learning with Knapsacks](https://mlsanity.com/paper/2202.13710/) (2022)

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

- [Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints](https://mlsanity.com/paper/2405.16118/) (2024)
- [Learning to Explore with Lagrangians for Bandits under Unknown Linear Constraints](https://mlsanity.com/paper/2410.18844/) (2024)
- [Bandits with Anytime Knapsacks](https://mlsanity.com/paper/2501.18560/) (2025)
- [Truly Adapting to Adversarial Constraints in Constrained MABs](https://mlsanity.com/paper/2602.14543/) (2026)
- [Regret Minimization in Bilateral Trade With Perturbed Markets](https://mlsanity.com/paper/2605.10475/) (2026)
- [Convex Optimization with Nested Evolving Feasible Sets (CONES) under Time-Varying Loss Functions](https://mlsanity.com/paper/2609.11207/) (2026)

## Abstract (arXiv)

In the bandits with knapsacks framework (BwK) the learner has m resource-consumption (packing) constraints. We focus on the generalization of BwK in which the learner has a set of general long-term constraints. The goal of the learner is to maximize their cumulative reward, while at the same time achieving small cumulative constraints violations. In this scenario, there exist simple instances where conventional methods for BwK fail to yield sublinear violations of constraints. We show that it is possible to circumvent this issue by requiring the primal and dual algorithm to be weakly adaptive. Indeed, even in absence on any information on the Slater's parameter ρ characterizing the problem, the interplay between weakly adaptive primal and dual regret minimizers yields a "self-bounding" property of dual variables. In particular, their norm remains suitably upper bounded across the entire time horizon even without explicit projection steps. By exploiting this property, we provide best-of-both-worlds guarantees for stochastic and adversarial inputs. In the first case, we show that the algorithm guarantees sublinear regret. In the latter case, we establish a tight competitive ratio of ρ/(1+ρ). In both settings, constraints violations are guaranteed to be sublinear in time. Finally, this results allow us to obtain new result for the problem of contextual bandits with linear constraints, providing the first no-α-regret guarantees for adversarial contexts.