Pareto-Optimal Learning-Augmented Algorithms for Online Conversion Problems
Year: 2022

Abstract:
This paper leverages machine-learned predictions to design competitive algorithms for online conversion problems with the goal of improving the competitive ratio when predictions are accurate (i.e., consistency), while also guaranteeing a worstcase competitive ratio regardless of the prediction quality (i.e., robustness). We unify the algorithmic design of both integral and fractional conversion problems, which are also known as the 1-max-search and one-way trading problems, into a class of online threshold-based algorithms (OTA). By incorporating predictions into design of OTA, we achieve the Pareto-optimal trade-off of consistency and robustness, i.e., no online algorithm can achieve a better consistency guarantee given for a robustness guarantee. We demonstrate the performance of OTA using numerical experiments on Bitcoin conversion.

heading: 1 Introductions
text: An online conversion problem aims to convert one asset to another through a sequence of exchanges at varying rates in order to maximize the terminal wealth in financial markets. With limited information on possible future rates, the core challenge in an online conversion problem is how to balance the return from waiting for possible high rates with the risk that high rates never show up. A high profile example of this risk is cryptocurrency markets, e.g., Bitcoin, where high fluctuations up and down make it challenging to optimize exchanges. Two well-known classical online conversion problems are 1-max-search [7] and one-way trading [8], which can be considered as integral and fractional versions of the online conversion problem that trade the asset as a whole or fraction-by-fraction (e.g., trading stock in lot or shares). Beyond these two problems, a number of extensions and variants of online conversion problems have been studied with applications to lookback options [14], online portfolio selection [13], online bidding [5], and beyond.
Most typically, conversion problems are studied through the lens of competitive ratios and the goal is to design online algorithms that minimize the worst-case return ratio of the offline optimal to online algorithm decisions. For example, EI-Yaniv et al. [8] have shown that optimal online algorithms can be designed to achieve the minimal competitive ratios for both 1-max-search and one-way trading. However, in real-world problems, predictions about future conversion rates are increasingly available and the algorithms developed in the literature are not designed to take advantage of such information. The challenge for using such predictions is that, in one extreme, the additional information is an accurate prediction (advice) of future inputs. In this case, the algorithm can confidently use the information to improve performance, e.g., [9]. However, most commonly, predictions have
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
no guarantees on their accuracy, and if an online algorithm relies on an inaccurate prediction the performance can be even worse than if it had ignored the prediction entirely.
This challenge is driving the emerging area of the learning-augmented online algorithm (LOA) design, which seeks to design online algorithms that can incorporate untrusted machine-learned predictions in a way that leads to near-optimal performance when predictions are accurate but maintains robust performance when predictions are inaccurate. To measure this trade-off, two metrics have emerged, introduced by [15] and [19]: consistency and robustness. Consistency is defined as the competitive ratio when the prediction is accurate, i.e., CR(0), where CR(ε) is the competitive ratio when the prediction error is ε. In contrast, robustness is the worst competitive ratio over any prediction errors, i.e., maxε CR(ε). Thus, consistency and robustness provide a way to quantify the ability of an algorithm to exploit accurate predictions while ensuring robustness to poor predictions.
In recent years, a stream of literature has sought to design robust and consistent LOA for a variety of online problems, such as online caching [15], ski-rental [19], and others. The ultimate goal is to develop algorithms that are Pareto-optimal across robustness and consistency, in the sense that for any γ, the LOA achieves the minimal consistency guarantee among all online algorithms that are γ-competitive. For the ski rental problem, recent works have derived Pareto-optimal algorithms, e.g., [4, 22], but in most cases the question of where the Pareto-boundary of LOA lies is yet to be answered.
In this paper, we focus on the design of LOA for online conversion problems and we seek to answer the following question: Is it possible to design a Pareto-optimal LOA for the online conversion problem?
Contributions. We show that the answer to the above question is “yes”, by designing an online threshold-based algorithm (OTA), and proving that it is Pareto-optimal. In particular, we introduce a class of OTA that unifies the algorithmic design of both 1-max-search and one-way trading. We then incorporate predictions into OTA by parameterizing the threshold functions based on the predictions. This approach yields bounded consistency and robustness (see Theorem 4.5 and Theorem 4.6). Further, we derive lower bounds for robustness-consistency trade-offs and show that our learningaugmented OTA achieves those lower bounds, and is thus Pareto-optimal (see Theorem 5.1 and Theorem 5.2). Finally, we demonstrate the improvement of the learning-augmented OTA over pure online algorithms using numerical experiments based on real-world data tracking Bitcoin prices.
The technical contributions of this paper are twofold. First, we provide a sufficient condition for design and analysis of the learning-augmented OTA with a guaranteed generalized competitive ratio. This competitive ratio is general in the sense that it not only can yield robustness and consistency guarantees, but can also potentially provide more fine-grained performance guarantees beyond robustness and consistency. Second, we provide a novel way of deriving the lower bound on the robustness-consistency trade-off, which may be of use beyond online conversion problems. The key idea is to construct a function that can model all online algorithms under a special family of instances, and the lower bound can be derived from combining the robustness and consistency requirements on this function. This constructive approach to arriving at a lower bound is distinctive.

