Compressing Value Predictions for Learning-Augmented Metrical Task Systems

Sizhe Li; Yecheng Li; Kun He

cs.LGSep 27, 2026

Compressing Value Predictions for Learning-Augmented Metrical Task Systems

Authors: Sizhe Li, Yecheng Li, Kun He

Organizations: School of Artificial Intelligence and Automation Huazhong University of Science and Technology Wuhan, Hubei 430074, China · School of Computer Science and Technology Huazhong University of Science and Technology Wuhan, Hubei 430074, China

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 $m$ landmarks and the remaining values are reconstructed by a Lipschitz extension. Our algorithm achieves additive excess cost $O(T\,r(L) + \sum_t δ_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 $Ω(T r_m)$ 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.

Figures & tables

Setting	$m/n$	Full	Distortion	Random	Geom.	WFA	DC
$K=3$ , 1 min	24/120	1.2712	1.2695	2.2326	1.6518	1.5286	2.5541
$K=3$ , 15 min	24/120	1.1657	1.1659	1.5988	1.3081	1.4035	2.1838
$K=4$ , 1 min	42/210	1.1788	1.1786	3.4129	1.1895	1.6160	3.5168
$K=4$ , 15 min	42/210	1.1524	1.2043	1.5396	2.9478	1.7067	2.4071
$K=5$ , 1 min	50/252	1.0502	1.0499	3.1009	1.0706	1.7300	4.9765
$K=5$ , 15 min	50/252	1.3810	1.2737	2.2557	1.5288	1.9049	2.7607

Table 1: Mean daily ALG/OPT on 365 dates with the mean predictor and approximately 20% of predicted values retained. Bold marks row minima, including ties, without implying statistical significance. Additional comparisons are in Section G.1 .

Appendix figures & tables14 assets

Supplementary material from the paper’s appendix.

Appendix

Split	Dates	Days	Filtered trips
Initial fit	2023-01-01–2024-09-30	639	55,497,434
Validation	2024-10-01–2024-12-31	92	8,910,606
Final refit	2023-01-01–2024-12-31	731	64,408,040
Evaluation	2025-01-01–2025-12-31	365	36,453,843

Appendix

Table 2: Citi Bike data split. The final refit overlaps the two preceding rows.

Quantity	Localized	Switching
States / horizon / pair budget	$9\,/\,12\,/\,2$	$9\,/\,12\,/\,2$
Train / validation / test per seed	$32\,/\,64\,/\,256$	$32\,/\,64\,/\,256$
Preferred-center template $\bar{\mu}_{t}$	$0.68+0.11\sin(2\pi t/6)$	$0.50+0.30\sin(2\pi t/6)$
Episode / task Gaussian scales	$0.045\,/\,0.035$	$0.045\,/\,0.035$
Amplitude distribution	$\mathrm{Unif}[1.5,2.5]$	$\mathrm{Unif}[4,7]$
Per-state additive noise	$\mathrm{Unif}[0,0.025]$	$\mathrm{Unif}[0,0.025]$

Appendix

Table 3: Complete pilot configuration. Gaussian scales are standard deviations. Both scenarios use the same split sizes and landmark budget.

$K$	Resolution / contrast	$\Delta$ or contrast	95% block CI
3	1 min	-0.001747	[-0.003456, -0.000187]
3	15 min	+0.000169	[+0.000000, +0.000506]
3	1 min minus 15 min	-0.001916	[-0.003676, -0.000297]
4	1 min	-0.000142	[-0.000862, +0.000551]
4	15 min	+0.0518	[+0.0306, +0.0728]
4	1 min minus 15 min	-0.0520	[-0.0729, -0.0306]

Appendix

Table 4: Distortion minus Full with approximately 20% of predicted values retained, and its paired cross-resolution contrast. Each resolution uses its own daily OPT. All intervals here use circular seven-day blocks, 2,000 replicates, seed 20260922.

Setting	Comparison	Difference	95% block CI
$K=3$ , 15 min	Distortion - Random	-0.43294	[-0.4845, -0.3891]
$K=3$ , 15 min	Distortion - Geom.	-0.14221	[-0.2242, -0.0664]
$K=4$ , 15 min	Distortion - Random	-0.33533	[-0.3843, -0.2904]
$K=4$ , 15 min	Distortion - Geom.	-1.74355	[-1.8554, -1.6376]
$K=5$ , 15 min	Distortion - Random	-0.98201	[-1.0892, -0.8776]
$K=5$ , 15 min	Distortion - Geom.	-0.25517	[-0.3431, -0.1614]

Appendix

Table 5: Paired selector differences at approximately 20%. Negative differences favor Distortion. Intervals use 2,000 seven-day block replicates (seed 20260919) and are unadjusted for multiple comparisons. Distortion–Full intervals are in Table 4 .

Setting	Method	ALG/OPT	$\eta$ /OPT	Recon.
$K=3$ , 15 min	Full	1.1657	7.6815	0.0000
$K=3$ , 15 min	Distortion	1.1659	9.4318	0.8925
$K=4$ , 15 min	Full	1.1524	9.7615	0.0000
$K=4$ , 15 min	Distortion	1.2043	18.2262	1.4162
$K=5$ , 15 min	Full	1.3810	15.5573	0.0000
$K=5$ , 15 min	Distortion	1.2737	39.5873	1.6323

Appendix

Table 6: Mean-predictor diagnostics for Full and approximately 20% Distortion. Recon. is the per-slot reconstruction span relative to predicted Full values. The supplementary CSV retains all four methods and their ordinary date-bootstrap marginal intervals.

Predictor	Full	95% block CI	RMSE	Error span	$\eta$ /OPT
Static	1.1520	[1.1202, 1.1863]	1.0403	4.3440	12.4987
Mean	1.1524	[1.1214, 1.1865]	0.7726	2.9219	9.7615
MLP	1.1464	[1.1207, 1.1736]	0.7856	3.2413	15.5222
GRU	1.1378	[1.1139, 1.1632]	0.7649	3.0593	14.5484

Appendix

Table 7: Full-predictor costs and value errors on the 365 evaluation dates. RMSE uses centered exact values; value-error span and Bellman residual are distinct diagnostics.

Predictor	Method	ALG/OPT	95% block CI	Ret.	Recon.
Static	Distortion	1.1877	[1.1576, 1.2201]	93.57%	1.5840
Static	Random	1.7223	[1.6565, 1.7925]	-2.81%	3.9430
Static	Geom.	2.6758	[2.5404, 2.8136]	-174.69%	3.2623
Mean	Distortion	1.2043	[1.1826, 1.2259]	90.65%	1.4162
Mean	Random	1.5396	[1.4922, 1.5905]	30.15%	3.9819
Mean	Geom.	2.9478	[2.8428, 3.0563]	-223.90%	3.0379

Appendix

Table 8: Temporal-family compression retaining

m=42

of 210 predicted values. Neural results average the crossed training and landmark seeds within each date. Bold marks the lowest ALG/OPT within each predictor, without implying statistical significance.

Comparison	Difference	95% block CI
GRU Full - Mean Full	-0.01463	[-0.0446, +0.0127]
GRU Full - MLP Full	-0.00860	[-0.0210, +0.0034]
GRU Full - Static Full	-0.01417	[-0.0442, +0.0134]
MLP Full - Mean Full	-0.00604	[-0.0328, +0.0182]
Static Full - Mean Full	-0.00046	[-0.0019, +0.0009]
Static: Distortion 20% - Full	+0.03569	[+0.0281, +0.0436]

Appendix

Table 9: Paired temporal-family comparisons. Intervals use seven-day block resampling and condition on the fitted data and seeds.

Setting	Oracle Distortion [95% CI]	Predicted minus oracle [95% CI]
$K=3$ , 1 min	1.0017 [1.0013, 1.0022]	+0.2678 [+0.2524, +0.2844]
$K=3$ , 15 min	1.0016 [1.0007, 1.0026]	+0.1643 [+0.1404, +0.1889]
$K=4$ , 1 min	1.0015 [1.0009, 1.0022]	+0.1771 [+0.1627, +0.1939]
$K=4$ , 15 min	1.0077 [1.0050, 1.0108]	+0.1966 [+0.1760, +0.2191]
$K=5$ , 1 min	1.0005 [1.0001, 1.0011]	+0.0494 [+0.0420, +0.0572]
$K=5$ , 15 min	1.0030 [1.0014, 1.0050]	+0.2707 [+0.2307, +0.3187]

Appendix

Table 10: Frozen-landmark exact-value diagnostic at approximately 20%. Oracle Full equals OPT in every setting. Intervals use seven-day blocks. The last column replaces inputs at fixed landmarks; it is not an independent causal component of total loss.

Minutes	Changed	Improved	Worsened	$\sum\Delta Q/\mathrm{OPT}$ [95% CI]
1 min	0.010	0.004	0.002	-0.000147 [-0.000493, +0.000110]
15 min	0.992	0.336	0.348	-0.0832 [-0.1311, -0.0360]

Appendix

Table 11:

K=5

actions compared at the same states visited by predicted Full. Counts are daily averages; the final column averages the daily normalized sum of exact-continuation action differences. This is not the cost difference between the two policies' actual trajectories.

Setting	$\bar{e}$	$S_{0}/\mathrm{OPT}$	$R_{\rm or}$	$1+\eta/\mathrm{OPT}$	$1+B_{\rm adj}/\mathrm{OPT}$	$1+B_{\rm act}/\mathrm{OPT}$
$K=3$ , 1 min	0.1848	1.450	1.0017	2.043	3.900	2.403
$K=3$ , 15 min	0.7715	8.138	1.0016	5.207	17.238	9.099
$K=4$ , 1 min	0.1423	3.506	1.0015	3.230	8.010	4.408
$K=4$ , 15 min	1.3849	19.542	1.0077	16.962	40.004	20.458
$K=5$ , 1 min	0.1725	9.965	1.0005	6.581	20.929	10.815
$K=5$ , 15 min	1.6489	41.135	1.0030	35.985	82.980	41.838

Appendix

Table 12: Exact-value distortion and certificates for Distortion at approximately 20%. Normalize within each date before averaging. The final three columns are cost-ratio upper bounds, not attained costs; Section F.7 defines

S_{0},B_{\rm adj},B_{\rm act}

Setting	365-day Distortion	355-day Distortion
$K=3$ , 1 min	1.2695	1.2707
$K=3$ , 15 min	1.1659	1.1688
$K=4$ , 1 min	1.1786	1.1797
$K=4$ , 15 min	1.2043	1.2054
$K=5$ , 1 min	1.0499	1.0494
$K=5$ , 15 min	1.2737	1.2743

Appendix

Table 13: Mean daily ALG/OPT at approximately 20% after excluding the first ten 2025 dates. All eight settings use the same fitted models and landmarks as their full-year evaluations.

Method	Localized	Switching
Uniform random pairs (exact average)	$0.40154\pm 0.01142$	$0.43569\pm 0.00668$
Geometric pair	$0.17838\pm 0.01720$	$0.39766\pm 0.01932$
Learned distortion pair	$\textbf{0.04810}\pm 0.00666$	$0.13927\pm 0.01661$
Learned validation pair	$\textbf{0.04810}\pm 0.00666$	$0.13927\pm 0.01661$
Learned singleton	$\textbf{0.04810}\pm 0.00666$	$0.41436\pm 0.00850$
Full-state fixed table	$\textbf{0.04810}\pm 0.00666$	$\textbf{0.04031}\pm 0.00882$

Appendix

Table 14: Test total episode excess

\mathrm{ALG}-\mathrm{OPT}

: mean

\pm

sample standard deviation of the three seed-level means (not confidence intervals). Oracle full-state excess is below

10^{-15}

in magnitude and displayed as zero. Bold marks the lowest non-oracle mean in each column, including ties, without implying statistical significance.

	Localized		Switching
Method	$C_{\kappa}$	$C_{\rm loc}$	$C_{\kappa}$	$C_{\rm loc}$
Geometric pair	3.05480	1.72344	3.94197	4.21647
Learned distortion pair	1.15931	0.60406	2.13124	1.79679
Learned validation pair	1.51201	0.49766	2.13124	1.79679
Learned singleton	1.30334	0.28874	4.05037	3.42253
Full-state fixed table	0.94929	0.94929	0.98307	0.98307

Appendix

Table 15: Mean offline certificates over the three seed-level test means. Observed excess and seed standard deviations are in Table 14 ;

C_{\kappa}

and

C_{\rm loc}

are defined in ( 59 ).

Explore similar work

May 26, 2026cs.DS

Parsimonious Learning-Augmented Online Metric Matching

Learning-augmented algorithms have received significant attention in recent years, particularly in the context of online optimization. Motivated by the high computational cost of generating predictions, a growing line of work studies the tradeoff between performance guarantees and the number of predictions used in learning-augmented algorithms for problems such as caching and metrical task systems. In this paper, we extend this line of research to online metric matching by developing parsimonious learning-augmented algorithms and establishing lower bounds on their performance. Our approach extends the Follow-the-Prediction framework to the parsimonious setting by filling in a virtual prediction in the absence of an actual prediction, using an online metric matching algorithm that maintains good intermediate matchings throughout its execution. We complement our theoretical results with an empirical evaluation, demonstrating the practical effectiveness of our approach.

Yongho Shin, Phanu Vajanopath

Institute of Computer Science, University of Wrocław, Wrocław, Poland.

Learning-Augmented Algorithms Similarity and Metrics

Ask PDF

Jun 3, 2026cs.DS

Learning-Augmented Online Minimization with Dual Predictions

We present learning-augmented algorithms for two general classes of online minimization problems: metrical task systems and laminar set cover. Both algorithms achieve improved theoretical guarantees using machine-learned predictions of an optimal solution to the dual linear program. Unlike optimal primal solutions, which can change drastically under tiny instance perturbations, these dual solutions are much more stable, which ensures the existence of good (and learnable) predictions for families of similar instances. While previous work has used dual predictions in offline settings and for online maximization problems, our algorithms are, to the best of our knowledge, the first demonstration that such dual predictions can be effective for online minimization. Our theoretical results are complemented by experiments on the

k

-server problem and the parking permit problem.

Christian Coester, Alexa Tudose, Alexander Turoczy

University of Oxford, United Kingdom

Learning-Augmented Algorithms Flat Minima New Tasks

Ask PDF

Jun 17, 2026cs.DS

Learning Augmented Exact Exponential Algorithms

The field of learning-augmented algorithms has demonstrated that machine-learned predictions can bypass worst-case lower bounds across a wide range of problems. So far, however, the focus has been almost exclusively on polynomial-time algorithms, where predictions improve competitive ratios, approximation guarantees, or running times. In this paper, we raise the question of whether predictions can push the frontier of exact exponential-time algorithms for NP-hard problems. We answer this question affirmatively by proposing a general approach that augments an entire family of state-of-the-art exact algorithms for a variety of subset selection problems. We show that a noisy predictor that is only marginally better than random guessing suffices to provably reduce the search space, and that the resulting runtime speedup scales smoothly with the prediction quality. Importantly, our algorithms require only pairwise independence of predictions or, alternatively, do not require the knowledge of the predictor's accuracy - both strictly weaker and more realistic settings than typically assumed.

Tatiana Belova, Yuriy Dementiev, Danil Sagunov

ITMO University

Learning-Augmented Algorithms

Ask PDF