acceptodds
Under review as a conference paper at ICLR 2027

Non-stationary Bandits with Knapsacks without Variation Knowledge

Abstract

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.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Bandits, online learning, nonstationary learning

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_tS3iOpenReview ↗
Rating
3
Confidence
2
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

The paper works with the well-known bandits with knapsacks framework for online resource allocation under uncertainty. The case of non-stationary rewards and consumptions within this framework was addressed by Liu et al. 2022. However, their algorithm required the knowledge of a variation bound across time. The present paper proposes an algorithm that achieves essentially the same performance without that knowledge.

Critical strengths

This is a clear theoretical contribution and a meaningful advance in bandit non-stationary learning. The BwK framework has several applications across various domains, and thus the contribution has practical value.

Critical weaknesses
  1. The main technical novelty of the paper rests on distinction from two works: Liu et. al 2022, and the black-box approach of Wei and Luo for achieving optimal regret bounds for non-stationary bandits without variation knowledge. In particular, the paper's approach seems to be an adaptation of the latter. The paper does not sufficiently discuss the inherent difficulties in this adaptation and hence it is unclear if this adaptation is non-trivial enough to merit a strong contribution.

  2. The paper uses AI editing (as acknowledged by the authors), which makes several sections difficult to comprehend due to unnecessary reversals and comparisons. Some notation is used before it is introduced.

Questions for authors
  1. Can you elucidate key difficulties in directly applying Wei and Luo's black-box approach to this setting? How does your approach overcome those difficulties?
1 comment

W1 / Q1. Applying MASTER as a black box

Suppose we feed Wei and Luo's MASTER the priced reward Rt−qZtR_t-qZ_t. Take two stationary arms with (reward, cost) pairs (1,1)(1,1) and (1/2,1/4)(1/2,1/4) and budget B=T/2B=T/2. At the optimal LP price q=2/3q=2/3, both arms give priced reward 1/31/3. A policy can always choose the cheap arm and earn T/2T/2 with zero regret on that feedback. For TT divisible by six, playing the expensive arm a third of the time earns 2T/32T/3 and uses the full budget.

Zero regret on the priced rewards can leave T/6T/6 of BwK regret. The policy leaves T/4T/4 units of budget unused, worth (2/3)(T/4)=T/6(2/3)(T/4)=T/6. For a price qq that is optimal in every round, the regret against the sum of per-round LPs equals the scalar regret plus q(B−∑tZt)q(B-\sum_t Z_t) (Appendix I).

Vector-MASTER targets the per-round LP at the reserve rate b′=(B−1)/Tb'=(B-1)/T. Here the target is 2/3−2/(3T)2/3-2/(3T), above the cheap arm's 1/21/2. The proof sums the actual minus predicted spending Ej(I)=∑t∈I(Zt,j−h~t,j)E_j(I)=\sum_{t\in I}(Z_{t,j}-\tilde h_{t,j}) across learners sharing resource jj. A fixed LP price bounds a replay's extra reward by q⊤E(I)q^\top E(I) plus drift and sampling terms. If resource jj crosses the reserve at τ\tau, then b′(T−τ)<Ej([1,τ])b'(T-\tau)<E_j([1,\tau]). These bounds control T1 and the reward lost after stopping (11, 12, 16, 17h).

For the comparison with Liu et al., take arms paying 1 and 1/21/2 with costs initially 1/41/4. The higher-paying arm jumps to cost 7/87/8 halfway through and then drifts by O(T−3/2)O(T^{-3/2}) per round. Switching to the cheaper arm at the jump spends 1/41/4 each round and attains both LPs, so Γb=0\Gamma_b=0. Liu et al.'s window keeps the cost estimate low after the jump, leading to Ω(w)\Omega(w) expensive pulls in expectation and Ω~(T2/3)\widetilde\Omega(T^{2/3}) regret at their prescribed width ww. The one jump and O(T−1/2)O(T^{-1/2}) residual drift give Vector-MASTER O~(T)\widetilde O(\sqrt T) regret (Appendices J and K.2).

W2. Notation and the replay test

Γb\Gamma_b is the global LP value minus the sum of per-round LP values at rate B/TB/T. A replay starts with fresh counts and uses the remaining budget. T1 compares the completed replay interval's average reward with the lowest reward prediction since the block began. These are now stated where we introduce the benchmark, the replay and the test (Sections 3, 4.1 and 4.3).

