acceptodds
Under review as a conference paper at ICLR 2027

Spend Now, Earn Later: A Bandit Framework for Delayed Resource Renewal

Abstract

Bandits with Knapsacks (BwK) captures sequential decision-making under hard resource constraints, but standard models either treat resources as non-replenishable or assume that replenishment is immediately usable. We study Delayed Replenishable BwK (BwDRK), a stochastic multi-resource bandit model in which each productive pull consumes resources immediately while the induced replenishment is credited only after a tagged bounded delay. Delayed renewal creates a physical funds-in-flight effect: resources can be sufficient in aggregate but temporarily unavailable for the next decision. We propose a queue-aware primal-dual algorithm with tagged queues, a bounded-delay primal wrapper, and arrival-order dual updates. The analysis first gives a pathwise liquidity identity that converts non-active waiting/terminal rounds into a maximum active-prefix deficit, and then decomposes expected LP regret into liquidity, primal-learning, and dual-control terms. Under , the statistical learning terms scale as up to resource-price constants. We also give a reserve-paced implementation based on the safe baseline, which enforces active-round slack and obtains complete sublinear expected regret against the corresponding reserve-aware comparator. The result separates the optimistic instantaneous-renewal LP from the operational price of maintaining lead-time liquidity.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
BwK, Delayed Replenishment

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_pv8SOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies the setting of delayed replenishment and designs an Exp3-type algorithm that achieves sublinear regret theoretically. The authors also conduct several experiments to demonstrate improvements over the baselines.

Critical strengths

The paper provides rich theoretical results, and the experiments also support the theory to some extent.

Critical weaknesses

However, the paper lacks discussion of the practical applications of the proposed setting. The entire setting seems somewhat artificially constructed, and it is currently unclear whether the proposed innovation has practical value.

In terms of writing, Section 4 mainly lists theoretical results without sufficient discussion of the key findings, the innovations in the underlying proofs, or the insights behind these results.

Questions for authors

In the first panel of Figure 1, the regret appears to be almost linear. Sublinear regret only becomes apparent when T is unrealistically large, as shown in Figure 2. This seems inconsistent with the theoretical results and also limits the practical applicability of the proposed algorithm.

2 comments
AuthorsOpenReview ↗

Rebuttal to Reviewer pv8S

Dear Reviewer pv8S:

Thank you for your rigorous review. Below we address your concerns:

  1. Practical applications and motivation (W1). Delayed replenishment arises when a decision immediately commits a scarce resource but restores it only later. Appendix D discusses inventory financing with lead times and advertising with delayed conversion revenue.
    • Firstly, one example is inventory management with delivery lead times. A retailer earns revenue and consumes available inventory when completing a sale, while the corresponding replenishment order becomes available only after transportation. Even when replenishment is sufficient to cover consumption in the long run, goods can remain in transit, causing temporary stockouts and lost sales. Sales decisions with associated replenishment orders correspond to actions, while order identifiers and arrival records correspond to the tagged replenishment queue.
    • Another example is advertising with revenue reinvestment. A platform pays immediately for an impression, whereas attributed conversion revenue arrives later and becomes available for subsequent bidding. Thus, a policy with sufficient long-run returns can still interrupt bidding because its available budget is temporarily exhausted. In this abstraction, immediately observable impression value is the reward, bidding expenditure is resource consumption, and subsequent cash inflow is delayed replenishment. These examples illustrate why sufficient aggregate resources do not automatically ensure resource availability at each decision.
  2. The central idea of Section 4 (W2). Section 4 addresses a central question: performance depends both on choosing rewarding actions and on having resources available when those actions are needed.
    • We first compare the actual system with a shadow system in which replenishment is credited immediately, identifying the resources still in flight and how they cause waiting. Then we separate the reward-loss bound into resource-unavailability loss and errors from action learning and resource-price adjustment, allowing operational and learning difficulties to be analyzed separately.
    • Within this framework, the primal–dual learner handles the trade-off between rewards and resource consumption, while safe-baseline mixing maintains slack for resource circulation and controls waiting losses. Combining these controls yields the complete sublinear guarantee against the stated mixed comparator. This explains where the losses arise and which algorithmic components control them.
  3. Interpretation of Figure 1 (Q1). Figure 1 plots cumulative rewards and budget trajectories. In the first panel, the dashed Oracle curve and the red BwDRK curve show cumulative rewards. Their vertical gap represents the realized reward shortfall relative to the instantaneous-renewal LP. An approximately linear gap over this finite interval does not establish asymptotically linear regret. The theoretical guarantee concerns expected regret under fixed dimensions, positive budget rates, and a fixed delay bound, with constants depending on these parameters.

