Piecewise-Stationary Bandits with Knapsacks

Many real-world problems involve dynamically changing reward structures, such as online advertising or dynamic pricing. The ‘bandits with knapsacks’ (BwK) problem models such scenarios, but existing solutions often assume stationary reward distributions or impose strict constraints on how the rewards can change over time. These assumptions limit the applicability of these methods to real-world problems, where reward structures often shift gradually or in sudden changes. This paper tackles these issues by considering piecewise-stationary environments where the reward structure changes between periods of stability.

The authors introduce a novel algorithm called IRES-CM that cleverly reserves resources based on an estimated reward-consumption ratio. This approach cleverly balances exploration and exploitation across different phases of the reward distribution. The key contribution is a theoretical guarantee showing that this algorithm achieves a near-optimal competitive ratio (a measure of performance relative to an ideal algorithm) that depends only on the ratio between the minimum and maximum reward earned per unit resource, without strong assumptions on how often the distribution changes. This result significantly advances the understanding and handling of non-stationary BwK problems.