# Bandits with Anytime Knapsacks

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 26 references that are in the map.
- First posted on arXiv 30 Jan 2025.

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

- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challenges](https://mlsanity.com/paper/1507.08025/) (2015)
- [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)
- [Conservative Bandits](https://mlsanity.com/paper/1602.04282/) (2016)
- [Improving Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms and Its Applications](https://mlsanity.com/paper/1703.01610/) (2017)
- [Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regression](https://mlsanity.com/paper/2211.07484/) (2022)
- [Stage-wise Conservative Linear Bandits](https://mlsanity.com/paper/2010.00081/) (2020)
- [Stochastic Bandits for Multi-platform Budget Optimization in Online Advertising](https://mlsanity.com/paper/2103.10246/) (2021)
- [Non-stationary Bandits with Knapsacks](https://mlsanity.com/paper/2205.12427/) (2022)
- [Contextual Combinatorial Bandits with Probabilistically Triggered Arms](https://mlsanity.com/paper/2303.17110/) (2023)
- [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)
- [Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints](https://mlsanity.com/paper/2405.16118/) (2024)
- [Dynamic Ad Allocation: Bandits with Budgets](https://mlsanity.com/paper/1306.0155/) (2013)
- [Logarithmic regret bounds for Bandits with Knapsacks](https://mlsanity.com/paper/1510.01800/) (2015)
- [Thompson Sampling for Combinatorial Network Optimization in Unknown Environments](https://mlsanity.com/paper/1907.04201/) (2019)
- [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)
- [Probably Anytime-Safe Stochastic Combinatorial Semi-Bandits](https://mlsanity.com/paper/2301.13393/) (2023)

## Abstract (arXiv)

We consider bandits with anytime knapsacks (BwAK), a novel version of the BwK problem where there is an textitanytime cost constraint instead of a total cost budget. This problem setting introduces additional complexities as it mandates adherence to the constraint throughout the decision-making process. We propose SUAK (Strategic Under-utilization for Anytime Knapsacks), an algorithm that utilizes upper confidence bounds to identify the optimal mixture of arms while maintaining a balance between exploration and exploitation. SUAK is an adaptive algorithm that strategically utilizes the available budget in each round in the decision-making process and skips a round when it is possible to violate the anytime cost constraint. In particular, SUAK slightly under-utilizes the available cost budget to reduce the need for skipping rounds. We show that SUAK attains the same problem-dependent regret upper bound of  O(K log T) established in prior work under the simpler BwK framework, where K denotes the number of arms, and T denotes the time horizon. We also establish an instance-dependent lower bound showing that the O(Klog T) dependence is unavoidable. Finally, we show via extensive simulations that SUAK achieves considerably higher rewards than naive adaptations of BwK algorithms that do not optimize learning under anytime cost constraints.