- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies offline planning and online learning in recovering-reward bandits with a per-round capacity constraint. The authors propose Multiscale Buffered Interleaving (MBI), achieving a constant additive planning loss relative to a renewal LP upper bound, independent of the number of arms, capacity, and recovery horizon. They also establish a constant-order lower bound. For unknown reward curves, MBI-KL achieves an learning bound relative to an approximate planning benchmark, with a lower bound on growing instance families. Synthetic experiments show improvements over PPP and RTI-based methods.
Critical strengths
-
Strong offline planning guarantee. The capacity-independent additive bound significantly improves upon previous guarantees and applies to general nondecreasing reward curves without requiring finite saturation. The constant-order lower bound also establishes the tight order of the renewal relaxation gap.
-
Novel and technically interesting framework. The combination of lossless aggregation, multiscale buffering, and order-preserving interleaving provides a sophisticated scheduling approach. The extension to unknown reward curves further strengthens the contribution.
Critical weaknesses
-
Limited scope of the learning lower bound. Theorem 4 uses , , and , so . This does not establish the optimal dependence on and separately. For example, rates such as or are not ruled out. The matching optimality claims should more clearly distinguish this specific joint scaling from separately optimal dependencies on and .
-
Limited finite-horizon implications of the online guarantee. Theorem 3 provides approximate regret relative to (standard in this literature), rather than sublinear regret against . More importantly, the learning term becomes negligible relative to a constant-order planning gap only when , up to logarithmic factors. In the central experiments, and , giving , so the theoretical guarantee is not informative at the tested scale.
-
Experimental evidence is narrow. All experiments use synthetic reward curves with finite saturation, so the claimed generality to non-saturating curves is untested. RTI-A requires substantial initial exploration but performs better after commitment in several settings, including Table 5. Comparisons with simple heuristic baselines (e.g., greedy top- using estimated current rewards or an LP-dual index policy) and component-wise ablations of MBI are missing. The motivating AI-agent memory application is also not evaluated.
Questions for authors
Questions
-
Can the authors establish learning lower bounds that separately characterize the dependence on and , particularly for fixed or ?
-
Can the authors clarify when the approximate-regret guarantee becomes nontrivial, and whether the learning loss can be bounded relative to MBI with known reward curves?
-
Can the authors add heuristic baselines and component-wise ablations? Table 5 shows that RTI-A retains lower last-quarter loss at . How do the methods compare over longer horizons, and does MBI-KL eventually outperform RTI-A?
4 comments
Response to Reviewer sLdt (2/2)
Q2 (part 2/2): Can the learning loss be bounded relative to MBI with known reward curves?
The loss is at most per round, and for MBI-KL the cannot be replaced by a vanishing term. The upper bound follows from Theorem 3, because known-curve MBI earns at most . For the lower bound, we construct a two-arm instance on which MBI-KL's average reward is asymptotically at least below known-curve MBI's (Linear Regret of MBI-KL Relative to Known-Curve MBI). With exact planning in place of MBI, the loss does vanish: the same learning scheme is at most per round below known-curve MBI (see W2).
W3, Q3: Can the experiments include heuristic baselines, component ablations, longer horizons and curves without finite saturation?
Heuristic baselines. We added two heuristic baselines, Greedy and an LP-dual index policy. With known curves, MBI has the lowest loss in every recovery family.
Offline: Comparison with Heuristic Baselines.
| Family | MBI | Greedy | LP-dual index |
|---|---|---|---|
| Continuous | 0.373 [0.353, 0.392] | 12.104 [11.876, 12.332] | 0.445 [0.425, 0.464] |
| Staircase | 0.416 [0.400, 0.431] | 6.990 [6.849, 7.131] | 0.743 [0.716, 0.769] |
| Hybrid | 0.385 [0.359, 0.410] | 9.789 [9.623, 9.955] | 0.607 [0.567, 0.646] |
| Mix | 0.404 [0.385, 0.422] | 9.668 [9.500, 9.835] | 0.591 [0.552, 0.630] |
Notes: Loss is measured relative to UB in units of , and lower is better. Entries are mean [95% CI] over ten paired seeds. , , .
With unknown curves, the two heuristics use the same learning procedure as MBI-KL and differ only in the scheduling rule. MBI-KL has lower average loss than both throughout the run up to (Online Comparison with Heuristic Baselines).
Component ablations. We also ran component ablations on the Mix family. In MBI, removing head coordination increases loss by , and removing buffering increases it by . In MBI-KL, whose full-horizon loss at is , changing any one of five learning components increases this loss, most of all removing the monotone envelope () or discarding observations at each new epoch () (Ablation Study).
Longer horizons against RTI-A. We extended the central Mix experiment from to . MBI-KL's full-horizon loss stays below RTI-A's at every horizon. Its last-quarter loss keeps falling as the horizon grows and is below RTI-A's from on, while RTI-A's stays at because RTI-A stops learning after its exploration phase. RTI-A can lower its late loss only by exploring longer, so at we also varied its exploration budget. Its last-quarter loss falls below MBI-KL's only when it explores for at least 35,828 rounds, over a quarter of the horizon, and its full-horizon loss stays above MBI-KL's for every tested budget (Late-Stage Online Performance).
Curves without finite saturation. MBI keeps a small loss, and its advantage over the baselines persists, when the curves do not saturate. We added asymptotic tails to the paper's four families, so that rewards keep growing with the wait and 76% to 94% of MBI's pulls occur beyond the original saturation ages. RTI and PPP receive the same LP and the curves truncated at a long certified horizon. Across all twelve tested conditions MBI has the lowest mean loss.
Offline: Curves without Finite Saturation.
| Family | MBI | RTI | PPP |
|---|---|---|---|
| Continuous | 0.300 [0.292, 0.308] | 1.885 [1.864, 1.906] | 1.096 [1.046, 1.147] |
| Staircase | 0.207 [0.195, 0.220] | 1.232 [1.206, 1.259] | 0.624 [0.561, 0.687] |
| Hybrid | 0.237 [0.227, 0.248] | 1.462 [1.431, 1.493] | 0.862 [0.766, 0.959] |
| Mix | 0.239 [0.233, 0.246] | 1.482 [1.451, 1.512] | 0.803 [0.695, 0.911] |
Notes: Same metric and seeds as above. , , . RTI has no guarantee on such curves. Planning cost on these curves is reported in our reply to Reviewer 3iqK (Q3).
AI-agent memory. AI-agent memory motivates the model, but our main contribution is the improved planning guarantee for recovering-reward bandits. Our experiments therefore test this guarantee on synthetic instances, where the true curves and hence UB are known. We plan to apply our algorithms to real agent-memory systems in future work.
We hope our responses have addressed your concerns, and we would be glad to answer any further questions.
Response to the rebuttal
Thank you for the detailed response and additional results. The new experiments and finite-horizon clarifications substantially address my earlier empirical and practical concerns.
My main remaining concern is the learning lower bound. The new fixed- lower bound is against , whereas for the comparator in Theorem 3, , the matching result still relies on the growing family with fixed . Thus, the separate dependence on and remains uncharacterized. The rates in my original review were meant only to illustrate why the current lower bound does not establish separate optimal dependence on and .
Overall, the revision is substantially improved, but this main theoretical concern remains, so I will keep my current rating.
Response to Reviewer sLdt (Follow-up)
We sincerely thank you for the follow-up and for your recognition of the empirical and practical sides of our work. On the theoretical side, our main technical contribution is the offline planning algorithm, which improves the loss relative to UB from in prior work to a constant . Below we address your remaining concern.
We agree that the new bound is stated against OPT rather than . In fact, no lower bound can separate and against , whereas against OPT the new bound already does so.
A separate dependence on and requires, in particular, a lower bound that holds for fixed as grows. Against , no such bound exists, because is strictly below OPT. Our planning analysis bounds the loss by (Section 3), so . With exact planning in place of our planner, the same learning scheme earns at least per round (Regret Against OPT with Exact Planning). For fixed and large , this learning term is below , and the average reward of this policy exceeds .
The separate dependence is therefore a property of learning against OPT, and the new bound characterizes it: for all , and , the lower bound of per round matches the exact-planning upper bound of up to logarithmic factors. This is the same learning term as in our online guarantee (Theorem 3). To our knowledge, neither RTI [1] nor PPP [2] gives any lower bound for learning. Whether a polynomial-time algorithm can attain this rate against OPT is a question of offline planning, which we will state as an open problem in the paper.
We will also add this discussion to the paper and revise the sentence that introduces Theorem 4 as a matching lower bound to state that it holds along its family of instances.
We hope that this explanation settles your remaining concern, and we would be grateful if you could kindly reconsider your rating. Thank you again for your time and for your constructive comments, which have helped us improve the paper.
References
[1] Papadigenopoulos, Caramanis, and Shakkottai. Non-Stationary Bandits under Recharging Payoffs: Improved Planning with Sublinear Regret. NeurIPS 2022.
[2] Simchi-Levi, Zheng, and Zhu. Dynamic Planning and Learning under Recovering Rewards. ICML 2021.
Response to Reviewer sLdt (1/2)
We sincerely thank you for your valuable time and thoughtful review. We greatly appreciate your recognition of our offline planning guarantee and of the novel scheduling framework behind it. We address each of your comments below.
W1, Q1: Can the learning lower bound characterize n and T separately, for fixed n or K?
Thank you for pointing this out. We agree that Theorem 4 fixes n/T. Its role in the paper is to show that the learning term of Theorem 3 is tight up to logarithmic factors: along its growing family, every online policy falls below UB−L by a constant multiple of nL/T on some instance. With minor changes to the proof of Theorem 4 (Lower Bound Against OPT for Fixed n and K), we also obtain a bound for fixed n and K: for every T≥C(n/K)4 and every online policy, some instance satisfies
TEST≤OPT(R)−cTnL,
where c,C>0 are absolute constants. For regret against OPT, this rules out both rates you mention: the first fails when n,K are fixed and T grows, the second when K=n≫T. The bound matches the O(nLT) upper bound obtained with exact planning (Regret Against OPT with Exact Planning), so nT is the statistical rate of learning against OPT. For the efficient algorithm's own comparator UB−L, the matching statement remains Theorem 4's growing family. We will add both results to the paper and state that Theorem 4 matches Theorem 3 along its growing family.
W2, Q2 (part 1/2): Why is regret measured against UB−L rather than OPT, and when does the guarantee become informative?
Thank you for this important question. Our main contribution is the offline planner. The online algorithm extends this planner to unknown curves, and learning them costs an additional O(nL/T) per round relative to the offline guarantee UB−L (Theorem 3). As you note, we follow the standard formulation in this literature: PPP [1] and RTI [2] also state their online regret against their own offline guarantees. To our knowledge, no polynomial-time online algorithm achieves sublinear regret against OPT for general monotone recovery curves. The obstacle is computational rather than statistical: with exact planning in place of our planner, the same learning scheme has regret O(nLT) against OPT (Regret Against OPT with Exact Planning), but exact planning is NP-hard even with known curves [3]. What our planner changes is the distance between the benchmark and OPT. Previous planning guarantees bound the loss only by O(LK) per round when UB=Θ(KL), while ours bounds it by L. Since OPT≤UB, our benchmark UB−L is within L per round of OPT. In the paper's central setting it is at least 98% of OPT (0.984–0.986 across the four curve families).
As for when the guarantee becomes informative: as you observe, the learning term of Theorem 3 falls below the allowance L only when T≫n2. At the paper's central scale (n=2048, K=128, T=214), a learning cost above L is unavoidable for any online policy: the lower-bound construction of Appendix D gives a loss of at least 2.05L per round relative to UB−L on some admissible instance. To show the regime T≥n2 directly, we ran MBI-KL to T=222=n2 in the central setting and to T=64n2 on a scaled-down instance (n=256, K=16). In the central setting, its full-horizon loss to UB falls from 15.4L at T=217 to 2.70L at T=n2, which is 96% of UB in average reward, and to 1.16L over the last quarter of that run. On the scaled-down instance, the loss is below L from T=16n2, so the average reward exceeds the benchmark UB−L, and it reaches 0.55L at T=64n2, against 0.36L for MBI with known curves (Very Long Horizons).
References
[1] Simchi-Levi, Zheng, and Zhu. Dynamic Planning and Learning under Recovering Rewards. ICML 2021.
[2] Papadigenopoulos, Caramanis, and Shakkottai. Non-Stationary Bandits under Recharging Payoffs: Improved Planning with Sublinear Regret. NeurIPS 2022.
[3] Kleinberg and Mishra. NP-Hardness and a PTAS for the Pinwheel Problem. arXiv preprint arXiv:2604.13974, 2026.