Thank you once again for your dedication to scientific rigor and for helping us refine our paper.

Best regards,

The Authors

Dear Reviewer pv8S,

We extend our sincerest gratitude for the invaluable time and meticulous effort you dedicated to reviewing our paper. We are keenly interested in knowing whether our responses have effectively resolved your initial concerns. If there are any remaining questions or if further clarification is required, we would be delighted to engage in further discussion to ensure that all your concerns are thoroughly addressed.

Thank you once again for your dedication to scientific rigor and for helping us refine our paper.

Best regards,

The Authors

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

This paper introduces a bandit framework called BwDRK for sequential decision-making when actions consume resources immediately but replenish them only after a stochastic delay. The key challenge is that resources may be sufficient in the long run but temporarily unavailable because replenishment is still in flight, which creates a liquidity constraint beyond standard delayed-feedback bandits. To address this issue, the authors propose a queue-aware primal-dual algorithm that explicitly tracks pending replenishments, combines multiple bandit learners to handle delayed feedback, and updates resource prices when complete replenishment information arrives. A key theoretical contribution is a pathwise liquidity analysis that relates the number of inactive rounds to the amount of in-flight resources and accumulated resource deficits. The paper also introduces a reserve-pacing mechanism based on a safe baseline policy that yields a complete sublinear regret guarantee with respect to a reserve-aware benchmark. The experiments show that the proposed method maintains resource availability more effectively than several delay-unaware baselines and degrades more gracefully as replenishment delays increase.

Critical strengths
  1. The model is a reasonable and well-motivated addition to replenishable BwK.

  2. The state machine, the shadow budget and the decomposition as well as primal and dual terms are clearly explained.

Critical weaknesses
  1. The theory is void in the regime the paper is about. Every bound on NoffN_{\mathrm{off}} carries (1+dˉ)/ρmin⁡=(1+dˉ)T/Bmin⁡(1+\bar d)/\rho_{\min}=(1+\bar d)T/B_{\min}, so it is sublinear only when the delay is small next to the budget, which is the regime in which the in-flight mass is negligible and the model is ordinary replenishable BwK up to a vanishing perturbation. The funds-in-flight regime of the introduction and of Section 5 is where the bounds say nothing.

  2. Theorem 4.11 compares the algorithm with the best mixture constrained to include a fixed safe baseline, not the instantaneous-renewal optimum or even the full reserve-adjusted LP optimum.

  3. The learning bound depends on the maximum delay through a wrapper that maintains multiple independent bandit learners. The paper provides no matching lower bound establishing whether this dependence is intrinsic to delayed resource renewal or partly an artifact of the wrapper. In particular, the analysis does not distinguish occasional long delays from consistently long delays with the same maximum.

Questions for authors
  1. What is the right benchmark when the in-flight mass is comparable to the budget, and can you give a lower bound on E[Noff]\mathbb E[N_{\mathrm{off}}] or on the regret against the LP in that regime? Does the throughput constraint Dˉ∑ax(a)gˉj(a)≤ρj\bar D\sum_ax(a)\bar g_j(a)\le\rho_j (or a sharper version) define a delay-aware LP that the algorithm can be shown to approach?

  2. Why can the dual regret against ej/ρe_j/\rho not pay for the lost rounds as in Castiglioni et al. (2022) and Bernasconi et al. (2024)?

2 comments
AuthorsOpenReview ↗

Rebuttal to Reviewer 1JWs

Dear Reviewer 1JWs:

