Skip to yearly menu bar Skip to main content


Poster

Piecewise-Stationary Bandits with Knapsacks

Xilin Zhang · Wang Chi Cheung

[ ]
Wed 11 Dec 4:30 p.m. PST — 7:30 p.m. PST

Abstract: We study Bandits with Knapsacks (Bwk) in a piecewise-stationary environment. We propose a novel inventory reserving algorithm which draws new insights into the problem. Suppose parameters $\eta_{\min}, \eta_{\max} \in (0,1]$ respectively lower and upper bound the reward earned and the resources consumed in a time round. Our algorithm achieves a provably near-optimal competitive ratio of $O(\log(\eta_{\max}/\eta_{\min}))$, with a matching lower bound provided. Our performance guarantee is based on a dynamic benchmark, distinguishing our work from existing works on adversarial Bwk who compare with the static benchmark. Furthermore, different from existing non-stationary Bwk work, we do not require a bounded global variation.

Live content is unavailable. Log in and register to view live content