# Non-stationary Bandits with Knapsacks arXiv: https://arxiv.org/abs/2205.12427 ยท HTML: https://mlsanity.com/paper/2205.12427/ ## Key facts - Cited by 25 papers in the map (data through 14 Oct 2026). - Builds on 16 of its 33 references that are in the map. - First posted on arXiv 25 May 2022. ## Builds on (most cited first, 16 of 16) - [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013) - [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013) - [Online Convex Optimization with Stochastic Constraints](https://mlsanity.com/paper/1708.03741/) (2017) - [Learning to Optimize under Non-Stationarity](https://mlsanity.com/paper/1810.03024/) (2018) - [Bandits with concave rewards and convex knapsacks](https://mlsanity.com/paper/1402.5758/) (2014) - [Adversarial Bandits with Knapsacks](https://mlsanity.com/paper/1811.11881/) (2018) - [Adaptive Algorithms for Online Convex Optimization with Long-term Constraints](https://mlsanity.com/paper/1512.07422/) (2015) - [Online Convex Optimization with Time-Varying Constraints](https://mlsanity.com/paper/1702.04783/) (2017) - [Online convex optimization for cumulative constraints](https://mlsanity.com/paper/1802.06472/) (2018) - [Regret and Cumulative Constraint Violation Analysis for Online Convex Optimization with Long Term Constraints](https://mlsanity.com/paper/2106.05135/) (2021) - [Online Primal-Dual Mirror Descent under Stochastic Constraints](https://mlsanity.com/paper/1908.00305/) (2019) - [The Symmetry between Arms and Knapsacks: A Primal-Dual Approach for Bandits with Knapsacks](https://mlsanity.com/paper/2102.06385/) (2021) - [Regret Bounds for Generalized Linear Bandits under Parameter Drift](https://mlsanity.com/paper/2103.05750/) (2021) - [Unifying the stochastic and the adversarial Bandits with Knapsack](https://mlsanity.com/paper/1811.12253/) (2018) - [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, 25 of 25) - [Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regression](https://mlsanity.com/paper/2211.07484/) (2022) - [Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints](https://mlsanity.com/paper/2405.16118/) (2024) - [Rectified Pessimistic-Optimistic Learning for Stochastic Continuum-armed Bandit with Constraints](https://mlsanity.com/paper/2211.14720/) (2022) - [Approximately Stationary Bandits with Knapsacks](https://mlsanity.com/paper/2302.14686/) (2023) - [No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization](https://mlsanity.com/paper/2405.06575/) (2024) - [Online Decision Deferral under Budget Constraints](https://mlsanity.com/paper/2409.20489/) (2024) - [High-dimensional Linear Bandits with Knapsacks](https://mlsanity.com/paper/2311.01327/) (2023) - [Learning to Price with Resource Constraints: From Full Information to Machine-Learned Prices](https://mlsanity.com/paper/2501.14155/) (2025) - [A New Benchmark for Online Learning with Budget-Balancing Constraints](https://mlsanity.com/paper/2503.14796/) (2025) - [Online Decision Making with Generative Action Sets](https://mlsanity.com/paper/2509.25777/) (2025) - [Cost-Aware Multi-Objective Bandits: Theory and Application to Budgeted LLM Configuration Evaluation](https://mlsanity.com/paper/2608.04333/) (2026) - [Cross-Epoch Adaptive Rollout Optimization for RL Post-Training](https://mlsanity.com/paper/2606.05606/) (2026) - [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) - [Learning with Posterior Sampling for Revenue Management under Time-varying Demand](https://mlsanity.com/paper/2405.04910/) (2024) - [Constrained Feedback Learning for Non-Stationary Multi-Armed Bandits](https://mlsanity.com/paper/2509.15073/) (2025) - [Non-Stationary Online Resource Allocation: Learning from a Single Sample](https://mlsanity.com/paper/2602.18114/) (2026) - [Drift-Aware LLM Routing with Sparse Contexts and Shared Budgets](https://mlsanity.com/paper/2609.00662/) (2026) - [Constrained Online Two-stage Stochastic Optimization: Near Optimal Algorithms via Adversarial Learning](https://mlsanity.com/paper/2302.00997/) (2023) - [Online Resource Allocation with Non-Stationary Customers](https://mlsanity.com/paper/2401.16945/) (2024) - [Bandits with Anytime Knapsacks](https://mlsanity.com/paper/2501.18560/) (2025) - [A Single-Sample Polylogarithmic Regret Bound for Nonstationary Online Linear Programming](https://mlsanity.com/paper/2603.14673/) (2026) - [Constrained user-item allocation for e-commerce marketing campaigns](https://mlsanity.com/paper/2606.09623/) (2026) - [Online LLM Selection via Constrained Bandits with Time-Varying Demand](https://mlsanity.com/paper/2606.17489/) (2026) - [From Novice to Expert: Cost-Aware Bandits for Evolving Worker Performance in Crowdsensing](https://mlsanity.com/paper/2607.13546/) (2026) ## Abstract (arXiv) In this paper, we study the problem of bandits with knapsacks (BwK) in a non-stationary environment. The BwK problem generalizes the multi-arm bandit (MAB) problem to model the resource consumption associated with playing each arm. At each time, the decision maker/player chooses to play an arm, and s/he will receive a reward and consume certain amount of resource from each of the multiple resource types. The objective is to maximize the cumulative reward over a finite horizon subject to some knapsack constraints on the resources. Existing works study the BwK problem under either a stochastic or adversarial environment. Our paper considers a non-stationary environment which continuously interpolates between these two extremes. We first show that the traditional notion of variation budget is insufficient to characterize the non-stationarity of the BwK problem for a sublinear regret due to the presence of the constraints, and then we propose a new notion of global non-stationarity measure. We employ both non-stationarity measures to derive upper and lower bounds for the problem. Our results are based on a primal-dual analysis of the underlying linear programs and highlight the interplay between the constraints and the non-stationarity. Finally, we also extend the non-stationarity measure to the problem of online convex optimization with constraints and obtain new regret bounds accordingly.