acceptodds
Under review as a conference paper at ICLR 2027

Online Resource Allocation with Replenishable Budgets

Abstract

Online Resource Allocation (ORA) is a fundamental framework for sequential decision-making problems under budget constraints. Classical ORA models typically assume that resources are monotonic, meaning that selecting actions can only decrease the available budget. In this work, we study a more general setting with replenishable budgets, in which actions may either consume or replenish resources over time. This extension is necessary to capture scenarios such as inventory systems or energy markets in which capacity can be actively recovered. We develop a dual-based algorithm that recovers best-of-both-world guarantees for standard ORA when the replenishment factor , and improves them when . In particular, our algorithm attains regret in the stochastic setting and -regret in the adversarial setting, where depends on the per-round budget and on the replenishment factor of the void action. Moreover, the algorithm ensures strict satisfaction of the budget constraints.

Primary area:
learning theory
Keywords:
Online Resource Allocation, Budget, Replenishment

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

The paper provides a clean analysis of a simple allocation algorithm with replenishable/non-monotonic resource consumption and hard feasibility. However, the contribution is insufficiently distinguished from existing replenishment studies, and important directly relevant allocation literature is missing. The stronger benchmarks and explicit bounds may constitute a useful contribution, but the manuscript does not adequately establish the nontriviality of this extension.

Critical strengths

S1. The proposed algorithm is easy to understand and implement given an exact Lagrangian optimization oracle.

S2. The authors provide both stochastic and adversarial guarantees while maintaining hard constraints.

S3. The proposed algorithm preserves O(T)O(\sqrt{T})-regret when β\beta is unknown.

Critical weaknesses

W1. The position of this paper relative to existing literature on online allocation with replenishment is unclear. Yang et al., "Online Allocation with Replenishable Budgets: Worst Case and Beyond" (POMACS 2024), already study online allocation with replenishable budgets, per-round feasibility, dual pricing, and adversarial competitive guarantees. Its exogenous replenishment and capacity-cap model differs from the present action-dependent signed-consumption model, so it does not automatically subsume this submission. Nevertheless, its omission substantially weakens the positioning. The authors should explain precisely which assumptions and guarantees distinguish their contribution.

W2. The reference “Bandits with Replenishable Knapsacks: the Best of both Worlds” already uses a replenishing void action, a budget-threshold safeguard, updates restricted to active rounds, and analysis organized around the last forced replenishment. Though this paper’s setting is different, the authors need to clearly explain whether their model is a full-information/general-action-space version of that problem, and what is genuinely new beyond adapting the dual argument. Without this, the novelty claim is not convincing.

W3. The paper claims an improved competitive ratio α=(ρ+β)/(1+β)\alpha=(\rho+\beta)/(1+\beta), but only proves an upper bound. It would strengthen the paper to show that this α\alpha is optimal or at least discuss known impossibility results. Otherwise, "improves the competitive ratio" is only an upper-bound statement.

W4. The algorithm plays the void action whenever any resource has Bt,i<1B_{t,i}<1, even if there are feasible actions that consume no such resource. This is simple and safe, but it can be overly conservative. The authors should discuss whether this affects the claim "recovers state-of-the-art for β=0\beta=0", and whether a more refined safety condition could improve constants or the competitive ratio.

W5. The replenishment assumption limits the application claims, where one known action must uniformly replenish every resource on every request, with no storage caps, delays, or acquisition costs. The paper acknowledges this as future work but provides no concrete application satisfying these assumptions, so practical significance remains under-established.

W6. This is a theoretical paper, so experiments are not mandatory, but a small synthetic experiment would help illustrate the non-monotonic dynamics and the effect of β\beta.

Questions for authors

Please refer to W1-W6.

2 comments

We thank the Reviewer for the effort in evaluating our work.

W1. The position of this paper relative to existing literature on online allocation with replenishment is unclear. Yang et al., "Online Allocation with Replenishable Budgets: Worst Case and Beyond" (POMACS 2024), already study online allocation with replenishable budgets, per-round feasibility, dual pricing, and adversarial competitive guarantees. Its exogenous replenishment and capacity-cap model differs from the present action-dependent signed-consumption model, so it does not automatically subsume this submission. Nevertheless, its omission substantially weakens the positioning. The authors should explain precisely which assumptions and guarantees distinguish their contribution.

