Abstract
This paper, presented at AAAI-25, explores the intersection of classical online algorithms and modern machine learning by tackling the List Update problem through the lens of "learning-augmented" frameworks. The authors propose a new randomized algorithm that leverages machine learning predictions to achieve near-optimal performance when predictions are accurate (smoothness) while maintaining a theoretical safety net if the predictions are wrong (robustness).
Introduction
The List Update problem is a classic challenge in online computation: given a linear list of items and a sequence of requests, the goal is to minimize the total access cost. Accessing an item at position $i$ costs $i$. Post-access, the item can be moved toward the front for free, or adjacent items can be swapped at a cost of 1. While the "Move-to-Front" (MTF) algorithm is 2-competitive, this factor is often too high for practical applications where data follows predictable patterns rather than worst-case adversarial behavior.
Methodology
The researchers introduce a randomized algorithm designed to maintain a specific invariant between three states: the algorithm's current list, the prediction's suggested list, and a simulated "Move-to-Front with probability $\epsilon$" ($MTF_\epsilon$) list.
Smoothness and Robustness
The algorithm is designed to be $(1+\epsilon)$-smooth, meaning if the prediction is perfect, the cost is only marginally higher than the prediction's cost. Simultaneously, it is $O(1/\epsilon^4)$-robust, ensuring a worst-case bound relative to the true optimal solution. This addresses the fundamental trade-off where following a prediction closely (smoothness) typically requires sacrificing worst-case protection (robustness).
Spatial Integration and Lazy Transformation
Unlike many learning-augmented algorithms that switch between modes over time, this algorithm integrates strategies over space by interleaving elements from the predicted list with elements from a robust online list ($MTF_\epsilon$). Additionally, the authors utilize a "lazy transformation" result, proving that any list update algorithm can be converted into a version that performs swaps only when an element is accessed without increasing total cost.
Empirical Evaluation
The algorithm was evaluated using synthetic request sequences (Exponential Decay and Multiplicative Weights models) designed to mimic temporal locality and other predictable behaviors. It was tested against standard online algorithms including MTF, Timestamp, and the Bit algorithm.
As shown in the experimental results, the proposed algorithm consistently outperformed classical baselines in most scenarios. It maintains a cost ratio very close to the "perfect prediction" baseline (Pred) when the ML model is accurate and remains stable even as model parameters or update rates vary.
Key Insights and Future Work
A significant contribution of this work is the treatment of "paid swaps" in predictions, providing a mechanism to incorporate predicted neighbor swaps while maintaining robustness. While the algorithm achieves $O(1/\epsilon^4)$-robustness, a theoretical gap remains as the lower bound for randomized algorithms is $\Omega(\log(1/\epsilon))$. Future work includes closing this gap, exploring deterministic variants, and testing with real-world ML oracles on trace data such as CPU cache hits or database queries.
Summary updated