heading: 2 Related Work
text: Online Conversion Problems. The online conversion problem is first introduced by El-Yaniv [7] and analyzed under the competitive analysis framework. It aims to search for the maximum rate to make conversions from a sequence of time-varying rates, which are chosen by an adversary in the worst-case. The subsequent works [8, 14] have designed competitive algorithms for both integral and continuous versions of the online conversion problem and achieved the minimal competitive ratios. Many variants and extensions have also been studied, such as online conversion under interrelated rates [20] or with inventory constraints [23, 12]. See [18] for a survey of other variants. In addition, the design and analysis of competitive algorithms for the online conversion problem have been shown to closely relate to those of the online knapsack problems, such as the online 0/1 knapsack with small weights [24, 26] and online fractional knapsack [21]. Beyond the worst-case input model, another line of research considers searching for the maximum value from the time-varying rates with some form of prior knowledge. For example, the secretary problem [3] assumes that the rates arrive in a uniformly random order and the prophet inequality [6] assumes that the rates arrive in the worst-case order but with prior distributions. The prior information in these problems makes the design and analysis of algorithms essentially different from those of online conversion problems.
Learning-augmented algorithms. The learning-augmented algorithm (LOA) takes advantages of machine learned predictions about the future input into the design of online algorithms and aims to optimize for a better competitive performance with an improved quality of predictions. The concepts of consistency and robustness are first introduced to study the online caching problem in [15]. Then the follow-up work [19] formally shows that there exist trade-offs between consistency and robustness in the ski-rental problem and its variants, and LOA needs to be designed to balance the two criteria unlike the online algorithms just optimized for the competitive ratio. Furthermore, the works [4] and [22] independently prove that the LOA designed in [19] is Pareto-optimal, i.e., given a robustness, no online algorithms can achieve a smaller consistency. Also, in [11] and motivated by an energy optimization scenario, the authors develop Pareto-optimal algorithms for an extended version of the ski-rental problem. From the aspect of methodology, the work [4] provides a general approach to incorporate the prediction into the online primal-dual algorithm and shows it can be applied to solve multiple online problems. In terms of applications, LOA has been designed for a variety of online problems, such as online caching [15], ski-rental [19, 22, 4, 1, 11], online set cover [4], online scheduling [19, 10], secretary and online matching [3], metrical task systems [2], etc. However, among those applications, the Pareto-optimality of LOA has only been rigorously shown for the ski-rental problem.

heading: 3 Problem statement and a unified algorithm
text: The online conversion problem. An online conversion problem considers how to convert one asset (e.g., dollars) to another (e.g., yens) over a trading period [N ] := {1, . . . , N}. At the beginning of step n ∈ [N ], an exchange rate (or price), vn, is announced and a decision maker must immediately determine the amount of dollars, xn, to convert and obtains vnxn yens. The conversion is unidirectional, i.e., yens are not allowed to convert back to dollars. The trading horizon N is unknown to the decision maker, and if there are any remaining dollars after N − 1 trading steps, all of them will be compulsorily converted to yens at the last price vN . Without loss of generality, the initial asset can be assumed to be 1 dollar, and the goal is to maximize the amount of yens acquired at the end of the trading period. The offline version of the conversion problem can be cast as
maximize xn ∑ n∈[N ] vnxn, subject to ∑ n∈[N ] xn ≤ 1. (1)
If the conversion is only allowed in a single transaction, the decision xn ∈ {0, 1} is a binary variable, and this integral version is called 1-max-search [7]. If the asset is allowed to convert fractionby-fraction over multiple transactions, the decision xn ∈ [0, 1] is a continuous variable, and this fractional version is refereed to as one-way trading [8]. Following the literature, we assume the prices {vn}n∈[N ] are bounded, i.e., vn ∈ [L,U ],∀n ∈ [N ], where L and U are known parameters, and define θ = U/L as the price fluctuation.
Online threshold-based algorithms. Online threshold-based algorithms (OTA) belong to a class of reserve-and-greedy algorithms where the idea is to use a threshold function to determine the amount of resources that need to be reserved based on resource utilization, and then greedily allocate resources respecting the reservation in each step.
OTA is known to be easy-to-use but hard-to-design due to the difficulties in developing the threshold function. Prior work using OTA has often been problem specific. For example, an optimal design of the threshold function in OTA is derived in [21] for one-way trading and in [25, 26] for the online knapsack problem, which is closely related to one-way trading.
Here, we unify online algorithms for online conversion problems in an OTA framework in Algorithm 1. Algorithm 1 takes a threshold function φ as its input, where φ(w) : [0, 1]→ [L,U ] is a function of resource utilization (i.e., amount of traded dollar) w and φ(w) can be considered as the reservation price when the utilization is w. The algorithm makes conversions only if the current price vn is at least φ(w(n−1)), where w(n−1) = ∑ i∈[n−1] x̄i is the utilization after the previous n − 1 steps of trading. More specifically, the conversion decision x̄n in each step is determined by solving an optimization problem in Line 3 of Algorithm 1. The OTA framework transforms the algorithmic design task in online conversion problems into the design of φ, and the challenge is to design φ such that OTA can have theoretical performance guarantees. To provide two examples, in the following we show how to recover the optimal online algorithms for 1-max-search and one-way trading.
Algorithm 1 Online threshold-based algorithm with threshold function φ (OTAφ) 1: input: threshold function φ(·), and initial resource utilization (i.e., traded dollar) w(0) = 0; 2: while price vn is revealed do 3: determine resource allocation x̄n = arg maxxn∈Xn vnxn − ∫ w(n−1)+xn w(n−1)
φ(u)du; 4: update the utilization w(n) = w(n−1) + x̄n. 5: end while
1-max-search. In this integral conversion problem, OTA sets the feasible space as Xn = {0, 1} and the threshold function as a constant φ(w) = Φ, w ∈ [0, 1], where Φ is also called a reservation price. Then the algorithm simply selects the first price that is at least Φ. When the reservation price is designed as Φ = √ LU , OTA is exactly the same algorithm as the reservation price policy in [8], which achieves the optimal competitive ratio √ θ.
One-way trading. OTA sets Xn = [0, 1 − w(n−1)] and φ as a continuous and strictly increasing function. The conversion decisions fall into three cases based on the solution of the optimization in Line 3: (i) if vn < φ(w(n−1)), make no conversions, i.e., x̄n = 0; (ii) if φ(w(n−1)) ≤ vn ≤ φ(1), x̄n can be solved based on the first-order optimality condition, i.e., vn = φ(w(n−1) + x̄n); and (iii) if vn > φ(1), x̄n = 1−w(n−1) converts all its remaining dollar at the price vn. By setting the threshold function to φ(w) = L + (α∗L − L) exp(α∗w), w ∈ [0, 1], OTA achieves the optimal competitive ratio α∗ = 1 +W ((θ − 1)/e), where W (·) is the Lambert-W function [21].

