# Logarithmic regret bounds for Bandits with Knapsacks

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Oct 2015.

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

- [Non-stationary Bandits with Knapsacks](https://mlsanity.com/paper/2205.12427/) (2022)
- [The Symmetry between Arms and Knapsacks: A Primal-Dual Approach for Bandits with Knapsacks](https://mlsanity.com/paper/2102.06385/) (2021)
- [Non-monotonic Resource Utilization in the Bandits with Knapsacks Problem](https://mlsanity.com/paper/2209.12013/) (2022)
- [A Lyapunov-Based Methodology for Constrained Optimization with Bandit Feedback](https://mlsanity.com/paper/2106.05165/) (2021)
- [Contextual Decision-Making with Knapsacks Beyond the Worst Case](https://mlsanity.com/paper/2211.13952/) (2022)
- [Bandits with Anytime Knapsacks](https://mlsanity.com/paper/2501.18560/) (2025)
- [Reoptimization Algorithms for Contextual Bandits with Knapsack Constraints](https://mlsanity.com/paper/2608.11383/) (2026)

## Abstract (arXiv)

Optimal regret bounds for Multi-Armed Bandit problems are now well documented. They can be classified into two categories based on the growth rate with respect to the time horizon T: (i) small, distribution-dependent, bounds of order of magnitude ln(T) and (ii) robust, distribution-free, bounds of order of magnitude √T. The Bandits with Knapsacks model, an extension to the framework allowing to model resource consumption, lacks this clear-cut distinction. While several algorithms have been shown to achieve asymptotically optimal distribution-free bounds on regret, there has been little progress toward the development of small distribution-dependent regret bounds. We partially bridge the gap by designing a general-purpose algorithm with distribution-dependent regret bounds that are logarithmic in the initial endowments of resources in several important cases that cover many practical applications, including dynamic pricing with limited supply, bid optimization in online advertisement auctions, and dynamic procurement.