acceptodds
Under review as a conference paper at ICLR 2027

Compressing Value Predictions for Learning-Augmented Metrical Task Systems

Abstract

Learning-augmented algorithms for metrical task systems (MTS) can exploit predictions of canonical dual values, but existing formulations typically require a prediction for every state. We study whether these predictions can be compressed to a small set of representative states while retaining their algorithmic value. We introduce landmark-compressed value predictions, in which the predictor reports predicted dual values only at landmarks and the remaining values are reconstructed by a Lipschitz extension. Our algorithm achieves additive excess cost , where is the covering radius of the landmarks and measures prediction error up to additive shifts; local and value-dependent bounds refine this guarantee. For sparse landmark sets on unit-spaced finite lines, we prove a matching lower bound for every randomized algorithm using fixed landmarks, even with advance access to their entire exact absolute-value table. The prediction interface also matters: on two states with one landmark, exact absolute values permit horizon-independent excess, whereas exact relative values force worst-case expected excess linear in . We give PAC guarantees for learning compressed prediction tables, with efficient empirical-risk minimization for fixed landmarks. Our results connect metric coverage, prediction interfaces, and learning guarantees for compressed predictions in online MTS.

Primary area:
learning theory
Keywords:
learning-augmented algorithms, metrical task systems, online algorithms, dual predictions, succinct predictions

Reviews

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

The paper extends the study of learning-augmented algorithms for metrical task systems (MTS) with dual predictions to a setting where the algorithm has an access to the prediction values of a given subset of states, called landmarks. From the algorithmic side, the paper presents an algorithm that additively incurs O(T⋅r(L))O(T \cdot r(L)) in the gap between the algorithm cost and the optimal cost, where TT is the time horizon and r(L)r(L) is the maximum distance to a nearest landmark. Complementing this positive result, the paper also shows that Ω(T⋅r(L))\Omega(T \cdot r(L)) is essentially tight even for a stronger setting where the whole prediction values of the landmarks are known upfront and for simple line metrics. The paper also argues the learnability of the prediction values for landmarks, and demonstrates the result of some qualitative experiments.

Critical strengths

The paper studies a natural extension from the previous work on learning-augmented algorithms for MTS with dual predictions. It is also good to see the paper presents a lower bound result showing the proposed algorithm is essentially optimal for the accurate prediction case.

Critical weaknesses

Despite the strengths, the paper also reveals some clear weaknesses. After understanding the setting, I felt the upper bound of O(T⋅r(L)+∑tδt)O(T \cdot r(L) + \sum_{t} \delta_t) looked somewhat natural to obtain when following the previous work. Hence, I was interested in the lower bound result, but found it quite difficult to understand in the first reading, which is mainly because some terms are used without proper definitions, including the following:

  • in Section 4: gadget, unhit, candidate, common baseline CC, and the optimal cost of a complete gadget,
  • in Appendix C: the discrete state space when used in set membership, 1-Lipschitz continuation VV, a score of a non-target state yy, an exterior/interior state.

I don’t think these terms are standard enough in MTS or related problems, so they should be properly defined before used. I believe readability becomes a much more important factor in assessing research papers these days. From this perspective, the paper would benefit from revision, especially of the lower bound part.

Questions for authors
  1. In Line 326, is DD defined before?
  2. In Line 786, isn’t ϕ\phi simply a function having hh at x=ax=a and −h-h at x=bx=b? Do we need this complicated definition?
  3. In Line 899, a landmark satisfying -> a landmark ℓ\ell satisfying
  4. In Line 902: a fixed tie rule -> a fixed tie-breaking rule?
2 comments

Thank you for pointing out these presentation issues. We have reorganized the lower-bound section and clarified Appendix C. Figure 1 now walks through all four rounds, and the terms you mentioned are explained where they first appear.

Regarding the four specific questions:

Definition of DD. D=max⁡x,y∈Md(x,y)D=\max_{x,y\in M}d(x,y) denotes the metric diameter, introduced in Section 2.

Definition of ϕ\phi. The values hh at aa and −h-h at bb are its extrema. The formula also specifies intermediate values, such as ϕ(a+1)=h−1\phi(a+1)=h-1, preserving the 1-Lipschitz property needed to realize fσ=C−σϕf_\sigma=C-\sigma\phi as canonical remaining costs. Two isolated spikes would create a jump of h≥2h\ge2 between adjacent states, violating this property. We have added this explanation alongside the definition.

Missing landmark symbol. Corrected to “a landmark ℓ∈L\ell\in L satisfying …”.

Tie-breaking terminology. Corrected to “a fixed tie-breaking rule”.

Thank you for the response. I will keep my original rating.

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

This paper studies the metrical task systems problem in the learning-augmented setting, where an online algorithm receives predictions of optimal remaining costs. It considers a value-greedy algorithm that reconstructs predictions for all states from values supplied at a small set of landmarks. The paper bounds the resulting excess cost in terms of landmark coverage and prediction error. A matching lower bound establishes the limitations of fixed landmarks on sparse finite lines, while a two-state example shows that absolute predictions can be more informative than relative ones. The paper also gives guarantees for learning fixed prediction tables and evaluates the approach on a server-placement benchmark.

