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

Publication

Proceedings of Machine Learning Research 267 (ICML 2025), pp. 11357–11378

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(\operatorname{OPT}^{2/3})$ and prove a tight lower bound based on the construction of Dekel et al. 2013.

1 Introduction

Metrical Task Systems (MTS) (Borodin et al. 1992) are a very broad class of online problems capable of modeling problems arising in computing, production systems, power management, and routing service vehicles. In fact, many fundamental problems in the field of Online Algorithms including Caching, $k$-server, Ski-rental, and Convex Body Chasing are special cases of MTS. Metrical Task Systems are also related to Online Learning from Expert Advice, see (Blum & Burch 2000) for the comparison of the two problems.

In MTS, we are given a description of a metric space $(M,d)$ and a starting point $s_{0}\in M$ beforehand. The points in $M$ are traditionally called states and, depending on the setting, they can represent actions, investment strategies, or configurations of some complex system. At each time step $t=1,\dotsc,T$, we receive a cost function $c_{t}\colon M\to\mathbb{R}_{+}\cup\{0,+\infty\}$. Seeing $c_{t}$, we can decide to stay in our previous state $s_{t-1}$ and pay its cost $c_{t}(s_{t-1})$, or move to some (possibly cheaper) state $s_{t}$ and pay $c_{t}(s_{t})+d(s_{t-1},s_{t})$, where the distance function $d$ represents the transition cost between two states. Our objective is to minimize the total cost paid over time.

MTS is very hard in the worst case. This is due to its online nature ($s_{t}$ has to be chosen without knowledge of $c_{t+1},\dotsc,c_{T}$) and also due to its generality. The performance of algorithms is evaluated using the competitive ratio which is, roughly speaking, the ratio between the algorithm’s cost and the cost of the optimal solution computed offline. Denoting $n$ the number of points in the metric space $M$, the best competitive ratio achievable for MTS is $2n-1$ and $\Theta(\log^{2}n)$ in the case of deterministic and randomized algorithms, respectively Borodin et al. 1992; Bartal et al. 2006; Bubeck et al. 2022a; Bubeck et al. 2019. Note that $n$ is usually very large or even infinite (e.g., $M=\mathbb{R}^{d}$).

This worst-case hardness motivates the study of MTS and its special cases in the context of Learning-Augmented Algorithms (Lykouris & Vassilvitskii 2021). Here, the algorithm can use predictions produced by an ML model in order to exploit specific properties of input instances. By augmenting the algorithm with the ML model, we obtain a heuristic with an outstanding performance, well beyond the classical worst-case lower bounds, on all inputs where the ML model performs well. One of the key techniques used in this context is Combining Heuristics which is used to achieve robustness (Lykouris & Vassilvitskii 2021; Wei 2020; Antoniadis et al. 2023b), adjust hyperparameters Antoniadis et al. 2021, and recognize the most suitable heuristic for the current input instance (Emek et al. 2021; Anand et al. 2022; Antoniadis et al. 2023a).

Combining heuristics.

In this basic theoretical problem, we are given $\ell$ heuristics $H_{1},\dotsc,H_{\ell}$ which can be simulated on the input instance received online. We want to combine them into a single algorithm which achieves a cost comparable to the best of the heuristics on each individual instance. The difficulty of the combination problem is given by the online setting: because we receive the input online, we cannot tell beforehand which heuristic is going to perform better. Moreover, steps performed while following a wrong heuristic cannot be revoked.

We can combine a heuristic deploying an ML prediction model with a classical online algorithm in order to obtain a new algorithm that satisfies worst-case guarantees regardless of the performance of the ML model (this property is called robustness). Similarly, we can use it to deploy a portfolio of very specialized ML models in a broader setting, where each model corresponds to a separate heuristic. The combination technique ensures that we achieve very good performance whenever at least one of the models performs well on the current input instance.

Full-feedback setting.

Most of the previous works on Combining Heuristics query the state of each heuristic at each time step, observe their costs, and choose between their states, see (Wei 2020; Antoniadis et al. 2023b; Blum & Burch 2000; Fiat et al. 1991). We call this the full-feedback setting and, indeed, methods from Online Learning in the full-feedback setting can be directly integrated in the combination algorithms. For example, Blum & Burch 2000 showed that by choosing between heuristics using the HEDGE algorithm (Freund & Schapire 1997) with a well-chosen learning rate we can be $(1+\epsilon)$-competitive with respect to the best heuristic.1

Bandit-feedback setting.

