Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search

We thank the reviewer for the time and effort spent on our submission and for the positive feedback. We address their questions and comments below.

Weakness

Due to page limitations, we could not always give detailed proof methodologies in the main paper. However, if the paper is accepted, we will use the additional page to enhance this aspect, as suggested by the reviewer. For instance, please see our response below for some specific paragraphs that we will add in regard to Section 3.

Technical Novelty. Our techniques fundamentally differ from those used by Sun et al. While their work aims to determine the Pareto-optimal tradeoffs between consistency and robustness, our work extends their results by leveraging the knowledge of the Pareto-optimal frontier for consistency-robustness, and establishes smoothness guarantees, which is not addressed in the previous work. Specifically, we characterize all threshold algorithms that achieve this frontier and further analyze the optimal smoothness within this class of algorithms using two distinct notions of smoothness: multiplicative and additive.

High level overview of proof techniques.

• Theorem 3.1: If a threshold function $\Phi$ belongs to $\mathcal{P}_r$, then we use the bounds on $\Phi$ defining $\mathcal{P}_r$ to prove its Pareto-optimal robustness and consistency. Conversely, for a Pareto-optimal $\Phi$, we analyze the worst-case instances $I_n(q)$ (Equation 15), where prices increase uniformly from 1 to $q$ before dropping to 1. By evaluating $\text{ALG}/\text{OPT}$ on these instances for well-chosen $q$, we derive the bounds on $\Phi(y)$ that define $\mathcal{P}_r$.
• Theorem 3.2: For any $\rho \in [0,1]$, the threshold of Algorithm $A^\rho_r$ lies in $\mathcal{P}_r$, ensuring $r$-robustness and $1/r\theta$-consistency (Theorem 3.1). To establish smoothness, we determine the best value of $s$ such that $\text{ALG}/\text{OPT} \geq (1/r\theta) \mathcal{E}^s$ across all price sequences and predictions. Since the threshold is piecewise-defined, it suffices to analyse cases based on $y$ and whether the maximum price is above or below the threshold. The final smoothness guarantee is then determined by the worst such case.
• Theorem 3.3: We first prove that, on worst-case instances $I_n(q)$, any Pareto-optimal algorithm behaves like a threshold algorithm. Using results from Theorem 3.1, we establish that its threshold function must belong to $\mathcal{P}_r$. Finally, by applying the defining inequalities of $\mathcal{P}_r$ with well-chosen $q$ and $y$, we derive lower bounds on the smoothness $s$.

Questions