heading: 4 Robustness and consistency
text: This paper is focused on the design of learning-augmented online algorithms (LOA) where the online algorithm is given a machine-learned prediction P ∈ [L,U ] of the maximum price V = maxn∈[N ] vn over the price sequence. In the online conversion problem, suppose V is known a prior, waiting to trade all assets at the price V achieves the maximum profit. Therefore, the maximum price is an appropriate value to be predicted and incorporated into the design of the online algorithm. The prediction P is not necessarily accurate and we define ε = |V − P | as the prediction error. Let CR(ε) denote the competitive ratio of OTA when the prediction error is ε. Our goal is to design an algorithm that is η-consistent and γ-robust, i.e., an algorithm where η ≥ CR(0) and γ ≥ maxε CR(ε). We first focus on designing a learning-augmented OTA by incorporating predictions into the design of the threshold function φ to achieve bounded robustness and consistency.

heading: 4.1 Warmup
text: To highlight the challenges of algorithm design in this setting, we start by showing that an intuitive use of predictions can result in poor robustness-consistency guarantees. Thus, it is of essential importance to take advantage of the problem structure in designing the learning-augmented OTA.
To illustrate this, we consider the design of the reservation price ΦP for 1-max-search as an example. If we blindly use the prediction of the maximum price by setting ΦP = P , OTA is indeed offline optimal when the prediction is accurate, and thus 1-consistent. However, its robustness is the worst possible competitive ratio θ, which is achieved when the prediction is P = U and the actual maximum price is V = U − , where → 0. In fact, the robustness guarantee approaches θ with an arbitrarily small prediction error.
Another intuitive design is to set the reservation price as a linear combination of P and the optimal reservation price for pure online algorithms √ LU , i.e., ΦP = λ √ LU + (1− λ)P , where λ ∈ [0, 1] is called the robustness parameter, indicating the distrust in the prediction. The robustness and consistency of this algorithm is characterized by the following result. Proposition 4.1. Given λ ∈ (0, 1], OTA with the reservation price ΦP = λ √ LU + (1 − λ)P for
1-max-search is (λ √ θ + (1− λ)θ)-robust and √ θ-consistent.
Above consistency-robustness result is tight in the sense that for a given λ, we can construct an instance, under which OTA with the reservation price ΦP can achieve the robustness and consistency
in Proposition 4.1 with arbitrarily small gaps. This result highlights that, while the robustness is a linear combination of the optimal competitive ratio √ θ and θ, the consistency is √ θ, which yields no improvement over the optimal competitive ratio except for a special case when λ = 0.

