Compressing Value Predictions for Learning-Augmented Metrical Task Systems

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 m landmarks and the remaining values are reconstructed by a Lipschitz extension. Our algorithm achieves additive excess cost O(T,r(L) + sumt δt), where r(L) is the covering radius of the landmarks and δt 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 Omega(T rm) 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 T. 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.