We thank the Reviewer for bringing [Yang et al. (2024)] to our attention. We completely agree that it is a highly relevant work and its omission was an oversight. We will include it in Section 1.3 in the final version of the paper. As the Reviewer correctly points out, the fundamental distinction lies in the nature of the replenishment. [Yang et al. (2024)] study exogenous replenishments where the environment restores capacity independently of the agent's actions. Our framework studies a different problem, where the agent is able to actively choose the replenishment. This implies a crucial distinction in the mechanism of the algorithm, since decisions are subject to the current budget left for each resource and the void action can be exploited to recover budget if needed.

W2. The reference “Bandits with Replenishable Knapsacks: the Best of both Worlds” already uses a replenishing void action, a budget-threshold safeguard, updates restricted to active rounds, and analysis organized around the last forced replenishment. Though this paper’s setting is different, the authors need to clearly explain whether their model is a full-information/general-action-space version of that problem, and what is genuinely new beyond adapting the dual argument. Without this, the novelty claim is not convincing.

We thank the Reviewer for the observation. We agree that our approach shares similarities with [Bernasconi et al. (2024b)], but we believe that the works are distinct for what concerns the addressed problem, the strength of the performance guarantees and the algorithmic approach. Specifically, the considered benchmarks are different: in the adversarial setting [Bernasconi et al. (2024b)] compare their algorithm against the best fixed action in hindsight, OPT(BwRK)=sup⁡x∈X∑t=1Tft(x).\text{OPT}({\text{BwRK}})= \sup {x \in \mathcal{X}} \sum_{t=1}^T f_t(x). while we consider the dynamic unconstrained optimum, OPT(ORA)=max⁡(x1,...,xT)∈XT∑t∈[T]ft(xt),\text{OPT}({\text{ORA}})= \max {(x_1,...,x_T) \in \mathcal{X}^T} \sum_{t \in [T]} f_t(x_t), which allows the comparator to select a different action at every round. Consequently, $\text{OPT}({\text{BwRK}}) \leq \text{OPT}({\text{ORA}}) $ and our adversarial guarantee holds against a more challenging benchmark, while retaining the same competitive ratio α\alpha. In the stochastic setting, [Bernasconi et al. (2024b)] compare with the stationary LP benchmark T⋅OPTLP(fˉ,bˉ)T \cdot \text{OPT}^{\text{LP}}({\bar{f}, \mathbf{\bar{b}}}), while our benchmark is the expected offline optimum OPT(stoc)=Eγ∼PT[OPT(γ)]\text{OPT}({\text{stoc}}) = \mathbb{E}_{\gamma \sim \mathcal{P}^T}[\text{OPT}(\gamma)] The two benchmarks therefore capture different notions of adaptivity and feasibility.

For what concerns the theoretical analysis, the bounding mechanism in [Bernasconi et al. (2024b)] (their Lemma 5.5) relies on a proof by contradiction over time intervals, strictly requiring the cumulative sublinear regret bound of the primal regret minimizer. In stark contrast, our exact maximizer enables a direct, step-by-step inductive proof (our Lemmas B.3 and 4.1). Our algorithm directly maximizes the instantaneous Lagrangian, eliminating the need for a primal regret minimizer and allowing us to deterministically prove that ⟨λt,bt(xt)−ρ⟩≤1−(ρ+β)∥λt∥1\langle \mathbf{\lambda}_t, \mathbf{b}_t(x_t) - \mathbf{\rho} \rangle \leq 1 - (\rho + \beta) \| \mathbf{\lambda}_t \|_1 in both the stochastic and the adversarial setting. Thus we achieve a tighter dependence on mm, attaining O(m/(ρ+β))\mathcal{O}(\sqrt{m} / (\rho + \beta)) bound on the norm of the Lagrangian multipliers.

Because of our deterministic dual bound and our definition of OPTstoc\text{OPT}_{\text{stoc}}, our proof for the stochastic regret (Theorem 4.2) diverges from [Bernasconi et al. (2024b)]. They rely on high-probability concentration bounds to relate realized sequences to expectations; we instead employ a clean martingale argument directly relating the expected Lagrangian to the stochastic optimum.

We believe that successfully tackling these specific challenges in order to considerably improve the ORA state-of-the-art provides a non-trivial contribution.

