acceptodds
Under review as a conference paper at ICLR 2027

Multiscale Buffered Interleaving: Constant-Gap Planning and Online Learning for Recovering Rewards

Abstract

Motivated by the need to keep large collections of AI-agent memories up to date, we study a recovering-reward bandit problem. In each round, at most of arms can be pulled, and each arm's expected reward is a bounded, nondecreasing function of the time since its last pull. We develop Multiscale Buffered Interleaving (MBI), which aggregates compatible periodic plans without reward loss and coordinates the remaining requests through multiscale buffering. For the offline problem with known reward curves, MBI achieves a long-run average reward within of the renewal upper bound, where bounds the reward of a single pull. This system-wide loss bound is independent of , , and the recovery horizon, improving previous guarantees, and a constant-order loss is necessary. For the online problem with unknown reward curves, the proposed policy achieves regret against our offline planning benchmark. A lower bound on growing instance families matches this learning order up to logarithmic factors. Experiments show lower losses than previous purely periodic and randomize-then-interleave methods in both offline and online settings.

Primary area:
learning theory
Keywords:
recovering rewards, non-stationary multi-armed bandits, online learning, capacity-constrained scheduling, regret bounds

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_sLdtOpenReview ↗
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 O~(nLT)\widetilde O(nL\sqrt T) 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
  1. 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.

  2. 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
  1. Limited scope of the learning lower bound. Theorem 4 uses n=16G2n=16G^2, K=16GK=16G, and T=G4T=G^4, so n/T=16n/\sqrt T=16. This does not establish the optimal dependence on nn and TT separately. For example, rates such as O(n2Lpolylog(T))O(n^2L\mathrm{polylog}(T)) or O(nT3/4L)O(\sqrt{n}T^{3/4}L) are not ruled out. The matching optimality claims should more clearly distinguish this specific joint scaling from separately optimal dependencies on nn and TT.

  2. Limited finite-horizon implications of the online guarantee. Theorem 3 provides approximate regret relative to UB(R)−LUB(R)-L (standard in this literature), rather than sublinear regret against OPT(R)OPT(R). More importantly, the O~(nLT)\widetilde O(nL\sqrt T) learning term becomes negligible relative to a constant-order planning gap only when T≫n2T\gg n^2, up to logarithmic factors. In the central experiments, n=2048n=2048 and T=16384T=16384, giving n/T=16n/\sqrt T=16, so the theoretical guarantee is not informative at the tested scale.

  3. 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-KK 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

  1. Can the authors establish learning lower bounds that separately characterize the dependence on nn and TT, particularly for fixed nn or KK?

  2. 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?

  3. Can the authors add heuristic baselines and component-wise ablations? Table 5 shows that RTI-A retains lower last-quarter loss at T=32768T=32768. How do the methods compare over longer horizons, and does MBI-KL eventually outperform RTI-A?

4 comments
AuthorsOpenReview ↗

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 nn and TT separately, for fixed nn or KK?

Thank you for pointing this out. We agree that Theorem 4 fixes n/Tn/\sqrt 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\mathrm{UB}-L by a constant multiple of nL/TnL/\sqrt 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 nn and KK: for every T≥C(n/K)4T\ge C(n/K)^4 and every online policy, some instance satisfies

ESTT≤OPT(R)−cnLT,\frac{\mathbb E S_T}{T}\le\mathrm{OPT}(R)-c\frac{nL}{\sqrt T},

