# No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need!

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 60 references that are in the map.
- First posted on arXiv 16 Jun 2025.

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

- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (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)
- [Exploration-Exploitation in Constrained MDPs](https://mlsanity.com/paper/2003.02189/) (2020)
- [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)
- [Bandits with concave rewards and convex knapsacks](https://mlsanity.com/paper/1402.5758/) (2014)
- [Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPs](https://mlsanity.com/paper/2106.02684/) (2021)
- [Adversarial Bandits with Knapsacks](https://mlsanity.com/paper/1811.11881/) (2018)
- [Stochastic Bandits with Linear Constraints](https://mlsanity.com/paper/2006.10185/) (2020)
- [Adaptive Algorithms for Online Convex Optimization with Long-term Constraints](https://mlsanity.com/paper/1512.07422/) (2015)
- [The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems](https://mlsanity.com/paper/2011.10124/) (2020)
- [Dual Mirror Descent for Online Allocation Problems](https://mlsanity.com/paper/2002.10421/) (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)
- [Fast Algorithms for Online Stochastic Convex Programming](https://mlsanity.com/paper/1410.7596/) (2014)
- [Constrained episodic reinforcement learning in concave-convex and knapsack settings](https://mlsanity.com/paper/2006.05051/) (2020)
- [Optimal Algorithms for Online Convex Optimization with Adversarial Constraints](https://mlsanity.com/paper/2310.18955/) (2023)
- [Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regression](https://mlsanity.com/paper/2211.07484/) (2022)
- [Online Stochastic Optimization with Wasserstein Based Non-stationarity](https://mlsanity.com/paper/2012.06961/) (2020)
- [Combinatorial Semi-Bandits with Knapsacks](https://mlsanity.com/paper/1705.08110/) (2017)
- [Truly No-Regret Learning in Constrained MDPs](https://mlsanity.com/paper/2402.15776/) (2024)
- [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)
- [Primal Beats Dual on Online Packing LPs in the Random-Order Model](https://mlsanity.com/paper/1311.2578/) (2013)
- [Learning Adversarial MDPs with Stochastic Hard Constraints](https://mlsanity.com/paper/2403.03672/) (2024)
- [Online Learning in Weakly Coupled Markov Decision Processes: A Convergence Time Study](https://mlsanity.com/paper/1709.03465/) (2017)
- [Safe Linear Bandits over Unknown Polytopes](https://mlsanity.com/paper/2209.13694/) (2022)
- [Optimal Strong Regret and Violation in Constrained MDPs via Policy Optimization](https://mlsanity.com/paper/2410.02275/) (2024)

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

- [Replicable Constrained Bandits](https://mlsanity.com/paper/2602.14580/) (2026)
- [Online Learning for Approximately-Convex Functions with Long-term Adversarial Constraints](https://mlsanity.com/paper/2508.16992/) (2025)
- [Beyond Slater's Condition in Online CMDPs with Stochastic and Adversarial Constraints](https://mlsanity.com/paper/2509.20114/) (2025)
- [Truly Adapting to Adversarial Constraints in Constrained MABs](https://mlsanity.com/paper/2602.14543/) (2026)
- [Constrained Online Learning with Noisy Constraint Values](https://mlsanity.com/paper/2609.06921/) (2026)

## Abstract (arXiv)

We study online decision making problems under resource constraints, where both reward and cost functions are drawn from distributions that may change adversarially over time. We focus on two canonical settings: (i) online resource allocation where rewards and costs are observed before action selection, and (ii) online learning with resource constraints where they are observed after action selection, under full feedback or bandit feedback. It is well known that achieving sublinear regret in these settings is impossible when reward and cost distributions may change arbitrarily over time. To address this challenge, we analyze a framework in which the learner is guided by a spending plan--a sequence prescribing expected resource usage across rounds. We design general (primal-)dual methods that achieve sublinear regret with respect to baselines that follow the spending plan. Crucially, the performance of our algorithms improves when the spending plan ensures a well-balanced distribution of the budget across rounds. We additionally provide a robust variant of our methods to handle worst-case scenarios where the spending plan is highly imbalanced. To conclude, we study the regret of our algorithms when competing against benchmarks that deviate from the prescribed spending plan.