# Unifying the stochastic and the adversarial Bandits with Knapsack

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Oct 2018.

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

- [Non-stationary Bandits with Knapsacks](https://mlsanity.com/paper/2205.12427/) (2022)
- [Saving Stochastic Bandits from Poisoning Attacks via Limited Data Verification](https://mlsanity.com/paper/2102.07711/) (2021)
- [Approximately Stationary Bandits with Knapsacks](https://mlsanity.com/paper/2302.14686/) (2023)
- [Online Learning under Budget and ROI Constraints via Weak Adaptivity](https://mlsanity.com/paper/2302.01203/) (2023)
- [Best of Many Worlds Guarantees for Online Learning with Knapsacks](https://mlsanity.com/paper/2202.13710/) (2022)
- [Sequential Choice Bandits with Feedback for Personalizing users' experience](https://mlsanity.com/paper/2101.01572/) (2021)
- [Online Resource Allocation: Bandits feedback and Advice on Time-varying Demands](https://mlsanity.com/paper/2302.04182/) (2023)
- [Constrained Online Two-stage Stochastic Optimization: Algorithm with (and without) Predictions](https://mlsanity.com/paper/2401.01077/) (2024)
- [Constrained Online Two-stage Stochastic Optimization: Near Optimal Algorithms via Adversarial Learning](https://mlsanity.com/paper/2302.00997/) (2023)
- [Clustered Linear Contextual Bandits with Knapsacks](https://mlsanity.com/paper/2308.10722/) (2023)
- [Online Bidding Algorithms with Strict Return on Spend (ROS) Constraint](https://mlsanity.com/paper/2502.05599/) (2025)
- [From Novice to Expert: Cost-Aware Bandits for Evolving Worker Performance in Crowdsensing](https://mlsanity.com/paper/2607.13546/) (2026)

## Abstract (arXiv)

This paper investigates the adversarial Bandits with Knapsack (BwK) online learning problem, where a player repeatedly chooses to perform an action, pays the corresponding cost, and receives a reward associated with the action. The player is constrained by the maximum budget B that can be spent to perform actions, and the rewards and the costs of the actions are assigned by an adversary. This problem has only been studied in the restricted setting where the reward of an action is greater than the cost of the action, while we provide a solution in the general setting. Namely, we propose EXP3.BwK, a novel algorithm that achieves order optimal regret. We also propose EXP3++.BwK, which is order optimal in the adversarial BwK setup, and incurs an almost optimal expected regret with an additional factor of log(B) in the stochastic BwK setup. Finally, we investigate the case of having large costs for the actions (i.e., they are comparable to the budget size B), and show that for the adversarial setting, achievable regret bounds can be significantly worse, compared to the case of having costs bounded by a constant, which is a common assumption within the BwK literature.