where c,C>0c,C>0 are absolute constants. For regret against OPT, this rules out both rates you mention: the first fails when n,Kn,K are fixed and TT grows, the second when K=n≫TK=n\gg\sqrt T. The bound matches the O~(nLT)\widetilde O(nL\sqrt T) upper bound obtained with exact planning (Regret Against OPT with Exact Planning), so nTn\sqrt T is the statistical rate of learning against OPT. For the efficient algorithm's own comparator UB−L\mathrm{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\mathrm{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)\widetilde O(nL/\sqrt T) per round relative to the offline guarantee UB−L\mathrm{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)\widetilde O(nL\sqrt T) 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)O(L\sqrt K) per round when UB=Θ(KL)\mathrm{UB}=\Theta(KL), while ours bounds it by LL. Since OPT≤UB\mathrm{OPT}\le\mathrm{UB}, our benchmark UB−L\mathrm{UB}-L is within LL per round of OPT. In the paper's central setting it is at least 98% of OPT (0.9840.984–0.9860.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 LL only when T≫n2T\gg n^2. At the paper's central scale (n=2048n=2048, K=128K=128, T=214T=2^{14}), a learning cost above LL is unavoidable for any online policy: the lower-bound construction of Appendix D gives a loss of at least 2.05L2.05L per round relative to UB−L\mathrm{UB}-L on some admissible instance. To show the regime T≥n2T\ge n^2 directly, we ran MBI-KL to T=222=n2T=2^{22}=n^2 in the central setting and to T=64n2T=64n^2 on a scaled-down instance (n=256n=256, K=16K=16). In the central setting, its full-horizon loss to UB falls from 15.4L15.4L at T=217T=2^{17} to 2.70L2.70L at T=n2T=n^2, which is 96% of UB in average reward, and to 1.16L1.16L over the last quarter of that run. On the scaled-down instance, the loss is below LL from T=16n2T=16n^2, so the average reward exceeds the benchmark UB−L\mathrm{UB}-L, and it reaches 0.55L0.55L at T=64n2T=64n^2, against 0.36L0.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.

AuthorsOpenReview ↗

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 L+O~(nL/T)L+\widetilde O(nL/\sqrt T) per round, and for MBI-KL the LL cannot be replaced by a vanishing term. The upper bound follows from Theorem 3, because known-curve MBI earns at most UB\mathrm{UB}. For the lower bound, we construct a two-arm instance on which MBI-KL's average reward is asymptotically at least L/135L/135 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 O~(nL/T)\widetilde O(nL/\sqrt T) 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.

FamilyMBIGreedyLP-dual index
Continuous0.373 [0.353, 0.392]12.104 [11.876, 12.332]0.445 [0.425, 0.464]
Staircase0.416 [0.400, 0.431]6.990 [6.849, 7.131]0.743 [0.716, 0.769]
Hybrid0.385 [0.359, 0.410]9.789 [9.623, 9.955]0.607 [0.567, 0.646]
Mix0.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 LL, and lower is better. Entries are mean [95% CI] over ten paired seeds. n=2048n=2048, K=D=128K=D=128, T=215T=2^{15}.

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 T=217T=2^{17} (Online Comparison with Heuristic Baselines).

Component ablations. We also ran component ablations on the Mix family. In MBI, removing head coordination increases loss by 0.137L0.137L, and removing buffering increases it by 0.717L0.717L. In MBI-KL, whose full-horizon loss at T=217T=2^{17} is 15.4L15.4L, changing any one of five learning components increases this loss, most of all removing the monotone envelope (+10.3L+10.3L) or discarding observations at each new epoch (+6.0L+6.0L) (Ablation Study).

Longer horizons against RTI-A. We extended the central Mix experiment from T=214T=2^{14} to 2172^{17}. 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 T=216T=2^{16} on, while RTI-A's stays at 15.2L15.2L because RTI-A stops learning after its exploration phase. RTI-A can lower its late loss only by exploring longer, so at T=217T=2^{17} 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.

FamilyMBIRTIPPP
Continuous0.300 [0.292, 0.308]1.885 [1.864, 1.906]1.096 [1.046, 1.147]
Staircase0.207 [0.195, 0.220]1.232 [1.206, 1.259]0.624 [0.561, 0.687]
Hybrid0.237 [0.227, 0.248]1.462 [1.431, 1.493]0.862 [0.766, 0.959]
Mix0.239 [0.233, 0.246]1.482 [1.451, 1.512]0.803 [0.695, 0.911]

Notes: Same metric and seeds as above. K=128K=128, T=215T=2^{15}, ρ=5\rho=5. 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.

Reviewer_sLdtOpenReview ↗

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-n,Kn,K lower bound is against OPT(R)OPT(R), whereas for the comparator in Theorem 3, UB(R)−LUB(R)-L, the matching result still relies on the growing family with fixed n/Tn/\sqrt{T}. Thus, the separate dependence on nn and TT 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 nn and TT.

Overall, the revision is substantially improved, but this main theoretical concern remains, so I will keep my current rating.

AuthorsOpenReview ↗

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 O(UB/K)O(\mathrm{UB}/\sqrt K) in prior work to a constant LL. Below we address your remaining concern.

We agree that the new bound is stated against OPT rather than UB−L\mathrm{UB}-L. In fact, no lower bound can separate nn and TT against UB−L\mathrm{UB}-L, whereas against OPT the new bound already does so.

A separate dependence on nn and TT requires, in particular, a lower bound that holds for fixed nn as TT grows. Against UB−L\mathrm{UB}-L, no such bound exists, because UB−L\mathrm{UB}-L is strictly below OPT. Our planning analysis bounds the loss by 0.98L0.98L (Section 3), so OPT≥UB−0.98L\mathrm{OPT}\ge\mathrm{UB}-0.98L. With exact planning in place of our planner, the same learning scheme earns at least OPT−O~(nL/T)\mathrm{OPT}-\widetilde O(nL/\sqrt T) per round (Regret Against OPT with Exact Planning). For fixed nn and large TT, this learning term is below 0.02L0.02L, and the average reward of this policy exceeds UB−L\mathrm{UB}-L.

The separate dependence is therefore a property of learning against OPT, and the new bound characterizes it: for all nn, KK and T≥C(n/K)4T\ge C(n/K)^4, the lower bound of Ω(nL/T)\Omega(nL/\sqrt T) per round matches the exact-planning upper bound of O~(nL/T)\widetilde O(nL/\sqrt T) 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.

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

This paper studies offline planning and online learning in recovering-reward multi-armed bandits, where each arm's expected reward is a bounded, nondecreasing function of the time since its last pull, and at most KK arms can be selected per round. The authors propose Multiscale Buffered Interleaving (MBI), a scheduling algorithm that achieves a constant additive gap to a renewal-based upper bound, independently of the number of arms, capacity, and recovery horizon. They also establish a matching constant-order planning lower bound. For unknown reward functions, the authors extend MBI using KL-UCB and blockwise planning, achieving O~(nLT)\widetilde O(nL\sqrt T) learning regret relative to the constant-gap planning benchmark, with a matching lower bound up to logarithmic factors on growing instance families.

Critical strengths
  • The paper establishes an additive O(L)O(L) planning gap independent of the number of arms, capacity, and recovery horizon, substantially improving previous capacity-dependent guarantees.

  • The proposed MBI algorithm combines lossless aggregation, multiscale buffering, and capacity-feasible interleaving to control scheduling losses. The authors further establish an Ω(L)\Omega(L) lower bound on the gap between the renewal relaxation and the optimal feasible policy, demonstrating the order-optimality of their planning guarantee.

  • The paper extends its planning framework to unknown reward functions and establishes an O~(nLT)\widetilde O(nL\sqrt T) learning guarantee, accompanied by a matching lower bound on growing instance families.

Critical weaknesses
  • The online learning guarantee is established relative to UB(R)−L\mathrm{UB}(R)-L, rather than the optimal feasible policy OPT(R)\mathrm{OPT}(R). Consequently, the result does not establish sublinear regret against the true offline optimum. It remains unclear whether the proposed algorithm can achieve a stronger regret guarantee relative to OPT(R)\mathrm{OPT}(R).

  • The matching lower bound is established only for growing instance families, where both the number of arms and the capacity increase with the horizon. Therefore, it does not establish the minimax optimality of the O~(nLT)\widetilde{O}(nL\sqrt{T}) learning bound for fixed-size systems, leaving open whether the dependence on nn, KK, and TT can be improved.

  • Several key components of the proposed algorithm build on established techniques. In particular, the renewal LP and the sparsity structure of its extreme-point solutions appear in Papadigenopoulos et al. (2022). Interleaved scheduling was studied by Kleinberg and Immorlica (2018), while divisibility-based periodic scheduling was employed by Simchi-Levi et al. (2021). The online extension also largely follows the standard optimism-based planning framework.

Questions for authors

I look forward to hearing the authors' responses to the concerns raised in the weaknesses.

4 comments
AuthorsOpenReview ↗

Response to Reviewer 7beB (1/2)

We sincerely thank you for your valuable time and thoughtful review. We greatly appreciate your recognition of our capacity-independent planning guarantee, its order-optimality, and its extension to unknown reward functions. We address each of your comments below.

W1: Why is online regret measured against UB−L\mathrm{UB}-L rather than OPT?

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 only an additional O~(nL/T)\widetilde O(nL/\sqrt T) per round relative to the offline guarantee UB−L\mathrm{UB}-L (Theorem 3). 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)\widetilde O(nL\sqrt T) 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)O(L\sqrt K) per round when UB=Θ(KL)\mathrm{UB}=\Theta(KL), while ours bounds it by LL. Since OPT≤UB\mathrm{OPT}\le\mathrm{UB}, our benchmark UB−L\mathrm{UB}-L is within LL per round of OPT. In the paper's central setting it is at least 98% of OPT (0.9840.984–0.9860.986 across the four curve families).

