Learning-Augmented Algorithms for MTS with Bandit Access to Multiple Predictors
A delayed-exploration MTS algorithm matches the best predictor within O(OPT^{2/3}), with a nearly matching lower bound.
Key Findings
Methodology
The framework uses HEDGE or SHARE as an internal full-information learner, alternating exploitation and structured exploration. An explored heuristic is queried for m consecutive steps, after which its movement-inclusive cost is observable. The feedback is normalized as g_t(i)=f_t(e_t)/(2D) for the sampled heuristic only. MTS-style Round rounding controls switching, while greedy actions from the last known state handle missing predictor states.
Key Results
- Theorem 1.1 proves E[ALG]≤OPT_{≤0}+O(OPT_{≤0}^{2/3}) for constant diameter D, predictor count ℓ, and delay m. Thus the competitive ratio relative to the best fixed heuristic converges to one.
- Theorem 1.3 gives E[ALG]≥OPT_{≤0}+~Ω(OPT_{≤0}^{2/3}) even for m=2, despite one-step look-ahead and access to improper MTS actions. The upper and lower bounds differ only polylogarithmically.
- For a benchmark switching at most k times, Theorem 1.2 gives OPT_{≤k}+~O(k^{1/3}OPT_{≤k}^{2/3}). General dependence includes (Dkℓ lnℓ)^{1/3}m^{2/3}; Section 6 obtains O(T^{2/3}) memory-bounded-bandit regret.
Significance
The paper extends learning-augmented online algorithms from full-feedback predictor portfolios to realistic query-limited settings. It shows that an algorithm can asymptotically match the best expert even when movement costs cannot be estimated from a single observation. This is relevant to caching, routing, k-server systems, and energy control, where running every expensive predictive model is impractical. The matching lower bound identifies a fundamental information-cost barrier rather than a weakness of a particular implementation.
Technical Contribution
The main ingredients are delayed exploration, biased single-arm feedback, improper actions, MTS rounding, and stability of HEDGE. Lemma 3.1 bounds the constructed MTS cost by (1+O(εm²))Σ_t(f_t^Tx_t+D||x_t−x_{t−1}||_1). With ε=(Dℓlnℓ)^{1/3}m^{-4/3}OPT_{≤0}^{-1/3} and a matched HEDGE learning rate, the method obtains sublinear regret in the benchmark cost, not merely in horizon T.
Novelty
Unlike Blum and Burch’s full-feedback HEDGE combination, Arora et al.’s fixed-block memory-bounded bandit method, and Antoniadis et al.’s model where predictors report movement costs, this work uses only one queried predictor and does not trust declared costs. It gives both an upper bound and a Dekel et al.-style lower bound for the natural delayed-access MTS model.
Limitations
- There are no public datasets or large-scale empirical experiments; the paper is theoretical. Consequently, practical inference latency, heterogeneous query prices, and constants hidden by O(·) are not measured.
- The analysis assumes bounded diameter D, costs reducible to f_t(i)∈[0,2D], an oblivious adversary, and full observation of the current task function. These assumptions may fail in adaptive or partially observed systems.
- The exploration schedule depends on OPT_{≤0}, which is unknown in practice; doubling guesses are available but add implementation overhead.
Future Work
Promising directions include unknown and time-varying D, adaptive adversaries, heterogeneous query costs, continuous metrics, and partial access to task functions. Empirical evaluations in caching, routing, and energy management are needed. Improving logarithmic factors for the k-switching guarantee and designing computation-aware exploration are also natural next steps.
AI Executive Summary
Modern online systems often maintain several machine-learning predictors, each specialized for a different workload. Running all of them at every step is expensive. This paper studies a stricter setting for Metrical Task Systems: only one heuristic may be queried per time step, and its movement cost cannot be inferred unless its state has been observed over consecutive steps. Full-feedback methods such as HEDGE therefore do not apply directly, while fixed-block bandit methods can suffer a large cost from a single poor exploration block.
Coşa and Eliáš propose a structured exploration–exploitation algorithm. HEDGE or SHARE maintains a distribution over predictors. Exploration samples one predictor and waits m steps until its state history makes the movement-inclusive cost observable. During this interval, the algorithm uses a greedy safe action rather than blindly following the sampled predictor. MTS-style Round rounding controls switching and preserves the desired predictor distribution. Lemma 3.1 reduces the resulting cost to a stable full-feedback expression.
Theorem 1.1 gives expected cost OPT_{≤0}+O(OPT_{≤0}^{2/3}) relative to the best fixed heuristic. Theorem 1.3 proves a nearly matching ~Ω(OPT_{≤0}^{2/3}) lower bound already for m=2, using a construction inspired by Dekel et al. For a benchmark switching k times, the regret becomes ~O(k^{1/3}OPT_{≤k}^{2/3}). There are no dataset experiments; the paper’s contribution is a sharp theoretical account of how delayed information and switching costs constrain predictor portfolios.
Deep Analysis
Background
MTS, introduced by Borodin et al., models online movement among metric states and includes caching, k-server, ski rental, and energy management. General MTS has deterministic ratio 2n−1 and randomized ratio Θ(log²n). Learning-augmented work uses predictions to improve typical instances; Blum and Burch showed that HEDGE can combine heuristics under full feedback. The unresolved issue is combining expensive predictors when only one can be queried.
Core Problem
For ℓ heuristics H_i with state s_t^i, define f_t(i)=c_t(s_t^i)+d(s_{t−1}^i,s_t^i). One heuristic may be queried per step. If it was not queried during the preceding m−1 required steps, the response is empty, so f_t(i) is not estimable. The goal is to approach OPT_{≤0}=min_iΣ_tf_t(i), or a benchmark that switches at most k times.
Innovation
First, exploration is an m-step dependent process rather than independent sampling. Second, the algorithm performs safe greedy actions during bootstrapping instead of following an unobserved heuristic. Third, MTS rounding controls transitions between sampled heuristics. Fourth, HEDGE stability compensates for non-unbiased delayed feedback. Finally, a Dekel et al.-inspired construction proves that the resulting OPT^{2/3} scale is essentially unavoidable.
Methodology
- �� Run HEDGE or SHARE over a predictor distribution x_t.
- �� Trigger exploration with probability ε and select e_t uniformly.
- �� Wait m steps, then observe f_t(e_t) and form g_t(i)=f_t(e_t)/(2D) only for i=e_t.
- �� During exploitation, sample according to x_t and use Round to control switching.
- �� When a predictor state is unavailable, choose argmin_s[d(b_t,s)+c_t(s)] from the last known state b_t.
- �� Set ε=(Dℓlnℓ)^{1/3}m^{-4/3}OPT_{≤0}^{-1/3}, with a matched HEDGE rate, and analyze the resulting movement and feedback errors.
Experiments
The paper reports no conventional datasets, training runs, or numerical benchmark tables because its claims are theorem-based. The analysis considers arbitrary bounded-diameter MTS instances, an oblivious adversary, and f_t(i)∈[0,2D]. Comparisons are theoretical: full-feedback HEDGE, Arora et al.’s O(μT^{2/3}) memory-bounded bandit framework, and the Dekel et al. lower bound for switching-cost bandits.
Results
Theorem 1.1 establishes E[ALG]≤OPT_{≤0}+O(OPT_{≤0}^{2/3}). Theorem 1.2 gives OPT_{≤k}+~O(k^{1/3}OPT_{≤k}^{2/3}) for k switches. Theorem 1.3 proves a ~Ω(OPT_{≤0}^{2/3}) lower bound at m=2, showing that the main loss comes from the delayed information structure, not from a loose analysis. The general upper bound scales as (Dkℓlnℓ)^{1/3}m^{2/3}.
Applications
Caching can use predictors specialized to different page-request patterns; routing and k-server systems can combine demand models; energy management can combine weather, load, and price forecasts. The method requires the current task function to be observable and assumes that exploration-induced movement is bounded. It is most attractive when predictor inference is expensive but task descriptions are cheap.
Limitations & Outlook
The guarantees rely on bounded diameter, bounded normalized costs, full current-task access, and an oblivious adversary. Real systems introduce model latency, memory limits, heterogeneous query prices, and nonstationary predictors, none of which are empirically evaluated. Future work should address adaptive adversaries, unknown parameters, continuous state spaces, partial observability, and practical constants.
Plain Language Accessible to non-experts
Imagine a factory with several consultants. Each consultant is excellent for a different kind of order, but you can call only one consultant per minute. Their advice also determines where machines must move, and moving machines costs money. If you did not call the same consultant in the previous minute, you cannot tell how much movement their plan required.
The paper proposes a trial-and-production system. Most of the time, the factory follows the consultant currently believed to be best. Occasionally, it tests another consultant for several consecutive minutes, long enough to reconstruct the hidden movement cost. During the test, it does not blindly follow the new plan; it chooses the cheapest safe move from the last known machine position.
As the factory handles more orders, the extra cost is roughly the two-thirds power of the cost paid by the best consultant. This is important because the authors prove that no general strategy can remove this scale: the factory is genuinely working with incomplete information while switching itself is costly.
ELI14 Explained like you're 14
Picture a video game with several strategy bots. One bot is great at boss fights, another at collecting items, and another at saving coins. Each turn you may ask only one bot for advice. Worse, a bot’s plan includes moving your character, and you cannot know that movement cost unless you asked the same bot during nearby turns.
The paper’s algorithm works like smart scouting. Most turns, it follows the bot that currently looks strongest. Sometimes it spends several turns checking one bot so that its hidden movement cost becomes visible. While checking, it chooses a safe action from its last known position instead of blindly obeying incomplete advice. Then it updates the ranking of the bots.
Why not ask everyone every turn? That could be too expensive. Why not trust one bot for a huge block? One bad choice could waste the whole block. The algorithm balances both problems using HEDGE, a classic “weights for advisers” method, plus a special rule for controlling movement.
The result says that if the best bot spends OPT, the algorithm loses only about OPT to the two-thirds power extra. Even more interesting, the authors prove that smarter algorithms cannot always beat roughly the same amount. The limit comes from missing information, not from careless programming!
Glossary
Metrical Task System (MTS)
An online model where an algorithm chooses states, pays task costs, and pays metric distances when moving. It unifies problems such as caching and k-server.
The paper’s underlying decision framework.
m-delayed bandit access
Only one heuristic can be queried per step, and consecutive queries are required before its state and movement cost become observable. It is the paper’s feedback model.
Defines the information restriction.
HEDGE
An exponentially weighted expert-advice algorithm that favors predictors with low cumulative loss. Here it maintains the distribution used for exploitation.
The internal full-feedback learner.
Regret
The algorithm’s expected cost minus a benchmark cost. The paper measures regret relative to the best fixed or k-switching heuristic.
Primary performance metric.
Improper action
An MTS action not currently recommended by any predictor. Such actions can be safer when queried predictor states are unavailable.
Used during delayed exploration and bootstrapping.
Oblivious adversary
An adversary that fixes the instance and heuristic trajectories before seeing the algorithm’s random bits. This is the adversary model for the guarantees.
Assumption in the theoretical analysis.
Open Questions Unanswered questions from this research
- 1 Predictor queries may have different prices and latencies in practice. A unified theory balancing query budgets, movement costs, and regret remains open.
- 2 The oblivious-adversary assumption is restrictive. It is unclear whether comparable bounds hold when an adversary observes the algorithm’s behavior and adapts.
- 3 No experiments quantify constants across cache sizes, predictor quality, or nonstationary workloads; empirical validation is needed.
Applications
Immediate Applications
Multi-model caching
A cache can treat specialized request predictors as heuristics and query only one per time step. The method is suitable when model inference is expensive but the current request is directly observable, offering performance close to the best predictor without running all models.
Energy and routing control
Load, weather, price, or traffic models can each propose a control policy. The system mostly follows the leading policy, periodically tests alternatives, and uses safe greedy actions while predictor states are unavailable.
Long-term Vision
Autonomous predictor portfolios
A platform could maintain many specialized predictors and dynamically allocate queries according to observed performance. Major obstacles include adaptive environments, unequal inference costs, continuous state spaces, and translating asymptotic guarantees into operational service-level metrics.
Abstract
We consider the following problem: We are given $\ell$ heuristics for Metrical Task Systems (MTS), where each might be tailored to a different type of input instances. While processing an input instance received online, we are allowed to query the action of only one of the heuristics at each time step. Our goal is to achieve performance comparable to the best of the given heuristics. The main difficulty of our setting comes from the fact that the cost paid by a heuristic at time $t$ cannot be estimated unless the same heuristic was also queried at time $t-1$. This is related to Bandit Learning against memory bounded adversaries (Arora et al., 2012). We show how to achieve regret of $O(\text{OPT}^{2/3})$ and prove a tight lower bound based on the construction of Dekel et al. (2013).