Wait-Less Offline Tuning and Re-solving for Online Decision Making

Response to Reviewer QGM5

We appreciate your valuable feedback.

Claims And Evidence

1. Claims on the assumptions (non-degeneracy)

   Thank you for pointing this out. We will add a more detailed discussion to clarify the assumptions in the paper. To achieve $\mathcal{O}(\sqrt{T})$ regret, we agree that these assumptions are not minimal. But we also want to note that without non-degeneracy (or its variant), [3] has shown that $\Omega(\sqrt{T})$ is a lower bound for OLP, and most of the literature in this line assumes non-degeneracy (or similar assumptions).

Experimental Designs Or Analyses

1. Experiments are only on uniform and normal distributions

   We have added additional experiments on more problem distributions and tested performance under different re-solving frequencies. Our algorithms continue to demonstrate strong performance, consistent with the result in Theorem 3.2. We kindly refer the reviewer to the anonymous link https://anonymous.4open.science/r/icml_2025_olp-6C17/ for more details.

Other Strengths And Weaknesses

1. Requirement on non-degeneracy

   Please see our response to Claims And Evidence.

2. Lack of direct comparison with existing literature

   Thank you for pointing this out. [1] studies a similar problem under the finite support setting. We adapted our algorithms to finite support and added experiments to compare with [1] in https://anonymous.4open.science/r/icml_2025_olp-6C17/. In the finite-support setting, we find that our algorithm achieves lower regret while [1] is often faster. We will add additional experiments and discussions in the revision.

Questions

1. Stopping time analysis

   We believe that a stopping time analysis is possible. This paper adapts the analysis of the LP-based method to the metric of first-order methods, and we can do the other way around by properly defining a stopping time for first-order methods [3]. Another simple way is to "subtract" $O(f + \log T)$ resource from the initial inventory and run OLP on this new problem, and in expectation, the resource violation from the original problem can be removed.

2. Unknown time horizon

   To our knowledge, in the OLP setting, not knowing the horizon $T$ makes the problem harder. In [1], it is shown that only a competitive ratio result is achievable when $T$ has uncertainty. The most challenging part is that the average resource assumption A2.1 (c) is no longer well-defined. Since both LP-based and first-order methods require some estimate of average resources to work, a lack of this knowledge makes the problem more difficult.

   Although the problem is theoretically challenging, in practice, it is often possible to make some prior prediction using data-driven approaches or based on the resources available at hand. For example, in online advertising, the number of customers can be predicted from historical statistics. Besides, in practice, the selling horizon is sometimes decided by some upper-level decision-makers. e.g., a company selling products before festival events. In this case, it is available to the decision-maker as a problem parameter.

3. $O(1)$ regret bound under finite support setting

   This is also a very good question. To our knowledge, $O(1)$ regret is achievable in the finite-support setting with the same LP-based algorithm and a non-degeneracy assumption [4]. Since our analysis interpolates between the regret guarantee of first-order and LP-based methods, we believe the analysis in [4] can be adapted to give a similar result, which we leave to future work.

Thank you for your time in the review process!

References

[1] Li, G., Wang, Z., & Zhang, J. (2024). Infrequent resolving algorithm for online linear programming. arXiv preprint arXiv:2408.00465.

[2] Balseiro, S., Kroer, C., & Kumar, R. (2023, June). Online resource allocation under horizon uncertainty. In Abstract Proceedings of the 2023 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (pp. 63-64).

[3] Balseiro, S., Lu, H., & Mirrokni, V. (2020, November). Dual mirror descent for online allocation problems. In International Conference on Machine Learning (pp. 613-628). PMLR.

[4] Chen, G., Li, X., & Ye, Y. (2024). An improved analysis of LP-based control for revenue management. Operations Research, 72(3), 1124-1138.

Response to Reviewer GkFi

Thank you for your positive evaluation of our paper!

Experimental Designs Or Analyses

1. Computational efficiency.

   We kindly refer the reviewer to Table 3 (Page 7 top) for a running time comparison between different methods, and in the revision we'll add a more comprehensive experiment to compare the computational aspects of different algorithms.

2. Parameter setting.

   Thank you for your comments. In Algorithm 1, we take the learning rate as $\mathcal{O}(1/f^{1/2})$ when $t \leq f$ and $\mathcal{O}(1/f^{2/3})$ when $t \geq kf$. In Algorithm 2, we take the learning rate as $\mathcal{O}(1/t)$. We'll add a more detailed experiment setup section in the revision to cover the parameter settings (frequency/learning rate) of different algorithms.

3. $T^{1/3}$ solving frequency.

   Thank you for pointing this out. We have experiments across different re-solving frequencies $f \in \\{ T^{1/3}, T^{1/2}, T^{2/3} \\}$ in Section 4.1 to evaluate the performance of our main algorithms. A smaller $f$ leads to lower regret but higher computational cost, while a larger $f$ improves the decision efficiency at the expense of decision optimality. Section 4.2 is designed to compare the performances among different algorithms, and the choice of $T^{1/3}$ for Section 4.2 is simply one of the candidate frequencies.

Other Strengths And Weaknesses

1. Insights of Algorithm 2.

   Thank you for pointing this out. Algorithm 1 has a solid theoretical guarantee, but it does not update the dual price between two consecutive LP resolves. Algorithm 2 is proposed to alleviate this issue: between two LP resolves, the dual price is also updated using the first-order method. We adopt a smaller step size for first-order updates between LP resolves in Algorithm 2 to avoid deviating too far from the LP-guided solutions. We leave a more rigorous analysis of Algorithm 2 to future work.

