Near-Optimal Consistency-Robustness Trade-Offs for Learning-Augmented Online Knapsack Problems

Thank you very much for your positive review and your constructive feedback.

On the small item weight assumption: We agree that this is a standard and important assumption in the integral setting. Our lower bounds (e.g., Theorem A.1) show that it is necessary for meaningful guarantees in our setting. But we agree that exploring other settings, or making additional assumptions that allow the small weight assumption to be relaxed, would be interesting.

On clarifying the intuition behind “prebuying” in PP-a: Thank you for this suggestion. We will improve the explanation of PP-a’s dynamic reservation strategy in the main text and use a small running example to provide better intuition for the “prebuying” mechanism.

Thank you for your thoughtful and positive review. We especially appreciate your recognition of the simplicity and practicality of our prediction models, as well as the value of extending results to the integral setting. We will continue to refine the writing and presentation to further improve clarity, especially in the introduction and technical sections.

Thank you for your detailed and thoughtful review. You have raised some great points which will help clarify the paper.

On Theorem 4.2 and randomized algorithms: Thank you for the careful reading – you are correct that Theorem 4.2 is currently proven only for deterministic algorithms. We will revise the paper to make this explicit in both the theorem statement and the surrounding discussion.

We strongly suspect that the theorem can be extended to randomized algorithms with some small modifications, and we will attempt to do so for the camera-ready. As evidence for this, note that the ZCL algorithm [4], which achieves the optimal worst-case competitive ratio for both fractional and integral OKP under a bounded value range, is itself deterministic, and cannot be improved on by any randomized algorithm.

To extend Theorem 4.2 to randomized algorithms, a first step is to modify the existing proof of Lemma A.5. Specifically, we can replace the deterministic utilization function with its expectation under a randomized algorithm—an approach aligned with the proof structure in Lemma A.6, which already reasons about expected capacity usage.

Thanks again for raising this point—we believe addressing it will significantly strengthen the clarity and completeness of the paper. Some of our lower bounds do hold under both randomized and deterministic algorithms (e.g., Theorem 3.1). We will make this explicit in their statements.

On the reviewer’s suggested randomized algorithm to avoid the small weights assumption: We appreciate the suggestion of a simple randomized strategy that mixes between accepting all items with unit value ≥ v^\hat{v} and accepting only items with unit value equal to v^\hat{v}. This algorithm does indeed achieve a 2-competitive ratio in the oblivious adversary model, and does not require a bounded weight assumption.

However, under an adaptive adversary, meaning that an adversary can change the input sequence “on the fly” based on the algorithm’s past decisions, this approach can fail. E.g., the first item presented can have unit value \hat{v} and weight 1. If the algorithm does not accept it, the adversary halts the input sequence. If the algorithm does accept it, the adversary may follow with a very high-value item with weight slightly less than 1, which cannot be packed due to limited capacity.

For this reason, the mentioned randomized algorithm does not contradict our lower bounds, which hold for an adaptive adversary. The adaptive adversary model is the standard model in the online algorithms literature [1,2]. However, we agree that we should add text throughout that explicitly mentions which adversarial model we are working under. We will also qualify the statement about small item weights being required by saying that this is for an adaptive adversary model only, and will note the simple randomized baseline for oblivious adversaries given by the reviewer. Thanks again for pointing this out.

On using Yao’s Minmax for Theorem 3.1: Thanks for the suggestion – we agree we should be able to do this and clean up the proof a bit.

On terminology "value" versus "unit value": Thank you for pointing this out. We use “value” to refer to the unit value (i.e., value-to-weight ratio). This convention is common in the online knapsack literature. For example, it is used in prior work by [3, 5] and other papers on learning-augmented knapsack. Nonetheless, we will revise the paper to clarify our terminology up front and make our usage more precise.

[1] Adam Lechowicz, Nicolas Christianson, Bo Sun, Noman Bashir, Mohammad Hajiesmaili, Adam Wierman, and Prashant Shenoy. 2025. Learning-Augmented Competitive Algorithms for Spatiotemporal Online Allocation with Deadline Constraints. Proc. ACM Meas. Anal. Comput. Syst. 9, 1, Article 8 (March 2025), 49 pages.

[2] Cygan, Marek & Jeż, Łukasz. (2014). Online Knapsack Revisited. Theory of Computing Systems. 58. 10.1007/978-3-319-08001-7_13.

[3] S. Im, R. Kumar, M. Montazer Qaem, and M. Purohit. Online Knapsack with Frequency Predictions. In Advances in Neural Information Processing Systems (NeurIPS), volume 34, pages 2733–2743, 2021.

[4] Y. Zhou, X. Lin, and H. Zhao. Online budgeted truthful matching: A randomized primal-dual approach. Theoretical Computer Science, 2008.

[5] Bo Sun, Lin Yang, Mohammad Hajiesmaili, Adam Wierman, John C. S. Lui, Don Towsley, and Danny H.K. Tsang. 2022. The Online Knapsack Problem with Departures. Proc. ACM Meas. Anal. Comput. Syst. 6, 3, Article 57 (December 2022), 32 pages.

Thank you for your thoughtful review and for highlighting the key question about the robustness of MIX when predictions may be arbitrarily incorrect.

On the robustness guarantee of MIX despite poor predictions: The MIX algorithm handles untrusted predictions by combining the decisions of a robust baseline (ZCL) and a prediction-based algorithm using a parameter $\lambda \in (0,1)$. Since this is a maximization problem, the competitive ratio is defined as $\text{OPT} / \text{ALG}$. Even if the prediction-based algorithm performs poorly (e.g., contributes zero profit), the robust algorithm still guarantees a fraction of OPT. To make this concrete, consider a simple example: suppose the algorithm allocates half the capacity to the robust algorithm and half to the prediction-based one. If the prediction is arbitrarily wrong and the prediction-based component gets zero value, then the robust half still contributes half of its guaranteed performance. The total gain is then: $\text{ALG} = \frac{1}{2} \cdot \text{ALG}{\text{pred}} + \frac{1}{2} \cdot \text{ALG}{\text{robust}} = 0 + \frac{1}{2} \cdot \frac{\text{OPT}}{C} = \frac{\text{OPT}}{2C}$

where C is the worst case competitive ratio achieved by $ALG_{robust}$. Thus, the competitive ratio of ALG is: $\frac{\text{OPT}}{\text{ALG}} = \frac{\text{OPT}}{\text{OPT}/(2C)} = 2C$.

Since ZCL is $C = \ln(U/L) + 1$-competitive, the MIX algorithm remains $2 \cdot (\ln(U/L) + 1)$-competitive in this extreme case. This reasoning critically relies on the fact that we are solving a maximization problem, where getting zero gain from the learning-augmented part of the algorithm still results in a bounded ratio. In contrast, in minimization settings, such an approach could lead to an unbounded competitive ratio if one component incurs a large cost. We will clarify this in the final version.