W3. The paper claims an improved competitive ratio α=(ρ+β)/(1+β)\alpha = (\rho + \beta)/(1 + \beta), but only proves an upper bound. It would strengthen the paper to show that this α\alpha is optimal or at least discuss known impossibility results. Otherwise, "improves the competitive ratio" is only an upper-bound statement.

We thank the Reviewer for the opportunity to clarify this aspect. In general adversarial ORA without additional structural assumptions, established impossibility results (see [Balseiro and Gur, 2019]) prove that the competitive ratio cannot exceed a factor proportional to the per-round budget ρ\rho. When β=0\beta = 0, our algorithm exactly matches this optimal achievable baseline. When β>0\beta > 0, the structure of the void action mathematically expands the guaranteed available budget margin from ρ\rho to ρ+β\rho + \beta. Thus, α=(ρ+β)/(1+β)\alpha = (\rho + \beta) / (1 + \beta) naturally generalizes the optimal worst-case bounds of the standard monotonic setting to the non-monotonic one.

W4. The algorithm plays the void action whenever any resource has Bt,i<1B_{t,i} < 1, even if there are feasible actions that consume no such resource. This is simple and safe, but it can be overly conservative. The authors should discuss whether this affects the claim "recovers state-of-the-art for β=0\beta = 0", and whether a more refined safety condition could improve constants or the competitive ratio.

We thank the Reviewer for the comment. It is correct that triggering the void action as soon as any resource falls below 11 is a conservative choice. We agree that in practical scenarios a safety condition would reduce forced void rounds and improve the empirical constants. However, in our case (worst-case bound) this does not affect the claim of recovering the state-of-the-art for β=0\beta = 0. In a worst-case adversarial sequence, assuming i⋆i^\star is the resource triggering the replenishment, the adversary can choose inputs that only consume i⋆i^\star, which is already depleted. A more refined safety condition would not improve the worst-case asymptotic bounds or the competitive ratio.

W5. The replenishment assumption limits the application claims, where one known action must uniformly replenish every resource on every request, with no storage caps, delays, or acquisition costs. The paper acknowledges this as future work but provides no concrete application satisfying these assumptions, so practical significance remains under-established.

We thank the Reviewer for pointing this out. We agree that a global, cost-free void action is a strong assumption. As detailed in Remark 2.1, it serves as a fundamental theoretical baseline to establish the worst-case safety margin β\beta required to stabilize the dual space and ensure strict constraint satisfaction. However, to bridge the gap toward practical applications, we have added a dedicated new section in the Appendix of the updated version (Appendix C). This section formally extends our primal-dual framework and bounded-multiplier analysis to accommodate decentralized, resource-specific replenishing actions. We believe this extension significantly strengthens the practical relevance of our framework.

W6. This is a theoretical paper, so experiments are not mandatory, but a small synthetic experiment would help illustrate the non-monotonic dynamics and the effect of β\beta.

We fully agree with the Reviewer that synthetic experiments ease the understanding of the theoretical analysis. To explicitly illustrate our claims, we have conducted a synthetic experiment showcasing the non-monotonic dynamics of the budget over time. The results clearly demonstrate how varying β>0\beta > 0 strictly stabilizes the dual variables and reduces the number of forced void rounds compared to the standard monotonic baseline. We have included these plots in the Appendix D of the updated version.

We hope to have addressed the Reviewer's concerns. Please let us know if further discussion is necessary.

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

This paper studies online resource allocation when resources can be replenished. Classical online resource allocation usually assumes that every action consumes resources. Here, actions may also restore them, and the authors assume a "void" action that yields no reward but recovers at least β\beta units of every resource. The algorithm follows the dual gradient descent approach. When the budget is sufficient, it chooses actions using the Lagrangian and updates the dual variables. When the budget runs low, it plays the void action and pauses the dual updates until the budget recovers. The authors prove O(T)O(\sqrt T) regret for stochastic inputs and O(T)O(\sqrt T) α\alpha-regret for adversarial inputs, and the budget constraint is never violated. Both bounds improve as β\beta grows. The problem is well motivated and the proofs are correct. However, the model, the algorithmic framework, and the analysis largely follow prior work on the bandit version of this problem (Bernasconi et al., 2024b), so the new contribution is limited.