• Confidence fluctuation. The confidence fluctuation in Figure 2 is indeed a result of the randomness of the environment.
• Relative performance. Could the reviewer clarify what they mean by the "win-rate" of $\rho=1$ against $\rho=0$? We interpret this as the ratio $CR(A^1)/CR(A^0)$, indicating how much $A^1$ gains compared to $A^0$. Both the empirical (solid line) and theoretical (dashed line) worst-case ratios are shown in the following figure (https://imgur.com/a/PmnrYOn). The figure shows that the empirical ratio is 1 when the prediction is perfect (i.e. $1-\mathcal{E} = 0$), as expected, since both algorithms have the same consistency. The ratio then increases abruptly to approximately $1.3$, for an arbitrarily small error, which is due to $A^0$'s brittleness. It then increases, up to a value of 1.5 approximately, after which it decreases down to 1, as the prediction becomes highly inaccurate. This is explained, respectively, by the fact that $A^0$ remains inefficient for relatively small values of error, and by the fact that both algorithms have the same robustness.
• Theoretical bounds in the figure. Thank you for the suggestion. We included the theoretical worst-case ratio (dashed lines) for $\rho \in$ {0, 0.5, 1} alongside the empirical ratios from Figure 2. The updated figure is available here (https://imgur.com/a/87xE5Qv). For the three values of $\rho$, the figure shows that the empirical ratio is better than the theoretical one because the latter represents the worst case over all predictions with error at most $\mathcal{E}$, while the empirical ratio is based on random predictions, explaining the observed gap. Note that, for $\rho < 1$, there is a sharp degradation in performance; for example, for $\rho=0$, this degradation occurs at infinitesimally small prediction error. In contrast, for $\rho=1$, the degradation is smooth, which aligns with our objectives and the intuition given in Section 3.

We thank the reviewer for the time and effort spent on our submission and for their positive feedback. We address their questions below.

Minor weakness.
The $k$-search problem generalizes the one-max search problem, requiring a trader to sell $k$ items instead of one, with arbitrary prices in a bounded range $[p_{\min}, p_{\max}]$. Lee et al. studied this problem in a learning-augmented setting with a prediction of the maximum price, proposing a threshold-based policy that achieves a Pareto-optimal tradeoff between consistency and robustness, but lacks smoothness guarantees. Given the Pareto-optimal consistency and robustness values, we can aim to characterize all algorithms achieving them. Building on the intuition we established for one-max search, the smoothness of such algorithms depends on the maximum slope of their thresholds. We can then analyse the algorithm within this family with the smallest maximum slope, which we expect to have good smoothness guarantees.

Other Comments Or Suggestions.
(1) We thank the reviewer for pointing out the typo. We have corrected it.
(2) We agree with the reviewer's observation and apologise for the confusing formulation. We meant to highlight the way that Optimal transport was used to characterise the effect of the interaction between $G$ and $F^*$ beyond their own effect. We will clarify this point.

Questions.
(Q1) The bound holds for deterministic algorithms. In the presence of randomization, the problem is equivalent to the one-way trading problem, in which fractions of an item can be bought. The interplay between smoothness and Pareto-optimality for one-way trading has been fully studied in "Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithms" (Elenter et al., NeurIPS '24), where the authors proved that any algorithm achieving Pareto-optimal consistency and robustness is necessarily brittle (i.e., it cannot have any smoothness guarantees). This gives further evidence that, unlike many decision problems, the deterministic and randomized versions of one-max search are significantly different.

We thank the reviewer for the time and effort spent on our submission, and for their positive feedback. We address their comments below.

• The objective of the robustness term is to give a valid guarantee even under arbitrarily inaccurate predictions, since no assumption is made on the quality of the prediction. This is why the robustness term should not depend on the prediction error.
• It might be possible to improve the bound if the error is known to be at most $\mathcal{E}_{\max}$. However, our main objective is to design an algorithm that is able to leverage a prediction without any additional assumptions on its quality. More generally, in any learning-augmented problem, if the error is assumed to be bounded, then the consistency, robustness, and smoothness guarantees might all be improved. While this question is out of the scope of our work, it constitutes a very interesting research direction.
• Along a single trajectory of prices, it is impossible to learn the coupling as the whole trajectory provides only a single sample of the maximum price and a single prediction, which is statistically meaningless. However, it is possible to learn the coupling if the game is repeated several times using standard density estimation techniques, see e.g. (Silverman, 2018; Chen, 2017). Studying a repeated version of the one-max-search problem (whether on-- or offline) is a significantly methodologically different task. This raises an interesting further direction of research.

References.
Silverman, Bernard W. Density estimation for statistics and data analysis. Routledge, 2018.
Chen, Yen-Chi. A tutorial on kernel density estimation and recent advances. Biostatistics & Epidemiology 1.1 (2017): 161-187.

We thank the reviewer for the time and effort spent on our submission, and for their positive feedback.

In proposing a stochastic formulation of the one-max-search problem with predictions, we aimed to introduce the concept of a stochastic notion of accuracy for predictions. We gave bounds in expectation, but, as the reviewer suggests, one can also consider high-probability bounds. However, these bounds would concern the joint tail probabilities of $P^*$ and $Y$, which are difficult objects to conceptualise. In contrast, bounds in expectation naturally give rise to a characterisation of the worst case as an optimal transport problem.