We are deeply grateful for your meticulous and rigorous review. Below we address your concerns point by point:

  1. Fixed bounded delays and liquidity (W1, Q1).

    • Our assumption allows any known fixed delay bound dˉ\bar d, which need not be numerically small at a finite horizon. The revised manuscript adds Theorem 4.7 and its complete proof in Appendix A.9, establishing that the unmixed Algorithm 1 satisfies E[RegLP(T)]≤CPUPK(1+dˉ)Tln⁡K+CDd(1+dˉ)Tρmin⁡+OPTLP(1+dˉ)ρmin⁡.E[Reg_{LP}(T)]\le C_PU_{P}\sqrt{K(1+\bar d)T\ln K}+\frac{C_D\sqrt{d(1+\bar d)T}}{\rho_{\min}}+\frac{OPT_{LP}(1+\bar d)}{\rho_{\min}}.
    • For fixed dimensions, positive budget rates, and each fixed dˉ\bar d, this is O(T)O(\sqrt T), with the delay dependence retained explicitly. The argument does not require a separate sublinear bound on NoffN_{\mathrm{off}}. Substantial in-flight resources and waiting can occur at finite horizons under these assumptions.
  2. Benchmarks and dual compensation (W2, Q1–Q2). Theorem 4.7 uses the original LP comparator without a fixed safe mixture. We can also add the suggested throughput constraint to the original LP:

    \sum_a x(a)(\bar c_j(a)-\bar g_j(a))&\le\rho_j,\\\\ \bar D\sum_a x(a)\bar g_j(a)&\le\rho_j,\qquad j\in[d]. \end{aligned}$$ Let $OPT_{D}$ denote the resulting optimal reward. Since its feasible set is contained in the original LP’s, $E[T\cdot OPT_{D}-REW(T)] \le E[T\cdot OPT_{LP}-REW(T)]=O(\sqrt T)$ under the same fixed-delay assumptions. The new proof in Appendix A.9 also explains how dual regret compensates for the remaining-horizon loss. Let $r_D=OPT_{D}$, and let $I$ be the prefix of length $n$ before the first shortage. For its triggering resource $j$, choose $\lambda^\star=(r_D/\rho_j)e_j$. The budget identity gives \begin{aligned} r_D(T-n)+D_I &=Q_I(\lambda^\star)+\frac{r_D(F_j+b_j)}{\rho_j}\\\\ &\le Q_I(\lambda^\star)+\frac{r_D(1+\bar d)}{\rho_{\min}}, \end{aligned} where $D_I$ is the prefix dual-pressure term, $Q_I$ is prefix dual regret, $F_j\le\bar d$ is the in-flight mass, and $b_j<1$ is the remaining budget. The uniform pathwise dual bound permits this resource-dependent comparator. Together with the primal bound, it controls regret without separately controlling $N_{\mathrm{off}}$. The same argument applies to the original LP. We will add this corollary and discuss how sequential inventory constraints can sharpen delay-aware benchmarks in the final version.
  3. Maximum-delay dependence (W3). The factor 1+dˉ1+\bar d comes from the wrapper, which maintains 1+dˉ1+\bar d primal learners so that every active round has a free instance. This yields a worst-case guarantee based on the maximum delay, applying to both occasional and persistent long delays.

Once again, thank you for your commitment to scientific rigor and for your crucial role in helping us improve our work.

Best regards,

The Authors

Dear Reviewer 1JWs,

We would like to express our sincere gratitude for the invaluable time and careful attention you have devoted to reviewing our paper. We are eager to hear if our responses have sufficiently addressed your concerns. Should any questions remain or if further clarification is needed, we would be more than happy to engage in additional discussions to ensure all your concerns are fully resolved.

Once again, thank you for your commitment to scientific rigor and for your crucial role in helping us improve our work.

Best regards,

The Authors

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

The paper studies stochastic bandits with several resources, where an action earns a reward and consumes resources immediately but generates replenishment that arrives after a bounded delay. The algorithm tracks pending replenishments, waits when current resources are insufficient, and combines a delayed-feedback primal learner with dual updates in arrival order. Experiments in a four-arm, two-resource environment study rewards, budget trajectories, delay, and horizon scaling.

Critical strengths
  1. Proposition 4.1 relates inactive rounds to bounded in-flight resources and the maximum active-prefix deficit. This makes the operational cost of delayed renewal explicit, even when aggregate net consumption looks feasible. The subsequent regret decomposition provides a useful starting point for studying how learning and resource availability interact.
Critical weaknesses
  1. My main reservation is the benchmark used by the full guarantee. Once every policy is mixed with a fixed safe baseline, the comparator becomes
