Non-stationary Bandits with Knapsacks without Variation Knowledge

In pay-per-click advertising, dynamic pricing, and crowdsourcing, each pull spends a hard budget that is not refilled, and the means can change over time. A better arm may appear only after the budget that would have paid for it has already been spent. If the variation \(V\) is known, existing work achieves a regret bound that depends on \(V\). However, \(V\) is usually unknown in advance, so the change and the rewards must be learned on the same hard budget. Throwing away old pulls does not return the budget already spent. We prove that an extra gap \(\Gamma_b\) is necessary even if \(V\) is given. Two worlds share the first half of the rounds and the same \(V\), and then move in opposite directions. Any algorithm pays \(\Gamma_b\) on one of them, since being told \(V\) does not say whether to spend early or to save the budget for later. We design Vector-MASTER, which is not told \(V\) and spends one shared budget. For constant \(b\) its regret is \(\widetilde O\big(mT+m^1/3(V_1+dV_2)^1/3T^2/3\big)+\Gamma_b\). The added term is this necessary gap, and nothing larger is charged when the gap is zero.