W2: Does the learning lower bound hold for fixed nn and KK, beyond growing instance families?

Thank you for pointing this out. We agree that Theorem 4 holds along a growing family. Its role in the paper is to show that the learning term of Theorem 3 is tight up to logarithmic factors: along this family, every online policy falls below UB−L\mathrm{UB}-L by a constant multiple of nL/TnL/\sqrt 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 nn and KK: for every T≥C(n/K)4T\ge C(n/K)^4 and every online policy, some instance satisfies

ESTT≤OPT(R)−cnLT,\frac{\mathbb E S_T}{T}\le\mathrm{OPT}(R)-c\frac{nL}{\sqrt T},

where c,C>0c,C>0 are absolute constants. This matches, up to logarithmic factors, the upper bound under exact planning (W1). For the comparator UB−L\mathrm{UB}-L of Theorem 3, the matching lower bound remains Theorem 4. We will add this result after Theorem 4.

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.

AuthorsOpenReview ↗

Response to Reviewer 7beB (2/2)

W3: What is new relative to the established techniques the algorithm builds on?

We agree that MBI builds on tools from prior work. What they leave open is a scheduling step whose loss does not grow with KK. Kleinberg and Immorlica [1] serve randomly shifted periodic requests in order, with one pull per round and concave curves. Simchi-Levi et al. [2] (PPP) schedule each arm strictly periodically, and no purely periodic policy can guarantee a loss below order UB/Klog⁡K\mathrm{UB}/\sqrt{K\log K} (Table 1). RTI [3], whose renewal LP and sparse basic solutions MBI also uses, gives arms independent random offsets and skips requests beyond capacity. The number of requests in a round then fluctuates by order K\sqrt K, which is the source of its UB/K\mathrm{UB}/\sqrt K loss.