Reviewer_vVaHOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper studies non-stationary bandits with knapsacks when the variation in rewards and resource consumption is unknown. The proposed algorithm, Vector-MASTER, combines a UCB-BwK learner with randomized replays and restart tests, with all instances using the same budget. Under the stated parameter assumptions, it recovers the leading tracking rate of methods that require prior knowledge of the variation. The regret bound also retains Γb\Gamma_b, the gap between the global budget LP and the sum of per-round LP values. A two-environment lower bound shows that this allocation gap can remain unavoidable even when the variation is known.

Critical strengths
  1. Removing the need to know the variation budget is a meaningful extension of the existing non-stationary BwK results. The algorithm adapts to the amount of change without requiring a window length tuned to that quantity, while preserving the leading tracking rate.

  2. The decomposition into a tracking term and an allocation gap makes the guarantee easier to interpret. Keeping Γb\Gamma_b explicitly avoids charging a large global-deviation term when cross-time budget allocation offers no benefit. The lower bound also clarifies why knowing the total variation does not resolve the spend-or-save decision.

Critical weaknesses
  1. The presentation needs substantial improvement. I found the paper difficult to follow, particularly when trying to understand the main result and its relation to prior work. The allocation gap Γb\Gamma_b is central to the abstract and introduction, but is only formally discussed in Section 5. Although some intuition is given earlier, its role in the guarantee remains unclear for much of the paper. The relationship between WW and Γb\Gamma_b, and the separate role of the replay parameter γ\gamma, should also be explained more clearly. This makes it difficult to identify the precise contribution and why it matters. Moreover, I think this paper lacks detailed discussion of the related applications, motivations and contributions for the proposed methods.

  2. The algorithmic contribution appears incremental. The main idea is to combine an existing BwK learner with standard techniques for adapting to unknown variation, namely multiscale randomized replays and restart tests. Applying these techniques to remove the known-VV assumption seems like a fairly natural extension of the existing approach. While the shared budget introduces technical complications, I find the overall construction intuitive and the additional algorithmic insight limited. The paper does not seem to offer much beyond adapting a familiar framework to this setting.

  3. The progress over prior guarantees is not sufficiently established. Removing advance knowledge of VV makes sense, but the leading tracking rate remains largely the same as in the variation-aware setting. The additional improvement attributed to Γb\Gamma_b also needs more careful positioning: [1] already compare the same global and per-round LP values and bound their difference. It is therefore unclear whether retaining Γb\Gamma_b provides an advantage specific to the proposed algorithm or is a refinement that could also be applied to the earlier analysis. The comparison should distinguish this analytical refinement from the contribution of adapting to unknown variation.

[1] Non-stationary Bandits with Knapsacks.

Questions for authors
  1. Could the authors give a clearer account of the motivation, intended applications, and main contribution? In particular, concrete examples connecting the model to applications would help. The algorithm and theoretical results also need a more accessible explanation, so that readers can understand why the proposed mechanisms are needed, what the guarantee means, and what progress it represents.

  2. Could the authors clarify the novelty and technical justification relative to prior work? In particular, what new ideas are required to extend the existing adaptation framework to shared hard budgets, and how do the proofs establish that this extension is valid? The comparison with earlier BwK results should also distinguish the benefit of removing knowledge of VV from the refinement of the allocation-gap term.

  3. Would the authors consider adding an evaluation on real-world data to assess the method’s practical value? This would be useful in helping understand the practicalness of the methodology.

Note that my main concerns remain the clarity of the presentation and the extent and justification of the contribution, and the third suggestion on experiments remain as a secondary suggestion.

2 comments

W3 / Q2. The comparison with Liu et al.

On a family with one cost jump and Γb=0\Gamma_b=0, Vector-MASTER has O~(T)\widetilde O(\sqrt T) expected regret. The windows prescribed by Liu et al. incur Ω~(T2/3)\widetilde\Omega(T^{2/3}) even with the true variation totals.

Take two arms paying 1 and 1/21/2 and costing 1/41/4 each, with budget T/4T/4. At the midpoint, the first arm's cost jumps to 7/87/8 and then drifts by O(T−3/2)O(T^{-3/2}) per step. Switching to the cheaper arm at the jump attains the global LP by spending 1/41/4 each round, so Γb=0\Gamma_b=0. For the first ⌊w/16⌋\lfloor w/16\rfloor rounds after the jump, old samples keep the first arm's estimated cost at most 5/165/16. The optimistic LP is worth at least 3U/43U/4, where UU is the largest reward index, and well-sampled alternatives have indices at most 5U/85U/8. So at least 1/31/3 of the mass goes to the first arm or under-sampled alternatives. The latter take only O(log⁡T)O(\log T) pulls. Each expensive pull loses at least 1/81/8 at price 1, giving Ω(w)\Omega(w) expected regret for Liu et al.'s w=Θ~(T2/3)w=\widetilde\Theta(T^{2/3}) (Appendix K.2).

