# Online Learning under Budget and ROI Constraints via Weak Adaptivity

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 67 references that are in the map.
- First posted on arXiv 2 Feb 2023.

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

- [Explore no more: Improved high-probability regret bounds for non-stochastic bandits](https://mlsanity.com/paper/1506.03271/) (2015)
- [Online Convex Optimization with Stochastic Constraints](https://mlsanity.com/paper/1708.03741/) (2017)
- [Online Convex Optimization with Time-Varying Constraints](https://mlsanity.com/paper/1702.04783/) (2017)
- [Resourceful Contextual Bandits](https://mlsanity.com/paper/1402.6779/) (2014)
- [A Unifying Framework for Online Optimization with Long-Term Constraints](https://mlsanity.com/paper/2209.07454/) (2022)
- [Online learning in repeated auctions](https://mlsanity.com/paper/1511.05720/) (2015)
- [Optimal No-regret Learning in Repeated First-price Auctions](https://mlsanity.com/paper/2003.09795/) (2020)
- [Learning to Bid Optimally and Efficiently in Adversarial First-price Auctions](https://mlsanity.com/paper/2007.04568/) (2020)
- [Online Learning with Vector Costs and Bandits with Knapsacks](https://mlsanity.com/paper/2010.07346/) (2020)
- [Online Bidding Algorithms for Return-on-Spend Constrained Advertisers](https://mlsanity.com/paper/2208.13713/) (2022)
- [Unifying the stochastic and the adversarial Bandits with Knapsack](https://mlsanity.com/paper/1811.12253/) (2018)
- [No-regret Learning in Repeated First-Price Auctions with Budget Constraints](https://mlsanity.com/paper/2205.14572/) (2022)
- [Non-quasi-linear Agents in Quasi-linear Mechanisms](https://mlsanity.com/paper/2012.02893/) (2020)
- [Learning to Price against a Budget and ROI Constrained Buyer](https://mlsanity.com/paper/2107.07725/) (2021)

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

- [Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints](https://mlsanity.com/paper/2405.16118/) (2024)
- [No-Regret Algorithms in non-Truthful Auctions with Budget and ROI Constraints](https://mlsanity.com/paper/2404.09832/) (2024)
- [A New Benchmark for Online Learning with Budget-Balancing Constraints](https://mlsanity.com/paper/2503.14796/) (2025)
- [Episodic Contextual Bandits with Knapsacks under Conversion Models](https://mlsanity.com/paper/2507.06859/) (2025)
- [Regret Minimization in Bilateral Trade With Perturbed Markets](https://mlsanity.com/paper/2605.10475/) (2026)

## Abstract (arXiv)

We study online learning problems in which a decision maker has to make a sequence of costly decisions, with the goal of maximizing their expected reward while adhering to budget and return-on-investment (ROI) constraints. Existing primal-dual algorithms designed for constrained online learning problems under adversarial inputs rely on two fundamental assumptions. First, the decision maker must know beforehand the value of parameters related to the degree of strict feasibility of the problem (i.e. Slater parameters). Second, a strictly feasible solution to the offline optimization problem must exist at each round. Both requirements are unrealistic for practical applications such as bidding in online ad auctions. In this paper, we show how such assumptions can be circumvented by endowing standard primal-dual templates with weakly adaptive regret minimizers. This results in a ``dual-balancing'' framework which ensures that dual variables stay sufficiently small, even in the absence of knowledge about Slater's parameter. We prove the first best-of-both-worlds no-regret guarantees which hold in absence of the two aforementioned assumptions, under stochastic and adversarial inputs. Finally, we show how to instantiate the framework to optimally bid in various mechanisms of practical relevance, such as first- and second-price auctions.