=(1-\alpha)\max_a r(a)+\alpha r(x^s).$$ This can be much smaller than the original resource-constrained optimum, including in instances where repeatedly choosing the productive arm is feasible. This also leaves me wondering how much of the algorithm is needed for the main result. Rewards are observed immediately, and the fixed mixture already ensures slack for every base policy. Could a standard reward-based bandit algorithm, using the same mixture and waiting rule, obtain a competitive guarantee against this comparator? 2. The experiments lack details. It is not clear to me whether the runs in Section 5 use the unmixed Algorithm 1 or the safe-mixture version. It also does not fully specify the mixing and learning parameters, independent repetitions, comparator used for regret, or budget scaling with the horizon. These details are needed to assess the claim that Figure 2 validates sublinear regret. 3. Some results in the figures also needs more explanation. In Figure 1, NaivePD stops accumulating reward even after its resources recover. Does it use the same wait-and-resume rule as the proposed method?
Questions for authors
  1. For a fixed safe policy and mixing level, what advantage of the primal-dual learner is established by the current analysis or experiments over a bandit that learns from immediate rewards and uses the same mixing and waiting rules?
  2. Which algorithm and parameter settings generated the plots? Please specify the regret comparator, how initial budgets change with the horizon, and the number of independent repetitions.
  3. Why does Naive PD stop accumulating reward after its resource balances recover? Please clarify the stopping and resumption rules for this baseline and the other baselines that model replenishment.
3 comments
AuthorsOpenReview ↗

Rebuttal to Reviewer vnd2

Dear Reviewer vnd2:

Thank you for your comprehensive analysis. Below we address your questions:

  1. The primal–dual framework. (W1 & Q1)

    • Our primal–dual framework makes the resource trade-off explicit in both the algorithm and the analysis: the primal learner evaluates actions using resource-adjusted utility, while the dual learner updates resource prices using consumption and replenishment feedback. The analysis therefore decomposes regret into primal-learning error, dual-control error, and the operational loss caused by non-active rounds. In particular, before introducing the safe mixture, our decomposition applies to any LP-feasible comparator and explicitly retains the liquidity-loss term. The safe mixture then provides a fair condition for controlling this term, yielding a complete sublinear guarantee against the stated mixed comparator.
    • In the revision, we also establish a complete guarantee without a fixed safe mixture. Specifically, Theorem 4.7 proves that the unmixed Algorithm 1 achieves O(T)O(\sqrt T) expected regret against the original instantaneous-renewal LP, for fixed dimensions, positive budget rates, and a fixed delay bound. The proof is given in Appendix A.9.
  2. Experimental settings. (W2 & Q2)

    • The plotting code uses no safe mixing. In Figure 1, T=1000T=1000, B1=B2=42B_1=B_2=42, ηP=0.1\eta_P=0.1, ξ=0.01\xi=0.01, and ηD=1/T\eta_D=1/\sqrt T. The oracle is the instantaneous-renewal LP, with value 0.80.8 per round in this environment. In Figure 2, the delay-sweep panel uses T=1000T=1000, B1=B2=39B_1=B_2=39, and one trajectory per delay range. The shortage panel uses T=1000T=1000, B1=B2=42B_1=B_2=42. All above experiments uses 100 random seeds.
  3. Naive PD and resumption. (W3 & Q3)

    • Naive PD credits queued replenishments and can choose productive arms again after its shortage condition clears. However, replenishment arrivals do not reduce its dual prices, and null actions update neither prices nor weights. Consequently, it can continue choosing the null arm after its budgets recover. Other baselines also process pending replenishments and can resume.

Thank you once again for your commitment to scientific rigor and for your invaluable assistance in refining our paper.

Best regards,

The Authors

Dear Reviewer vnd2,

We extend our sincerest gratitude for the invaluable time and meticulous effort you dedicated to reviewing our paper. We are keenly interested in knowing whether our responses have effectively resolved your initial concerns. If there are any remaining questions or if further clarification is required, we would be delighted to engage in further discussion to ensure that all your concerns are thoroughly addressed.

Thank you once again for your dedication to scientific rigor and for helping us refine our paper.

Best regards,

The Authors

I read the authors' response and appreciate the effort the authors put into the revised manuscript. However, I don't think the response quite answers my questions on how much of the algorithm is needed for the main result. It doesn't seem to establish that a standard reward-based bandit algorithm, using the same mixture and waiting rule, cannot obtain a competitive guarantee against the original comparator. I also remain concerned with the benchmark used in this work. I will keep my original score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.