# Non-monotonic Resource Utilization in the Bandits with Knapsacks Problem

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 23 references that are in the map.
- First posted on arXiv 24 Sep 2022.

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

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [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)
- [Bandits and Experts in Metric Spaces](https://mlsanity.com/paper/1312.1277/) (2013)
- [The Symmetry between Arms and Knapsacks: A Primal-Dual Approach for Bandits with Knapsacks](https://mlsanity.com/paper/2102.06385/) (2021)
- [Logarithmic regret bounds for Bandits with Knapsacks](https://mlsanity.com/paper/1510.01800/) (2015)
- [Bandits with Knapsacks beyond the Worst-Case](https://mlsanity.com/paper/2002.00253/) (2020)

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

- [Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regression](https://mlsanity.com/paper/2211.07484/) (2022)
- [No-Regret Learning in Bilateral Trade via Global Budget Balance](https://mlsanity.com/paper/2310.12370/) (2023)
- [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)
- [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)
- [Learning to Price with Resource Constraints: From Full Information to Machine-Learned Prices](https://mlsanity.com/paper/2501.14155/) (2025)
- [Constrained Online Decision-Making: A Unified Framework](https://mlsanity.com/paper/2505.07101/) (2025)
- [Adaptive Multi-Round Allocation with Stochastic Arrivals](https://mlsanity.com/paper/2605.12111/) (2026)
- [Bandits with Anytime Knapsacks](https://mlsanity.com/paper/2501.18560/) (2025)
- [Multi-Armed Bandits with Minimum Aggregated Revenue Constraints](https://mlsanity.com/paper/2510.12523/) (2025)

## Abstract (arXiv)

Bandits with knapsacks (BwK) is an influential model of sequential decision-making under uncertainty that incorporates resource consumption constraints. In each round, the decision-maker observes an outcome consisting of a reward and a vector of nonnegative resource consumptions, and the budget of each resource is decremented by its consumption. In this paper we introduce a natural generalization of the stochastic BwK problem that allows non-monotonic resource utilization. In each round, the decision-maker observes an outcome consisting of a reward and a vector of resource drifts that can be positive, negative or zero, and the budget of each resource is incremented by its drift. Our main result is a Markov decision process (MDP) policy that has constant regret against a linear programming (LP) relaxation when the decision-maker knows the true outcome distributions. We build upon this to develop a learning algorithm that has logarithmic regret against the same LP relaxation when the decision-maker does not know the true outcome distributions. We also present a reduction from BwK to our model that shows our regret bound matches existing results.