MBI extends order-preserving service to KK pulls per round and to any monotone curves. It uses divisibility to merge streams without changing any arm's wait (Lemma A.1), but its schedule is not purely periodic: each group of arms with similar periods receives an exact number of slots in every round (Lemma A.3), so excess demand only delays service. A buffer FF between requests absorbs this delay without concavity. It costs at most LF/PLF/P for periods at least PP, and the remaining loss decays exponentially in F2/dF^2/d, where dd counts the distinct periods in the group (Lemmas A.4 and A.5). Over geometric period scales these losses sum to a constant, which gives the additive LL. In Figure 2(b), as KK grows from 6464 to 10241024, RTI's loss rises from 0.71L0.71L to 2.80L2.80L, while MBI's rises only from 0.37L0.37L to 0.59L0.59L.

This offline result is our main contribution, and the online algorithm extends it. The online algorithm does follow the optimism principle, but it also relies on two further components: a monotone envelope that lets observations at longer waits tighten the confidence bounds at shorter waits, and the retention of observations across epochs. Ablations confirm that the components of both algorithms contribute. In MBI, removing head coordination or buffering raises the loss by 0.137L0.137L and 0.717L0.717L, respectively. In MBI-KL, removing the monotone envelope or discarding observations at each new epoch raises the loss at T=217T=2^{17} by 10.3L10.3L and 6.0L6.0L, respectively (Ablation Study).

We hope our responses have addressed your concerns, and we would be glad to answer any further questions.

References

[1] Kleinberg and Immorlica. Recharging Bandits. FOCS 2018.

[2] Simchi-Levi, Zheng, and Zhu. Dynamic Planning and Learning under Recovering Rewards. ICML 2021.

[3] Papadigenopoulos, Caramanis, and Shakkottai. Non-Stationary Bandits under Recharging Payoffs: Improved Planning with Sublinear Regret. NeurIPS 2022.

Thank you for the detailed responses. I appreciate the contribution of the constant-gap offline planning result. However, the online contribution appears to be a relatively natural extension of the offline planner using standard optimism-based learning techniques.

My main remaining concern is the strength of the online guarantee. Theorem 3 establishes sublinear regret against UB(R)−L\mathrm{UB}(R)-L, rather than OPT. While exact offline planning is NP-hard, this alone does not rule out polynomial-time online algorithms achieving sublinear regret against OPT. Moreover, I appreciate the new lower bound for fixed nn and KK, but it is established against OPT, whereas Theorem 3 uses UB(R)−L\mathrm{UB}(R)-L. Since these benchmarks can differ by a nonvanishing constant, the new lower bound does not directly establish the tightness of Theorem 3 for fixed nn and KK.

AuthorsOpenReview ↗

Response to Reviewer 7beB (Follow-up)

We sincerely thank you for the follow-up and for your recognition of the constant-gap offline planning result. The main focus of our work is the design of a planning algorithm that improves the loss relative to UB from O(UB/K)O(\mathrm{UB}/\sqrt K) in prior work to a constant LL. By combining MBI with KL-UCB, we show that its guarantee carries over to unknown curves. Below we address your two remaining points.

How strong is the online guarantee, given that it is stated against UB−L\mathrm{UB}-L rather than OPT?