In this paper, we consider what can be seen as a bandit-feedback setting of Combining Heuristics. At each time step, we are allowed to query the current state of only one heuristic. This setting allows us to study the impact of restricting information about the heuristics on our ability to combine them effectively. Further motivation is the fact that querying all the heuristics is costly, especially if they utilize some heavy-weight prediction models. This issue was already considered by Emek et al. 2021 and Antoniadis et al. 2023a whose works inspired our study. Note that the combination algorithm retains full access to the input instance. This is required by any positive result for general MTS, since the cost functions $c_{t}$ usually do not satisfy any natural properties such as Lipschitzness or convexity; see further discussion in Section 2. Moreover, $c_{t}$ is often easy to encode. For example, in Caching, $c_{t}$ is fully determined by the page requested at time $t$.

In contrast to the full-feedback setting, classical learning methods cannot be directly integrated in combination algorithms operating in the bandit setting. The main reason is that the state $s_{t}^{i}$ of the heuristic $H_{i}$ is not enough to estimate its cost at time $t$: the cost paid by $H_{i}$ at time $t$ is $c_{t}(s_{t}^{i})+d(s_{t-1}^{i},s_{t}^{i})$, i.e., we cannot calculate this cost2 unless we have queried $H_{i}$ in both time steps $t-1$ and $t$. We also consider the case where each heuristic needs to be bootstrapped for $m-2\geq 0$ time steps before we can see its state. This way, to receive the state of $H_{i}$ in time steps $t-1$ and $t$, and to be able to calculate its cost at time $t$, we have to query $H_{i}$ in the $m$ time steps $t-m+1,\dotsc,t$.

A similar phenomenon occurs in the setting of Online Learning against Memory-Bounded Adversaries (Arora et al. 2012), which is our main theoretical motivation for considering non-zero bootsrapping time (i.e., $m>2$). There, one needs to play an action $a$ at least $m$ times in a row to see the loss of the reference policy which plays $a$ at each time step. The algorithm of Arora et al. 2012 splits the time horizon into blocks of length larger than $m$. In the block $i$, they keep playing the same action $a_{i}$ which allows them to observe the loss of the corresponding reference policy after the first $m$ time steps in the block. However, this does not work in our setting. The adversary can set up the MTS instance in such a way that $c_{t}\neq 0$ and the heuristics move only on the boundaries of the blocks, so that the algorithm would not observe the cost of any heuristic. This way, the algorithm cannot be competitive with respect to the best heuristic.

A different bandit-like setting for Combining Heuristics for MTS was proposed by Antoniadis et al. 2023a. In their setting, the queried predictor reports both its state and the declared moving cost incurred at time $t$. We discuss their contribution in Section 1.2. Their $(1+\epsilon)$-competitive algorithm and absence of lower bounds motivated us to study regret bounds which can provide more refined guarantees when the competitive ratio is close to 1. However, we have decided to pursue these bounds in the more natural setting where the moving costs are not reported as it does not rely on the honesty of the predictors.3 Since our algorithms use a subset of information available in the setting of Antoniadis et al. 2023a, our upper bounds also apply to their setting.

1.1 Our Results

For $m\geq 2$, we say that an algorithm $\operatorname{ALG}$ has $m$-delayed bandit access to heuristics $H_{1},\dotsc,H_{\ell}$ if (i) it can query at most one heuristic $H_{i}$ at each time step $t$ and (ii) the query yields the current state of $H_{i}$ only if $H_{i}$ was queried also in steps $t\!-\!m\!+\!2,\dotsc,t$, otherwise it yields an empty result.

Our main result is an algorithm with the following regret.

Theorem 1.1. Let $D$, $\ell$, and $m\geq 2$ be constant. Consider heuristics $H_{1},\dotsc,H_{\ell}$ for an MTS with diameter $D$. There is an algorithm $\operatorname{ALG}$ which, given an $m$-delayed bandit access to $H_{1},\dotsc,H_{\ell}$, satisfies the following guarantee. The expected cost of $\operatorname{ALG}$ on any input $I$ is

where $\operatorname{OPT}_{\leq 0}=\min_{i=1}^{\ell}H(I)$ denotes the cost of the best heuristic on input $I$.

We prove this result in Section 3, where we state explicitly the dependence on $D$, $m$, and $\ell$ in the case when they are larger than a constant. We can interpret our result in terms of the competitive ratio. Since the regret term in Theorem 1.1 is sublinear in $\operatorname{OPT}_{\leq 0}$, the expected cost of our algorithm is at most $\mathbb{E}[\operatorname{ALG}]\leq(1+o(1))\operatorname{OPT}_{\leq 0}$. In other words, its competitive ratio with respect to the best of the $\ell$ heuristics converges to $1$. Therefore, our algorithm can be used for robustification. If we include a classical online algorithm which is $\rho$-competitive in the worst case among $H_{1},\dotsc,H_{\ell}$, our algorithm will never be worse than $(1+o(1))\rho$-competitive. However, on input instances where some of the heuristics incur a very low cost, the algorithm can match their performance asymptotically. For example, if the cost of the best heuristic is only 1.01 times higher than the offline optimum, our algorithm’s cost will be only $(1+o(1))\cdot 1.01$ times the offline optimum.

