Abstract
In the online (time-series) search problem, a player is presented with a sequence of prices which are revealed in an online manner. In the standard definition of the problem, for each revealed price, the player must decide irrevocably whether to accept or reject it, without knowledge of future prices (other than an upper and a lower bound on their extreme values), and the objective is to minimize the competitive ratio, namely the worst-case ratio between the maximum price in the sequence and the one selected by the player. The problem formulates several applications of decision-making in the face of uncertainty on the revealed samples. Previous work on this problem has largely assumed extreme scenarios in which either the player has almost no information about the input, or the player is provided with some powerful, and error-free advice. In this work, we study learning-augmented algorithms, in which there is a potentially erroneous prediction concerning the input. Specifically, we consider two different settings: the setting in which the prediction is related to the maximum price in the sequence, as well as the setting in which the prediction is obtained as a response to a number of binary queries. For both settings, we provide tight, or near-tight upper and lower bounds on the worst-case performance of search algorithms as a function of the prediction error. We also provide experimental results on data obtained from stock exchange markets that confirm the theoretical analysis, and explain how our techniques can be applicable to other learning-augmented applications.
Introduction
Deciding when to sell an asset is a fundamental challenge in online decision-making. In the classic online search problem, a player observes a sequence of prices and must decide irrevocably whether to accept the current price or wait for a potentially better one in the future. Traditionally, these problems are analyzed through the lens of the competitive ratio: the ratio between the optimal price (revealed in hindsight) and the price chosen by the algorithm.
Standard deterministic algorithms achieve a competitive ratio of $\sqrt{M/m}$, where $M$ and $m$ are known upper and lower bounds on the possible prices. While robust, this approach is often overly pessimistic as it assumes a worst-case adversary. This paper introduces learning-augmented algorithms that leverage machine-learned predictions to improve performance when predictions are accurate, while maintaining a "safety net" for when they fail.
Learning-Augmented Strategies
The authors propose two distinct frameworks for incorporating external advice into the search process:
1. Best-Price Prediction
In this model, the algorithm receives a single predicted maximum price $p$. The authors develop the ROBUST-MIX algorithm, a hybrid strategy that balances following the prediction with maintaining robustness. If the prediction error is within a known bound, the algorithm sets a reservation price near $p$. If the error is too high, it reverts to the classic $\sqrt{M/m}$ strategy to prevent catastrophic losses.
2. Query-Based Prediction
Instead of a single price, the algorithm can ask $n$ binary questions (e.g., "Will the price exceed $x$?"). The paper's primary technical contribution here is the Robust Binary Interval Search (RBIS) algorithm. Unlike standard binary search, which fails if a single answer is incorrect, RBIS performs a "noisy" search. It uses a "Move-up/Move-down" logic to self-correct when it detects contradictory responses, allowing it to navigate a search tree effectively even with up to $H$ erroneous answers.
Key Results and Experimental Validation
The theoretical analysis shows that RBIS achieves a competitive ratio of $(M/m)^{2^{2H-n/2}}$, a significant improvement over linear search methods. To validate these bounds, the authors tested the algorithms on real-world financial data, including high-volatility cryptocurrencies (Bitcoin, Ethereum) and lower-volatility fiat currencies (Euro, Yen).
As shown in the figure above, the learning-augmented algorithms exhibit several critical properties:
- Graceful Degradation: As the prediction error $\eta$ increases, the competitive ratio does not "crash." Instead, it increases gently, eventually leveling off at the performance of the classic robust algorithm ($ON^*$).
- Asymmetry of Error: The impact of error is asymmetric; predicting a price too low (negative $\eta$) is often more punishing than predicting too high, as the algorithm may settle for a mediocre price prematurely.
- Consistency vs. Robustness: By adjusting the parameter $r$, the algorithm can be tuned to be more "consistent" (performing exceptionally well with good predictions) or more "robust" (staying closer to the $ON^*$ baseline regardless of error).
Conclusion
This work bridges the gap between pessimistic worst-case analysis and overly optimistic reliance on machine learning. By designing algorithms that can self-correct and revert to safe baselines, the authors provide a framework for more effective online trading. Future research directions include extending these techniques to one-way trading (selling fractions of an asset), portfolio selection, and multi-search scenarios.
Summary updated