Mark any kk boundaries. Let DD sum the largest absolute changes in reward and cost means over unmarked boundaries, with costs scaled by 1/b′1/b' for b′=(B−1)/Tb'=(B-1)/T. At fixed bb, dimensions and γ\gamma, with probability at least 1−δ1-\delta the same run satisfies the following for every choice of marks, with Rt=0R_t=0 after stopping.

\le \widetilde O\bigl(\sqrt{(k+1)T}+T^{2/3}D^{1/3}\bigr)+\Gamma_b+O(b^{-1}).$$ At most $k$ restarted epochs contain a mark. Each remaining restarted epoch $E$ needs drift $\Delta_E$ of order at least $1/\sqrt{|E|}$. Their count is bounded up to logs by $\sum_E\Delta_E^{2/3}|E|^{1/3}\le D^{2/3}T^{1/3}$. Inside each block, extending a nonfinal low-drift piece by one round crosses the drift threshold, so the same count applies. We add the final piece and sum square-root costs by Cauchy–Schwarz (Appendix J). Here one mark leaves $D=O(T^{-1/2})$. With $\delta=T^{-2}$ this gives the expected square-root rate up to logs. Table 1 keeps $\Gamma_b$ in both bounds. ### W2 / Q2. The replay proof and the budget stop Several learners can play within one replay interval. We sum their errors separately for each resource to bound $E_j(I)=\sum_{t\in I}(Z_{t,j}-\tilde h_{t,j})$. At fixed resource prices $q$, extra spending raises the replay's reward by at most $q^\top E(I)$ plus drift and sampling terms. The bound keeps T1 below its threshold on nearly stationary data (11, 16). At a reserve crossing on round $\tau$, the resource $j$ that crosses has actual spending above $b'T$ and predicted spending of at most $b'\tau$. Thus $T-\tau<E_j([1,\tau])/b'$. T2C bounds that sum on the prefix of each block through its penultimate round. The last pull contributes at most one more unit in each block (17h). The block can end at a random time. We decide whether a replay start is eligible using the history at that start. At a scale with scheduling probability $p$, the chance of $n$ eligible failures before a success is at most $(1-p)^n$. After a sufficiently low prediction, a replay that finishes in the same nearly stationary piece before the block ends would trigger T1. The failure bound controls how long the block can continue with a low prediction (17a–17b). ### W1 / Q1. Bidding with one budget A bid that works in the morning may buy fewer impressions in the afternoon. The tracking term measures the clicks lost while learning the best bid mixture at a fixed spending rate. The allocation gap $\Gamma_b=\mathrm{LP}_{\rm glob}(B)-\sum_t\phi_t(b)$ measures how many more clicks the LP can get by moving budget between hours. The global deviations $W_1,W_2$ measure how far rewards and costs move from their time averages. They give the upper bound $W_1+2\bar q W_2$ on that gain, with $\bar q$ the price bound (Sections 3 and 5). The parameter $\gamma$ sets how often the learner tries a fresh replay. ### Q3. Replay on logged impressions We replayed 100,000 held-out impressions from iPinYou campaign 1458, choosing one bid per 100 impressions. A bid above the logged price pays that price and receives the recorded click, if any. The two caps are 25% and 50% of projected spend at the mean training price. The table averages 30 policy seeds on the same trace. | Policy | Clicks at tighter cap | Spend / tighter cap | Clicks at twice the cap | |---|---:|---:|---:| | Vector-MASTER | **17.10** | 98.4% | 34.70 | | ADWIN-UCB-BwK | 15.23 | 98.4% | 34.70 | | Fixed window | 15.03 | 98.3% | 31.00 | | Stationary UCB-BwK | 16.27 | 98.4% | 35.80 | At the tighter cap, Vector-MASTER gets 1.87 more clicks than ADWIN at about the same spend (paired 95% bootstrap interval [0.70, 3.10] on this trace, Appendix L.3).

Thanks the authors for responding. Their response has partially addressed my concerns about the comparison with prior work. I also appreciate much that they added an experiment on real-world data.

