Piecewise-Stationary Bandits with Knapsacks

We propose a novel inventory reserving algorithm which draws new insights into Bandits with Knapsacks (Bwk) problems in piecewise-stationary environments. Suppose parameters η min , η max P p0, 1s respectively lower and upper bound the ratio between the reward earned and the resources consumed in a round. Our algorithm achieves a provably near-optimal competitive ratio of Oplogpη max η min qq, with a matching lower bound provided. Our performance guarantee is based on a dynamic benchmark that upper bounds the optimum, different from existing works on adversarial Bwk Immorlica et al. (2019); Kesselheim and Singla (2020) who compare with the stationary benchmark. Different from existing non-stationary Bwk work Liu et al. (2022), we do not require a bounded global variation. Adversarial Bwk is firstly considered in Immorlica et al. ( 2019) where pr t , c t q " tpr t paq, c t paqqu aPK can change arbitrarily over the horizon. They achieve a competitive ratio (CR) of Opd logpT qq with respect to a static benchmark when there are d budget constraints. A static benchmark picks a fixed optimal action (or a fixed optimal distribution over arms), and applies the same action (or distribution) in all T rounds. Kesselheim and Singla ( 2020)further improve the CR to Oplogpdq logpT qq. Other papers consider different regimes such as unlimited rounds (Rangi et al. (2018)), large budget B " ΩpT q (Castiglioni et al. (2022a)), strict feasibility (Castiglioni et al. (2022b)) and approximate stationarity (Fikioris and Tardos (2023)). All these works compare with static benchmarks (see Appendix A.1). Moreover, adversarial Bwk could be too conservative in certain real-life scenarios. For instance, sales patterns could be stationary for a duration of time, but only change during periods of hot seasons/promotions/new trends, which fits into our piecewise-stationary Bwk regime. 38th Conference on Neural Information Processing Systems (NeurIPS 2024).