We agree that our online guarantee (Theorem 3) is stated against UB−L\mathrm{UB}-L rather than OPT, and that the NP-hardness of exact planning does not by itself rule out a polynomial-time online algorithm with sublinear regret against OPT. In fact, the remaining gap to OPT is a question of offline planning rather than of learning, and prior online guarantees have such a gap as well. We explain these two points in turn.

First, an online guarantee against OPT requires a planner that comes arbitrarily close to OPT. A polynomial-time online algorithm with regret poly(n,K)⋅L⋅T1−α\mathrm{poly}(n,K)\cdot L\cdot T^{1-\alpha} against OPT could be run on known curves, and repeating its schedule would give, for every ε>0\varepsilon>0, a planner whose expected value is within εL\varepsilon L of OPT in time polynomial in nn, KK and 1/ε1/\varepsilon. Our planner comes within the constant LL of OPT. Whether a polynomial-time planner can reduce this constant to εL\varepsilon L for every ε>0\varepsilon>0 is, to our knowledge, an open problem, which we will state in the paper, and RTI [1] lists a better approximation or a matching hardness result for planning as a direction for future work.

Second, the online guarantees of prior work are also stated against approximate benchmarks, namely the guarantees of their planners. Over TT rounds, and showing only the dependence on TT in the learning terms, RTI [1] guarantees (1−O(1/K))⋅OPT(T)−O~(T2/3)(1-O(1/\sqrt K))\cdot\mathrm{OPT}(T)-\widetilde O(T^{2/3}) and PPP [2] guarantees (1−O(1/K))⋅T⋅UB−O~(T)(1-O(1/\sqrt K))\cdot T\cdot\mathrm{UB}-\widetilde O(\sqrt T). Our paper guarantees (1−L/UB)⋅T⋅UB−O~(T)(1-L/\mathrm{UB})\cdot T\cdot\mathrm{UB}-\widetilde O(\sqrt T), and its factor is 1−O(1/K)1-O(1/K) when UB=Θ(KL)\mathrm{UB}=\Theta(KL). In this regime, our benchmark is the closest to OPT, and our learning rate in TT matches the better of the two.

Does the new lower bound establish the tightness of our online guarantee for fixed nn and KK?

We agree that the new bound is relative to OPT and does not establish the tightness of our online guarantee for fixed nn and KK. Theorem 4 matches the learning term of our guarantee, up to logarithmic factors, along its stated growing family, whereas the new bound gives a lower bound of Ω(nL/T)\Omega(nL/\sqrt T) per round against OPT for fixed nn and KK and all large TT.

For fixed nn and KK, no lower bound can match our guarantee against UB−L\mathrm{UB}-L, for the reason you point out: the two benchmarks differ by a constant. Our planning analysis bounds the loss by 0.98L0.98L (Section 3), so OPT≥UB−0.98L\mathrm{OPT}\ge\mathrm{UB}-0.98L. With exact planning in place of our planner, the same learning scheme earns at least OPT−O~(nL/T)\mathrm{OPT}-\widetilde O(nL/\sqrt T) per round (Regret Against OPT with Exact Planning), which exceeds UB−L\mathrm{UB}-L once TT is large. Theorem 4 avoids this because nn grows with TT along its family, so the learning term stays comparable to LL. For fixed nn and KK, the matching result is therefore against OPT, where the new bound matches the exact-planning upper bound up to logarithmic factors, with the same learning term as in our online guarantee. To our knowledge, neither RTI [1] nor PPP [2] gives any lower bound for learning. We will 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.

Thank you again for your time and for your careful reading of our response. We hope this clarifies the strength and scope of the online guarantee, and we would be glad to answer any further questions.

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.

Reviewer_3iqKOpenReview ↗
Rating
3
Confidence
2(+1)
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies a recovering-reward bandit problem. In the offline setting, it proposes Multiscale Buffered Interleaving (MBI), which converts a renewal LP solution into a feasible schedule whose long-run average reward is within LL of the renewal upper bound. Together with an Ω(L)\Omega(L) lower bound on the relaxation gap, this establishes a tight Θ(L)\Theta(L) worst-case gap relative to this upper bound. In the online setting, the paper develops MBI-KL, which achieves an O~(nLT)\widetilde{O}(nL\sqrt{T}) upper bound on the expected cumulative reward shortfall relative to the per-round benchmark UB(R)−L\mathrm{UB}(R)-L. Synthetic experiments compare both offline planning and online performance with existing methods.

Critical strengths

Capacity-independent planning loss. Removing the dependence on KK from the additive planning gap is a meaningful theoretical advance. The capacity-scaling experiments (Figure 2-(b)) also support the practical relevance of this improvement.

