# Bandits with Knapsacks beyond the Worst-Case

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Feb 2020.

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

- [Non-stationary Bandits with Knapsacks](https://mlsanity.com/paper/2205.12427/) (2022)
- [Non-monotonic Resource Utilization in the Bandits with Knapsacks Problem](https://mlsanity.com/paper/2209.12013/) (2022)
- [Best of Many Worlds Guarantees for Online Learning with Knapsacks](https://mlsanity.com/paper/2202.13710/) (2022)
- [Contextual Decision-Making with Knapsacks Beyond the Worst Case](https://mlsanity.com/paper/2211.13952/) (2022)
- [Learning to Price with Resource Constraints: From Full Information to Machine-Learned Prices](https://mlsanity.com/paper/2501.14155/) (2025)
- [Improved Algorithms for Multi-period Multi-class Packing Problems with Bandit Feedback](https://mlsanity.com/paper/2301.13791/) (2023)

## Abstract (arXiv)

Bandits with Knapsacks (BwK) is a general model for multi-armed bandits under supply/budget constraints. While worst-case regret bounds for BwK are well-understood, we present three results that go beyond the worst-case perspective. First, we provide upper and lower bounds which amount to a full characterization for logarithmic, instance-dependent regret rates. Second, we consider "simple regret" in BwK, which tracks algorithm's performance in a given round, and prove that it is small in all but a few rounds. Third, we provide a general "reduction" from BwK to bandits which takes advantage of some known helpful structure, and apply this reduction to combinatorial semi-bandits, linear contextual bandits, and multinomial-logit bandits. Our results build on the BwK algorithm from citetAgrawalDevanur-ec14, providing new analyses thereof.