acceptodds
Under review as a conference paper at ICLR 2027

Pure Tail Constraints for Online Problems

Abstract

Controlling tail risk is an important objective in online optimization, and recently it has been studied in the context of competitive analysis. Continuing this line of research, we investigate *pure tail constraints*, which capture the tradeoff between expected and worst-case competitiveness. For two fundamental search problems, online bidding and line search, we derive the Pareto-optimal frontiers of this tradeoff. We then investigate another classic problem, TCP acknowledgment, which has structure similar to the iterated ski rental problem. There, we construct an algorithm whose tradeoff coincides with the known Pareto-optimal tradeoff for ski rental. The lower bounds for this problem are substantially more involved as the problem exhibits adaptive structure: an online algorithm observes requests of the adversary (packet arrivals) and may *adaptively* adjust its actions (acknowledgments) on this basis. We emphasize that all previous work on tail risk in the context of competitive analysis was restricted to non-adaptive problems, where the feedback given to an algorithm was essentially limited to a binary indicator of whether the algorithm has succeeded or not. Nonetheless, we identify a set of constraints implied by tail bounds in this adaptive setting, and show that they imply a nontrivial lower bound on the TCP acknowledgment problem.

Primary area:
optimization
Keywords:
Pure tail constraints, competitive analysis, online optimization

Reviews

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

The paper studies randomized online algorithms subject to a worst-realization performance guarantee, termed dependability. It derives exact tradeoffs between dependability and expected competitive ratio for online bidding and line search. For TCP acknowledgment, it provides an upper bound and a nontrivial lower bound, extending the analysis to a setting where algorithms adapt their decisions to arriving requests.

Critical strengths
  1. The exact frontiers are substantive theoretical contributions. The results characterize what randomization can achieve while retaining a deterministic-style worst-realization guarantee. Matching upper and lower bounds for two canonical problems provide a complete answer rather than merely another competitive algorithm.

  2. The step-ratio lemma supplies a clear structural insight. It explains how dependability restricts the growth of feasible bidding or search sequences and why geometric strategies attain the optimal tradeoff. Reusing the lemma across online bidding and line search makes the contribution more coherent and potentially reusable.

  3. The TCP lower-bound argument addresses a genuine additional difficulty. The penalizing-suffix construction derives constraints on dependable deterministic algorithms despite their ability to adapt to packet arrivals. These constraints then support a fixed adversarial distribution for the randomized lower bound; this is more substantial than directly transferring the non-adaptive search analysis.

Critical weaknesses
  1. The most distinctive extension remains incomplete. For TCP acknowledgment, the upper and lower bounds do not coincide, and the new lower bound improves on the unconstrained randomized bound only over a limited dependability range. Thus, the paper characterizes the adaptive setting less completely than the two search problems.

  2. The algorithmic contribution is narrower than the collection of results might initially suggest. The constructive strategies primarily parameterize or modify established algorithms. The strongest novelty therefore lies in the lower-bound techniques. A sharper explanation of which proof ingredients are specific to these problems and which support a broader theory would strengthen the paper’s significance.

Questions for authors
  1. Is the proposed TCP distribution optimal within the family of fixed-threshold algorithms, or is it only a feasible construction achieving the stated bound?

  2. Does the remaining TCP gap primarily reflect the restriction to two-burst lower-bound instances, or is there also evidence that the upper-bound algorithm could be improved?

2 comments
AuthorsOpenReview ↗

Response to Reviewer 38UK

We thank the reviewer for the insightful comments. We hope the below answers adequately address your concerns.

Weakness W1 (bounds gap for TCP acknowledgment)

We agree that the adaptive setting is characterized less completely than the two search problems. As we explain in our responses to Reviewers 8uVB and 48eW, we believe that neither of our two bounds for TCP acknowledgment is tight, and that adaptivity is the reason in both cases. The adversary can use instances with more bursts, and the algorithm can carry its unused budget over to later rounds. Our paper is the first to study tail constraints for an adaptive problem. It provides concrete tools for this setting (the post-ack budget and the penalizing suffix) that could be useful in further work on related problems.

Weakness W2 (contribution)

We agree that the lower bounds are the most novel parts of the paper.

In our view, they are not only interesting results by themselves, but our intention was also to extract certain properties of algorithms constrained by the tail bounds that may generalize to a wider group of problems. One of them is the step ratio lemma (Lemma 9), which shows that if the prefix sums of bids satisfy the tail constraint, then the sum of ratios of consecutive bids is appropriately lower-bounded. The other is the penalizing suffix lemma (Lemma 27), where the adversary repeatedly forces the algorithm to pay a fixed cost while the optimal cost grows slowly, and the budget is upper-bounded by an affine map with an unstable fixed point.