Critical strengths
  1. Resources that are both consumed and replenished arise in inventory management, energy storage, and cloud computing. Most of the online resource allocation literature assumes that resources only decrease, so extending the framework to replenishment is a reasonable direction.

  2. The same algorithm, without modification, provides guarantees for both stochastic and adversarial inputs, and it never exceeds the budget at any time.

  3. The theoretical results are clearly stated. I checked the main proofs and found no errors.

Critical weaknesses
  1. Bernasconi et al. (2024b) study almost the same problem under bandit feedback. Both papers share:

    • the same model and void-action assumption;
    • the same algorithmic framework, which plays the void action and pauses the updates when the budget is low;
    • the same proof strategy;
    • the same competitive ratio (ρ+β)/(1+β)(\rho+\beta)/(1+\beta).

    The main difference is that the full-information setting allows the algorithm to maximize the Lagrangian directly in each round. This is standard in online resource allocation (Balseiro et al., 2023), and Bernasconi et al. note that their results extend to full feedback. As a result, the paper reads mainly as a transfer of an existing framework to online resource allocation. However, it mentions this work only briefly in the related work section and does not compare with it in Table 1. The authors should clarify which technical difficulties are new relative to this work.

  2. The improvement attributed to β\beta comes mainly from the model rather than from the algorithm. Because the void action restores at least β\beta per round, the budget available per round effectively grows from ρ\rho to ρ+β\rho+\beta. Replacing ρ\rho with ρ+β\rho+\beta in the standard results already yields the regret bounds and competitive ratio in this paper, so these improvements are expected. In the adversarial setting, the benchmark is the optimum that ignores the budget. Against this benchmark, even an offline algorithm that knows all future inputs can only achieve an α\alpha fraction. The improved ratio therefore reflects the choice of benchmark rather than a better online algorithm. A more meaningful question is what ratio is achievable against the budget-constrained offline optimum, but the paper does not discuss this or provide any lower bound. Finally, the improvement in regret requires knowing β\beta in advance. When β\beta is unknown, the bound has the same order as for β=0\beta=0, which contradicts the claim in Section 5 that prior knowledge of β\beta is not required.

  3. The paper assumes an action that costs nothing yet replenishes all resources at the same time. In the inventory and energy examples used as motivation, however, replenishment has to be paid for and usually concerns a single resource. Bernasconi et al. (2024b) also point out that this kind of assumption rarely holds in practice. Moreover, the results depend only on the amount restored by the void action. Other actions that replenish resources never improve the guarantees, which weakens the practical value of allowing replenishment in the model.

Questions for authors
  1. Following Weakness 1, consider the framework of Bernasconi et al. (2024b) with an exact Lagrangian maximizer as the primal step and OGD as the dual step. Can Theorem 4.4 be derived directly from this framework? If not, where does the difficulty arise?

  2. Lines 309–312 argue that the dual updates must be paused in rounds where the void action is played. What would go wrong if, in those rounds, the dual variables were updated with the action that maximizes the Lagrangian, as in Balseiro et al. (2023)?

5 comments

We thank the Reviewer for the effort in evaluating our work.

Bernasconi et al. (2024b) study almost the same problem under bandit feedback. Both papers share:

  • the same model and void-action assumption;
  • the same algorithmic framework, which plays the void action and pauses the updates when the budget is low;
  • the same proof strategy;
  • the same competitive ratio (ρ+β)/(1+β)(\rho + \beta)/ (1 + \beta).

The main difference is that the full-information setting allows the algorithm to maximize the Lagrangian directly in each round. This is standard in online resource allocation (Balseiro et al., 2023), and Bernasconi et al. note that their results extend to full feedback. As a result, the paper reads mainly as a transfer of an existing framework to online resource allocation. However, it mentions this work only briefly in the related work section and does not compare with it in Table 1. The authors should clarify which technical difficulties are new relative to this work.

We thank the Reviewer for the opportunity to better clarify the relation with [Bernasconi et al. (2024b)]. We agree that this work is closely related to ours, although the two papers solve different problems. For this reason, we believe that a direct side-by-side comparison in Table 1 would not be particularly informative; we will instead expand the discussion to clarify the relationship between the two works in the final version of the paper.