Our algorithm alternates between exploitation and exploration, as in the classical approach for the Multi-Armed Bandit (MAB) setting, see e.g. (Slivkins 2019). However, each exploration phase takes $m$ time steps and we are unable to build an unbiased estimator of the loss vectors. Moreover, our algorithm sometimes needs to take improper steps, i.e., going to a state which is not suggested by any of the predictors. This is clearly necessary with $m>2$, since we may receive empty answers to our queries. Such improper steps are crucial for achieving regret in terms of $\operatorname{OPT}_{\leq 0}$ even for $m=2$.

In Section 6, we show that our algorithm can be adapted to the $m$-memory bounded setting for bandits, where it achieves a regret of $O(T^{2/3})$ comparable to Arora et al. 2012, while slightly improving the dependence on $m$. Note that $T$ can be much larger than $\operatorname{OPT}_{\leq 0}$.

We extend our result to a setting with a benchmark which can switch between the heuristics at most $k$ times, while the algorithm’s number of switches still remains unrestricted.

Theorem 1.2. Let $D$, $\ell$, and $m\geq 2$ be constant and $k\geq 1$ be a parameter. Consider heuristics $H_{1},\dotsc,H_{\ell}$ for an MTS with diameter $D$. There is an algorithm $\operatorname{ALG}$ which, given an $m$-delayed bandit access to $H_{1},\dotsc,H_{\ell}$, satisfies the following guarantee. The cost of $\operatorname{ALG}$ on input $I$ with offline optimum cost at least $2k$ is

where $\operatorname{OPT}_{\leq k}$ denotes the cost of the best combination of heuristics in hindsight that switches between heuristics at most $k$ times on input $I$.

Again, we can interpret this regret bound as a competitive ratio converging to 1. In Section 5, we show that the competitive ratio of our algorithm is below $(1+\epsilon)$ for $k$ as large as $\tilde{\Omega}(\epsilon^{3}\operatorname{OPT}_{\leq k})$ which is worse by a log-factor than the result of Antoniadis et al. 2023a in their easier setting.

In Section 4, we show that our upper bound in Theorem 1.1 is tight up to a logarithmic factor even with 0 bootstrapping time ($m=2$). Our result is based on the construction of Dekel et al. 2013 for Bandits with Switching Costs. Their lower bound cannot be applied directly, since algorithms in our setting have an advantage in being able to take improper actions and having one-step look-ahead. Both of these advantages come from the nature of MTS and are indispensable in our setting, see Section 2.

Theorem 1.3. For any algorithm $\operatorname{ALG}$ with $2$-delayed bandit access to $\ell$ predictors, there is an input instance $I$ such that the expected cost of $\operatorname{ALG}$ is

where $\operatorname{OPT}_{\leq 0}=\min_{i=1}^{\ell}H(I)$ denotes the cost of the best heuristic on input $I$.

In Section 4.1, we also show that the dependence on $D,\ell$ and $k$ in our bounds is (almost) optimal. In particular, our regret bound in Theorem 1.1 scales with $(Dk\ell\ln\ell)^{1/3}m^{2/3}$ and we show that this dependence needs to be at least $(Dk\ell)^{1/3}$ with $m=2$.

1.2 Related Work

Arora et al. 2012 introduced the problem of Bandit Learning against Memory-Bounded Adversaries. Here, the loss functions depend on the last $\mu+1$ actions taken by the algorithm. This setting captures, for example, Bandits with Switching Costs (Cesa-Bianchi et al. 2013; Amir et al. 2022; Rouyer et al. 2021). They propose an elegant algorithm with regret $O(\mu T^{2/3})$ that partitions the time horizon into blocks of equal size and let a classical online learning algorithm (e.g., EXP3) play over the losses aggregated in each block. Their result was shown to be tight by Dekel et al. 2013 who provided a sophisticated lower bound construction showing that any algorithm suffers regret at least $\tilde{\Omega}(T^{2/3})$ already for $\mu=1$. Our results are also related to Non-Stationary Bandits and Dynamic Regret (Auer et al. 2002, Section 8).