However, I believe the presentation still needs substantial improvement, as I still find the paper difficult to follow (lack of motivation discussion, unclear contributions, quite short introduction, etc). The algorithm design also remains incremental in my view since its main idea is a fairly natural combination of existing methods and techniques.

I believe the paper would benefit from further revision and therefore maintain my original score.

Reviewer_DkdWOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

This paper investigates the non-stationary Bandits with Knapsacks (BwK) problem where the magnitude of change is unknown. It focuses on scenarios where both rewards and resource consumption drift over time, and under hard-stopping budget setting. The authors propose Vector-MASTER, which achieves adaptive learning through multi-scale stochastic replay, detection of shifts in rewards and consumption, and a ledger for the non-resettable shared budget. Theoretically, the algorithm attains a local tracking error of the same order as methods that assume prior knowledge of the change magnitudes (V1,V2V_1, V_2). The paper also introduces Γb\Gamma_b to characterize the additional gap arising from the allocation of a shared budget across time, and proves that this term is unavoidable.

Critical strengths
  • The problem of removing the need for prior knowledge of variation budgets in non-stationary BwK is a meaningful problem. It is important and has many good applications. The algorithm's performance guarantee is established.
Critical weaknesses
  • The proposed approach appears to largely combine the MASTER framework of Wei and Luo (2021) with the UCB-based BwK techniques of Liu et al. (2022). The multi-scale replay, stationarity tests, and restart mechanisms are already well established. The shared-budget implementation and consumption-based tests provide adaptations to BwK, but it is not sufficiently clear which technical developments are fundamentally new.

  • The paper replaces the global variation penalty W1+qˉW2W_1+\bar q W_2 in Liu et al. (2022) with the allocation gap Γb\Gamma_b. While this may provide a tighter characterization of regret, the global LP and its comparison with per-round LPs are already central to Liu et al. (2022). It is therefore unclear whether this improvement requires fundamentally new analysis or simply follows from retaining the exact LP gap rather than upper-bounding it by global variation measures. .

  • The experiments consider only a few highly simplified synthetic environments, with two of the main instances being deterministic. Although stationary UCB-BwK and sliding-window references are included, the experiments do not provide convincing comparisons with competitive non-stationary BwK methods, particularly the approach of Liu et al. (2022). For example, we can just make the fixed T2/3T^{2/3} sliding-window baseline, which does not require knowledge of the variation budget and therefore appears to be a legitimate prior-free comparison.

  • The paper is difficult to follow. Some key notations are used before being clearly defined. Moreover, the algorithm needs more detailed explanation, particularly the intuition and motivation behind its main components and how they work together.

Questions for authors

Please see the weakness above.

2 comments

W1. Why MASTER needs a spending bound

An arm that pays and costs 1 earns 1 per pull. At spending rate 1/21/2, the per-round LP is worth 1/21/2. So a replay can beat the LP on stationary data just by spending faster.

On a completed replay interval II, write Ej(I)=∑t∈I(Zt,j−h~t,j)E_j(I)=\sum_{t\in I}(Z_{t,j}-\tilde h_{t,j}) for actual minus predicted spending of resource jj. Each learner plays an initial segment of its own history in II. When drift ΔI\Delta_I is small, summing their bounds on the dyadic schedule gives Ej(I)≤O~(∣I∣+∣I∣ΔI)E_j(I)\le\widetilde O(\sqrt{|I|}+|I|\Delta_I) at fixed budget fraction and dimensions. A fixed LP price qq bounds excess reward by q⊤E(I)q^\top E(I) plus drift and sampling terms. That keeps T1 below its threshold (11, 16).

If resource jj crosses the reserve at τ\tau, actual spending exceeds b′Tb'T and predicted spending is at most b′τb'\tau, where b′=(B−1)/Tb'=(B-1)/T. Thus b′(T−τ)<Ej([1,τ])b'(T-\tau)<E_j([1,\tau]). T2C bounds the error through each block's penultimate round. The last pull adds at most one unit (12, 17h).

W2. What the allocation gap adds

Take even TT, integer budget 2≤B≤T/22\le B\le T/2, a null arm and a unit-cost arm paying 1/21/2 in the first half and 1/2±η1/2\pm\eta in the second, with 0<η≤1/20<\eta\le1/2. The planner spends all BB in the better half. Both paths have V1=ηV_1=\eta, V2=0V_2=0 and Γb=ηB/2\Gamma_b=\eta B/2. Spending nn in expectation in the first half costs at least ηn\eta n in regret on the rising path and η(B−n)\eta(B-n) on the falling path. One regret is at least Γb\Gamma_b even with the true variation totals (Theorem 3).