We will try to make these tools more self-contained and ready to be reused in other problems.

Question Q1 (conditional optimality of proposed TCP distribution)

We conjecture that the presented algorithm is optimal not only in the family of fixed-threshold algorithms, but even in the class of algorithms defined in Remark 19 (an algorithm that: (i) samples a parameter z1∈[r,1]z_1 \in [r, 1] at the beginning of its execution, (ii) after the ii-th acknowledgment, chooses a new parameter zi+1∈[r,1]z_{i+1} \in [r, 1] and uses it to determine the time of the next acknowledgment). We also kindly refer you to our answer for Questions 1 and 2 of Reviewer 48eW. We will state this conjecture formally in our paper.

Question Q2 (tightness of TCP bounds)

The lower bound can be improved, and we conjecture that the upper bound can be improved as well. We include here a part of the answer to the question of Reviewer 8uVB:

On the one hand, the lower bound can be improved by using instances with more than two bursts, as Lemma 22 provides constraints for any number of bursts. However, the improvement that we obtained this way was minor while it made the analysis substantially more complicated, so we decided to present the two-burst construction only.

On the other hand, we conjecture that the upper bound is not tight either. Dependability constrains the total cost of the whole execution, while our algorithm satisfies it separately in each round. On instances where the algorithm pays less than the constraint allows in initial rounds, it could keep the unused budget and spend it in later rounds by choosing thresholds smaller than rr. We will mention both observations as interesting future directions in the conclusion.

Thanks a lot for the detailed rebuttal message, which addresses most of my concerns. I'll keep my original positive score.

Reviewer_48eWOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies the trade-off between the expected competitive ratio of a randomized online algorithm and a worst-case bound that must hold for every realization of its randomness. The latter is called dependability and corresponds to a pure tail constraint. The paper gives optimal trade-offs for online bidding and line search. For TCP ack problem, it constructs an algorithm with the same trade-off as the known ski-rental result and derives a lower bound, but the two bounds do not match.

Critical strengths
  • Studying how to control the tail risk of randomized algorithms is an important and challenging question. This paper studies pure tail constraints for online bidding, line search, and TCP ack: it fixes a worst-case cost-ratio bound γ\gamma and seeks a low expected competitive ratio by randomizing only over deterministic algorithms that satisfy this bound for every input. The cost ratio therefore has zero probability of exceeding γ\gamma. Although this trade-off can be conservative, I think it is a reasonable way to constrain the risk of randomized algorithms.

  • The main technical contribution appears to be the lower bound for TCP ack. In particular, the first step derives structural constraints that every γ\gamma-dependable deterministic algorithm must satisfy on the constructed burst instances. This result could be useful for future work.

Critical weaknesses
  • Pure tail constraints simplify risk control to restricting the support to dependable deterministic algorithms and optimizing expected competitive ratio over this class. The upper bound constructions also largely adapt existing algorithms. The authors should more clearly explain the new technical challenges relative to prior tail probability and CVaR competitive ratio formulations (maybe from the lower bound perspective).

  • The pure tail constraint may be overly conservative when a small probability of a high cost ratio is acceptable. Also, the paper does not include numerical comparisons with nonzero-tail-probability or CVaR-based approaches. Such comparisons would help clarify how this more conservative guarantee affects expected performance and tail behavior.

  • The upper and lower bounds for TCP ack problem do not match.

Questions for authors
  • For the TCP acknowledgment upper bound, is the proposed sampling distribution optimal among distributions over {DETz:z∈[r,1]}\{\mathrm{DET}_z:z\in[r,1]\}, or does it only give the stated upper bound? In addition, could the authors comment on whether the current upper bound for TCP ack could be tight?

  • Remark 19 allows the threshold to change after each ack based on the observed history. Can this additional adaptivity improve the expected competitive ratio while preserving the same dependability guarantee?

  • There is a lack of numerical tests to compare different risk control methods, including algorithms with probabilistic tail constraints and CVaR-based algorithms.

2 comments
AuthorsOpenReview ↗

Response to Reviewer 48eW

We thank the reviewer for the insightful comments. We hope the below answers adequately address your concerns.

Weakness 1 (Technical challenges relative to prior formulations)

We agree with the reviewer: compared to prior work, we consider a simpler constraint, but we study it for problems with a richer structure.

A pure tail constraint reduces the task to optimizing the expected ratio over distributions on γ\gamma-dependable deterministic algorithms; this follows directly from Definition 5. We also agree that our algorithms adapt existing ones, and our main contributions are the lower bounds, where the difficulty moves to describing the set of γ\gamma-dependable algorithms. To apply the min-max principle, we need a property that every such algorithm satisfies, and that is strong enough to bound its expected ratio on a fixed input distribution.

