- 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 -regret when 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 , but only proves an upper bound. It would strengthen the paper to show that this 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 , 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 ", 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 .
Questions for authors
Please refer to W1-W6.
2 comments
W3. The paper claims an improved competitive ratio , but only proves an upper bound. It would strengthen the paper to show that this 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 . When , our algorithm exactly matches this optimal achievable baseline. When , the structure of the void action mathematically expands the guaranteed available budget margin from to . Thus, 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 , 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 ", 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 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 . In a worst-case adversarial sequence, assuming is the resource triggering the replenishment, the adversary can choose inputs that only consume , 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 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 .
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 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.
We thank the Reviewer for the effort in evaluating our work.
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.
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)=supx∈X∑t=1Tft(x). while we consider the dynamic unconstrained optimum, OPT(ORA)=max(x1,...,xT)∈XT∑t∈[T]ft(xt), 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 α. In the stochastic setting, [Bernasconi et al. (2024b)] compare with the stationary LP benchmark T⋅OPTLP(fˉ,bˉ), while our benchmark is the expected offline optimum OPT(stoc)=Eγ∼PT[OPT(γ)] 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 in both the stochastic and the adversarial setting. Thus we achieve a tighter dependence on m, attaining O(m/(ρ+β)) bound on the norm of the Lagrangian multipliers.
Because of our deterministic dual bound and our definition of OPTstoc, 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.