Matching upper and lower bounds in order. The O(L)O(L) planning guarantee and the Ω(L)\Omega(L) relaxation gap lower bound establish the optimal order of the gap relative to the LP benchmark.

Generality of the assumptions. The results hold for bounded, nondecreasing recovery functions without requiring concavity or a known finite saturation time. Establishing these guarantees under such limited structural assumptions strengthens the contribution.

Critical weaknesses

Limited number of seeds. Most experiments use only three paired seeds, and some sensitivity studies use two (Appendix E.1). Since these are lightweight synthetic simulations, running more seeds would make the empirical comparisons more reliable. Reporting confidence intervals in the tables and confidence bands in the learning curves, which currently shade only the seed range (Figures 3 and 8), would also help.

The horizon dependence of the online advantage remains insufficiently characterized. RTI-A incurs substantial initial exploration costs but achieves lower loss over the common post-exploration window (Table 3). As the horizon grows, the contribution of this initial cost to its average loss decreases. Indeed, Table 5 shows that doubling the horizon reduces the full-horizon loss gap between MBI-KL and RTI-A. These results leave open whether the observed advantage persists over substantially longer horizons or primarily reflects the benefit of avoiding a long initial exploration phase.

Questions for authors
  1. Please address the concerns raised in the weaknesses section.

  2. While MBI improves the planning-loss bound when UB(R)=Θ(KL)\mathrm{UB}(R)=\Theta(KL), existing algorithms can have stronger guarantees when UB(R)\mathrm{UB}(R) is smaller. Could the authors characterize the regimes where MBI is advantageous and those where it may perform worse? Is there evidence that UB(R)=Θ(KL)\mathrm{UB}(R)=\Theta(KL) is representative of practical applications? Without such justification, the abstract’s statement about improving previous guarantees may suggest a broader improvement than the results establish.

  3. Without a known finite recovery horizon, the truncated LP considers periods up to Q=100nQ=100n, which may substantially increase its size. All experimental curves saturate by DD, and Appendix E.2 notes that dominated columns can be removed for known saturated curves. The computational cost on non-saturating curves therefore remains unclear. Could the authors report LP sizes and planning runtimes on such curves and, together with the replanning tradeoff in Table 7, explain how they recommend balancing reward performance and computation in practice?

4 comments
AuthorsOpenReview ↗

Response to Reviewer 3iqK (1/2)

We sincerely thank you for your valuable time and thoughtful review. We greatly appreciate your recognition of our capacity-independent planning guarantee, its optimal order, and the generality of our assumptions. We address each of your comments below.

W1, Q1: Do the comparisons hold with more seeds and with confidence intervals?

We repeated the paper’s offline, online, and sensitivity experiments with ten paired seeds. The conclusions remain unchanged: MBI has the lowest central offline loss, and MBI-KL the lowest full-horizon online loss in every recovery family. The updated figures and tables include 95% confidence intervals and confidence bands for the learning curves (Paper Experiments with Ten Paired Seeds). We will update the figures and tables of the paper with these ten-seed results.

W2, Q1: Does MBI-KL's advantage persist over much longer horizons, beyond avoiding RTI-A's initial exploration?

Thank you for this question. Yes, it does. We extended the central Mix experiment from T=214T=2^{14} to 2172^{17}. 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 T=216T=2^{16} on, while RTI-A's stays at 15.2L15.2L because RTI-A stops learning after its exploration phase. RTI-A can lower its late loss only by exploring longer, so at T=217T=2^{17} 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).

Q2: In which regimes does MBI's guarantee improve on earlier ones, and is UB=Θ(KL)\mathrm{UB}=\Theta(KL) representative of practice?

Our guarantee and PPP's [1] also cover instances without finite recovery, while RTI's [2] does not. With finite recovery, RTI's guarantee (1−δK)UB(1-\delta_K)\mathrm{UB}, where δK=KK/(eKK!)\delta_K=K^K/(e^K K!), is larger than PPP's for every KK. Our guarantee UB−L\mathrm{UB}-L is therefore stronger than both earlier guarantees whenever UB>L/δK≈2.5KL\mathrm{UB}>L/\delta_K\approx 2.5\sqrt{K}L. In the paper's central setting (K=128K=128) this threshold is 28.378L28.378L, while the workloads have UB\mathrm{UB} between 61.55L61.55L and 69.72L69.72L. Without finite recovery only PPP's guarantee remains for comparison, and ours is stronger above a lower threshold (6.415L6.415L at K=128K=128).