For instance, for ski rental, a deterministic algorithm is a single number (the day of buying), and such a property would be immediate: this number lies in an interval. However, for online bidding, a deterministic algorithm is an infinite sequence of bids, and dependability gives one constraint per bid (we need Lemma 9 to combine these constraints into a bound on the growth of the bids). For TCP acknowledgment, a deterministic algorithm is a function of the observed history, so its constraints cannot be read off from a fixed instance. To our knowledge, such analysis of adaptivity has no counterpart in prior work on tail risk.

We will include a detailed discussion of the technical challenges in the camera-ready version of the paper, together with a comparison with the CVaR approach.

Weakness 2 and Question 3 (Conservativeness and numerical comparison)

We agree that pure tail constraints are conservative: they are the endpoint δ=0\delta = 0 of the family of tail constraints (γ,δ)(\gamma, \delta). We see this setting as a necessary foundational first step in understanding the general tail bound constraints, and we argue that the strength of our paper lies in two areas: understanding exact Pareto frontiers for the two “non-adaptive” problems (online bidding, line search), giving non-trivial bounds for “adaptive” problem, the TCP acknowledgment.

Here, the answer is similar to the previous one: we consider a simpler constraint than previous works, but we study it for problems with a richer structure.

Regarding numerical comparisons: for online bidding, line search and TCP acknowledgment, no CVaR guarantees or tail constraints with δ>0\delta > 0 have been analyzed, so there is no result that we could compare against. Our guarantees hold for worst-case inputs and are given in closed form; Fig. 1 plots them exactly, with the deterministic and the unconstrained randomized optima as the two reference points.

In the camera-ready version, we will consider providing a numerical comparison of the ski-rental bounds as an illustrative example of the differences in these performance metrics.

Weakness 3 and the second part of Question 1 (optimality of TCP acknowledgment bounds)

For the discussion of the source of the gap between the upper and lower bounds, please see our response to Weakness W1 (bounds gap for TCP acknowledgment) raised by Reviewer 8uVB; we do not copy it here due to the character limit.

Questions 1 and 2 (Analysis of TCP acknowledgment algorithm)

Thank you for these questions. Since the bounds for TCP acknowledgment do not match, it is natural to think about the generalizations of algorithm RANDrRAND_r that may improve its performance. We came up with the following generalization:

  • Consider the class ZrZ_r of algorithms that choose a parameter zi∈[r,1]z_i \in [r, 1] both at the beginning of their execution and after every acknowledgment and use it to determine the time of the next acknowledgment. Note that this class contains the class of algorithms that sample z∈[r,1]z \in [r,1] once and then run procedure DETzDET_z.

Remark 19 states that every (deterministic or randomized) algorithm belonging to class ZrZ_r is γ(r)\gamma(r)-dependable.

We conjecture that no algorithm from class ZrZ_r can achieve a competitive ratio better than our algorithm (which is an extension of that of Karlin et al. (Algorithmica 2003)). This conjecture, if true, would imply that a significantly different algorithm is needed to beat the current upper bound. We also believe that our distribution is optimal among distributions over DETz:z∈[r,1]DET_z : z \in [r, 1] since it is essentially equivalent to the optimal distribution for ski rental derived in Dinitz et al. (SODA 2024) while the connection between ski rental and TCP acknowledgment was intensively studied by Karlin et al. (Algorithmica 2003).

Thank you for your very detailed response. Since the problem itself is challenging, I think this paper gives a very good step to better understand the pure risk constrained setting. The lower bound is also a good contribution. I will keep my rating due to the still incomplete results for tcp ack problem, but I lean towards accepting the paper.

Reviewer_8uVBOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the trade-off between expected competitive performance and realization-wise worst-case guarantees (dependability) under pure tail constraints. It establishes exact Pareto frontiers for online bidding and line search, and non-matching upper and lower bounds for TCP acknowledgment. The main technical contributions are structural restrictions on dependable algorithms, including the first adaptive problem in this framework, and the resulting lower bounds.

Critical strengths

S1. The dependability notion captures pure tail risk and is a natural counterpart to CVaR/tail-constraint formulations. The distinction between worst-case dependability and expected competitiveness is clearly stated.

S2. The step-ratio lemma connects worst-case guarantees to restrictions on bidding or exploration sequences. It is a reusable technical tool and gives a unified explanation for why geometric sequences are essentially forced.

S3. This paper provides a nontrivial adaptive lower bound for TCP acknowledgment, an important and practical problem in real applications.

Critical weaknesses

W1. The upper and lower bounds do not match. The authors have acknowledged this, but TCP acknowledgment is one of the three main problems and the title emphasizes "pure tail constraints". Further evidence identifying whether the gap stems from the algorithm or the two-burst lower-bound construction would strengthen the contribution.