Antoniadis et al. 2023a studied dynamic combination of heuristics for MTS. By reducing to the Layered Graph Traversal problem (Bubeck et al. 2022b), they achieved a competitive ratio $O(\ell^{2})$ with respect to the best dynamic combination of $\ell$ heuristics. Then, they focused on the scenario where the input instance is partitioned into $k$ intervals and a different heuristic excels in each of the intervals. They provided bounds on how big $k$ can be to make $(1+\epsilon)$-competitive algorithms possible. Finally, they also studied this question in the bandit-like setting which is strictly easier compared to ours.

First works on Combining Heuristics were by Fiat et al. 1990 for $k$-server, Fiat et al. 1991 for Caching, and Azar et al. 1993; Blum & Burch 2000 for MTS. More recently, Emek et al. 2021 studied Caching with multiple predictors and achieved regret sublinear in $T$, while also tackling a bandit-like setting. Further results on other online problems are by Anand et al. 2022; Dinitz et al. 2022; Bhaskara et al. 2020; Gollapudi & Panigrahi 2019; Almanza et al. 2021; Wang et al. 2020; Kevi & Nguyen 2023.

Learning-augmented algorithms were introduced by Lykouris & Vassilvitskii 2021; Kraska et al. 2018 who designed algorithms effectively utilizing unreliable machine-learned predictions. Since these two seminal works, many computational problems were studied in this setting, including Caching (Rohatgi 2020; Wei 2020), Scheduling (Lindermayr & Megow 2022; Benomar & Perchet 2024b; Balkanski et al. 2023; Bamas et al. 2020), graph problems (Eberle et al. 2022; Bernardini et al. 2022; Dong et al. 2025; Davies et al. 2023) and others. Several works consider algorithms using the predictions sparingly (Im et al. 2022; Drygala et al. 2023; Sadek & Eliáš 2024; Benomar & Perchet 2024a). See the survey (Mitzenmacher & Vassilvitskii 2022) and the website by (Lindermayr & Megow 2023).

Metrical Task Systems were introduced by Borodin et al. 1992 who gave a tight competitive ratio of $2n-1$ for deterministic algorithms ($n$ is the number of states). The best competitive ratio for general MTS is $\Theta(\log^{2}n)$ by Bubeck et al. 2019 and Bubeck et al. 2022a.

2 Notation and Preliminaries

We consider MTS instances with a bounded diameter and denote $D=\max_{s,s^{\prime}\in M}d(s,s^{\prime})$ the diameter of the underlying metric space. For example, $D$ in caching is equal to the size of the cache. At each time step, the algorithm receives the cost function $c_{t}$ first, and then it chooses its new state $s_{t}$, i.e. there is a 1-step look-ahead. This is standard in MTS definition and it is necessary for existence of any competitive algorithm, since $c_{t}$ is potentially unbounded, see (Blum & Burch 2000, Section 2.3). We denote $\Delta^{d}$ the $d$-dimensional probability simplex, and $[d]=\{1,\dotsc,d\}$.

m-delayed bandit access to heuristics.

Given $\ell$ heuristics $H_{1},\dotsc,H_{\ell}$, we denote $s_{t}^{i}$ the state of $H_{i}$ at time $t$ and $f_{t}(i)=c_{t}(s_{t}^{i})+d(s_{t-1}^{i},s_{t}^{i})$ the cost incurred by $H_{i}$ at time $t$. Let $m\geq 2$ be a parameter. At each time $t$, the algorithm is allowed to query a single heuristic $H_{i}$. If $H_{i}$ was also queried in time steps $t-m+2,\dotsc,t$, the result of the query is the state $s_{t}^{i}$. Otherwise, the result is empty. While the access to the states of the heuristics is restricted, the algorithm has full access to the input instance which is not related to acquiring costly predictive information. Moreover, the input instance can be often described in a very compact way. For example, $c_{t}$ in Caching is completely determined by the page requested at time $t$. Access to the input instance is necessary because the cost functions are not required to satisfy any natural assumptions (like boundedness, Lipschitzness, convexity). For example, if the queried heuristic reports a state $s$ with $c_{t}(s)=+\infty$, the algorithm needs to know $c_{t}$ in order to choose a different state and avoid paying the infinite cost. Note that a similar situation can easily happen in Caching, $k$-server, Convex Body Chasing, or Convex Function Chasing.

We assume that $f_{t}(i)\in[0,2D]$. This is without loss of generality for the following reason. First, we can assume that at each time $t$ there is a state with zero cost, since subtracting $\min_{s}c_{t}(s)$ from the cost of each state affects the cost of any algorithm (including the offline optimum) equally. Second, any predictor can be post-processed so that, in each time step where its cost is higher than $2D$, it serves the request in the state with 0 cost and returns to the predicted state, paying at most $2D$ for the movement.

