acceptodds
Withdrawn from ICLR 2027

The Power of Knowing Horizons in One-Way Trading: A Unified Framework for Optimal Competitive Ratios

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

This paper studies the One-way Trading Problem (OTP) with different forms of horizon information. We first show that knowing only the earliest horizon in OTP yields no algorithmic improvement. We then propose three new algorithms for the other forms of horizon information: (i) the Latest Horizon Algorithm (LHA), an optimal solution that strictly improves upon the original bound in OTP when the latest horizon is known; (ii) the Earliest-and-Latest Horizon Algorithm (ErLHA), an asymptotically optimal solution when both the earliest and the latest horizons are known; (iii) the Exact Horizon Algorithm (ExHA), an optimal solution and also a special form of ErLHA when the earliest and latest horizons coincide and become the exact horizon. Notably, ErLHA attains asymptotic optimality when both the earliest and latest horizons are known, recovering the optimality in all other settings, and thereby standing as the first unified and optimal framework for OTP with different horizon information.

Primary area:
optimization
Keywords:
one-way trading, online conversion problem, competitive-ratio analysis

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_9onKOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies one-way trading, where a trader must irrevocably allocate a unit budget as exchange rates in a known range arrive online. Performance is measured against an offline trader that converts the entire budget at the highest rate. Building on classical results for known and unknown horizons, the paper examines how partial horizon information affects competitive ratios. It shows that an earliest bound alone gives no improvement and derives a globally optimal algorithm for a latest bound. For general horizon intervals, it proposes a two-phase algorithm with adaptive budget allocation and claims optimality within this algorithm family, recovering classical guarantees in special cases.

Critical strengths
  • The problem setting is clean, natural, and worth studying.

  • The analytical techniques are generally solid, and the paper systematically examines how different levels of horizon information affect competitive ratios.

Critical weaknesses
  • The characterization is incomplete for general horizon intervals, where optimality is established only within the proposed algorithm family.

  • Lemma 22 has a feasibility issue that leaves a gap in the subsequent parameter-optimality argument; see the question below.

Questions for authors

How does the parameter choice in Lemma 22 satisfy constraint (260)? Writing Y(y)=βY(y)q0/LY(y)=\beta_Y(y)q_0/L, this constraint requires

Y(y)≥β1G(q0,y,N−).Y(y)\ge \beta_1G(q_0,y,N^-).

Consider

q_0=\frac32,\quad \beta_1=\frac56.$$ These choices of $q_0,\beta_1$ are feasible: $Y(y)\equiv1$ satisfies the constraint for every $y$, since $$\beta_1G(q_0,4,2) =\frac53\left(1-\frac1{\sqrt6}\right)<1.$$ However, at $y=3$, Lemma 22 gives $$Y(3) =\frac{3-\frac14\cdot\frac56\cdot\frac32}{3+\frac14} =\frac{43}{52} <\frac56 =\beta_1G(q_0,3,2),$$ violating constraint (260). The proof checks that the proposed choice lies within the bounds in (263), but does not establish this additional lower bound. Could the authors explain how to correct the lemma and whether the subsequent parameter-optimality results remain valid?
Reviewer_WhUBOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper investigates how different forms of horizon information affect the competitive ratio of the One-way Trading Problem (OTP). It proposes three algorithms: Latest Horizon Algorithm (LHA), Earliest-and-Latest Horizon Algorithm (ErLHA), and Exact Horizon Algorithm (ExHA). Optimal competitive ratios are established for several settings, and ErLHA is presented as a unified framework that recovers existing optimal results and achieves asymptotic optimality for the horizon-window setting.

Critical strengths
  1. The paper studies four forms of horizon information and provides a comprehensive analysis of competitive ratios, tightness, and optimality.
  2. ErLHA connects multiple OTP variants through a two-stage strategy with adaptive budget allocation.
  3. The results characterize when earliest- and latest-horizon information can improve online decision-making and how their effects interact.
Critical weaknesses
  1. The paper does not sufficiently distinguish its main theoretical contributions from previously established optimal results, particularly for OTP with an exact horizon.
  2. Theorem 9 relies on N^- to 1, a boundary case for an integer-valued horizon, raising concerns about the definition and interpretation of asymptotic optimality.
  3. The paper should more clearly distinguish optimality within the proposed algorithm family from global optimality for the general OTP-ErL problem.
  4. Additional quantitative analyses across different exchange-rate ranges and horizon-window widths would better demonstrate the significance of the theoretical findings.