We now turn to when UB=Θ(KL)\mathrm{UB}=\Theta(KL) holds in practice. Our model belongs to the class of restless bandits, where arms keep changing even when they are not pulled and only KK of them can be pulled per round. The standard setting for this class, from Whittle [3] and Weber and Weiss [4] to recent work [5, 6, 7], takes KK proportional to the number of arms. In this setting UB\mathrm{UB} grows linearly in KK, which gives UB=Θ(KL)\mathrm{UB}=\Theta(KL). More generally, capacity is modeled in applications because pulls are scarce, so one more pull per round has substantial value. Writing λ⋆\lambda^\star for this value, LP duality gives UB≥λ⋆K\mathrm{UB}\ge\lambda^\star K, so UB=Θ(KL)\mathrm{UB}=\Theta(KL) whenever λ⋆\lambda^\star is a constant fraction of LL.

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] Whittle. Restless Bandits: Activity Allocation in a Changing World. Journal of Applied Probability, 1988.

[4] Weber and Weiss. On an Index Policy for Restless Bandits. Journal of Applied Probability, 1990.

[5] Zhang and Frazier. Restless Bandits with Many Arms: Beating the Central Limit Theorem. arXiv preprint arXiv:2107.11911, 2021.

[6] Hong, Xie, Chen, and Wang. Restless Bandits with Average Reward: Breaking the Uniform Global Attractor Assumption. NeurIPS 2023.

[7] Gast, Gaujal, and Yan. Linear Program-Based Policies for Restless Bandits: Necessary and Sufficient Conditions for (Exponentially Fast) Asymptotic Optimality. Mathematics of Operations Research, 2024.

AuthorsOpenReview ↗

Response to Reviewer 3iqK (2/2)

Q3: What are the LP size and planning time on non-saturating curves, and how should reward be balanced against computation in practice?

Thank you for this practical question. The LP stays tractable without a finite saturation time. The paper truncates the LP at Q=100nQ=100n because the general bound (A.1) then limits the error in UB to 0.01L0.01L, an error already counted in the guarantee UB−L\mathrm{UB}-L (Section 3.2). In practice the same accuracy needs far fewer than all nQnQ columns. We solve the LP only over periods up to MM, starting from M=128M=128 and doubling MM when needed. Its dual solution, together with an upper bound on each arm's reward, then bounds how much all longer periods could add to UB, and we stop once this certified bound is at most 0.01L0.01L. In our experiments this happens at MM between 256 and 1024, with about a thousand times fewer columns than Q=100nQ=100n. The table reports the resulting LP size and planning time, and MBI's loss stays well below LL.

Offline: LP Size, Planning Cost and Loss without Finite Saturation.

ρ\rhonnLP variablesLP time (s)Planning time (s)MBI loss
1.652048524,2881.82 [1.71, 1.93]5.22 [5.06, 5.39]0.074 [0.049, 0.099]
56141–63453,194,31735.60 [33.65, 37.55]56.09 [54.09, 58.10]0.239 [0.233, 0.246]
1012279–1254012,720,333167.30 [156.86, 177.75]243.04 [232.44, 253.64]0.437 [0.424, 0.451]

Notes: Loss is measured relative to UB in units of LL, and lower is better. Entries are mean [95% CI] over ten paired seeds. Mix with asymptotic tails, K=128K=128. ρ\rho is the capacity pressure defined in Section 5.1, and nn is the number of arms needed to reach it. The LP has n+1n+1 constraints. Planning time is for one call.

For the online algorithm, the main computational parameter is the replanning frequency, which Table 7 of the paper varies on saturating curves. On the non-saturating curves, replanning twice as often as the default takes about 1.81.8 times the planning time and raises the average reward by 0.15L0.15L. Replanning half as often takes about half the time and lowers it by 0.38L0.38L.

Online: Replanning Frequency on Non-Saturating Curves.

Block multiplierReplansPlanning CPU time (s)Full-horizon loss
4838479.1 [476.6, 481.5]9.792 [9.680, 9.904]
8 (default)422261.1 [260.3, 261.9]9.939 [9.823, 10.055]
16215136.4 [134.9, 137.8]10.318 [10.187, 10.450]

Notes: Loss is measured relative to UB in units of LL, and lower is better. Entries are mean [95% CI] over ten paired seeds. Central Mix instances with asymptotic tails, T=215T=2^{15}. Planning CPU time is the total over all replans.

In practice we therefore recommend the following. For planning, the certified accuracy of 0.01L0.01L suffices, since a more accurate LP can raise the planned value by at most 0.01L0.01L, and one planning call then takes about 5 seconds at n=2048n=2048 and 4 minutes at n≈12,400n\approx 12{,}400. For learning, the reward gained per additional CPU second falls by a factor of about four from one doubling of the replanning frequency to the next, and Table 7 shows the same diminishing return on saturating curves. We therefore recommend the default frequency, which costs about 8 ms of CPU time per round on our machine, and more frequent replanning only when computation is cheap relative to reward.