Benchmarks and performance metrics.

Let $\operatorname{OPT}_{\leq 0}=\min_{i=1}^{\ell}\sum_{t=1}^{T}f_{t}(i)$ be the static optimum, i.e., the cost of the best heuristic. For $k>0$, we define

where the minimum is taken over all solutions $i_{1},\dotsc,i_{T}$ such that the number of steps where $i_{t-1}\neq i_{t}$ is at most $k$.

We evaluate the performance of our algorithms using expected pseudoregret regret (further abbreviated as regret). For $k\geq 0$, we define

where $\operatorname{ALG}$ denotes the cost incurred by the algorithm on the given input instance with access to the given heuristics. We assume that the adversary is oblivious and has to fix the MTS input instance and the solutions of the heuristics before seeing the random bits of the algorithm. We say that an algorithm is $\rho$-competitive with respect to an offline algorithm $\operatorname{OFF}$, if $\mathbb{E}[\operatorname{ALG}]\leq\rho\operatorname{OFF}+\alpha$ holds on every input instances, where $\alpha$ is a constant independent on the input instance and we use $\operatorname{OFF}$ to denote both the algorithm and its cost. If $\operatorname{OFF}$ is an offline optimal algorithm, we call $\rho$ the competitive ratio of $\operatorname{ALG}$.

Rounding fractional algorithms.

A fractional algorithm for MTS is an algorithm which, at each time $t$, produces a distribution $p_{t}\in\Delta^{M}$ over the states in $M$. These distributions do not yet say much about the movement costs of the algorithm. But there is a standard way to turn such a fractional algorithm into a randomized algorithm for MTS.

Proposition 2.1. There is an online randomized algorithm for MTS which, receiving online a sequence of distributions $p_{1},\dotsc,p_{T}\in\Delta^{M}$, produces a solution $s_{1},\dotsc,s_{T}\in M$ with expected cost equal to

where $\operatorname{EMD}$ denotes the Earth mover distance with respect to the metric space $M$.

We include the proof of this standard fact in Appendix B together with the following, very similar, proposition, where we overestimated the cost of switching between the states of two heuristics by $D$.

Proposition 2.2. There is an online randomized algorithm which, receiving online a sequence of distributions $x_{1},\dotsc,x_{T}\in\Delta^{\ell}$ over the heuristics, queries at each time $t$ a heuristic $i_{t}$ with probability $x_{t}(i_{t})$ such that

Basic learning algorithms.

We use the classical algorithms for online learning with expert advice HEDGE (Freund & Schapire 1997) and SHARE (Herbster & Warmuth 1998). Both satisfy the following property with $\eta$ being their learning rate. For both of them, the proof is contained in (Blum & Burch 2000), we discuss more details, as well as the learning dynamics in Appendix C.

Property 2.3. There is a parameter $\eta$ such that the following holds. Denoting $x_{t-1}$ and $x_{t}$ the solutions of the algorithm before and after receiving loss vector $g_{t-1}$, we have

We use the bounds for HEDGE tuned for “small losses”, see (Cesa-Bianchi & Lugosi 2006).

Proposition 2.4. Consider $x_{1},\dotsc,x_{T}\in\Delta^{\ell}$ the solution produced by HEDGE with learning rate $\eta$ and denote $\gamma:=1-\exp(-\eta)$. For any $x^{*}\in\Delta^{\ell}$, we have

3 Algorithm for m-Delayed Bandit Access to Heuristics

3.1 Basic Approach and Comparison to Previous Works

Arora et al. 2012 use the following approach to limit the number of switches between arms (or heuristics): split the time horizon into blocks of length $\tau$ and use some MAB algorithm to choose a single arm (or heuristic) for each block which is then played during the whole block. The number of switches is then at most $T/\tau$. This is a common approach to reduce the number of switches, see (Rouyer et al. 2021; Amir et al. 2022; Blum & Mansour 2007). However, this approach does not lead to regret sublinear in $\operatorname{OPT}_{\leq 0}$ which can be much smaller than $T$. In order to have the number of switches $T/\tau\leq o(\operatorname{OPT}_{\leq 0})$, we have to choose $\tau=\omega(T/\operatorname{OPT}_{\leq 0})$ which can be $\omega(\operatorname{OPT}_{\leq 0})$ for small $\operatorname{OPT}_{\leq 0}$. However, with blocks so large, already a single exploration of some arbitrarily bad heuristic would induce a cost of order $\tau\geq\omega(\operatorname{OPT}_{\leq 0})$.