The gap can differ even with fixed costs and identical V1,W1V_1,W_1. With two unit-cost arms and B=T/2B=T/2, rewards (1/2,0)(1/2,0) jump to either (1/2,1/4)(1/2,1/4) or (3/4,0)(3/4,0). The gaps are 00 and T/16T/16. Table 1 keeps the exact gap for both methods. In Liu et al.'s proof, subtracting the per-round LPs before stopping from the global LP leaves Γb+∑t=τTϕt(b)\Gamma_b+\sum_{t=\tau}^T\phi_t(b) (Appendix I).

W3. The window comparisons

Any fixed cost window for SW-UCB-BwK with full reward history incurs Ω(T2/3)\Omega(T^{2/3}) regret on one of two paths with identical variation totals. Vector-MASTER has O~(T)\widetilde O(\sqrt T) on both. Take b=1/4b=1/4 and ϵ=T−1/3/2\epsilon=T^{-1/3}/2. On the first path, rewards are (1,1−2ϵ,0)(1,1-2\epsilon,0) and costs start at (b+ϵ,b,b)(b+\epsilon,b,b). At the midpoint, the zero-reward arm's cost jumps by 5/85/8. A window w≤⌈T2/3⌉w\le\lceil T^{2/3}\rceil makes the first arm look affordable, leading to Ω(T)\Omega(T) pulls at a loss of ϵ\epsilon each at price 3. On the second path, rewards are (1,1/2,0)(1,1/2,0), all costs start at bb, and the jump hits the first arm. For w>⌈T2/3⌉w>\lceil T^{2/3}\rceil, stale samples keep that arm's cost estimate low for ⌊w/64⌋\lfloor w/64\rfloor rounds after the jump, causing Ω(w)\Omega(w) expected regret. On both paths an optimal global allocation spends bb each round, so Γb=0\Gamma_b=0 (Appendix K.3).

We tested both profiles with Bernoulli rewards and costs at T=8192T=8192, using 30 paired seeds per profile and the same budget reserve. The table gives mean full-run pseudo-regret as a percentage of the global LP.

PolicyJump on zero-reward armJump on high-reward armLarger loss
Vector-MASTER3.90%5.19%5.19%
Common ⌈T2/3⌉\lceil T^{2/3}\rceil window2.65%6.17%6.17%
Best of six swept cost windows3.57%5.72%5.72%
Liu et al.'s lengths, common bonus3.21%10.60%10.60%
Liu et al.'s lengths, published radii2.74%15.12%15.12%
ADWIN-UCB-BwK4.02%4.21%4.21%

The sweep keeps all reward samples and minimizes the last column. Vector-MASTER uses γ=1/16\gamma=1/16 from separate pilots. On the high-reward jump its paired gain over the common window is 0.98 points (95% interval [0.54, 1.36]). At T=2048T=2048 the larger losses are 8.61% for the common window and 9.23% for Vector-MASTER (Appendix L.2).

Figure 1 uses the suggested horizon-only window. With equal costs and reward gap of order log⁡T/w\sqrt{\log T/w}, once the window fills, playing the better arm requires more than w/4w/4 pulls of the worse arm in the window. Each such pull enters at most ww windows, forcing Ω(T)\Omega(T) inferior pulls and Ω(T2/3)\Omega(T^{2/3}) regret on stationary data (Appendix K.1).

With Bernoulli outcomes and random jump times, Vector-MASTER gains 10.22 and 13.35 points of the global LP over ADWIN on the reward and joint-change examples (T=8192T=8192, 40 paired paths each). The common window leads in these settings (Appendix L.1).

W4. The notation and the three tests

Γb\Gamma_b is the global LP value minus ∑tϕt(b)\sum_t\phi_t(b), the value at a fixed per-round rate bb. A replay starts with fresh counts and uses the remaining budget. T1 compares its interval's average reward with the lowest reward prediction in the block so far. T2R checks for reward shortfall and T2C checks excess spending by resource on the current prefix. We state these next to the benchmark, the replay and the tests (Sections 3 and 4).

AuthorsOpenReview ↗

We are keen to discuss further with you

Dear Reviewer DkdW,

Thanks again for your time and effort. As the deadline for the discussion period is approaching, we would greatly appreciate it if you could kindly let us know whether our responses solve your concerns and/or there are any further questions.

Thank you so much for your attention to our work.

Warmest regards,

Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.