We believe that the works are distinct for what concerns not only the setting but the strength of the performance guarantees and the algorithmic approach used to establish them. Specifically, in the adversarial setting [Bernasconi et al. (2024b)] compare their algorithm against the best fixed action in hindsight, OPT(BwRK)=sup⁡x∈X∑t=1Tft(x).\text{OPT}({\text{BwRK}}) = \sup_{x \in \mathcal{X}} \sum_{t=1}^T f_t(x). In contrast, our benchmark is the dynamic unconstrained optimum, OPT(ORA)=max⁡(x1,…,xT)∈XT∑t∈[T]ft(xt),\text{OPT}({\text{ORA}}) = \max{(x_1,\ldots,x_T) \in \mathcal{X}^T} \sum_{t \in [T]} f_t(x_t), which allows the comparator to select a different action at every round. Consequently, $\text{OPT}({\text{BwRK}}) \leq \text{OPT}({\text{ORA}}) $ and our adversarial guarantee holds against a more challenging benchmark, while retaining the same competitive ratio α\alpha.

A similar distinction arises in the stochastic setting. [Bernasconi et al. (2024b)] establish regret with respect to the stationary LP benchmark T⋅OPTLP(fˉ,bˉ)T \cdot \text{OPT}^{\text{LP}}({\bar{f}, \mathbf{\bar{b}}}), which optimizes over a fixed distribution on actions and imposes resource constraints in expectation. Our benchmark is instead the expected offline optimum OPT(stoc)=Eγ∼PT[OPT(γ)]\text{OPT}({\text{stoc}}) = \mathbb{E}_{\gamma \sim \mathcal{P}^T}[\text{OPT}(\gamma)] where, for each realized input sequence, the comparator can choose a potentially different action at every round, subject to satisfying the cumulative resource constraints on that sequence. The two benchmarks therefore capture different notions of adaptivity and feasibility.

The same bound of Theorem 4.4 cannot be derived directly from the framework of [Bernasconi et al. (2024b)] by simply replacing the primal regret minimizer with a greedy Lagrangian maximizer. This fundamental algorithmic difference requires an entirely different proof technique for bounding the dual multipliers. The analysis in [Bernasconi et al. (2024b)] (their Lemma 5.5) relies on a proof by contradiction over time intervals, strictly requiring the cumulative sublinear regret bound of the primal regret minimizer. In contrast, our exact maximizer enables a direct, step-by-step inductive proof (our Lemmas B.3 and 4.1). If one were to adapt their interval-based argument to an exact maximizer, the analysis would yield a looser bound on the dual multipliers. As the Reviewer pointed out, our algorithm directly maximizes the instantaneous Lagrangian, eliminating the need for a primal regret minimizer and allowing us to deterministically prove that ⟨λt,bt(xt)−ρ⟩≤1−(ρ+β)∥λt∥1\langle \mathbf{\lambda}_t, \mathbf{b}_t(x_t) - \mathbf{\rho} \rangle \leq 1 - (\rho + \beta) \| \mathbf{\lambda}_t \|_1 in both the stochastic and the adversarial setting. Thus we achieve a tighter dependence on mm, attaining O(m/(ρ+β))\mathcal{O}(\sqrt{m} / (\rho + \beta)) bound on the norm of the Lagrangian multipliers.

Because of our deterministic dual bound and our definition of OPTstoc\text{OPT}_{\text{stoc}}, our proof for the stochastic regret (Theorem 4.2) diverges from [Bernasconi et al. (2024b)]. They rely on high-probability concentration bounds to relate realized sequences to expectations; we instead employ a clean martingale argument directly relating the expected Lagrangian to the stochastic optimum.

We believe that successfully tackling these specific challenges in order to considerably improve the ORA state-of-the-art provides a non-trivial contribution.