In turn, our algorithm is more similar to the classical MAB algorithm alternating exploration and exploitation steps, see (Slivkins 2019). However, there are three key differences and each of them is necessary to achieve our performance guarantees:

• • Our algorithm makes improper steps (i.e., steps not taken by any of the heuristics);
• • We use MTS-style rounding to ensure bounded switching cost instead of independent random choice at each time step;
• • Exploration steps are not sampled independently since our setting requires $m\geq 2$.

In particular, the last difference leads to more involving analysis. This is because we cannot assume that we have an unbiased estimator of the loss vector and consequently need to do extensive conditioning on past events. Moreover, the cost of only one of the time steps during each exploration phase can be directly charged to the expected loss of the internal full-feedback algorithm. We need to exploit the stability property of the internal full-feedback algorithm in order to relate the costs incurred during the steps of each exploration block.

During each exploitation step $t$, our algorithm follows the advice of the exploited heuristic which is sampled from the algorithm’s internal distribution $x_{t}$ over the heuristics. Each exploration step $t$ is set up so that the algorithm discovers the cost of the heuristic $H_{e_{t}}$ chosen uniformly at random and updates its distribution over the heuristics. However, the algorithm does not follow $H_{e_{t}}$. Instead, it makes a greedy step from the last known state of the exploited heuristic.

3.2 Description

Let $\bar{A}$ be an algorithm for the classical learning from expert advice in full feedback setting (e.g. HEDGE or SHARE), and $\epsilon$ be a parameter controlling our exploration rate. For each time step $t=1,\dotsc,T$, we sample $\beta_{t}\in\{0,1\}$ such that $\beta_{t}=1$ with probability $\epsilon$ and $e_{t}$ is chosen uniformly at random from $\{1,\dotsc,\ell\}$. We set $\beta_{0}=0$ since the algorithm starts querying predictors from $t=1$. Moreover, we assume all heuristics reside in $s_{0}$ at $t=0$. If $t$ is an exploitation step ($t\in X$) and $\beta_{t}=0$, the next step will be again exploitation. Otherwise, the algorithm skips $m$ time steps which are needed to bootstrap the explored heuristic $H_{e_{t+m}}$ and performs exploration in step $t+m$. At this latter step, the algorithm receives the cost $f_{t+m}(e_{t+m})$ of $H_{e_{t+m}}$ and uses it to update its distribution $x_{t+m+1}$ over the heuristics. This update is performed using the algorithm $\bar{A}$ receiving as input a loss vector $g_{t+m}^{e_{t+m}}$ defined as follows: $g_{t+m}^{e_{t+m}}(i)=f_{t+m}(e_{t+m})/2D$ if $i=e_{t+m}$ and 0 otherwise. Thanks to the assumption that $f_{t+m}\in[0,2D]^{\ell}$, we have $g_{t+m}\in[0,1]^{\ell}$. Each exploration step is followed by an exploitation step. See the summary of this learning dynamics in Algorithm 1. With $m=1$, up to the scaling of the loss function, this dynamics would correspond to the classical algorithm for MAB which performs exploration with probability $\epsilon$ and achieves regret $O(T^{2/3})$ (Slivkins 2019). Note that our setting requires $m\geq 2$.

Algorithm 1 Learning dynamics

1. Initialization:
2. $\beta_{0}:=0$, $t:=0$, $X:=\emptyset$, $E:=\emptyset$
3. $\beta_{1},\dotsc,\beta_{T}\sim\text{Bernoulli}(\epsilon)$
4. $e_{1},\dotsc,e_{T}\sim U(\{1,\dotsc,\ell\})$
5. $x_{0}$ is chosen by $\bar{A}$
7. while $t\leq T$ do
8. add $t$ to $X$
9. // Exploitation step
10. if $\beta_{t}=1$ then
11. $t:=t+m$
12. // Skip $m$ steps
13. add $t$ to $E$
14. // Exploration step
15. $x_{t+1}$ chosen by $\bar{A}$ after feedback $g_{t}^{e_{t}}$
16. $t++$

Now, it is enough to describe how to turn the steps of Algorithm 1 into a solution for the original MTS instance. First, we define $x_{t+1}=x_{t}$ for any $t\notin E$. At $t=1$, we sample the exploited heuristic from the distribution $x_{1}$ and at each update of $x_{t}$, we switch to a different heuristic with probability $\frac{1}{2}\lVert x_{t-1}-x_{t}\rVert_{1}$ using the procedure Round from Proposition 2.2 in order to ensure that, at each time step $t$, we are following heuristic $i$ with probability $x_{t}(i)$. The state of the exploited heuristic is not known to us $m$ steps before each exploitation step and another $m$ steps after. During these time steps, we make greedy steps from the last known state $s_{t^{\prime}}^{i_{t^{\prime}}}$ of the heuristic $H_{i_{t^{\prime}}}$ exploited at time $t^{\prime}$. Namely, we choose $s_{t}:=\arg\min_{s\in M}(d(s_{t^{\prime}}^{i_{t^{\prime}}},s)+c_{t}(s))$. This procedure is summarized in Algorithm 2.