We hope our responses have addressed your concerns, and we would be glad to answer any further questions.

Thank you for the additional experiments and clarifications. These have addressed most of my concerns, and I will maintain my positive rating.

AuthorsOpenReview ↗

Response to Reviewer 3iqK (Follow-up)

We sincerely thank you for your follow-up and your positive assessment of our work. We are glad that our additional experiments and clarifications have addressed most of your concerns, and we greatly appreciate your constructive feedback. We will incorporate these experiments and clarifications into the revised manuscript.

Comments on the paper

2 comments
AuthorsOpenReview ↗

General Response

We sincerely thank all three reviewers for their valuable time and constructive feedback. Here we summarize the points the reviewers agree on and how we addressed the concerns raised by more than one reviewer. Full details are in the individual replies.

(a) Points the reviewers agree on

The reviewers agree on the offline result, which is the core contribution of our paper.

  1. A capacity-independent planning guarantee. MBI's long-run average reward is within LL of the renewal upper bound for any number of arms, capacity and recovery horizon, whereas earlier guarantees bound the loss only by O(LK)O(L\sqrt K) per round when UB=Θ(KL)\mathrm{UB}=\Theta(KL). The reviewers describe this as “substantially improving previous capacity-dependent guarantees” (Reviewer 7beB), a bound that “significantly improves upon previous guarantees” (Reviewer sLdt), and “a meaningful theoretical advance” (Reviewer 3iqK).

  2. The optimal order. No policy can guarantee a loss below 5L/365L/36 against this bound (Theorem 2), “demonstrating the order-optimality of their planning guarantee” (Reviewer 7beB) and establishing “the optimal order of the gap relative to the LP benchmark” (Reviewer 3iqK).

  3. A new scheduling framework. Lossless aggregation, multiscale buffering and order-preserving interleaving fix each group's capacity in every round and absorb the resulting delays, so the scheduling loss no longer grows with KK. Reviewer sLdt calls this a “novel and technically interesting framework” and “a sophisticated scheduling approach”.

The online algorithm extends this planner to unknown curves, which “further strengthens the contribution” (Reviewer sLdt).

(b) Concerns raised by more than one reviewer

  1. Is UB−L\mathrm{UB}-L the right online benchmark? (Reviewers 7beB and sLdt) Theorem 3 measures learning against the offline guarantee UB−L\mathrm{UB}-L, as PPP and RTI do for theirs. With exact planning, the same learning scheme has regret O~(nLT)\widetilde O(nL\sqrt T) against OPT (Regret Against OPT with Exact Planning). The remaining gap to OPT is therefore computational, since exact planning is NP-hard, and our planner reduces it from O(LK)O(L\sqrt K) to LL per round.

  2. Does the lower bound require a growing family? (Reviewers 7beB and sLdt) Theorem 4 indeed relies on such a family. Its role is to show that the learning term of Theorem 3 is tight along that family. With minor changes to its proof, we also obtain a lower bound for fixed nn and KK: over long horizons, every online policy has regret Ω(nLT)\Omega(nL\sqrt T) against OPT on some instance (Lower Bound Against OPT for Fixed n and K). This matches the upper bound with exact planning up to logarithmic factors.

  3. How does MBI-KL perform over longer horizons? (Reviewers 3iqK and sLdt) With a fixed exploration budget, RTI-A's late loss stays constant as the horizon grows, while MBI-KL's keeps falling and is lower from T=216T=2^{16} on. At T=217T=2^{17}, RTI-A matches it only by exploring for over a quarter of the horizon, and its full-horizon loss stays higher (Late-Stage Online Performance). On a scaled-down instance run to T=64n2T=64n^2, MBI-KL's loss falls below LL from T=16n2T=16n^2, so its average reward exceeds UB−L\mathrm{UB}-L (Very Long Horizons).

  4. Are the experiments reliable and broad enough? (Reviewers 3iqK and sLdt) With ten paired seeds, the paper's conclusions are unchanged (Paper Experiments with Ten Paired Seeds). MBI and MBI-KL also have lower loss than two added heuristics, Greedy and an LP-dual index policy (Online Comparison with Heuristic Baselines), and ablations show that their components contribute (Ablation Study). On curves without finite recovery, MBI has the lowest mean loss against RTI and PPP in all twelve conditions, and the LP stays tractable.

Dear reviewers,

If you believe the authors have addressed your questions, please respond to the rebuttal.

Best, AC

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.