Research map / Bandits and online learning / Online convex optimization and games

Learning-Augmented Algorithms for MTS with Bandit Access to Multiple Predictors

ICML 2025 · Bandits and online learning › Online convex optimization and games · approach: Online allocation with constraints · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Studies combining ℓ MTS heuristics when only one heuristic can be queried per step (m-delayed bandit access), giving an algorithm with regret O(OPT^{2/3}) and a matching lower bound.

Problem

Online combination of multiple heuristics for Metrical Task Systems under bandit-style access, where a heuristic's movement cost is only observable after querying it for several consecutive steps (bootstrapping delay m).

Approach

Exploration-exploitation scheme with m-step exploration blocks, improper greedy steps from last known state, and MTS-style rounding of a Hedge/Share distribution over heuristics; a matching lower bound adapts bandits-with-switching-costs construction to MTS.

Key results

• Algorithm achieves E[ALG] ≤ OPT + O((Dlℓ ln ℓ)^{1/3} m^{2/3} OPT^{2/3}) under m-delayed bandit access.
• Matching lower bound: any algorithm with 2-delayed bandit access suffers regret Ω̃(OPT^{2/3}) on some instance.
• Extension against benchmark with at most k switches gives regret Õ(k^{1/3} OPT^{2/3}) and matching lower bound Ω̃((kℓ)^{1/3} T^{2/3}).

Surprising findings

• Improper steps (states not suggested by any heuristic) are necessary to achieve regret in terms of OPT even for m=2.

Limitations

• Requires diameter D, number of heuristics ℓ and bootstrapping m to be constant or known; regret bounds hold when D·ℓ·m is small relative to OPT^{1/3}.
• Lower bound and upper bound differ by a logarithmic factor in the k-switch setting.

Experimental setup

Metrics: expected pseudoregret competitive ratio

Baselines: Full-feedback Hedge combination Block-based MAB switching (Arora et al. style)

Builds on: Hedge Share Bandit learning against memory-bounded adversaries Bandits with switching costs

Closest papers by meaning

• Mixing Predictions for Online Metric Algorithms (ICML 2023 · similarity 0.88)
• Adaptive Regret for Bandits Made Possible: Two Queries Suffice (ICLR 2024 · similarity 0.86)
• No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization (ICML 2025 · similarity 0.86)
• Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints (NeurIPS 2024 · similarity 0.86)
• Managing Self-Learning Experts under Per-Round Budget Constraints (NeurIPS 2026 · similarity 0.85)
• Improved Bayes Regret Bounds for Multi-Task Hierarchical Bayesian Bandit Algorithms (NeurIPS 2024 · similarity 0.85)