Algorithm 2 Producing solution for MTS

1. Input: $x_{0},\dotsc,x_{T}$ produced by Algorithm 1
2. $i_{0}\sim U(\{1,\dots,\ell\})$
3. for $t=1,\dotsc,T$ do
4. if $x_{t}\neq x_{t-1}$ then $i_{t}\!\sim\!\text{ Round$(i_{t-1},x_{t-1},x_{t})$}$
5. else $i_{t}:=i_{t-1}$
6. if $s_{t}^{i_{t}}$ is known then
7. go to state $s_{t}:=s_{t}^{i_{t}}$ and set $b_{t}:=s_{t}$
8. else /* $m$ states before and after exploration */
9. set $b_{t}:=b_{t-1}\quad$ /* last successful query */
10. $s_{t}:=\arg\min_{s\in M}(d(b_{t},s)+c_{t}(s))$

Lemma 3.1. Given $x_{1},\dotsc,x_{T}\in[0,1]^{\ell}$ produced by Algorithm 1, the expected cost of Algorithm 2 is at most

A similar statement is proved in (Antoniadis et al. 2023a). We include our proof in Appendix A.

Choice of hyperparameters.

To achieve the regret bound in Theorem 3.9, we choose the parameter $\epsilon:=(D\ell\ln{\ell})^{1/3}m^{-4/3}\operatorname{OPT}_{\leq 0}^{-1/3}$ for Algorithm 1 and the learning rate $\eta$ of HEDGE which is used as $\bar{A}$ is chosen based on $\gamma:=(D\ell\ln{\ell})^{1/3}m^{2/3}\operatorname{OPT}_{\leq 0}^{-1/3}$, where $\gamma=1-\exp(-\eta)$. While $D,\ell,m$ are usually known from the problem description, $\operatorname{OPT}_{\leq 0}$ can be guessed by doubling as described in Appendix D.

3.3 Analysis

We introduce the following random variables which will be useful in our analysis. We define $X_{t}$ as an indicator variable such that $X_{t}=1$ if $t\in X$ and 0 otherwise. Similarly, $E_{t}$ is an indicator of $t\in E$. These variables are determined by $\beta_{1},\dotsc,\beta_{T}$. We also define $g_{t}=E_{t}\cdot g_{t}^{e_{t}}$ which is 0 for any $t\notin E$. We consider a filtration $\mathcal{F}_{0}\subseteq\mathcal{F}_{1}\subseteq\dotsb\subseteq\mathcal{F}_{T}$, where $\mathcal{F}_{t}$ is a $\sigma$-algebra generated by the realizations of $\beta_{1},\dotsc,\beta_{t}$ and $e_{1},\dotsc,e_{t}$. Note that these realizations determine $X_{t^{\prime}},E_{t^{\prime}},g_{t^{\prime}}$, and $x_{t^{\prime}+1}$ for any $t^{\prime}\leq t$. Moreover, we have the following observations.

Observation 3.2. For any $t=0,\dotsc,T-m$, we have $E_{t+m}=\beta_{t}X_{t}$.

This is because $t+m\in E$ if and only if $t\in X$ and $\beta_{t}=1$.

Observation 3.3. For any $i=1,\dotsc,m$ and $t=0,\dotsc,T-i$, we have $X_{t+i}\geq\prod_{j=0}^{i-1}(1-\beta_{t+j})X_{t}$.

This holds because if $X_{t}=1$ and $\beta_{t}=\dotsb=\beta_{t+i-1}=0$, then also $X_{t+i}=1$.

Observation 3.4. For $i=1,\dotsc,m$ and $t=i,\dotsc,T$, we have $\mathbb{E}[g_{t}\mid\mathcal{F}_{t-i}]=E_{t}f_{t}/(2D\ell)$.

This follows from $\mathbb{E}[g_{t}\mid\mathcal{F}_{t-i}]=\mathbb{E}[E_{t}g_{t}^{e_{t}}\mid\mathcal{F}_{t-i}]=\mathbb{E}[\beta_{t-m}X_{t-m}g_{t}^{e_{t}}\mid\mathcal{F}_{t-i}]=E_{t}\cdot\mathbb{E}[g_{t}^{e_{t}}\mid\mathcal{F}_{t-i}]$.