2. Discussion on the frequency of resolving and comparison with [1].

   Thank you for the comment. Indeed, in [1], the LPs are solved at geometric intervals. However, this type of resolving only guarantees regret of order $O(\sqrt{T})$, and to achieve $o(\sqrt{T})$ regret under our setting, the only two ways we are aware of are

   • solving the LPs at every time interval with an action-history dependent algorithm (adjusting $d_t$). This achieves $O(\log T)$ regret [2].

   • using an $o(\sqrt{T})$ stepsize for the first-order method starting from a good initial guess of $p^\star$. This achieves $O(T^{1/3})$ regret [3].

   Our algorithm essentially interpolates between these two $o(\sqrt{T})$ regret bounds, and our LP-based algorithm also requires periodic re-solving. Otherwise, only $O(\sqrt{T})$ regret can be guaranteed.

Questions For Authors

1. Insights on the performance enhancement from Algorithm 2.

   Please see our response to "Other Strengths And Weaknesses".

2. Frequency $T^{1/3}$.

   Please see our response to Experiment Designs or Analyses.

Thank you again for your efforts in the review process!

References

[1] Agrawal, S., Wang, Z., & Ye, Y. (2014). A dynamic near-optimal algorithm for online linear programming. Operations Research, 62(4), 876-890.

[2] Li, X., & Ye, Y. (2022). Online linear programming: Dual convergence, new algorithms, and regret bounds. Operations Research, 70(5), 2948-2966.

[3] Gao, W., Sun, C., Xue, C., Ge, D., & Ye, Y. (2024). Decoupling Learning and Decision-Making: Breaking the $\mathcal {O}(\sqrt {T})$ Barrier in Online Resource Allocation with First-Order Methods. arXiv preprint arXiv:2402.07108.

Response to Reviewer LeBH

Thank you for the valuable feedback on our paper.

Other Strengths And Weaknesses

1. Unknown horizon $T$

   This is a very good point. To our knowledge, in the OLP setting, an unknown horizon length $T$ can make the problem much more complicated: it is shown in [1] that it may not be possible to achieve sublinear regret with horizon uncertainty. In particular, the average resource assumption A2.1 (c) widely used in OLP literature is no longer well-defined, and an algorithm would also have to adapt to horizon uncertainty. Addressing this challenge would likely require first adapting LP-based and first-order OLP methods to uncertain horizons before tackling a hybrid approach.

   Despite the theoretical challenge, in practice, it is often possible to make some prior prediction of $T$ using data-driven approaches or based on the resources available in hand. For example, in online advertising, the number of customers can be predicted from historical statistics. Besides, in practice, the selling horizon is sometimes decided by upper-level decision-makers. e.g., a company selling products before festival events. In this case, $T$ is available to the decision-maker as a problem parameter.

2. Determine $f$ based on the remaining resource

   Thank you for the insightful comment. Since $f$ determines both the LP resolving frequency and the switching time to the first-order method, the analysis would be challenging if the LP resolving frequency is dynamically adjusted.

   However, we believe it's a good idea to determine the switching time based on the remaining resources:

   • One way is to define a new stopping time based on some pre-specified resource level (e.g., $f \cdot d$ when there's only one resource), after which the algorithm switches to the first-order method. The regret accumulated by the first-order method would be of order $O(\sqrt{\tau_f})$. A rough estimate of $\tau_f =O(\max\\{\log f + \log T, f\\})$ can be obtained from the analysis of the constraint consumption process [1], where $\log f + \log T$ arises from the deviation of $d_t$ (average remaining resource at time $t$) from $d$.
   • The other way (more heuristic) is to determine the switching frequency based on the stability of the dual price $\{p_t\}$ obtained by LP. Suppose $\{p_t\}$ remains stable near the end of the horizon, then it suggests the resource consumption is smooth, and solving LP frequently is less necessary--switching to first-order methods would be ideal in this case.

   We are glad to add a discussion in the revision but will leave a more rigorous regret analysis for future work.

3. More discussions on technical novelty

   Thanks for the comment. To our knowledge, our paper is the first result combining LP-based and first-order OLP algorithms, achieving the best-of-both-worlds guarantee: achieving efficient decision-making with regret that interpolates the performance of two algorithms. Technically, our contributions include

   • We develop a regret analysis framework that unifies both LP-based and first-order methods. In the current OLP literature, there are two types of analyses, one based on stopping time [2] and the other based on a joint metric of regret and resource violation [3]. Although intuitively, these two analyses should yield similar guarantees, it is non-trivial to combine them when two algorithms need to switch to each other. In particular, we need to carefully handle the evolution of the dual price $p_t$ when switching between two algorithms. Since first-order methods are known to be less stable, it is important to also take care of the stepsize of the algorithm (see our discussion in B.2 and B.9).
   • In addition, our work addresses a technical limitation of a previous work [4], where the authors also consider solving LPs periodically but require customers to wait at the beginning/end. Our analysis removes the need of waiting.

   From a high-level point of view, our method resembles the pre-training (LP) and fine-tuning (first-order methods) of large-language models. "Pre-training" provides baseline regret guarantee $\log (T/f)$ and "fine-tuning" performs minor refinement with improved efficiency.

   We will add more discussion about the technical intuitions in the paper in the revision.

Questions

1. Discussion of technical novelty.

   Please see our response to "Other Strengths And Weaknesses".

We hope our response addresses your concerns and thank you again for your efforts in the review process!

References

[1] Balseiro, Kroer, & Kumar (2023). Online resource allocation under uncertain horizons. ACM SIGMETRICS Abstract Proceedings.

[2] Li & Ye (2022). Online linear programming with new algorithms and regret bounds. Operations Research, 70(5), 2948–2966.

[3] Li, Sun, & Ye (2020). Fast algorithm for binary integer and online LP. NeurIPS, 33, 9412–9421.

[4] Xu, Glynn, & Ye (2024). Online LP with batching. arXiv:2408.00310.