heading: 4.2 A sufficient condition
text: Together, the two examples in the previous section highlight some of the challenges associated with balancing robustness and consistency in OTA. Given the challenges, we now focus on developing a general approach for the design and analysis of robust and consistent learning-augmented OTA. To do so, we first generalize the competitive ratio from a scalar to a vector, where each element corresponds to a competitive ratio over a subset of instances (see Definition 4.2). Since consistency and robustness can be considered as the competitive ratios over the subsets of the predicted instances and the other instances, the competitiveness of OTA can be transformed to robustness-consistency guarantees (see Lemma 4.3). This transformation leads us to characterize a general sufficient condition (see Theorem 4.4) on the threshold function of OTA that guarantees a generalized competitive ratio over a given subsets of instances. Then, combining Theorem 4.4 and Lemma 4.3 gives a general approach for analyzing the consistency and robustness of OTA, which we leverage in the analysis of 1-max-search and one-way trading in the following sections in order to illustrate its applicability.
To begin, let OPT(I) and ALG(I) denote the returns of offline optimal and an online algorithm under instance I, respectively. Let P := {P1, . . . ,PI} be a partition of the set Ω of all instances. Definition 4.2 (Generalized competitive ratio). α := (α1, . . . , αI) is a generalized competitive ratio over P if αi = maxI∈Pi OPT(I)/ALG(I) is the worst-case ratio over Pi for all i ∈ [I].
In online conversion problems, let Ωp ⊆ Ω be a subset, in which each instance has a maximum price p. Thus, if we have a prediction P on the maximum price, it means the instance is predicted to belong to ΩP . We can show the consistency and robustness of a learning-augmented OTA by proving its generalized competitive ratio over a partition. In particular, given prediction P , OTA is η-consistent and γ-robust if there exists a partition such that OTA is η-competitive over the subset that contains ΩP and γ-competitive for the remaining subsets. Formally we have the following claim. Lemma 4.3. Given a prediction P ∈ [L,U ], and parameters η and γ with η ≤ γ, OTA for online conversion problems is η-consistent and γ-robust if there exists a partition P = {Pη,Pγ} with Ω = Pη ∪ Pγ and ΩP ⊆ Pη , and OTA is (η, γ)-competitive over P .
Building on Lemma 4.3, we now focus on how to design the threshold function φ in OTA to ensure a small generalized competitive ratio. To this end, divide the range of price [L,U ] into I price segments [M0,M1), . . . , [MI−1,MI ] with L = M0 < M1 < ... < MI = U . We partition Ω based on the price segments, i.e., Ω = {Ωp}p∈[M0,M1) ∪ · · · ∪ {Ωp}p∈[MI−1,MI ]. Hereafter, we use Pi or [Mi−1,Mi) to denote the i-th instance subset {Ωp}p∈[Mi−1,Mi). To ensure different worst-case ratios over different subsets of instances, we consider a piece-wise threshold function φ created by concatenating a sequence of functions {φi}i∈[I], where each piece φi is designed to guarantee αi-competitiveness over Pi. In particular, divide the feasible region [0, 1] into I resource segments [β0, β1), . . . , [βI−1, βI ] with 0 = β0 ≤ β1 ≤ · · · ≤ βI = 1, and φi(w) ∈ [Mi−1,Mi), w ∈ [βi−1, βi). We say φi is absorbed if βi−1 = βi. The following theorem then provides a sufficient condition for designing the threshold function φ in OTA to guarantee a generalized competitive ratio. Theorem 4.4. OTA is α-competitive over {Pi}i∈[I] for online conversion problems if φ := {φi}i∈[I] is a piece-wise and right-continuous function, φ(1) ∈ {Mi}i∈[I] is one of the partition boundaries, and each threshold piece φi(w) : [βi−1, βi)→ [Mi−1,Mi) satisfies one of the following conditions: Case I: if Mi ≤ φ(0), then Mi ≤ αiL and βi = 0; Case II: if φ(0) < Mi ≤ φ(1), then φi is in the form of
φi(w) = { Mi−1 w ∈ [βi−1, β′i−1) ϕi(w) w ∈ [β′i−1, βi) , (2)
which consists of a flat segment in [βi−1, β′i−1) and a strictly increasing segment ϕi(w) that satisfies{ ϕi(w) ≤ αi [∫ β′i−1 0 φ(u)du+ ∫ w β′i−1 ϕi(u)du+ (1− w)L ] ,∀w ∈ [β′i−1, βi)
ϕi(βi) = Mi ; (3)
Case III: if Mi > φ(1), then Mi ≤ αi ∫ 1
0 φ(u)du and βi = 1.
Theorem 4.4 is the key to the analysis that follows. In particular, it provides a sufficient condition for analyzing the generalized competitive ratio of OTA, which in turn yields bounds on consistency and robustness as highlighted in Lemma 4.3. We show its broad applicability in the subsections that follow by applying it in the context of 1-max search and one-way trading.
Further, this approach is general and provides opportunities to derive more fine-grained performance metrics for the learning-augmented OTA beyond consistency and robustness. For example, instead of just focusing on the improved competitive ratio when predictions are accurate, we can redefine the consistency as a prediction-error dependent metric κ(ξ) := maxε≤ξ CR(ε). κ(ξ) characterizes the improved competitive ratio if the actual value is within the neighbourhood of the prediction [P − ξ, P + ξ]. Thus, κ(ξ) is a more general and fine-grained metric, and η and γ are two extreme points of κ(ξ), i.e., η = κ(0) and γ = κ(∞). Given ξ, we can leverage the competitive ratio to design κ(ξ)-consistent and γ-robust OTA. In particular, given P , OTA is κ(ξ)-consistent and γ-robust if there exists a partition P = {Pκ(ξ),Pγ} with Ωp∈[P−ξ,P+ξ] ⊆ Pκ(ξ), and OTA is (κ(ξ), γ)-competitive over P .

heading: 4.3 1-max search
text: We now apply the sufficient condition in Theorem 4.4 to the setting of 1-max search. Our goal is to design the reservation price ΦP given a prediction P . To do this, we set η := η(λ) and γ := γ(λ) as
γ(λ) = [ √ (1− λ)2 + 4λθ − (1− λ)]/(2λ), and η(λ) = θ/γ(λ), (4)
where λ ∈ [0, 1] is the robustness parameter, and η and γ are predetermined parameters for designing ΦP that represent the consistency and robustness that we target to achieve. In particular, η and γ are designed as the solution of
η(λ) = θ/γ(λ), and η(λ) = λγ(λ) + 1− λ. (5)
The first equation is the desired trade-off between robustness and consistency, which will be shown to match the lower bound in Section 5, and thus represents a Pareto-optimal trade-off. The second equation sets η as a linear combination of 1 and γ. In this way, as λ increases from 0 to 1 , η increases from the best possible ratio 1 to the optimal competitive ratio √ θ, and γ decreases from the worst possible ratio θ to √ θ. Taking η and γ as inputs, we design the reservation price ΦP as follows:
when P ∈ [L,Lη), ΦP = Lη; (6a) when P ∈ [Lη,Lγ), ΦP = λLγ + (1− λ)P/η; (6b) when P ∈ [Lγ,U ], ΦP = Lγ. (6c)
The following theorem provides robustness and consistency bounds for this algorithm. The result follows from the general sufficient condition for the class of OTA in Section 4.2. Given each reservation price ΦP , the key step of analysis is to determine a proper partition of instances and then analyze the competitive ratio over each subset, in which ΦP can satisfy the sufficient condition in one of the cases in Theorem 4.4. Take ΦP in (6a) for an example. We partition [L,U ] into [L,Lη) and [Lη,U ] by letting M1 = Lη. Since φ(0) = φ(1) = ΦP = Lη, ΦP satisfies Case I and Case III for [L,Lη) and [Lη,U ], respectively, and the corresponding competitive ratios are α1 = ΦP /L = η and α2 = U/ΦP = θ/η = γ. Thus, OTA is (η, γ)-competitive over [L,Lη) and [Lη,U ]. Additionally, the predicted instance ΩP ⊆ Ωp∈[L,Lη), and thus OTA is η-consistent and γ-robust based on Lemma 4.3. Theorem 4.5. Given λ ∈ [0, 1], OTA with the reservation price in Equation (6) for 1-max-search is γ(λ)-robust and η(λ)-consistent, where γ(λ) and η(λ) are given in Equation (4).
Before moving to the proof it is important to give insights into the form of the reservation price (6). It consists of three segments for predictions that are in boundary regions [L,Lη) and [Lγ,U ] close to price lower and upper bounds, and in intermediate region [Lη,Lγ). Figure 1 illustrates the form and compares it with two intuitive designs ΦP = P and ΦP = λ √ LU +(1−λ)P , which we have shown providing poor robustness and consistency guarantees. Given any reservation price Φ ∈ [L,U ], the robustness of OTA is max{Φ/L,U/Φ}, where Φ/L and U/Φ are the worst-case ratios over subsets [L,Φ) and [Φ, U ]. To ensure a good robustness, (6a) and (6c) are designed to balance Φ/L and U/Φ
by just ensuring η-competitiveness over the boundary region that contains the prediction. The intuitive design ΦP = P neglects this structure, and thus its robustness approaches the worst possible ratio θ. Given an accurate prediction P , the consistency of OTA is max{Φ/L, P/Φ}. To guarantee a good consistency, we must avoid the case that P < Φ, leading to the ratio Φ/L that cannot be properly bounded. (6b) is designed by enforcing P ≥ ΦP . In this way, OTA always makes conversions in the intermediate region and the consistency is P/ΦP , which can be designed to be upper bounded by η. The intuitive design ΦP = λ √ LU + (1 − λ)P fails to improve the consistency over √ θ since it cannot always guarantee P ≥ ΦP in the intermediate region, and thus may make no conversions even with an accurate prediction. A full proof of Theorem 4.5 is in Appendix A.4.

heading: 4.4 One-way trading
text: Next, we apply the sufficient condition in Theorem 4.4 to one-way trading. We also aim to design the threshold function based on the prediction P . Here, we set γ := γ(λ) and η := η(λ) as
η(λ) = θ/
[ θ
γ(λ) + (θ − 1)
( 1− 1
γ(λ) ln θ − 1 γ(λ)− 1
)] , and γ(λ) = α∗ + (1− λ)(θ − α∗), (7)
where λ ∈ [0, 1] is the robustness parameter and α∗ is the optimal competitive ratio of one-way trading. Similarly to the design in 1-max-search, the two equations in (7) determine the desired trade-off between η and γ, and their desired relationship with λ. Again, we derive a lower bound in Section 5 showing that this relationship is tight and provides a Pareto-optimal trade-off.
Taking η and γ as inputs, we design the threshold function as follows: when P ∈ [L,M), φP (w) = { L+ (ηL− L) exp(ηw) w ∈ [0, β) L+ (U − L) exp(γ(w − 1)) w ∈ [β, 1] , (8a)
when P ∈ [M,U ], φP (w) =  L+ (γL− L) exp(γw) w ∈ [0, β1) M1 w ∈ [β1, β′1) L+ (M1 − L) exp(η(w − β′1)) w ∈ [β′1, β2] L+ (U − L) exp(γ(w − 1)) w ∈ (β2, 1] , (8b)
where β and M are solutions of{ M = L+ (ηL− L) exp(ηβ), Mγ/η = L+ (U − L) exp(γ(β − 1)); (9)
and M1, β1, β′1, and β2 are all functions of P and are determined by β1 = 1 γ ln max{M1/L,γ}−1 γ−1 , M1 η = ∫ β1 0 φ(u)du+ (β′1 − β1)M1 + (1− β′1)L,
P = L+ (M1 − L) exp(η(β2 − β′1)), β2 = 1 + 1 γ ln min{Pγ/η,U}−L U−L .
(10)
The following theorem provides robustness and consistency bounds for this algorithm. Again, the result follows from the general sufficient condition for the class of OTA that we introduce in Section 4.2.
Compared to 1-max-search, the additional difficulty of one-way trading lies in the analysis of the competitive ratios over the subsets belonging to Case II of the sufficient condition since the threshold function φP ranging in these subsets needs to satisfy a set of differential equations (3). φP in (8) is in fact designed as the solution of the differential equation (3) with binding inequalities and properly designed boundary conditions (by setting the length of the flat segment of each threshold piece). Theorem 4.6. Given λ ∈ [0, 1], OTA with the threshold function (8) for one-way trading is γ(λ)robust and η(λ)-consistent, where γ(λ) and η(λ) are given in Equation (7).
Figure 1 illustrates the function given different predictions. The basic idea behind the design of the threshold function (8) is similar to that of 1-max-search. When the prediction is in the boundary region P ∈ [L,M), the threshold function (8a) (i.e., red curve) is designed to ensure η-competitiveness over [L,M), and additionally guarantee γ-competitiveness over [M,U ]. In the other extreme when P = U , the threshold function (8b) becomes φP (w) = L + (Lγ − L) exp(γw), w ∈ [0, β1) and φP (w) = U,w ∈ [β1, 1] (i.e., green curve) since β2 = β′1 = 1 and M1 = U by solving equation (10) with P = U . This threshold is (η, γ)-competitive over [U ] and [L,U). When the prediction is in the intermediate region P ∈ [M,U), the threshold function consists of at most four segments. The first and the forth segments when w ∈ [0, β1) and w ∈ (β2, 1] are exponential functions with rate γ, aiming to ensure γ-competitiveness over [L,M1) and (P,U ]. These two segments may be absorbed when the prediction is small (M1 ≤ Lγ) or large (Pγ/η ≥ U ), corresponding to β1 = 0 and β2 = 1. To guarantee a good consistency, a flat segment in w ∈ [β1, β′1) is designed to convert enough dollar before reaching the price P by enforcing P ≥M1, and an exponential segment with rate η in w ∈ [β′1, β2] to ensure η-competitiveness over [M1, P ]. A full proof can be found in Appendix A.5.

heading: 5 Pareto-optimal consistency-robustness trade-off
text: To this point, we have focused on upper bounds for robustness and consistency. This section provides lower bounds on the robustness-consistency trade-offs for both 1-max-search and one-way trading and shows the Pareto-optimality of our proposed learning-augmented algorithms. Note that, obtaining lower bounds on the trade-off between robustness and consistency for online algorithms has proven difficult. The only existing tight lower bounds we are aware of are in the case of deterministic [1] and randomized [4, 22] algorithms for the ski-rental problem. Theorem 5.1. Any γ-robust deterministic LOA for 1-max-search must have consistency η ≥ θ/γ. Thus, OTA with the reservation price (6) is Pareto-optimal. Theorem 5.2. If a deterministic LOA for one-way trading is γ-robust, its consistency is at least η ≥ θ/[ θγ + (θ − 1)(1− 1 γ ln θ−1 γ−1 )]. Thus, OTA with the threshold function (8) is Pareto-optimal.
We illustrate the Pareto-optimal trade-offs of robustness and consistency for 1-max-search and oneway trading in Figure 2. Notice that the Pareto-boundary of one-way trading dominates that of 1-max-search since the fractional conversion leaves more flexibility to online decisions in one-way trading, leading to a better lower bound. For both problems, with the improvement of consistency from the optimal competitive ratio (i.e., √ θ or α∗) to the best possible ratio 1, the robustness degrades from the optimal competitive ratio to the worst possible ratio θ. This means there is no free lunch in online conversion problems; to achieve a good consistency, robustness must be sacrificed.
We end the section by proving Theorem 5.2 for one-way trading. A proof of Theorem 5.1 is included in Appendix A.6.
Proof of Theorem 5.2. To show a lower bound result, we first construct a special family of instances, and then show that for any γ-robust LOA (not necessarily being OTA), their consistency η is lower bounded under the special instances.
We focus on a collection of p-instances {Ip}p∈[L,U ] where p ranges from L to U , where a p-instance is defined as follows. Definition 5.3 (p-instance). Given p ∈ [L,U ] and a large N , an instance Ip := {v1, . . . , vN} is called a p-instance if vn = L+ (n− 1)δ, n ∈ [N − 1] with δ = p−LN−2 and vN = L.
Notice that, when N → ∞, the sequence of prices in Ip continuously increases from L to p, and drops to L in the last step.
Let g(p) : [L,U ]→ [0, 1] denote a conversion function of a deterministic LOA for one-way trading, where g(p) is its total amount of converted dollar under the instance Ip before the compulsory conversion in the last step. A key observation is that for a large N , executing the instance Ip+δ is equivalent to first executing Ip (excluding the last step) and then processing p+ δ and L. Since the conversion decision is unidirectional and deterministic, we must have g(p+ δ) ≥ g(p), i.e., g(p) is non-decreasing in [L,U ]. In addition, the whole dollar must be converted once the maximum price U is observed, i.e., g(U) = 1.
Under the instance Ip, the offline optimal profit is OPT(Ip) = p and the profit of an online algorithm with conversion function g is ALG(Ip) = g(L)L+ ∫ p L udg(u) + L(1− g(p)), where udg(u) is the profit of converting dg(u) dollar at the price u. The first two terms are the cumulative profit before the last step and the last term is from the compulsory conversion.
For any γ-robust online algorithm, the corresponding conversion function must satisfy ALG(Ip) ≥ OPT(Ip)/γ = p/γ,∀p ∈ [L,U ]. If, additionally, given prediction P ≥ γL, no dollar needs to be converted under instances {Ip}p∈[L,γL), i.e., g(p) = 0,∀p ∈ [L, γL). This is because if a γ-robust online algorithm converts any dollar below the price γL, we can always design a new algorithm by letting it convert the dollar at the price γL instead. The new online algorithm is still γ-robust and achieves a smaller consistency when the prediction is accurate. Thus, given P = U ≥ Lγ, the conversion function of any γ-robust online algorithm must satisfy
ALG(Ip) = g(γL)γL+ ∫ p γL udg(u) + L(1− g(p)) ≥ p γ , ∀p ∈ [γL,U ]. (11)
By integral by parts, a necessary condition for above robustness constraint (11) to hold is g(p) ≥ p/γ−L p−L + 1 p−L ∫ p γL g(u)du. Based on Gronwall’s Inequality (see Theorem 1, p.356, [17]), we have
g(p) ≥ p/γ − L p− L + 1 γ ∫ p γL u− γL (u− L)2 du = 1 γ ln p− L γL− L , ∀p ∈ [γL,U ]. (12)
In addition, to ensure η-consistency when the prediction is P = U , we must ensure ALG(IU ) ≥ OPT(IU )/η. Combining this constraint with g(U) = 1 gives∫ U
γL
g(u)du ≤ (η − 1)U/η. (13)
By combining equations (12) and (13), the conversion function g(p) of any γ-robust and η-consistent online algorithm given P = U must satisfy ∫ U γL 1 γ ln u−L γL−Ldu ≤ ∫ U γL g(u)du ≤ (η − 1)U/η, which equivalently gives η ≥ θ/[ θγ + (θ − 1)(1− 1 γ ln θ−1 γ−1 )].
Finally, since Theorem 4.6 has shown that OTA with the threshold function (8) can achieve the lower bound in Theorem 5.2, it is Pareto-optimal.

heading: 6 Numerical results
text: We end with a case study on the exchange of Bitcoin (BTC) to USD. This case study is timely since the rapid growth of cryptocurrency has left many traders eager to profit from rising and falling of exchange rates in average-case scenarios, while the uncertainty and volatility of cryptocurrency have made many traders cautious of unforeseeable crashes in worst-case scenarios. Our results answer two questions: (Q1) How does the learning-augmented OTA compare to pure online algorithms with different prediction qualities and drastic exchange rate crashes? (Q2) How should the OTA select the robustness parameter λ, and especially, would an online learning algorithm work in practice?
Setup. We use historical BTC prices in USD of 5 years from 2015 to 2020, with exchange rates collected every 5 minutes from the Gemini exchange. We assume one BTC is available for trading during 250 instances of length one week. Since BTC is traded in the unit of satoshi (i.e., 0.00000001 BTC), this problem fits the fractional conversion setting and we apply the LOA for the one-way trading problem in the following experiments. We set L and U as the historical minimum and maximum prices over the entire 5 years.1 To generate a prediction P , we simply use the observed maximum
1The focus of this paper is not on the impact of L and U , and thus we simply set them as historical values. In practical trading problems, L and U can be considered as predetermined parameters that represent the stop-loss and take-profit prices in the exit strategy of the trading process.
exchange rate of the previous week. To evaluate the impact of prediction quality, we adjust the error level between 0.0 to 1.0, where 0.0 indicates perfect predictions and 1.0 indicates unadjusted predictions. To evaluate the performance in worst-case settings, we also introduce a crash probability q, where the exchange rate of BTC at the last slot will crash to L with probability q.
We compare the empirical profit ratio of four different algorithms: (i) Alg(λw), the worst-case optimized online algorithm that does not take into account predictions, but, guarantees the optimal competitive ratio; (ii) Alg(λoff), an algorithm that finds the best possible distrust parameter λ in an offline manner; this algorithm is not practical since it is fed with the optimal parameter; however, it illustrates the largest possible improvement from predictions under our algorithm; (iii) Alg(λalf), an online learning algorithm from [16] which selects the parameter using the adversarial Lipschitz algorithm in a full-information setting; and (iv) Alg(λstc), an online algorithm that uses the best static λ and serves as the baseline for Alg(λalf). Additional details are in the supplementary material.
Experimental results. We answer Q1 in Figures 3(a) and 3(b), and Q2 in Figures 3(c) and 3(d). Figure 3(a) compare the profit ratios of several algorithms at different error levels. First, it shows that Alg(λoff) and Alg(λalf) noticeably improve the performance of Alg(λw). The upper boxplot whisker of Alg(λw) is 1.35, while Alg(λalf) at 1.0 error level has an upper boxplot whisker around 1.25. Second, it shows that the gap between Alg(λoff) and Alg(λalf) is quite small, as the upper boxplot whisker of Alg(λoff) is slightly lower. Comparing the profit ratios of different algorithms with different crash probability values at 1.0 error level in Figure 3(b), we see that the performance of Alg(λw) drastically degrades at crash probability 0.45. However, both Alg(λalf) and Alg(λoff) are stable at high crash probability. Figure 3(c) compares the average normalized profit of Alg(λalf) and Alg(λstc) and shows the reward of Alg(λalf) converges toward that of Alg(λstc) as the learning process moves forward. Figure 3(d) indicates that the regret of Alg(λalf) stabilizes.

heading: 7 Concluding remarks
text: To improve upon the performance of algorithms for online conversion problems that are designed with worst-case guarantees in mind, this paper has incorporated machined-learned predictions into the design of a class of OTA and shown that the learning-augmented OTA can achieve Pareto-optimal robustness-consistency trade-offs. This result represents only the second tight lower bound result in the robustness and consistency analysis of LOA, with the first being for ski rental problem [1, 4, 22]. We expect that our method of deriving lower bounds can be extended to more general online optimization problems with capacity constraints. A limitation of this work is that consistency and robustness only measure the competitive performance in two extreme cases, i.e., the predictions are perfectly accurate or completely wrong. Although our approach for design and analysis of OTA provides opportunities to design OTA in ways that guarantee more fine-grained performance metrics, this is left for the future work. Another limitation is that this work provides only empirical evaluation of the algorithm Alg(λalf) that selects the robustness parameter in an online manner. Deriving theoretical bounds remains open. Last, we cannot see any negative societal impacts of our work.

heading: Acknowledgements
text: Bo Sun and Danny H.K. Tsang acknowledge the support received from the Hong Kong Research Grant Council (RGC) General Research Fund Project 16211220. Russell Lee and Mohammad Hajiesmaili’s research is supported by NSF CAREER 2045641, CNS 2106299, CNS 2102963, CNS 1908298. Adam Wierman’s research is funded by NSF CNS-2106403 and NGSDI-2105648. We also acknowledge the support received from the Resnick Institute and the Center for Autonomous Systems and Technologies at Caltech.

Review summaries:
This paper provides learning-augmented algorithms for online conversion problems. Suppose you have $1 and want to convert it to a different currency where the exchange rate varies over time. The ideal would be to do the conversion when the exchange is at its highest, but at any time, we do not know if the current exchange rate is in fact the highest (similar to secretary problems). The paper considers both the integer and fractional versions of this problem, i.e., when the conversion of the entire one unit has to be done all at once or when it can be done in fractions multiple times adding up to one. Algorithms are presented for these problems if a prediction of the maximum value is given in advance, the goal being to achieve the optimal tradeoff between consistency and robustness. Matching lower bounds on this tradeoff are also presented. Finally, an empirical evaluation of the algorithms are carried out for the application of trading dollars for bitcoins.

The paper considers the following conversion problem: You start with a good (e.g. 1 bitcoin) that you can convert into another good (e.g. dollars) at a conversion rate that changes over time. Every day you have the opportunity to convert part of the good at the day's rate. On the last day, you have to convert any remaining amount of the original good that you might still own. The goal is to maximize the final amount owned. It is assumed that upper and lower bounds U and L on the conversion rate are known that hold throughout the time horizon.  Two versions of this problem are considered: 1-max search, where the good is unsplittable, i.e., one can only convert it as a whole. And a smoother version where arbitrary fractions can be converted, called one-way trading. It seems to me that one-way trading is equivalent to the randomized version of 1-max search.  Let $\theta=U/L$ be the ratio between the upper and lower bounds. In the classical online setting, for 1-max search it is known that the best competitive ratio is $\sqrt{\theta}$, and for one-way trading it is $1+W((\theta-1)/e)$, where W is the Lambert function.  This paper considers this problem through the learning-augmented lens: The algorithm receives as additional input at time 0 a prediction of the maximal conversion rate that will be observed. The paper gives algorithms for both problems and proves via upper and lower bounds that they achieve the pareto-optimal trade-off between consistency (i.e., the competitive ratio when the prediction is correct) and robustness (i.e., the competitive ratio in the worst case). For 1-max trading, the result is that if the consistency is a multiplicative factor c better than the classical competitive ratio $\sqrt{\theta}$, then the robustness is a factor c worse than $\sqrt{\theta}$. The result for one-way trading is more difficult to express and I have no clear intuition of the trade-off. The paper also includes a brief experimental evaluation.

The paper considers learning-augmented algorithms for the online conversion problem. In the online conversion problem, a trader starts with a unit of money in the source currency. Given a sequence of conversion rates v_i that arrive online, the online conversion problem is to determine what fraction of their money to convert using the current rate so that the total amount of money in the target currency is maximized. The paper considers this problem in both the integral and fractional settings. The primary focus of the paper is to design online algorithms for the online conversion problem when provided with a prediction for the maximum conversion rate that achieves the optimal tradeoff between robustness (competitive ratio) and consistency (competitive ratio when prediction is correct).

The paper considers learning augmented algorithms for the integral and fractional online conversion problem. One has one unit of some asset that he wishes to convert into another asset. In each step $n = 1,\dots N$  the conversion rate $v_n$ becomes known to the algorithm, and the algorithm decides what amount $x_n$ (possibly $x_n=0$) of the asset should be converted in this step to obtain $x_n v_n$ of the new asset. Summing over all steps, the algorithm obtains in total $\sum_{n\in[N]}x_nv_n$ many units of the new assets, and naturally the objective is to maximise this. In the integer version the whole asset must be converted in only one step, whereas in the fractional version the asset can be converted piece by piece over different steps.  The paper designs a learning augmented online algorithm that is Pareto optimal between robustness and consistency.  Experimental results are presented where the flunctuation of the bitcoin exchange rate over the last five years is used as input data.