W2. The adversary model needs more explicit explanations. The TCP lower bound first uses an adversary that reacts to acknowledgments, and then applies Yao's principle with a fixed distribution over instances. These two steps play different roles: the reactive construction only establishes necessary properties of deterministic algorithms, whereas the final randomized lower bound is against a fixed input distribution, not an adaptive adversary. The paper would be clearer if this distinction were stated.

W3. The equivalence between dependability and zero-probability tails needs more clarification. Definition 5 requires the bound for every supported deterministic algorithm and every input. A per-input probability-zero tail condition can allow exceptional random outcomes. Please clarify the intended notion of support and justify this equivalence, especially for algorithms using continuous randomization.

W4. The paper is a competitive-analysis theory paper with no learning or empirical component. It fits ICLR's algorithms track to some extent, but the audience may be narrower than for learning-theoretic work.

Questions for authors

Please refer to W1-W4.

1 comment
AuthorsOpenReview ↗

Response to Reviewer 8uVB

We thank the reviewer for the insightful comments. We hope the below answers adequately address the concerns.

Weakness W1 (bounds gap for TCP acknowledgment)

For the first point, we are not sure about the comment related to the title, but “pure” is not connected to the tightness of the bounds. Please correct us if we got the question wrong.

For the second point, it is difficult for us to answer at this moment where the gap stems from. On the one hand, the lower bound can be improved by using instances with more than two bursts, as Lemma 22 provides constraints for any number of bursts. However, the improvement that we obtained this way was minor while it made the analysis substantially more complicated, so we decided to present the two-burst construction only.

On the other hand, we conjecture that the upper bound is not tight either. Dependability constrains the total cost of the whole execution, while our algorithm satisfies it separately in each round. On instances where the algorithm pays less than the constraint allows in initial rounds, it could keep the unused budget and spend it in later rounds by choosing thresholds smaller than rr. We will mention both observations as interesting future directions in the conclusion.

Weakness W2 (adversary model)

As the reviewer pointed out, our lower bound proof for TCP acknowledgment consists of two parts, and we will make it more explicit at the beginning of Section 6. Indeed, our bound holds against oblivious adversaries. In the paper the term “adaptive” refers to the algorithm, which observes packets and adjusts its future acknowledgments; we will make sure it is not associated with the adversary.

More concretely, in Section G.1, the adaptivity serves only to restrict the support of γ\gamma-dependable randomized algorithms using an adaptive construction; the result is a set of necessary properties (Lemma 22). The lower bound of Section G.2 is then proved against a fixed distribution over instances, i.e., against an oblivious adversary, and Lemma 6 is applied in the standard way.

Weakness W3 (dependability vs. zero-probability tails)

Thank you for this comment; the term "support" that we used in Definition 5 was incorrect.

We require that the ratio is at most γ\gamma surely (for every outcome of the random choices), not only almost surely (with probability one). Formally, a randomized algorithm is a map w→DETww \to DET_w that assigns a deterministic algorithm to each outcome ww of the random choices. It is γ\gamma-dependable if R(DETw,σ)≤γR(DET_w, \sigma) \leq \gamma for every outcome ww and every instance σ\sigma. In other words, the bound holds for every deterministic algorithm in the image of this map, i.e., in the set DETww\\{ DET_w \\}_w of all algorithms that the random choices can produce. In Definition 5, we wrote "support" for this set. We will rephrase the definition as above and replace "support" by a more appropriate term throughout the paper.

We will also correct the sentence after Definition 5: γ\gamma-dependability implies the tail constraint (γ,0)(\gamma, 0), and the two are not equivalent.

Weakness W4 (conference fit)

Risk-sensitive sequential decision-making is an established topic in the machine learning community. To give a small set of examples, it was studied for expert advice (Even-Dar, Kearns and Wortman, ALT 2006), multi-armed bandits (Sani, Lazaric and Munos, NeurIPS 2012; Agrawal, Koolen and Juneja, NeurIPS 2021) and Markov decision processes (Fei, Yang, Chen, Wang and Xie, NeurIPS 2020). It is noteworthy that the CVaR competitive ratio, one of the two frameworks that we build on, was introduced at COLT (Christianson, Sun, Low and Wierman, COLT 2024).

Moreover, the problems that we study are standard benchmarks in the learning-augmented line of work published at NeurIPS, e.g., ski rental (Purohit, Svitkina and Kumar, NeurIPS 2018) and TCP acknowledgment (Bamas, Maggiori and Svensson, NeurIPS 2020). We believe that exact tradeoff characterizations for these basic problems are useful for that line of work.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.