Questions for authors
  1. What are the key novel theoretical contributions beyond existing results on OTP with unknown and exact horizons?
  2. How is asymptotic optimality formally defined in Theorem 9, and why does taking N^- to 1 establish asymptotic optimality for the general OTP-ErL setting?
  3. Does ErLHA achieve global optimality for arbitrary N^- and N^+, or only optimality within its specified algorithmic structure? If the former, a corresponding lower-bound proof needs to be provided.
  4. How does the competitive-ratio improvement vary with U/L and the horizon-window width?
Reviewer_bFU1OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper considers adversarial one-way trading of a unit budget, with exchange rates pi∈[L,U]p_i\in[L,U] revealed sequentially and an unknown trading horizon NN. It investigates knowing a minimum horizon N−N^-, a maximum horizon N+N^+, both, or the exact horizon. The paper proves that the minimum horizon alone does not improve the classical competitive ratio, derives an optimal Latest Horizon Algorithm (LHA), and proposes a two-phase Earliest-and-Latest Horizon Algorithm (ErLHA) with a record-price threshold and adaptive budget allocation. Its exact-horizon specialization recovers a previously known competitive ratio. The numerical results primarily visualize the theoretically derived ratios for different horizon bounds.

Critical strengths
  1. The distinctions among earliest, latest, window, and exact horizons are clear, and the latest-horizon result gives an explicit finite-horizon competitive ratio. The record-increment trading rule is also simple and interpretable.
  2. The two-phase ErLHA scheme provides a concrete way to reserve an early trading budget and allocate the remainder later. The appendix develops sufficient budget-feasibility conditions and worst-case performance bounds, which are useful even if the full optimality interpretation needs revision.
Critical weaknesses
  1. The paper is a valid adversarial online optimization model: future exchange rates are not known to the online trader. However, it does not model stochastic exchange-rate dynamics, transaction costs, or a realistic terminal value/requirement for remaining unconverted holdings. These omissions are acceptable for a competitive-analysis abstraction but substantially limit the claimed financial motivation. The practical value of knowing horizon bounds, separately from price uncertainty and trading frictions, is not convincingly established. From an optimization standpoint, much of the method consists of recalibrating record-based online allocation rules and embedding previously known special cases. It is unclear what broadly useful new principle is obtained.
  2. Theorem 9 calls ErLHA asymptotically optimal for general horizon windows, but Appendix N.2 only considers N−→1N^-\to1. Since N−N^- is integer valued, this recovers the endpoint N−=1N^-=1 rather than a nontrivial asymptotic regime or a matching general-window minimax lower bound. More concretely, evaluating the paper's Eqs. (5)--(12) at L=1L=1, U=5U=5, N−=100N^-=100, and N+=1000N^+=1000 yields an ErLHA worst-case ratio of approximately 2.6103702.610370, whereas LHA with the same latest horizon guarantees approximately 2.6081422.608142. Therefore, the prescribed window policy can perform worse than simply ignoring the extra earliest-horizon information. This does not invalidate its stated feasibility or algorithm-specific tightness, but it undermines the general optimality interpretation and the claimed monotonic behavior. In addition, Theorem 7 optimizes budget conditions identified as sufficient; the proof does not establish that these restrictions are without loss over all feasible executed trades.
Questions for authors
  1. What is the main new optimization insight beyond existing one-way trading and competitive-ratio frameworks? Can the authors explain the relevance of the adversarial horizon-information setting to financial exchange decisions with stochastic prices, transaction costs, and terminal holdings?
  2. What is the intended nontrivial asymptotic regime in Theorem 9, and what lower bound on the unrestricted optimal competitive ratio supports that claim? How do the authors reconcile Eqs. (5)--(12) with the counterexample L=1L=1, U=5U=5, N−=100N^-=100, N+=1000N^+=1000, for which ErLHA has a worse ratio than LHA?
  3. Can the authors justify that the sufficient feasibility constraints optimized in P0P_0 are without loss for Theorem 7, taking into account that the final early-horizon action is adjusted in Algorithm 2? Otherwise, which restricted parameter class is actually covered by the optimality claim?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.