- 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
-
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.
-
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
- 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?
W1 / Q1. Applying MASTER as a black box
Suppose we feed Wei and Luo's MASTER the priced reward Rt−qZt. Take two stationary arms with (reward, cost) pairs (1,1) and (1/2,1/4) and budget B=T/2. At the optimal LP price q=2/3, both arms give priced reward 1/3. A policy can always choose the cheap arm and earn T/2 with zero regret on that feedback. For T divisible by six, playing the expensive arm a third of the time earns 2T/3 and uses the full budget.
Zero regret on the priced rewards can leave T/6 of BwK regret. The policy leaves T/4 units of budget unused, worth (2/3)(T/4)=T/6. For a price q that is optimal in every round, the regret against the sum of per-round LPs equals the scalar regret plus q(B−∑tZt) (Appendix I).
Vector-MASTER targets the per-round LP at the reserve rate b′=(B−1)/T. Here the target is 2/3−2/(3T), above the cheap arm's 1/2. The proof sums the actual minus predicted spending Ej(I)=∑t∈I(Zt,j−h~t,j) across learners sharing resource j. A fixed LP price bounds a replay's extra reward by q⊤E(I) plus drift and sampling terms. If resource j crosses the reserve at τ, then b′(T−τ)<Ej([1,τ]). 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/2 with costs initially 1/4. The higher-paying arm jumps to cost 7/8 halfway through and then drifts by O(T−3/2) per round. Switching to the cheaper arm at the jump spends 1/4 each round and attains both LPs, so Γb=0. Liu et al.'s window keeps the cost estimate low after the jump, leading to Ω(w) expensive pulls in expectation and Ω(T2/3) regret at their prescribed width w. The one jump and O(T−1/2) residual drift give Vector-MASTER O(T) regret (Appendices J and K.2).
W2. Notation and the replay test
Γb is the global LP value minus the sum of per-round LP values at rate B/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).