The improvement attributed to β\beta comes mainly from the model rather than from the algorithm. Because the void action restores at least β\beta per round, the budget available per round effectively grows from ρ\rho to ρ+β\rho + \beta. Replacing ρ\rho with ρ+β\rho + \beta in the standard results already yields the regret bounds and competitive ratio in this paper, so these improvements are expected. In the adversarial setting, the benchmark is the optimum that ignores the budget. Against this benchmark, even an offline algorithm that knows all future inputs can only achieve an α\alpha fraction. The improved ratio therefore reflects the choice of benchmark rather than a better online algorithm. A more meaningful question is what ratio is achievable against the budget-constrained offline optimum, but the paper does not discuss this or provide any lower bound. Finally, the improvement in regret requires knowing β\beta in advance. When is unknown, the bound has the same order as for β=0\beta = 0, which contradicts the claim in Section 5 that prior knowledge of β\beta is not required.

  • While it is true that the model increases the theoretical margin to ρ+β\rho + \beta, standard ORA algorithms (e.g., Balseiro et al., 2023) would fail to exploit it. Due to the presence of negative costs, unaligned budget dynamics (cross-constraints compensation) break the natural self-regulation of the dual space. Without our framework, the multipliers can grow unboundedly, and standard bounding arguments (see Proposition 2 from [Balseiro et al., 2023]) would fail. Our approach safely extracts the ρ+β\rho + \beta margin while keeping dual multipliers tightly bounded (Lemma 4.1).

  • Regarding the adversarial benchmark, we evaluate the performance of the algorithm against the dynamic unconstrained optimum (OPT$_{\text{adv}}$), which is the standard, well-established benchmark in literature. It is a known result that under fully adversarial constraints, no algorithm can achieve a stronger competitive ratio or bypass the scaling factor. Matching lower bounds from the ORA literature (e.g., [Balseiro and Gur, 2019]) prove that no algorithm can do better than a factor proportional to the problem-specific margin without any additional assumption. Consequently, the α\alpha-regret metric is necessary and represents the strongest achievable guarantee in this setting.

  • For what concerns the knowledge on β\beta, we clarify that there is no contradiction. As stated in Theorem 4.2 and Theorem 4.4, if β\beta is unknown, the algorithm sets the learning rate using only the known budget ρ\rho. This still achieves the optimal O(T)\mathcal{O}(\sqrt{T}) sublinear regret. Knowing β\beta strictly improves the constant factors, but is not required for the algorithm to run or attain sublinearity.

The paper assumes an action that costs nothing yet replenishes all resources at the same time. In the inventory and energy examples used as motivation, however, replenishment has to be paid for and usually concerns a single resource. Bernasconi et al. (2024b) also point out that this kind of assumption rarely holds in practice. Moreover, the results depend only on the amount restored by the void action. Other actions that replenish resources never improve the guarantees, which weakens the practical value of allowing replenishment in the model.

We thank the Reviewer for this observation. We agree that a cost-free, globally replenishing void action is a strong assumption. As detailed in Remark 2.1 and Section 5, our model serves as a theoretical baseline establishing the worst-case replenishment margin β\beta required to stabilize the dual space. We remark that while it is true that the final algebraic guarantees (Theorem 4.2 and Theorem 4.4) only explicitly feature β\beta, it is not true that other replenishing actions are useless for the guarantees. Since we cannot a priori assume the availability of other replenishing actions (although they are allowed by the model) our worst-case analysis must necessarily rely on the guaranteed parameter β\beta provided by the void action. However, the primal-dual dynamic actively exploits any action that replenishes resources. If a standard action xx provides a negative consumption (bt,i(x)<0b_{t,i}(x) < 0), it yields a negative cost in the Lagrangian formulation. This naturally encourages the greedy primal step to select it when dual multipliers are high. By selecting these replenishing actions, the algorithm effectively injects negative components into the cumulative sum $\sum \langle \mathbf{\lambda}_t, \mathbf{b}_t(x_t) - \mathbf{\rho} \rangle $. This dynamic strictly decreases the dual penalties and reduces the number of forced void rounds where zero reward is collected.

To formalize this mechanism and bridge the gap toward practical applications, we have added a dedicated new section in the Appendix of the updated version (Appendix C). This section extends our bounded-multiplier analysis to accommodate resource-specific replenishing actions (without requiring a global void action), proving that our analytical machinery seamlessly adapts to more complex, decentralized replenishment dynamics.

Lines 309–312 argue that the dual updates must be paused in rounds where the void action is played. What would go wrong if, in those rounds, the dual variables were updated with the action that maximizes the Lagrangian, as in Balseiro et al. (2023)?

As explained in Section 3, If we updated the dual variables during forced void action rounds, the strictly negative costs (replenishment β>0\beta > 0) would artificially and rapidly drive the dual multipliers towards zero. Once the budget is restored and the algorithm starts playing actively, it would perceive all resources as extremely "cheap", being induced to over-consume resources and immediately deplete the budget again. Pausing the updates prevents this behavior and preserves the dual penalties for future active rounds.

We hope to have addressed the Reviewer's concerns. Please let us know if further discussion is necessary.

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