Critical strengths
  1. The paper studies the fundamental problem of metrical task systems (MTS) and asks how much future-value information is needed for effective online decisions. It provides a coherent theoretical treatment through compression upper bounds, a matching-order lower bound on sparse finite lines, learning guarantees, and a separation between absolute and relative prediction interfaces. The lower bound is particularly strong: it applies to any policy with fixed-landmark access, even when the complete exact landmark-value table is supplied in advance. Studying the tradeoff between prediction size and algorithmic performance is a valuable step in the right direction for the learning-augmented literature.
  2. The landmark reconstruction is simple and intuitive, and integrates naturally with the value-greedy policy. The excess-cost bound clearly separates geometric coverage from prediction error and shows a smooth, linear dependence on the latter. The matching-order lower bound establishes that the geometric loss cannot generally be eliminated, even with perfect landmark predictions. These results make the tradeoff between prediction size and online performance transparent.
Critical weaknesses
  1. The explicit separation between absolute and relative predictions is established only for two states and one landmark, where the relative interface always returns zero and therefore provides no information. Although the absolute-value upper bound extends to settings with one unreported state, a corresponding separation with multiple landmarks is not established. This limits the generality of the interface comparison and leaves open whether a similar separation persists when relative predictions themselves contain useful information.
Questions for authors

Comments about presentation and readability: I found the introduction difficult to understand on a first reading and needed to revisit it after reading the problem setup and later sections. The exposition would benefit from more intuitive explanations of the central concepts. In Section 3, a self-contained algorithm statement or pseudocode would help distinguish the reconstruction and decision rule from their motivation and analysis. Clearer signposting of proof dependencies in the appendix would also make the arguments easier to navigate. For example, the proof of Theorem 2 in Appendix B relies on Lemma 7 in Appendix A.

2 comments

Thank you for raising this point. We have added a three-state example with two landmarks in Appendix D.3 (Proposition 13). Here, relative predictions are useful: they identify one of three possible futures and reduce the minimum expected excess per four-round block from 1/31/3 to 1/61/6. Each state is the best choice at the decision round in one case, so the additional landmark directly helps the decision.

The other two futures still have identical Relative tables but require different actions. This gives an excess-cost lower bound growing linearly with TT for every randomized Relative policy, even with random landmark selection before the episode and the complete table supplied in advance. A Raw policy, meanwhile, guarantees excess at most 2r(L)=22r(L)=2 on every episode of this metric.

We have also clarified the introduction, added a self-contained algorithm statement, and made the proof references explicit.

Thank you for the response and revisions. I will maintain my original score.

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

This paper studies the metric task system (MTS) problem in the learning-augmented setting. Recent work of Coester shows that using predictions of the standard dual variables, one can obtain near-optimal solutions for this problem. But this needs a dual variable per state in the metric space in every time-step. The current paper asks: if we only have dual variable predictions at certain landmark times, what is the best approximation bound that we can obtain using this information? Auxiliary questions include obtaining lower bounds on the fundamental tradeoffs between the coverage of landmarks and the approximation quality of the solution, learning these dual predictions in a PAC setting, and empirical performance on real-world application data.

Critical strengths

I like the direction of research which asks about the cost of predictions in online algorithms, and the necessary tradeoffs between granularity of predictions and solution quality. Of course, this is a question that has been previously studied for other problems such as paging, but MTS being a meta problem in the online domain is a good candidate for this line of research. The paper is also quite comprehensive in its treatment of the problem: upper and lower bounds, learnability of the predictions, noise tolerance, and empirical performance.

Critical weaknesses

The main weakness is that the writing of the paper really feels preliminary, possibly because of the heavy use of AI. There are many unexplained or under-explained terms, and as such, the main contributions of the paper at a technical level are difficult to follow because of the current writing quality. The paper would be much more valuable in terms of value creation if the authors distilled the results and rewrote the paper in a way that is easier for a reader even well-versed in the area to follow.

Another weakness is that the main result (the upper bound in Theorem 2) is pretty straightforward, and does not appear to be conceptually interesting.

Questions for authors

No questions, but I would strongly suggest that the authors reduce the amount of jargon used in the paper and rewrite it in a way that exposes the main conceptual and technical contributions to the reader.

2 comments

Thank you for the comment. We agree that the paper introduced too many terms before making the main idea clear. We have reorganized the Introduction and Sections 3–4, added a step-by-step algorithm box, and used a four-round example and figure to explain the lower bound.

Our main question is simple: how much do we lose when only a few state values are reported at each round? Building on Coester et al., we bound the extra cost and show that this bound is tight up to constants on sparse unit-spaced finite lines. The lower bound holds for every randomized policy with fixed landmarks, even if it receives the entire exact landmark-value table in advance. The hard part is to make two inputs look identical up to the decision while requiring different actions. Even earlier absolute values must stay identical, so they cannot give away the hidden choice.

Thanks for the rebuttal response. Unfortunately, the paper still reads like it has come straight from an LLM and does not make an effort to explain its significance, ideas, and techniques to a human reader. I believe such a paper is not suitable for publication in its current state. Hence, I will retain my score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.