Using Observation 3.4, we estimate the cost of the optimal solution $\operatorname{OPT}_{\leq 0}$.

Lemma 3.5. Let $x^{*}\in\Delta^{\ell}$ be a solution minimizing $\sum_{t=1}^{T}f_{t}^{T}x^{*}$. We have

Proof. By Observation 3.4, we have

for each $t=1,\dotsc,T$. Summing over $t$, we get

The next lemma will be used to bound the costs perceived by Algorithm 1 at time steps $t$ such that $X_{t-m}=1$.

Lemma 3.6. For each $i=0,\dotsc,m$, we have

Proof. For $t=m+1,\dotsc,T$, we have

where the second equality follows from Observation 3.4. To finish the proof, it is enough to note that $\mathbb{E}[\beta_{t-m}]=\epsilon$ and $x_{t}X_{t-m}=x_{t-i}X_{t-m}$ for any $i=0,\dotsc,m$. ∎

Bounding costs in time steps $t$ when $X_{t-m}=0$ is more involving. In such case, there is $E_{t-i}=1$ for some $i\in\{1,\dotsc,m\}$. We will use the following stability property.

Lemma 3.7. If $\bar{A}$ satisfies Property 2.3, the following holds for every $t\geq m+1$ and $i\in\{1,\dotsc,m\}$:

Proof of Lemma 3.7. We use the Cauchy-Schwarz inequality and Property 2.3:

The last inequality follows from $\lVert f_{t}\rVert_{\infty}\leq 2D$ and the following computation. Here, we use $x_{t-i+1}=x_{t}$ whenever $E_{t-i}=1$, Property 2.3, $x_{t-i}$ and $E_{t-i}$ depending only on time steps up to $t-i-1$, and Observation 3.4:

The following lemma is the core of our argument. In the proof, it decomposes the costs perceived by Algorithm 1 in each step $t$ depending on the value of $X_{t-m}$. If $X_{t-m}=1$, such costs are easy to bound using Lemma 3.6. Those with $X_{t-m}=0$ need to be charged to some other exploitation step using the preceding stability lemma.

Lemma 3.8. If $\bar{A}$ satisfies Property 2.3 then $\mathbb{E}\big[\sum_{t=1}^{T}f_{t}^{T}x_{t}\big]$ is at most

Proof. We start with an observation that for any $t\geq m+1$, exactly one of the following holds: either $X_{t-m}=1$ or the step $t-m$ is skipped due to the exploration at time $t-i$ (i.e., $E_{t-i}=1$) for some $i\in 1,\dotsc,m$. We can write

By Lemma 3.6, the first expectation in the right-hand side is at most $\frac{2D\ell}{\epsilon}\mathbb{E}[\sum_{t=1}^{T}g_{t}^{T}x_{t}]$. In order to prove the lemma, it is therefore enough to show that, for each $i=1,\dotsc,m$, $\mathbb{E}\big[\sum_{t=2m+1}^{T}f_{t}^{T}x_{t}\cdot E_{t-i}\big]$ is at most

First, we use Lemma 3.7 to obtain

The second term is easy to bound: by Observation 3.2, we have $\mathbb{E}[f_{t-i}^{T}x_{t-i}E_{t-i}]=\mathbb{E}[\beta_{t-i-m}]\,\mathbb{E}[f_{t-i}^{T}x_{t-i}X_{t-i-m}]$. Therefore, we can write

Using Observation 3.2, independence of $X_{t-i-m}$ and $\beta_{t-j-m}$ for $j=1,\dotsc,i$, and Observation 3.3, we get

In other words, we can bound the first term of (2) as

Now it is enough to apply Lemma 3.6 to the right-hand sides of (4) and (3). Equation (2) then implies (1) which concludes the proof. ∎

Theorem 3.9. Algorithm 2 using HEDGE as $\bar{A}$ with $m$-delayed bandit access to $\ell$ heuristics on any MTS input instance with diameter $D$ such that $D\ell m\leq o(\operatorname{OPT}_{\leq 0}^{1/3})$ satisfies the following regret bound:

Proof. By Lemma 3.1, $\mathbb{E}[\operatorname{ALG}]$ is at most

The first term in the parenthesis can be bounded using Lemma 3.8. The second term can be bounded using Property 2.3: denoting $\eta$ the learning rate of $\bar{A}$, we have

Altogether, using $(1-\epsilon)^{m}>1/2$ and $D\eta\leq m\epsilon\cdot\eta\cdot\frac{2D\ell}{\epsilon}$, we get that $\mathbb{E}[\operatorname{ALG}]$ is at most