The paper studies online resource allocation when actions can both consume and restore resources, with rewards and costs revealed before each decision. It analyzes a primal–dual algorithm that maximizes the current Lagrangian when sufficient budget is available and otherwise takes a safe replenishing action while freezing the dual variables. The algorithm maintains budget feasibility throughout and achieves O(T)O(\sqrt{T}) expected regret under i.i.d. inputs and an O(T)O(\sqrt{T}) additive loss relative to a fraction (ρ+β)/(1+β)(\rho+\beta)/(1+\beta) of the unconstrained dynamic optimum under adversarial inputs. Here, TT is the number of rounds, ρ\rho is the per-round budget for each resource, and β\beta is the minimum replenishment guaranteed by the fallback action for every resource on every round.

Critical strengths

The paper studies a natural generalization of the fundamental online resource allocation problem by allowing actions to replenish resources. It cleanly extends the classical guarantees to signed resource consumption, retaining the familiar regret rate even without guaranteed positive replenishment (β=0\beta=0), and obtaining sharper guarantees when β>0\beta>0. The same algorithm handles both stochastic and adversarial inputs while maintaining budget feasibility at every round. This is a meaningful extension of the classical theory: it accommodates richer resource dynamics without sacrificing either feasibility or robustness to the input model.

Critical weaknesses
  1. The technical novelty could be explained more clearly. The algorithm and analysis appear to build substantially on techniques from closely related work. While the extension and resulting guarantees are useful, it would help to identify which parts require new ideas and which follow by adapting existing arguments. This would make the technical contribution easier to assess.

  2. The improved guarantees for β>0\beta>0 rely on a restrictive replenishment assumption: a single known fallback action must replenish every resource by at least β\beta on every round, with zero reward rather than a negative replenishment cost. This excludes settings where recovery is uncertain, resource-specific, or costly in the reward objective. Although the authors acknowledge related extensions as future work, the assumption limits how broadly the stronger guarantees apply to the motivating applications. This concern does not invalidate the results, but it reduces their practical significance.

Questions for authors

See weakness 1

2 comments

We thank the Reviewer for the positive evaluation of our work.

The technical novelty could be explained more clearly. The algorithm and analysis appear to build substantially on techniques from closely related work. While the extension and resulting guarantees are useful, it would help to identify which parts require new ideas and which follow by adapting existing arguments. This would make the technical contribution easier to assess.

We thank the Reviewer for appreciating the usefulness of our analysis. We agree that clarifying the technical boundary between our work and existing approaches would strengthen the paper. The core technical novelty of our work lies in the self-regulation of the dual space under non-monotonic budget dynamics. In standard ORA frameworks (e.g., [Balseiro et al., 2023]) resource consumption is strictly positive, ensuring the dual variables are naturally bounded. However, introducing negative costs (replenishments) creates the risk of cross-constraints compensation (as explained in Section 1.2), that is, unaligned constraints could mask violations and cause the Lagrangian multipliers of scarce resources to grow unboundedly. In Lemma 4.1, we prove that despite negative costs, our primal-dual dynamics keep the norm of the multipliers strictly bounded by a tight O(m/(ρ+β))\mathcal{O}(\sqrt{m} / (\rho+\beta)) factor. Crucially, this result holds deterministically in both the stochastic and the adversarial setting, yielding a sharper dependence on the number of resources mm and the effective margin than the bounding techniques of related works.

The improved guarantees for β>0\beta>0 rely on a restrictive replenishment assumption: a single known fallback action must replenish every resource by at least β\beta on every round, with zero reward rather than a negative replenishment cost. This excludes settings where recovery is uncertain, resource-specific, or costly in the reward objective. Although the authors acknowledge related extensions as future work, the assumption limits how broadly the stronger guarantees apply to the motivating applications. This concern does not invalidate the results, but it reduces their practical significance.

We thank the Reviewer for the opportunity to clarify this. The assumption of a global void action is necessary to establish a uniform safety margin β\beta across all resources, ensuring strict constraint satisfaction. While we agree that this analysis is not immediately applicable to complex systems with resource-specific replenishments, the extension is straightforward. To explicitly address this, we have added a dedicated new section in the Appendix of the updated version (Appendix C). This section formally sketches how our framework and analysis can be generalized to accommodate resource-specific replenishing actions, bridging the gap toward these practical applications.

Please let us know if further discussion is necessary.

Thank you for the clarifications and for addressing my comments. I will maintain 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.