Learning-Augmented Algorithms for MTS with Bandit Access to Multiple Predictors
Authors: Matei Gabriel Cosa
Marek Elias
Venue: ICML 2025 poster (2025)
Keywords: Metrical Task System
Bandits
Learning-Augmented Algorithms
Primary area: theory->online_learning_and_bandits
TL;DR: We obtain tight regret bounds for combining heuristics for MTS in a bandit setting.

Abstract: Combining algorithms is one of the key techniques in learning-augmented algorithms.
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).

Learning-Augmented Algorithms for MTS with Bandit Access to Multiple Predictors
Matei Gabriel Cosa
Marek Eliáš!
Abstract
or configurations of some complex system. At each time step t = ,,..., we receive cost function ct: M + R+ U {0, +oo). Seeing cr we can decide to stay in our pre- vious state $t-1 and pay its cost Cr (r(*x-1), or move to some (possibly cheaper) state s, and pay (s(s) + d(s;,1, where the distance function d' represents the transition cost between two states. Our objective is minimize the total cost paid over time.
We consider the following problem: we are given heuristics for Metrical Task Systems (MTS), where each might be tailored to a different type of input instances. While processing an input in- stance 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 heuristic at time cannot be estimated unless the same heuristic This related
MTS is very hard in the worst case. This is due to its online nature (s; has to be chosen without knowledge of C++1....,cy7 and also due to its generality. The perfor- mance of algorithms evaluated using the competitive ra- tio which is, roughly speaking, the ratio between the algo- rithm's cost and the cost of the optimal solution computed offline. Denoting the number of points in the metric space M, the best competitive ratio achievable for MTS is 2n 1 and (log" n) in the case of deterministic and randomized algorithms, respectively (Borodin et al., 1992; Bartal et al., 2006; Bubeck et al., 2022a; 2019). Note that n is usually very large or even infinite (e.g.. M Rd).
was also queried time to Bandit Learning against memory bounded ad- versaries (Arora et al., 2012). We show how to achieve regret of ((OPT2/3) and prove a tight lower bound based on the construction of Dekel et al. (2013).
1. Introduction
This worst-case hardness motivates the study of MTS and its special cases in the context of Learning-Augmented Algo- rithms (Lykouris & Vassilvitskii, 2021). Here, the algorithm can use predictions produced by an MI model in order to exploit specific properties of input instances. By augment- ing the algorithm with the ML model, we obtain a heuristic with an outstanding performance, well beyond the classi- cal 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; An- toniadis et al., 2023a), 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., 2023b).
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 Algorithmss 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 given description of metric space (M, d) and a starting point sp .M beforehand. The points in M are traditionally called states and, depending on the setting, they can represent actions, investment strategies,
'Department of Computing Sciences, Bocconi Univer- sity, Milan, Italy. Correspondence to: Matei Gabriel Coça <matcigabrreelcosa@ otg.gabbree...seeeeuonooooooii.o @ttudusccoobtiit........... Marck Eliáš <marck.eliase unibocconi.it..
Combining heuristies. In this basic theoretical problem, given heuristics Hı...., He which can be simu- lated 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,
Proceedings of the 4dnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Learning-Augmenter Algorithms for MTS with Bandit Access to Multiple Predictors
we cannot tell beforehand which heuristic is going to per- form better. Moreover, steps performed while following wrong heuristic cannot be revoked.
(e(s)) d(st_1, sf), i.e., we cannot calculate this cost² un- less have queried H; in both time steps & 1 and t. We also consider the case where each heuristic needs to be boot- strapped for m - 2 2 0 time steps before we can see its state. This way, to receive the state of H. in time steps t - 1 and t, and to be able to calculate its cost at time t, we have to query H; in the m time steps ( m + 1,...,/.
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 called robustness). Similarly, we can use it to deploy a portfolio of very specialized ML models in broader setting, where each model corresponds to 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.
A similar phenomenon occurs in the setting of Online Learn- ing against Memory-Boudd 2012), which is our main theoretical motivation for consid- ering 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, 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 o # 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.
Adversaries (Arora et al.,
Full-feedback setting. Most of the previous works on Combining Heuristies query the state of each heuristic at each time step, observe their costs, and choose between their states, see (Wei, 2020; Antoniadis et al., 2023a, 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 well-chosen learning rate we can be (1 + e)-competitive with respect to the best heuristic.'
A different bandit-like setting for Combining Heuristics for MTS was proposed by Antoniadis et al. (2023b). 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 + cccopetiiie 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 subset of information available in the setting of Antoniadis et al. (2023b), our upper bounds also apply to their setting.
Bandit-feedback setting, In this paper, we consider what can be seen as a bendit-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 study the impact of restricting information about the heuristics our ability to combine them effectively. Fur- ther motivation is the fact that querying all the heuristics is costly, especially if they utilize some heavy-weight predic- tion models. This issue was already considered by Emek et al. (2021) and Antoniadis et al. (2023b) whose works inspired our study. Note that the combination algorithm retains full access the input instance. This is required by any positive result for general MTS, since the cost fune- tions e, usually do not satisfy any natural properties such as Lipschitzness or convexity; see further discussion in Sec- tion 2. Moreover, e is often easy to encode. For example, in Caching, c is fully determined by the page requested at time l.
1.1. Our Results
For m 2 2, we say that an algorithm ALG has m-delayed bandit access to heuristies HI..... He if (i) it can query at most one heuristic H; at each time step f and (ii) the query yields the current state of H, only if H4, was queried also in steps f- t, otherwise it yields an empty result.
"In fact, cannot even estimate it. In Caching, keserver, and Convex Body Chasing. to give few examples, the cost of each state is either 0 or +oc. Therefore, any algorithm with a finite cost is always located at some state 8, such that (=())) = 0 and the difference in the performance of the algorithms can be seen only in the moving costs.
In contrast to the full-feedback setting, classical learning methods cannot be directly integrated in combination al- gorithms operating in the bandit setting. The main reason is that the state st of the heuristic H; is not enough to es- timate its cost at time t: the cost paid by H; at time t is
'Alternatively we could require predictors to certify their mov- ing cost by providing their state in the previous time step. This way, however, end up querying the state of two predictors in single time step.
In fact, one can achieve cost Hf + O IT*), where If" denotes the cost of the hest heuristic and D the diameter of the metric space M.
2

---

Learning-Augmenter Algorithms for MTS with Bandit Access to Multiple Predictors
Our main result is an algorithm with the following regret. Theorem 1.1. Let D, f, and m. 2 2 be constant. Consider heuristics Hi..... for an MTS with diameter D. There an algorithm ALG which, given an m-delayed bandit access H1,..., HG, satisfies the following guarantee. The expected cost of ALG on any input 1 is
the following guarantee. The cost of ALG on input I with offline optimum cost at least 2k is
B[ALG] & OPT + OPT 2k)
where OPT Sk denotes the cost of the best combination of heuristics in hindsight that switches between heuristics at most k times input I.
B[ALG] < OPT ((PPT)
Again, we can interpret this regret bound as a competitive ratio converging to 1. In Appendix C, we show that the competitive ratio of our algorithm is below (1 + e) for k as large as ( OPTss) which is worse by a log-factor than the result of Antoniadis et al. (2023b) in their easier setting,
where OPT 50 min (1) denotes the cost of the best heuristic on input I.
We prove this result Section 3, where we state explic- itly the dependence on D, m, and in the case when they larger than constant. We can interpret our result in terms of the competitive ratio. Since the regret term in Theorem 1.1 is sublinear in OP the expected cost of our algorithm is at most E[ALG] S (1 + o(1) OP In other words, its competitive ratio with respect to the best of the heuristics converges to 1. Therefore, our algorithm can be used for robustification. If we include a classical online algorithm which is p-competitive in the worst case among H....., He, our algorithm will never be worse than (1 (1+ ++)()))--ooppetity 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 's cost will be only (1 + (1)) 1.01 times the offline optimum.
In Section 4, we show that our upper bound in Theorem 1.1 is tight up to logarithmic factor even with bootstrapping time (m = 2). Our result is based on the construction of Dekel al. (2013) for Bandity with Switching Costs. Their lower bound cannot be applied directly, since algorithms in our setting have an advantage in being able to take im- proper 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 ALG with 2-delayed ban- dit access to predictors. there is an input instance I such that the expected cost of ALG is
E[ALG] 2 OPT + ((OPT
where OPT co = min H(I) denotes the cost of the best heuristic on input I.
Our algorithm alternates between exploitation and explo- ration, 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 state which is not suggested by any of the predic- tors. 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 OPT go even for m 2
In Appendix B.I, we also show that the dependence on D, and in our bounds is (almost) optimal. In particular, our regret bound in Theorem 1.1 scales with (Dké In /3 and we show that this dependence needs to be at least (Dk6)1/3 with m = 2.
1.2. Related Work
Arora et al. (2012) introduced the problem of Bandit Learn- ing against Memory-Bounded Adversaries. Here, the loss functions depend on the last μ + 1 actions taken by the algorithm. This setting captures, for example, Bandits with Switching Costs (Amir et al., 2022; Rouyer et al., 2021). They propose an elegant algorithm with regret OuTT2/3) that partitions the time horizon into blocks of equal size and let a classical online learning algorithm (c.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 2 already for μs 1. Our results are also related to Non- Stationary Bandits and Dynamic Regret (Auer et al., 2002, Section 8).
In Appendix D, we show that our algorithm can be adapted to the m-memory bounded setting for bandits, where it achieves regret of ((T2/3) comparable Arora et al. (2012), while slightly improving the dependence on m. Note that T can be much larger than OPT co-
We extend our result to setting with a benchmark which can switch between the heuristics at most k times, while the algorithm's 's number of switches still remains unrestricted.
Theorem 1.2. Let D, l, and m 2 2 be constant and k 2 1 be a parameter. Consider heuristics Hi...., Hr for an MTS with diameter D. There an algorithi ALG which, given an m-delayed bandit access to H1...., He, satisfies
3

---

Learning-Augmenttr Algorithms for MTS with Bandit Access to Multiple Predictors
Antoniadis et al. (2023b) studied dynamic combination of heuristics for MTS. By reducing to the Layered Graph Traversal problem (Bubeck et al., 2022b), they achieved a competitive ratio ( with respect to the best dynamic combination of heuristics. Then, they focused on the sce- nario where the input instance is partitioned into intervals and different heuristic excels in each of the intervals. They provided bounds on how big can be to make (1 + e)- competitive algorithms possible. Finally, they also studied this question in the bandit-like setting which is strictly easier compared to ours.
d-dimensional probability simplex, and [d] = (I....,d d..
m-delayed bandit access to heuristics. Given heuristies Hi..... He. we denote st the state of H; at time t and f(()) = (s)) + s()) the cost incurred by H; at time t. Let 2 2 be parameter. At each time t, the algorithm is allowed to query single heuristic H; If H; was also queried in time steps t - m + ,....,f. t, the result of the query is the state si. 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 very compact way. For example, 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 with cs(s +oc the algorithm needs to know Ct in order to choose 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.
First works on Combining Heuristics were by Fiat et al. (1990) for seserrer, 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 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).
Leaminn-augmmettdd algorithms were introduced by Lyk- ouris & Vassilvitskii (2021); Kraska et al. (2018) who de- signed algorithms effectively utilizing unreliable machine- learned predictions. Since these two seminal works, many computational problems were studied in this setting, in- cluding 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 con- sider algorithms using the predictions sparingly (Im et al., 2022: Drygala et al., 2023; Sadek & Eliás, 2024; Benomar & Perchet, 2024a). See the survey (Mitzenmacher & Vas- silvitskii, 2022) and the website by (Lindermayr & Megow, 2023).
We assume that fi(i) E [0, 2D). This is without loss of generality for the following reason. First, we can assume that at each time there is state with zero cost, since subtracting min, ci)) from the cost of each state affects the cost of any algorithm (including the offline optimum) equally. Second, any predictor can be post- post-processed so that, in each time step where its cost is higher than 2D, it serves the request in the state with cost and returns to the predicted state, paying at most 2D for the movement.
Benchmarks and performance metrics. Let OPT = min ΣT f((i) be the static optimum, i.e., the cost of the best heuristic. For k > O, we define
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
OPT SA min èr Σt= (c((3)) + d(s 1, st))
> minl Σt. fe((e) kD,
best competitive ratio for general MTS is O(log" n) by Bubeck et al. (2019) and Bubeck et al. (2022a).
where the minimum is taken over all solutions in ....... 'T such that the number of steps where i, # in is at most k.
2. Notation and Preliminaries
We evaluate the performance of our algorithms using ex- pected pseudoregret regret (further abbreviated as regret). For l: 2 0, we define
We consider MTS instances with a bounded diameter and denote D = mM s's, the diameter of the under- lying 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, first, and then it chooses its new state 8t, i.c. there is a I-step look-ahead. This is standard in MTS definition and it necessary for existence of any competitive algorithm, since e, is potentially unbounded, see (Blum& & Burch, 2000, Section 2.3). We denote A the
Rega (ALG) = E[ALG] - OPT
where 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
4

---

Learning-Augmenti Algorithms for MTS with Bandit Access to Multiple Predictors
that algorithm is p-competitive with respect to offline algorithm OFF, if [[ S p pOFF+t +a holds every imput instances, where is constant independent the input instance and we use OFF to denote both the algorithm and its cost. If OFF is an offline optimal algorithm, we call p the competitive ratio of ALG.
3. Algorithm for m-Delayed Bandit Access to Heuristics
3.1. Basic Approach and Comparison to Previous Works
Arora al. (2012) use the following approach to limit the number of switches between arms (or heuristics): split the time horizon into blocks of length 7 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/T. 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 OPT so which can be much smaller than T. In order to have the number of switches T/T S o(OPTsg)) we have to choose 7 = wT/ <P) which can be w(PT co) for small OPT However, with blocks so large, already a single exploration of some arbitrarily bad heuristic would induce a cost of order w w(PPTgo).
Rounding fractional algorithms. A fractional algorithm for MTS is an algorithm which, at each time t, produces distribution Pt E AM over the states in M. These distri- butions 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 Pi.....Pr E AM, produces solution SI....,ST E M with expected cost equal to
E[ALG]= = =iin (ct EMD(
where EMD denotes the Earth mover distance with respecl to the metric space M.
In tum, 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:
We include the proof of this standard fact in Appendix E 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 algo- rithm which, receiving online sequence of distributions .1....,2TT ET E A over the heuristics, queries at each time t a heuristic in with probability x, vi()s) such that
Our algorithm makes improper steps (i.e., steps not taken by any of the heuristics);
We use MTSS-ttle rounding to ensure bounded switch- ing cost instead of independent random choice at each time step;
T
D ( +1)) S Σ x1 1
T
Σ ce(s)))
Exploration steps are not sampled independently since our setting requires 2 2.
Basic learning algorithms. We use the classical algo- rithms for online learning with expert advice HEDGE (Fre- und & Schapire (1997)) and SHARE (Herbster & Warmuth (1998)). Both satisfy the following property with r) 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 F.
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.
Property 2.3. There is a parameter 1) such that the following holds. Denoting I and x, the solutions of the algorithm before and after receiving loss vector gt-1, have
|0--1 xz S n9. --
We use the bounds for HEDGE tuned for "small losses", see (Cesa-Bianchh & Lugosi, 2006).
During each exploitation step f, our algorithm follows the advice of the exploited heuristic which is sampled from the algorithm's 's internal distribution D; over the heuristics. Each exploration step / is set up so that the algorithm discovers the cost of the heuristic He, chosen uniformly at random and updates its distribution over the heuristics. However, the algorithm does not follow He,- Instead, makes a greedy step from the last known state of the exploited heuristic.
Proposition 2.4. Consider "1....,TT E A the solution produced by HEDGE with learning rate n and denote 7 ==
1 -exp(-1) 1). For any x² A we have
T
1 of x"" + Inf
T
Inl
Σ
T Di x2 <
< (1+7)
Σ
T
1 expl -1)
7
tm1
5

---

Learning-Augmentte Algorithms for MTS with Bandit Access to Multiple Predictors
3.2. Description
known state s of the heuristic Hip exploited at time '', Namely, we choose := arg min (d(s") iM ,s) + cs(s)) This procedure is summarized in Algorithm 2.
Let A be an algorithm for the classical learning from expert advice in full feedback setting (e.g. HEDGE SHARE), and be a parameter controlling our exploration rate. For each time step t = 1, I....,T, T, we sample 3: E {0, } such that B, = 1 with probability and e, is chosen uniformly at random from {I....,{} We set Pg = 0 since the al- gorithm starts querying predictors from t = Moreover, we assume all heuristics reside in Su at 0. t is an exploitation step (1 E X) and B 0, the next step will be again exploitation. Otherwise, the algorithm skips m time steps which are needed to bootstrap the explored heuristic He. and performs exploration in step t + m. At this latter step. the algorithm receives the cost ft+m (et+mm) of Herr and uses to update its distribution #++m++ over the heuristics. This update is performed using the algorithm À receiving input loss vector 91+m defined as follows: It+m (i) = ft+m (et+m) 3/2D if j ct+m and 0 otherwise. Thanks to the assumption that fi+m E [0, 2D we have 9t+m E [0, _1 Each exploration step is followed by an ex- ploitation 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 proba- bility and achieves regret ( (Slivkins, 2019). Note that our setting requires m 2 2.
Algorithm 2: Producing solution for MTS
Input: Io, .r produced by Algorithm in U(11, ,.ll,.,,,]]] {})
l}.
for t = 1, 1..... -
if Jt + -4-1 then in (o
else is == --1
6
if a is known then
go to state 8 := s/ and set bj := 8t else /e m states before and after exploration */
7
set b, := bt-1 1 last successful query #/ 8t == arg min (d + cs(s)
Lemma 3.1. Given 21...., DT E [0, 1] produced by Algo- rithm 1, the expected cost of Algorithm is at most
(1+0 Ets (ft' + D1| - zell1).
A similar statement is proved in (Antoniadis al., 2023b). We include our proof in Appendix A.I.
Choice of hyperparameters. To achieve the regret bound in Theorem 3.9, we choose the parameter := (DE In f)33 m--3m333/ OPT 1/3 for Algorithm and the learn- ing rate 1) of HEDGE which is used as Å is chosen based on y: (Dé () OPT where y = 1 (1cxxp--m). While D,e, are usually known from the problem descrip- tion, OPT'o can be guessed by doubling as described in Appendix G.
Algorithm 1: Learning dynamics
I Initialization:
<o
2 30 := 0,, 0, X = 0, E: ==0 0
3 $1....,33 3r Bernoulli(c)
4 ee.....ey eT ~ U(.
5 Zo is chosen by A
6 while L < T do
add to X 7
// Exploitation step
8
if B, = 1 then
3.3. Analysis
9
t: t m add to J++1 chosen by A after feedback gf
// skip m steps // Exploration step
We introduce the following random variables which will be useful in our analysis. We define X, as an indicator variable such that X, = 1 if t E X and 0 otherwise. Similarly, E, is an indicator of t E E. These variables are determined by B Br. We also define g: = E, gf which 0 for any $ E. We consider a filtration Fo S S...
10
11
12
+++
Now, it is enough to describe how to turn the steps of Algo- rithm 1 into a solution for the original MTS instance. First, we define 1 = 2e for any i & E. At t 1, we sam- ple the exploited heuristic from the distribution 21 and at each update of xt, we switch to a diffferent heuristic with probability } 311-2-1 æ2al2 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 (i). The state of the exploited heuristic is not known to us m steps before each exploitation step and another m steps after. Dur- ing these time steps, we make greedy steps from the last
Fr, where F, is o-algebra generated by the realizations of Bi...., 3r and ... Note that these realizations determine Xe, Er,, It', and Fe for any t' < t. Moreover, we have the following observations.
Observation 3.2. For any O...., T m, we have E 3.X, This is because + m E E if and only if l X and 3r 1. Observation 3.3. For any i = 1,..., m and t = O.... . T i, we have X 2 1]=b(1 Bett)
6

---

Learning-Augmentte Algorithms for MTS with Bandit Access to Multiple Predictors
This holds because if X = 1 and Br _..._.................... =...==--.- ....-1941-111 =0 0, then also Xe+i = 1.
By Lemma 3.6, the first expectation in the right-hand side is at most 2D/ of ate). In order prove the lemma, it is therefore enough to show that, for each = 1,..., m, E Et=2m41 f! Ie Es-s] is at most
Observation 3,4. For i
= 1, 1,..., and t = :....T. we
have E(g. Fc-i] = (2De)
This follows from Elge Fi-il = B
Ft-il
T
7
2D
Bl Fi-s] = E, Elgi" Fe-i].
E
96
Dt
(I)
e
E
t=1
Using Observation 3.4, we estimate the cost of the optimal solution go Missing proofs are in Appendix A.
First, we use Lemma 3.7 to obtain
Lemma 3.5. Let x²
E
A be a solution minimizing
Σx x" We have
T
E
EIT
Fe-d
(2)
T
E
Σ
T
x
$ OP
1=2m+1
1=2m+1
2D
T
+ ?
Σ
The next lemma will be used to bound the costs perceived by Algorithm at time steps such that Xt-m- 1. Lemma 3.6. For each i O,..., m, we have
1=2m++
The second term is easy to bound: by Observation 3.2, we have tr- = B[ - { Therefore, we can write
T
E
Σ [=+++
T Dt Zt
e
E
Σ 1=
S xt -xt-
2D
Σ 1=2m+1
TE 1
Σ BiS X.m) 1=++1
Bounding costs in time steps i when Xt-m = O is more involving. In such case, there is Ex_s = for some i E (1...., mm). We will use the following stability property. Lemma 3.7. If A satisfies Property 2.3, the following holds for every 2 + 1 and E (1,...,m} m.):
(3)
Using Observation 3.2, independence of X,-i-m and Bi-j-m for j = -1, l...., i, and Observation 3.3, we get
Σ El xe- Er (1-
E[SF'x E. < EEST D4 E.
, E.
EE a
t= 2m++1
The following lemma is the core of our argument. In the proof, it decomposes the costs perceived by Algorithm 1 in each step depending on the value of Xt-m- If X,-m= = 1, such costs are easy to bound using Lemma 3.6. Those with Xt-m 0 need to be charged to some other exploitation step using the preceding stability lemma.
Σ B[B--im
Wif Iz- ix E
3 B(-j-m) m)
2=2
T
B|Br-iml
t= 21
Lemma 3.8. If A satisfies Property 2.3 then
In other words, we can bound the first term of (2)
[Fat] is at most
T
Σ ElS 21 Ee (1 e) 1=2m+1 A= 21
EElf I x
2m (1+ (1 c)m
TAUTE
2D
E
T 96 sr
(4)
Proof: We start with an observation that for any 2 m + 1, exactly one of the following holds: either Xt-m = 1 or the step - m is skipped due to the exploration at time - (i.e., F,_; 1) for some i 1,...,m. m. We can write
Now it is enough to apply Lemma 3.6 to the right-hand sides of (4) and (3). Equation (2) then implics (1) which concludes the proof.
Theorem 3.9. Algorithm using HEDGE as À with m- delayed bandit access to E heuristics any MTS imput instance with diameter D such that Dem S (/PT1/3 satisfies the following regret bound:
T
ST we S 2m + E
Σ
Na. X.-m]
1=2m+1
go
m
E
Σ
E.
1=1
1=2m+1
[[ALG]] & OPT (0 OPT
50
7

---

Learning-Augmentted Algorithms for MTS with Bandit Access to Multiple Predictors
Proof. By Lemma 3.1, B[ALG] is most
Q2
T
T Σ
1
(1+ (mm)e)
Σ
B| - 2: -x1lll)
M1
1
M₂
1
The first term in the parenthesis can be bounded using Lemma 3.8. The second term can be bounded using Prop- erty 2.3: denoting 17 the learning rate of A, we have
b1
b2
Figure 1. With 2 = 2, M is the metric closure of this graph.
rellil S Dn Σ Elgt m1).
1. The algorithm can see the full MTS input instance as it arrives online, and therefore it can take actions on its own regardless of the advice of the queried heuristic.
Altogether, using (1 - c) > 1/2 and Dr S me . 17 we get that [[ is at most
2DL
2. The algorithm (as it is common in MTS setting) has 1 1-step lookahead, i.e., it observes the cost function ca first and only then chooses the state
(1+0(m?e)) 2m + 000+++++0000) (1+0(me) 2D T
Now we use the regret bound of À (Proposition 2.4). Let Hi be the best heuristic and x² E [o, 1] be the vector such that x. (i*) = and x² x²(1)= = O for every + i* We have
Note that both properties are indispensable in our model, see Section 2, and any non-trivial positive result would be impossible without them.
2DE T
2D
T
2DEIn&
We create an MTS input instance circumventing the advan- tages of the algorithm mentioned above. Our instance is generated random and oblivious to the construction of Dekel et al. (2013). However, we make correspondence between the timeline in our MTS instance and in their Ban- dit instance: our instance consists of blocks of length three, where each block corresponds to single time step in their Bandit instance. The construction of Dekel et al. (2013) itself comes into play when generating the solutions of the heuristics. We create these solutions in such a way that the cost of the heuristic H; can be related to the cost of the ith arm in (Dekel et al., 2013). Moreover, the state of H; depends only the loss of the ith arm at given time.
Elg x.) S (1+
Σ
Elgt x'1
EY
< (1+ OPT co
where the second inequality used Lemma C.2. In total, E[ALG] is at most
(n
OPT +0 my) OPT +0
It is enough choose : (Déln 0) 13mm 1:/30mm33///0///// 4/3 OPT 1/3 5o
1/3 to get the desired and y (Dé m2 OPT
bound.
Proposition 4.1 (Dekel al. (2013)). There stochastic instance fi...., lr of Bandits with Switching Costs such that the expected regret of any deterministic algorithm pro- ducing solution i......iu E [0] is
Theorem 3.10. Algorithm 2 with SHARE as Å and m- delayed bandit access to & heuristics on any MTS instance with diameter D with offline optimum cost at least 2k such 1/3 achieves Regg(ALG) at most that Dêm S o(OPT//3
E
Σ (((())+((i # b-1)) 1=1
min 401 (((TT))
o ( 2/T 2/3 (OPTT Sk
In (Dk)2/3m443
The metric space M consists of l parts M1,..., Mr, where M, = {ri, a; h:). The distances are chosen as follows: For j * i, we have d(r., rÿ) 1, d(r:, az) = d(ri, b,) = 2, and d(ri, a:) = d(r,, b,) 1. We have d(a,, b,) if j and other- wise. See Figure I for illustration.
Description of the MTS instance.
The proof can be found in Appendix C.
4. Tight Lower Bound: Proof of Theorem 1.3
In this section, we prove a lower bound matching Theo- rem 3.9. Our proof is based on the construction of Dekel et al. (2013) for Bandits with Switching Costs, which is a special case of Bandit Learning against a 1-Memory Bounded Adversary. In order to use their construction in our setting, we need to address additional challenges due to the algorithm having more power in our setting:
The input sequence consists of blocks of length three. We choose the cost functions in block j as follows. For i = 1,...,&, l, we choose o¹ E {a,, b,} uniformly at random. For the first step of the block j. we define the cost function ds(s) such that (s))) = 0 if (ri...., rE) and (s(s) -00
8

---

Learning-Augmennte Algorithms for MTS with Bandit Access to Multiple Predictors
otherwise. In the second time step, we issue (5( +00 if E re) and o (s) 0 otherwise. In the third time step, we issue (s) = i E (o)......f.. and (s)
E 1(6 + i-1)).
Proof. In each block I.................... T, the algorithm pays 2 + l(i # i in the first two steps. In the third step, it pays 2 only if s/ + of which happens with probability (te) 2
(s) +oo otherwise*.
Here is the intuition behind this construction. During block J. any reasonable algorithm stays in s' E (ri...., J in the first step and in s" E {o)..... of in the third step. Ideally, the algorithm would move to s" already in the second step. However, it does not yet know o)...., of and therefore needs the advice of the heuristies. In the first step of each block, the algorithm pays I if it is staying in the same part M, of the metric space (for returning to r;). If it is moving from Mj to M,, it has to pay 2, i.e., an additional unit cost.
Theorem 1.3 is derived from the following statement by Yao's principle and from the fact that we can pad the con- structed instance with zero cost vectors to get an input in- stance of length higher than OPT go-
Theorem 4.6. There a stochastic instance I of MTS of length 3T with heuristicy H1,...; He such that any deter- ministic algorithm with bandit access to HI...., HHg suffers expected regret at least (1/1333//3
Description of the heuristics. For each the heuristic H; remains in Mj throughout the whole input instance. In the first step of the block f, it moves to the state Tú. In the third step, it moves to of. Its position in the second step is derived from the Bandit instance. With probability (1 (+(0)) ), it
Proof. Let I be the input instance constructed above from f...... by in Proposition 4.1. Consider a fixed deterministic algorithm A. Firstly, we consider queries made by A. The queries in the first and the third step of each block have a trivial answer which are independent of the loss sequence L .1...... by: if A queries H,, then the answers are r; and of respectively. For each block / 1,.... T, we denote i, the heuristic queried in its second step. Note that the result of the query depends only on f
is of and with probability - far, b,} \ } In the block f, the heuristic H; pays 2 for the movements in the steps and 2 and, with probability 4(0))
f.(0) it is the other point, i.e.,
2. another 2 for the movement in the step 3. Therefore, we have the following observation.
Observation 4.2. The expected cost of the heuristic H₃ is equal to 27 + Ei= (i).
We can assume that A is tracking, since making it track- ing would only decrease its expected cost. Therefore, the expected cost of A can be written as
We consider the following special class of algorithms for our MTS instance called tracking algorithms. This class has two important properties: firstly, any algorithm on our MTS instance can easily be converted without increasing its cost. Secondly, solutions produced by tracking algorithms can be naturally converted online to the problem of Bandits with Switching Cost.
1 (ir
+ i2 +2 1 # #oil
tracking algorithm
T
2T
+
Σ
E
1 + in + + ot) (((ii)
t=1
T
Definition 4.3. Consider an algorithm A with a bandit ac- cess to heuristics HI...., Heg We say that A is a tracking algorithum if, while processing the MTS instance described above, satisfies the following condition in every block. Let H, be the heuristic queried in the second step. Then the algorithm resides in M, during the whole block and moves to the state of H₃ in its second step.
2T
+
E[1 # i-11) + Ee(ie].
1=1
Let Hj. denote the best heuristic. Using Observation 4.2, the regret of A with respect to H;- is equal to
T
Bli + in-1) + (o(te)) - Σ B[((1))
Lemma 4.4. Any algorithm A with bandit access to HI,..., He can be converted to a tracking algorithm Á without increasing its expected cost.
t=1
This is equal to the expected regret of the strategy playing arms i ,r on the sequence li,..., bT. By Proposi- tion 4. this regret is at least (((1/372/3)
Proof can be found in Appendix B.
Lemma 4.5. Consider tracking algorithm A. For each
block t, define is such that A is located at str in its sec- ond step. The expected cost of A is 2T + ΣT= ((i))) +
A Akknowlegements
This research was supported by Junior Researchers' Grant which was awarded by Bocconi University thanks to the philanthropic gift of the Fondazione Romeo ed Enrica Inv- ernizzi.
"We use infinite costs for cleaner presentation. But choosing 2D = instead of +oo does the same job, discussion in Section 2.

---

Learning-Auggeented Algorithms for MTS with Bandit Access to Multiple Predictors
Impact Statement
SODA '93, pp. 432-440, USA, 1993. Society for Indus- trial and Applied Mathematics. ISBN 0898713137.
This paper presents work whose goal to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which feel must be specifically highlighted here.
Balkanski, E.,, Perivier, N., Stein, C., and Wei, H.-T. Energy- efficient scheduling with predictions. In Proceedings of the 37th International Conference Neural Information Processing Systems, NIPS '23. Red Hook, NY, USA, 2023. Curran Associates Inc.
References
Bamas, É.,, Maggiori, A., Rohwedder, L., and Svensson, O. Learning augmented energy minimization via speed scaling, In NeurIPS, 2020.
Almanza, M., Chierichetti, F., Lattanzi, S., Panconesi, A., and Re, G. Online facility location with multiple advice. In NewrlPS, pp. 4661-4673, 2021. 2021.
Bartal, Y. Bollobás, B., and Mendel, M. Ramsey-type theorems for metric spaces with applications to online problems. Journal of Computer and System Sciences, 72(5):890-921, August 2006. ISSN 0022-0000. doi: 10. 10.1016ff.eess.000..555 joss. 2005. 05. 008008.
Amir, I., Azov, G., Koren, T., and Livni, R. Better best of both worlds bounds for bandits with switching costs. In Advances in Neural Information Processing Systems, volume 35, pp. 15800-15810, 2022.
URL http: / dxx doi.
Anand, K. Ge, R., Kumar, A., and Panigrahi. D. Online algorithms with multiple predictions. In ICML, volume 162 of Proceedings of Machine Learning Research, pp. 582-598. PMLR, 2022.
Benomar, Z. and Perchet, V. Non-clairvoy scheduling with partial predictions. In Proceedings of the 41st In- ternational Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 3506-3538, 21-27 Jul 2024a.
Antoniadis, A., Coester, C.,, Eliáš, M., Polak, A., and Simon, B. -annninedd dynamic power management with multiple states via new ski rental bounds. In NeurlPS, 2021.
Benomar, Z. and Perchet, V. Non-clairvoyant schedul- ing with partial predictions. Kolter, Z., Heller, K., Weller, A., Oliver, N., Scar- lett J. and Berkenkamp, F. (eds.), Proceedings of the 41st International Conference Learning, volume 235 of Proceedings of Machine Learning Research, pp. 3506-336 3538. PMLR, 21-27 Jul 2024b. URL https: pentts::/prooee http///ooooccccceeeeeeecoo eigeeeding.g.. waw.nngsmmm..... .mlr.
Salakhutdinov, R.
Antoniadis, A., Coester, C., Eliáš, M., Polak, A., and Simon, B. aagmene- dynamic power management with multiple states via new ski rental bounds. ACM Trans. Algorithms,, 19(2), apr 2023a. ISSN 1549-6325. doi: 10. 1053558235,,689 URL https: /oi. /1. 1145/3582689.
Machine
Antoniadis, A., Coester, C., Eliáš, M., Polak, A., and Simon, B. Mixing predictions for online metric algorithms. In Proceedings of the 40th International Conference on Ma- chine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 969.9883 23-29 Jul 2023b.
Bernardini, G., Lindermayr, A., Marchetti Marchetti-Spaccaane Spaccamela, A., Megow, N., Stougie, L., and Sweering, M. A uni- versal error measure for input predictions applied to online graph problems. CoRR, abs/2205. 12850, 2022. doi: 10.485500axXx.2225512885 URL https: /doi. org 10. (05555//aXiiin 2205. 12850.
Arora, R., Dekel, O., and Tewari, A. Online bandit learning against an adaptive adversary: from regret to policy regret. In Proceedings of the 29th International Coference on In- ternational Conference Machine Learning, ICML' 12, pp. 1747-1754, Madison, WI, USA, 2012. Omnipress. ISBN 978 12851.
Bhaskara, A., Cutkosky, A., Kumar, R., and Purohit, M. Online linear optimization with many hints. In NeurlPS, 2020.
Blum, A. and Burch, C. On-line learning and the metrical task system problem. Mach. Learn., 39(1):35-58, 2000. doi: 10.1023/::100061133666
Auer, P., Cesa-Bianchi, N., Freund, Y., and Schapire, R. E. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(1):48-77, 2002, doi: 10.1137/ 300975397011988355.. URL https: /ww...oooo1....//////// 1137 00377/00097539901398888
Blum, A. and Mansour, Y. Learning, Regret Minimization, and Equilibria, pp. 79-102. Cambridge University Press, 2007.
Azar, Y., Broder, A. Z., and Manasse, M. S. On-line choice of on-line algorithms. In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms,
Borodin, A., Linial, N., and Saks, M. E. An optimal on- line algorithm for metrical task system. J. ACM, 39(4): 745-763, 1992. doi: 10.1 46.15455146885.446668
10

---

Learning-Augmenter Algorithms for MTS with Bandit Access to Multiple Predictors
Bubeck, S., Cohen, M. B., Lee, J. R., and Lee, Y. T. Metrical task systems trees via mirror descent and unfair gluing. In Proceedings of the Thirtieth Annual ACM-SIAM Sym- posium Discrete Algorithms,, SODA 2019, Pp. 89-97, 2019. doi: 19t 19 1975482.6. URL https: 6.
Emek, Y., Kutten, S., and Shi, Y. Online paging with vanishing regret. In ITCS, 2021.
Fiat, A., Rabani, Y., and Ravid, Competitive k-server algorithms (extended abstract). FOCS, 1990.
//doi .rgoi.org/ii
9781 978111191.711111195599999999
Fiat, A., Karp, R. M., Luby, M., McGeoch, L. A., Sleator, D. D., and Young, N. E. Competi- tive paging algorithms. Journal of Algorithms, 12(4):685-699, 1991. ISSN 0196-6774. doi:
Bubeck, S., Coester, C.,, and Rabani, Y. The randomized k-
server conjecture is false! CoRR, abs/2211.0575 2022a. doi: 00448550/aXXx.22111.5777
Bubeck, S., Coester, C., and Rabani, Shortest paths without a map, but with an entropic regularizer. FOCS, pp. 1102-1113, IEEE, 2022b.
URL https:/ http::/www.ciiccee.. wew.ddiiert.ooooooooooooo science/article/piiiiii.. siienc//artiaaee///////667/11111
Freund, Y. and Schapire, R. E. A decision- theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1):119139,, 1997. ISSN 0022-0000. doi: http://bbb...g//11.000////.s.// 1504. hww.httpps//www.seeeneddeeeeee
Cesa-Bianchi, N. and Lugosi, G. Prediction, learn- ing, and games. Cambridge University Press, 2006. ISBN 778-0-521-84108-1 CB09780511546921. URL htttt::::/ddo.rrogg 1017/CB09780511544
doi: 10.1017/
Davies, S., Moseley, B., Vassilvitskii, S., and Wang, Y. Pre- dietive flows for faster ford-fulkerson. In Proceedings of the 40th International Conference on Machine Learn- ing, volume 202 of Proceedings of Machine Learning Research, pp. 7231-7248. PMLR, 23-29 Jul 2023.
Gollapudi, S. and Panigrahi, D. Online algorithms for rent- or-buy with expert advice. In ICML., volume 97 of Pro- ceedings of Machine Learning Research, pp. 2319-2327. PMLR, 2019.
Dekel, O., Ding. J., Koren, T., and Peres, Y. Bandits with switching costs: T2/3 regret. Proceedings of the forty- sixth annual ACM symposium on Theory of computing, 2013. URL https: /ttp/aap./a//
Herbster, M. and Warmuth, M. K. Tracking the best expert. Machine learning, 32(2):151-17,, 1998.
Im, S., Kumar, R., Petety, A., and Purohit, M. Parsimonious Deamingg-uggeent caching. In ICML, 2022.
http://ppp...aaat.a..se.. semant weemmnticscoolle. icscholar.
org/CozpusID: 9425790.
Kevi, E. and Nguyen, K.-T. Online covering with multi- ple experts, 2023. URL /attpp:///axii...../// 2312. 14564.
Dinitz, M., Im, S., Lavastida, T., Moseley, B., and Vas- silvitskii, S. Algorithms with prediction portfolios. In NeurlPS, 2022.
Komm, D., Královië, R.. Královič, R., and Mömke, T. Ran- domized online computation with high probability guar- antees. Algorithmica, 8445):3377-1384, May 2022. ISSN 0178-4611 doi: 10. 00.10077/00453-222-099999
Dong, Y., Peng, P., and Vakilian, A. Augmented Streaming Algorithms for Approximating MAX-CUT. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025), volume 325, pp. 44:1-44:24, Dagstuhl, Germany, 2025. Schloss Dagstuhl Leibniz- Zentrum für Informatik. ISBN 978-3-959777361-44 doi: 10.4230/LIPIcs.TTCC ITCC.TT...02...
Kraska, T., Beutel, A., Chi, E. H., Dean, J., and Polyzotis. N. The case for learned index structures. In Proceedings of SIGMOD' 18, pp. 489-504, 2018. doi: 10.1 145/3183373 3196909.
Drygala, M., Nagarajan, S. G., and Svensson, O. On- line algorithms with costly predictions. In Ruiz, F., Dy, J.. and van de Meent, J.-W. (eds.), Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pp. 8078-8101. PMLR, 25-27 Apr 2023. URLhttps: httptpp:://pppeeeeeeeeeee wwwpe//doeeeeeoeoooooooocccoce.c ngs mlr press/ v206 http///yyaaaaaaaaaaaaaaaaa htmi. htmi.
Lattimore, T. and Szepesvari, C. Bandit algorithms. 2017. URL https: http:s:///oolllimorreee com/ downloads/bood haalls/boooboooo bof.
Lindermayr, A. and Megow, N. Permutation predictions for non-clairvoyant scheduling. In SPAA, pp. 357-368. ACM, 2022.
Eberle, F., Lindermayr, A., Megow, N., Nölke, L., and Schlöter, J. Robustification of online graph exploration methods. In AAAI, pp. 9732-9740. AAAI Press, 2022.
Lindermayr, A. and Megow, N. Algorithms with predictions. https: http///aggrrrtrre www.twpeeetitiiio.o github. io, 2023.
URL https://

---

Learning--uggeented Algorithms for MTS with Bandit Access to Multiple Predictors
seporithm--ae w www.tthhppeiiiiiins....e... io. Online: accessed 2023-07-12.
Lykouris, and Vassilvitskii, S. Competitive caching with machine learned advice. J. ACM, 68(44:24:1 2021.
Mitzenmacher, M. and Vassilvitskii, S. Algorithms with predictions. Commun. ACM, 65(7):33-35, 2022. doi: 10.1145/352808. hRthttp:: /ttp:::://doiooxxo/ 114 1145/3528087.
Rohatgi, D. Near-optimal bounds for online caching with machine learned advice. In SODA, 2020.
Rouyer, C., Seldin, Y., and Cesa-Bianchi, N. An algorithm for stochastic and adversarial bandits with switching costs. In Meila, M. and Zhang. T. (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp- 9127-9135. PMLR, 18-24 Jul 2021.
Sadek, K. A. A. and Eliás, M. Algorithms for caching and MTS with reduced number of predictions. In The Twelfth International Conference on Learning Representations, 2024.
Slivkins, A. Introduction to multi-armed bandits. Founda- tions and Trends@ in Machine Learning, (2(1-2):1-288 2019. ISSN 1935-8237.
doi: 10.1561/22000000668. URL :ttp::/ / dx. doi. otg/1001156/2200000
Wang, S., Li, J., and Wang, S. Online algorithms for multi- shop ski rental with machine learned advice. In NewrlPS, 2020.
Wei, A. Better and simpler Saming--augmente online caching, In APPROX/ANDOM, 2020.
12

---

Learning-Augmentted Algorithms for MTS with Bandit Access to Multiple Predictors
A. Omitted Proofs from Section 3
A.1. Proof of Lemma 3.1
We compare the cost of Algorithm 2 to the cost of a hypothetical algorithm A' which, at each time step t, located at state At time step I, this algorithm pays cost C2 (x(s + d( ((.(=1,8)))
As proxy for the cost of Algorithm 2, we define C₁ in the following way. If 8t s/" we set C2 == Cy. Otherwise, we set
C. = d(s d(s 8t) + cx(x)) + d( be) d(be, sft).
This way, the total cost of Algorithm 2 is at most T 1=1 C₁, since the cost of its movement d(be, 8841) S d(b sf:) + d(s)', s141) time + 1 split into Ct and C(+1-
The following statement is part of the proof of Lemma 5.4 in (Antoniadis et al., 2023b), we include it here for completeness. Proposition A.1 (Antoniadis al. (2023b)). Consider t {1....,T) and denote the last step such that s, 87 Then C. < C2 + (0 Ei'=+114
Proof. If r = 1, i.e., = st then we have C. = C₁ and the sum Er=r+1 Cp is empty. Otherwise, 7 < t and the following relations hold due to b, b, = si. triangle inequality, and the greedy choice of s, in Algorithm 2 respectively.
d(b,, s()) d(b,, s
d( d(s s1) S d(s bb) + dlbe, 81)
d(br, 8t) + ce(t)) S d(b,, s + (s)')
Plugging this in the definition of Ct, we get
C = d(s 5t) + (((() d(s bi) + d(br, ot
s d(be . 1) + d(h + (x:) + d(sr. bz) - d(hr, st)
< d(bb s/ - 2(d(b,, (s))) d(bb s(r)
< [d(b,, - 2|
ca (5 )] [dd(be, [])]
s as well as s and pay (s))). Therefore, each bracket Between time steps T and f, A' has to traverse from b = s to in the equation above is bounded by Et=r+1 Cy.-
Proof of Lemma 3.1. By Proposition A.I, the cost of Algorithm 2 is at most
T
T
Σ
C
C
O())
Σ Σ C Σ 1 Σ (ai-t)C
t=1
1=1
where 7, == max(t t < t and
s and minft' |t N t and sp s Therefore, it is enough to show that
IE
ar
1)0%
< (Em=² E
Σ c
If aa > t, then 81 # s/ and there must be an exploration step within m time steps before or after Therefore, we have
t+m
E
- 1)C
Σ K=t-m
(0 (0.-1) ()]
EI - () Fill.
E
d'
13

---

Learning-Auggmented Algorithms for MTS with Bandit Access to Multiple Predictors
Here, we used that i and therefore C2 is determined only by random choices up time Now, for each 1' L-m, -......... L+m, have
T
1 (ax - Fil F Xe Xu (at - 1 Fi) S Ber mm
+
Σ
mi(2me)))
m33 m.)-m001))))
because in order to have a2 -t = mi, we need to have Brr 1 in at least once in every block of 2m time steps between to t + mi and < 1/2. Therefore, we have
Σ au - 1jy
O(Em3)
Σ C₁
which concludes the proof.
A.2. Proofs of Technical Lemmas
Proof of Lemma 3.5. By Observation 3.4, we have
Es
Elyi x=1 = E [ [u []-1]] E
2D st
[[X, mmmfff f2101 S
2DE
2D1
for each t 1,...,T T. Summing over t. get
T
ge x²"
I
1 x"
OP
2D
2D
Proof of Lemma 3.6. Fort + I,..., T. have
Eg 2TE
9i Fr-1 xz] =
St zt.
E[Be-ml ml
[TT 34 N.N.
2DE
where the second equality follows from Observation 3.4. To finish the proof, it is enough to note that [[ and I.Xe-m Tt it for any = O,..., m.
Proof of Lemma 3.7. We use the Cauchy-Schward inequality and Property 2.3:
E[S x. F.-]] = Bi(F (ot x1-1) f7t x: xx-1) Ex-1)
s E((ll æz-ill1 + fir x4 xe Er
s B RBS st- Fp-
The last inequality follows from || < 2D and the following computation. Here, we use d4-i41 whenever Er = 1, Property 2.3, Fz-i and E. depending only on time steps to t i - 1, and Observation 3.4:
Bl[l2, x1-1l11 Er-s] B[[| xz-ill1 E.-s]
[[ngg__50 - Fx-1)
E [ inoo Fr Fe-i-1] Ee (e-iEE-)
. E.- " El El
2D!
14

---

Learning-Augmentted Algorithms for MTS with Bandit Access to Multiple Predictors
B. Omitted proofs from Section 4
Proof of Lemma 4.4. Consider a block such that the algorithm A moves to another part of M in the second step. The cost functions in the first two steps are deterministic, so we can simulate what part the algorithm would go in the second step and move there already in the first step for the same cost.
Consider a block such that the algorithm moves to another part of M in the third step, i.e., moves from E {a,, b&} to s' E {ag. bj). This costs 3 in the third step and the subsequent move rjj in the beginning of the next block will cost 1. Instead, staying in M, costs at most 2 in the third step and moving to rj in the beginning of the next block will cost 2.
Therefore, we can make sure that the algorithm moves between different parts of M only in the first step of each block.
Consider the step 2 of block where queries the state st of H,. If A moves to & E {az, b5}, where j * i, its expected cost will be at least 1, since of is chosen from {aj. bj} uniformly at random.
If moves to s {as: bi) \ (s(), Then the expected cost of A in step 3 will be
(1
(((i)
2 ( 1 (i) (()
where the right-hand side corresponds the cost of algorithm Á which moves sf instead.
B.1. Optimality of the Dependence on D and k
We elaborate on the asymptotic dependence on l and D for the lower bound with 2-delayed exploration starting from the construction in Section 4.
The optimality of the dependence on D can be seen from scaling. If we scale the input instance in Theorem 4.6 by factor D, i.e. multiply all distances in the metric space and all cost vectors by D, the cost of any algorithm including OPT will be scaled by D. Therefore, the lower bound in Therorem 4.6 becomes
D B[ALG) < D OO so D 2PT OPT so +D0 (OPT<0)) 2//3)
where OPT 50 = go is the new value after the scaling.
Now, we show tightness of k in Theorem 1.2.
Theorem B.1. There exists a stochastic instance of MTS of length 3T with heuristics H Hi...., He such that any determin- istic algorithm with bandit access to HI...., He suffers expected regret at least /1(5))188122))
Proof. Let ALG be any deterministic algorithm for MTS with bandit access to Hi...., He. We assume without loss of generality that there exists N multiple of 3 such that T k We split the time horizon into k segments of size By Theorem 4.6, for each j E [k] we have
E
Σ
2 +(H))++((0) +0(0)+
1)-+1
where c(H3) represents the cost of the best heuristic in the segment j. follows that
E
c(H,)) + 12ke)
OPT S ( (Kk
C. Upper Bound for m-Delayed Bandit Access to Heuristics against OPT <k In what follows, we prove an upper bound for Algorithm using SHARE as A against OPT Firstly, SHARE satisfies the following performance bound found in (Cesa- Basa-Bianchi & Lugosi, 2006).
15

---

Learning-Augmennte Algorithms for MTS with Bandit Access to Multiple Predictors
Proposition C.1. Consider "1....;.7 F E [0, 1J the solution produced SHARE with learning rale 7t sharing parameter o, and denote y == exp(-1) For any solution f1,---. vr such that the number of time steps where it-1 o it is most k, we have
1 T In 1-7
In (e/o)
9r It S
E
g((l))
K
7(1 a)
7(1 (1-a)
The following is a generalization of Lemma 3.5 that holds for 2 0.
Lemma C.2. Consider k 2 O. Let iT iT E [e] be solution minimizing Etz (ce(s() + d(s)_i,, ,()) such that
i--1 * is holds in at most time steps L. For each I, we define It E 10,, 11 such that xy xxe(t) = and xz(1) = 0 for each
i * ic. We have
ek
E
Σ It
9t
T
S
2DL
Proof. By Observation 3.4, we have
Elg 2æ] = E [E
9r 2t
T
[F-11]] E
ff
2DL
E E[X, m-m
T
E
2D
2D
for each 1,...,? T. Let 6, d(s)
80)
d(si-1 1 88 s D. Summing over we get
T
T
E
9
T
Zt
<
e
ff'. xt
2DE
t=1
Σ
(c(())
d(sp=1 1--1 +++)+++ +o,)
2D
1=1
(OPT +kD),
2DL
since 6, for at most & time steps.
We now ready prove the following upper bound.
Theorem C.3. Algorithm with SHARE A and m-delayed bandit access heuristics any MTS instance with 1/3
diameter D with offline optimum cost at least 2k such that Dłm S 333PT//3
achieves Regg,(ALC at most
Sk
o ( (D
<OPT
2PT2/3
2/3 Sk (Dk)2/3mm43
Proof. Let Hij...., H.z be the sequence of optimal heuristics such that i + f241 for at most k indices / [7 - -1]. Then we define x; E [0, 1] such that 2 (ii) = 1 and xz(() = O for i + 87.
Proceeding analogously to the proof of Theorem 3.9 we have
E|ALG] < (1+0(m?e)) 2m + (1+0(me)(++n) 2DE T
Elg xr
Using the regret bound of Á (Proposition C.I) followed by Lemma C.2 have
2D
I
In -- 2DL
T
In (e/a)
E Elgh
xt
Σ
T
at
+ 2Dek
711 a)
07(1 aa) In (f/aa) ey a)
In 1
OPT +(1 28)
7(1 -
16

---

Learning-Augmentee Algorithms for MTS with Bandit Access to Multiple Predictors
By setting (DEk)/(e 5A) and 7 = (D (+) and considering that k S SPPT<* Sk /2, obtain
2D
DEK OPT
EOPTER
-0 -0 -D(Delnn
<OPTSR
(1 + 1))
Elgt xz S SP +0
In
Dk:
Dk:
t=1
where 77 =n In 1/(1 -7) 7) is the learning rate. It follows that the total expected cost is most
( (DeKOPTSE
EOPTSR
TOPT
E|ALG] S OP 40 +0 Finally, by setting c: (OPT
+0
meDekkn
Dk
Dk
we obtain the desired bound.
Corollary C.4. Algorithm is (1 + coompettieevve against OPT sk for k large
3 OPT SR Dim (In 2)3
Ω
where Z (00((((P)))))))((0))))))))))))))
D. Upper Bound in the Setting of Arora et al. (2012)
We demonstrate how to use the solutions 21,..., IT produced by Algorithm in order obtain solutions in the setting of MAB against m-memory bounded adversaries introduced by Arora et al. (2012). To achieve this, we propose Algorithm and analyze its performance. Note that Algorithm does not require any look-ahead, so can be used directly in the setting of Arora al. (2012).
Algorithm 3: Producing solutions for MAB against m--eemor bounded adversaries
Input: 21,..., Ty resulting from Algorithm 2 for ,....,T do if xx # Iz-1 then is 2t- else i i--1 play
To obtain regret bound in this setting, we must relate the total cost incurred by Algorithm 3 to E Sf af) which can upper bound using Lemma 3.8. Lemma D.1. Given Z1...., E [0, 11f produced by Algorithu 1, the expected cost of Algorithm 3 is at most
Ommel))
Σ
f ạt
zz]. since the algorithm plays i, sampled from 2y during exploitation rounds. For the time steps leading up to an exploration round and the exploration step itself we can only say that the per round incurred most 1. We thus have
Proof. We begin the proof by observing that (E(4((e) x
T
E[ = E
(e()))
< E
(1 - -x)) + le(ee) X.)
S
Σ x,)
+
Σ ff xt
17

---

Learning-Augmenteed Algorithms for MTS with Bandit Access to Multiple Predictors
remains estimate the first term. By definition of X,, BBy Sr and Observation 3.2 we have:
T
m
T
E
11
Xi)
$ 2m +
E
Ei-
1=
(=22m+1
m
2m +
I8 | [3---mml
(=2m-1
m-1
T
- 2m
+
Σ
Σ
E|3e-iml
1=0
(=2m-1
(m
We also need to link the real and perceived costs resulting from following an optimal policy,
Lemma D.2. Let x² E A be solution minimizing Et C.
x.
We have
T
T
E
9t
x²
2D
Proof. By Observation 3.4, we have
Ex 2D
T x²" [ = R Elui T x=1 = E
2T x B[X, m
2D ft x
2D
for each 1,..., T. The second equality holds because E, only if the same action was taken for the last steps. Summing over t, we get
T
Σ
Ax
ge x
2D
2D
Putting everything together, we may now prove the following theorem.
Theorem D.3. Consider é available arms and let m 2 be the memory bound of the adaptive adversary in the setting of Arora et al. (2012). Then Algorithm 3 achieves the following policy regret bound
1333/723)
Proof. We begin the proof by observing that Lemma 3.8 still holds in the setting of Arora al. (2012) as is based solely on the dynamics of Algorithm 1 and the stability assumption on A. Using Lemma D.1 followed by Lemma 3.8 we have
E[ALG] S (meeT) + E
ft 2t
majé f
2D
T
OmmcT) + 2m +
1
.t
(1
e)
Arguing as in the proof of Theorem 3.9, we can use Proposition 2.4 and Lemma D.2 to obtain
2D
2D
E
9t Zt
< (1+
xx +
é
ey
18

---

Learning-Augmentted Algorithms for MTS with Bandit Access to Multiple Predictors
Since fe=lfxt S, it follows that
< < 7)T) +)) + ( (Demee) B|ALG| 5
67
Since the losses in the setting of Arora et al. (2012) are contained in [0, 1js, we may drop the dependence on D. By choosing and = (mE In 1/1/3711/3 we get the desired bound.
: (EIn
E. Rounding Algorithm for MTS
We describe a procedure for rounding the solutions produced by fractional algorithms inspired by Blum & Burch (2000) and prove Proposition 2.1 and Proposition 2.2.
For two distributions p.p' A EMD(p,p') = E. max(0, - -')).). For every i,j [N], let Ta. 2 0 represent the mass transferred from p(i) to (i) such that p(i) = Σラ= Tr, and EMD(p,p') = Eijs Tr.j. Suppose a fractional algorithm chose i E [M] at the previous time step with the associated distribution p. At the next time step (with new associated distribution p²), the algorithm moves to i' [N] with probability T2 T,,/p((i) This procedure is summarized in Algorithm 4 which we also refer as Round. Note that Algorithm 4 can be applied to distributions over the states of metric space (i.e., N = M) as well as distributions over heuristics/arms (i.e., N = t). We will not mention N explicitly when calling the procedure as sub-routine for conciseness.
Algorithm 4: Round
Input: i,p, N
3 for j = ,,..., N do
Tij = mass transferred from p(i) to ('))
set {(}) = 72.3
5
p())
sample i' q
Proof of Property 2.1. Given P1,---,PP Pr M let $1,...;87 8r be the solutions produced after iteratively calling Algorithm 4, i.e. 5t- (o-:P(s) for every t E [T]. Then for every E [7]] we have
M
M
B[ea(s)) + d( 86-1) = Σ
(1))((() +
Σ
= c. Pt + EMD(Pt-1.P).
from which we obtain the desired conclusion by summing over / = I....
4, let .i....,fh in be the solutions produced after iteratively calling Algorithm 4. i.c. i, := (i. Ft, v2)) for every t E [T] and in is selected uniformly at random. We subsequently define s as the state predicted by heuristic Hi, at time t. It follows that for every E [I'] we have
Proof of Property 2.2. Given Z1,..., .r E A
D 111-11-0
B(ce(s(*) + d(stt a S of + D EMD(2,, xx-1) = ot
-1el1
where argued as in the proof of Property 2.1 and used the fact that the distance between any two states is bounded by the diameter D. By summing over t 1,... T we obtain the desired conclusion.
F. Online Learning from Expert Advice
F.1. Classical Algorithms
In this setting, a learner plays an iterative game against an oblivious adversary for T rounds. At each round t, the algorithm chooses among experts, incurs the cost associated to choice, and then observes the losses of all the experts time In
19

---

Learning-Augmennte Algorithms for MTS with Bandit Access to Multiple Predictors
this full-feedback model, several successful algorithms have been proposed and demonstrated achieve strong performance guarantees. For in-depth analysis of these classical algorithms, we invite the reader (Cesa-Bianch) & Lugosi, 2006; Blum & Burch, 2000).
The idea behind this algorithm is simple: associate to each expert weight and then use an exponential update rule for the weights after observing new loss function. The weights are normalized to produce a probability distribution over the expert set, from which the subsequent action is sampled. The learning dynamics are summarized in Algorithm 5.
HEDGE.
Algorithm 5: HEDGE
Input: 7/ E T
wo(() == 1 Vi [d]
3 for f = 1..... T do
W; = [E( wi(()
(1) = wi (t) Vi E [E]
Play i dt
Observe gr [0. 1]
7
Set (i) = wi exp(-1) (c)1
Vie [C]
This algorithm starts from the same exponential update rule as HEDGE, but introduces an additional term. Given the reduction the sum of the weights A, the SHARE algorithm adds to each weight a fixed fraction a A. The effect of this change that information is shared across experts, which makes the algorithm better tracking the best moving expert. This allows SHARE achieve good performance with respect to benchmark that allowed to switch experts a limited number of time. Algorithm 6 summarizes these dynamics.
SHARE.
Algorithm 6: SHARE
Input: 7), O. E,
2 wo(()= == Vi [t]
3 for I..... do
W. Eieg (i)
(1) = wi (i) We Vi E [e]
6
Play is ~ Dt
Observe 9r E [0, 1]
Compute A = Evelg We exp
Set (() = (i) -xp(-n--0-(()) a Vi e
F22 Proof of Property 2.3
We consider the weight vector E [0, o associated to each expert and the loss vector 9t-1 E [0, 1J The distribution over the experts 2,-1 E [0, 1] obtained 11) (i) (i)(() where W E/= 1)-1(j).
The HEDGE algorithm with parameter 7) > 0 uses the following update rule
wx(() w (t) exp (-1 (t)) Vi [A].
(5)
The SHARE algorithm with parameters 17 0 and [0, 1/2] uses the following update rule
(8) w exp (-1 - + a A/E We [4]
(6)
where A := (w,1((1 - exp (-1 -
The following statement part of the proof of Theorem 10 (Blum Burch, 2000), which we include here for completeness.
20

---

Learning-Augmentt Algorithms for MTS with Bandit Access to Multiple Predictors
Lemma F.I. The SHARE algorithm satisfies the following
Σ (z)()
E
xz-1 exp (-1) Gt- (1))
1:0 (3) 160)
i: (f)<. 1(6)
for everyt E [T].
Proof. Using the update rule in (6) we have
Σ
(Ir- (i) zz(1))
Σ
Wt-1
Wt-1 exp (-1) (1)) + A/E
Wr-1
W,
iin (a) 18)
uz (z) 160)
W4-1
W/-1 eep (-1) (-11-9t-10 10))
W
We
(z(())(z--1
Σ
W/-1
Wt-1 exp ( (-1) 1017779-1111 -9--
W
W
100)
where the last inequality uses the observation that W Wi-1 for all e [T].
Proof of Property 2.3. The proof for HEDGE follows immediately from Theorem 3 in (Blum & Burch, 2000). The result for SHARE is obtained by applying F. followed by the previous argument, since the right-hand side of (7) contains the update rule in (5). As consequence, for both HEDGE and SHARE, 1) (i.e., the learning rate parameter) directly appears in the expression of Property 2.3.
G. Estimating the Baseline Online
The bounds obtained in Theorem 3.9 and Theorem 3.10 require tuning parameters based on the values of OPT go and OPT respectively. These values are typically unknown priori and we need to estimate them online. In particular, our algorithm can observe the MTS input instance and, at each time 4, compute the value of the offline optimal solution up to time t. Let OFF denote the cost of the offline optimal solution the given input instance. H1, ....... He achieves cost most OFF, then OFF < OPT R OFF. We use OFF as estimate of OPT in order to tune the parameters of our algorithm and achieve regret bound depending on R. Note that we do not need to know Rt beforehand and we can ensure that R is bounded by including some classical online algortihm which is competitive in the worst case among H H1,...,Hf,
least one of the heuristies
We use the guess and double trick which resembles the classical problem of estimating the time horizon T in a MAB setting, see Bessa-Binnchi & Lugosi, 2006; Lattimore & Szepesvari, 2017). Here, one starts with prior estimate of the time horizon and an instance of some online algorithm whose parameters are tuned based on this estimate. Whenever the estimate becomes smaller than the index of the current iteration, the guess is doubled, new instance of the online algorithm is created, and its parameters are set according to the new guess. In what follows, we show how to adapt this strategy to our setting. We focus on OPT go. but similar argument can be made for OPT
Let ALG(w) be Algorithm configured with parameters e := (n 1000mmmm3333//// 1/33 and 7 == (D 1/3 /333 1/3 Here D, f, m are known and w is our estimate of the unknown OPT Our strategy is to instantiate a sequence of algorithms ALG,,ALG2 A such that ALG, = ALG(2'w) runs between rounds a; (included) and b, (excluded). The optimal heuristic interval has cost OPT; 2 by construction. Let OFF; be the offline MTS optimal cost computed on the interval between a; and b;- Note that we can always compute this value time t after observing the sequence of local cost functions Ca. .,.,, Cb,-1- Suppose one of the heuristics is R-competitive with high probability w.r.t. the offline MTS optimum. Then it must be that 2'w < R OFFF; with high probability. This effectively provides a threshold for switching to the next instance without knowledge of the true value of OPT, It remains to show that this procedure, summarized in Algorithm 7, guarantees a limited overhead w.r.t. to the bound that requires knowledge of OPT
Proposition G.1. Let D. E, m be fixed and assume there exists H E (H...., He) such that H is R-competitive with high 2/3 probability, Then Algorithm 7 achieves regret ORR2/3 2/3 5o) with respect to OPT go-
21

---

Learning-Augmennte Algorithms for MTS with Bandit Access to Multiple Predictors
Algorithm 7: Doubling algorithm
1 Input: w
2
3 ==0
4 t=1
5 ALGo := (LG(w)
while S T do
if OFF;; R2-2'w then +++
ALG, == ALG(2W)
Choose s according to ALG,
+++
Proof.
By construction of the sequence of algorithms, we have that 2'w S OPT, and Σ OPT; S OPT go. It follows
that
Σ 2'w w' OPTSo,
which implies that N < log(OPTsa). Moreover, we have
Reg E[ALGG] OPT go
[B[ALG.] OPT,)
O(OPT
N
0
Σ
(R. 2))33
1=0
0 R2 OPT 2/3)
where the first inequality comes from Theorem 1.1 and the second from the assumption in the hypothesis.
The previous result means that we can guarantee regret which is worse by a factor of R22/ w.r.. to the bound which requires knowledge of OPT R depends on the MTS variant being solved. For general MTS, we can assume < 2n by including the classical deterministic algorithm by Borodin et al. (1992), or R Ologg² n) by including the algorithm by Bubeck al. (2019). Using the procedure of Komm al. (2022), any algorithm for MTS which is R-competitive in expectation be made (1 + R-compettivve with high probability for any 0.
22


Reviews:
[{"review_id": "2hJDdWfHRf", "reviewer": "Reviewer_syMW", "summary": "This paper considers the problem of sequentially selecting heuristics for Metrical Task Systems (MTS) when multiple heuristics are available. We focus on the bandit feedback setting, in which only the output of the heuristic chosen at each time step is observable. For this problem, we design and analyze algorithms that minimize the difference in total cost compared to the best fixed heuristic in hindsight, a quantity analogous to regret in bandit problems. Furthermore, we establish lower bounds that nearly match the upper bounds achieved by our proposed algorithms.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> References Not Discussed\n\nThank you for the references; we will include them in the revision of our paper.\n\n> In practice, OPT is often unknown beforehand.\n\nWe can guess OPT using the doubling technique, getting virtually the same bound, e.g. as in Cesa-Bianchi\nand Lugosi (Section 2.3) or Lattimore, Szepesvari (Section 28.5).\nWe thank you for your question. We will add a detailed explanation in the\nrevision of our paper.\n\n> Conversely, a strength that is not emphasized is the dependence on the number of heuristics in the theoretical bounds.\n\nThank you for pointing out this strength of our result. We will make it more\nprominent in the revision.\n\n> question regarding the connection to bandits with switching costs [Dekel et al. (2013)]. is it possible to leverage their results for the upper bound as well?\n\nIn MTS, the losses are not a priori bounded. Therefore, we cannot blindly follow\nthe advice of the explored heuristic, since its state can have arbitrary large cost.\nHowever, it is true that if a heuristic suggests a state with a very high\ncost,  we can always find a different (improper) step as described\nin our paper, ensuring that our cost is bounded by $2D$.\nHaving this, we can apply\nthe algorithm of Arora, Dekel, Tewari (2021)\nfor bandits with switching cost and\nachieve a regret of order $O(T^{2/3})$ in our setting.\n\nTheir result is formulated as a meta algorithm and proving a formal lower\nbound is not easy.\nHowever, we do not think that a refinement of their analysis would lead to an\nupper bound in terms of $OPT^{2/3}$. Here is a simple argument:\nTheir algorithm\nsplits the input sequence into blocks of size $\\tau$ and let\nsome MAB algorithm choose a single arm (or heuristic) for each block which is then played during the whole block.\nThis is to limit the switching cost to $O(T/\\tau)$.\nIf we want it to be of order $OPT^{2/3}$,\nwe need to choose the block size $\\tau \\geq T/OPT^{2/3}$.\nHowever, with blocks so large, already a single exploration of some\nvery bad heuristic would cause a cost of order $\\tau \\gg OPT^{2/3}$\nif $OPT$ is small.", "claims_and_evidence": "The main contributions of this paper are theoretical, and all appear to be supported by correct proofs.", "methods_and_evaluation_criteria": "The evaluation metric used in this paper is natural and reasonable.", "theoretical_claims": "I have briefly checked the proofs of Lemma 3.8, Theorem 3.9, Lemma C.2, and Theorem 4.6. \nNo particular issues were found.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "This paper considers MTS as an application, while its technical components are primarily based on techniques from online learning and bandit problems. In particular, it appears to be closely related to topics such as bandits with switching costs and non-stationary bandits.", "essential_references_not_discussed": "For the setting where $ k \\geq 1 $, concepts from non-stationary bandits and dynamic regret appear to be relevant, so it would be beneficial to mention them, e.g., Section 8 of [Auer, P., Cesa-Bianchi, N., Freund, Y., & Schapire, R. E. (2002). The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1), 48-77.]", "other_strengths_and_weaknesses": "For the proposed algorithm, achieving the guarantees stated in Theorem 3.9 and Theorem 3.10 appears to require setting parameters such as the learning rate based on the value of *OPT*. In other words, prior knowledge of *OPT* or at least an approximation of it seems necessary. However, in practice, *OPT* is often unknown beforehand. This is a potential weakness that is not mentioned in the main text.\n\nConversely, a strength that is not emphasized in the paper is the dependency on the number of heuristics $ \\ell $ in the theoretical bounds. While the introduction does not explicitly discuss this aspect, the derived bounds actually show that both the upper and lower bounds scale approximately as $ \\ell^{1/3} $. This means that the guarantees on *OPT* have a tight dependency on $ \\ell $, which could be highlighted more prominently.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "I have a question regarding the connection to *bandits with switching costs* [Dekel et al. (2013)]. This paper uses their results to establish the lower bound, but is it possible to leverage their results for the upper bound as well? \n\nFor example, in the case of $ m = 2 $, if we simply define the loss as $ f_t $ or $ g_t $ in your paper and apply their algorithm, wouldn’t we obtain an upper bound of $ (DT)^{2/3} $ instead of $ OPT^{2/3} $? \n\nAdditionally, I wonder if some refinement of their analysis could lead to an upper bound of $ OPT^{2/3} $. I would appreciate hearing the authors' thoughts on this point.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BbAYIBOfL1", "reviewer": "Reviewer_Jzgp", "summary": "The paper studies the problem of metrical task system (MTS) under the bandit feedback setting. Given multiple heuristic predictors of what action to take, the algorithm can choose one predictor and receive feedback only if the same predictor is used consecutively across m time steps. A tight regret bound was proven and the authors also studied an extension to the setting that one can switch between heuristics at most k times.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We provide answers to your questions clarifying the framing of our work\nin the learning-augmented framework and the difficulties present in our setting\ncompared to the previous works.\nWe believe that these answers could also be valuable to other\nresearchers as suggested by\nReviewer uNsW. We will add a further discussion to our paper.\n\n> I do not believe that this work fits into the learning-augmented algorithms framework... Typically, a work in this area would require one to prove robustness guarantees...\n\nIn fact, our result can be used (and is intended) as a tool to robustify any\nlearning-augmented algorithm (or any heuristic) with a negligible overhead.\nLet $A_0$ be a classical online algorithm\nand let $A_1$ be a heuristic with no worst-case guarantee.\nOn any input sequence, our algorithm is never more than $(1+o(1))$ factor worse\nthan the *best* of $A_0$ and $A_1$.\nI.e., if $A_0$ is $R$-competitive for the given MTS variant,\nour algorithm is guaranteed to be at most $(1+o(1))R$-competitive.\nHowever, if the cost of $A_1$ on the given input is only\n1.01 times the offline optimum, our algorithm's\ncost will be only factor $(1+o(1))*1.01$ from offline optimum.\n\nHere, it is crucial that our regret guarantees are in terms\nof $OPT$ instead of the time horizon $T$ as common in online learning\nliterature, because $OPT$ can be much smaller than $T$ in general MTS inputs.\n\n> The problem setting of \"m-delayed bandit access to heuristics\" feels made up\n\nOur results, in order to be meaningful in MTS setting, require $m\\geq 2$\nconsecutive queries to the same heuristic when performing exploration.\nThis is necessary to estimate the cost of the\nheuristic: imagine a heuristic which, at each time $t$, moves to a state $s_t$\nsuch that $c_t(s_t)$ is 0. Typically, this is a very bad idea in MTS, since such\nalgorithm would most likely pay very large movement costs.\nHowever, the movement cost can be calculated only if we know its previous state\n$s_{t-1}$, i.e., if we have queried the same heuristic in the previous time\nstep.\n\nGeneralization to $m>2$ is inspired by Arora et al.\nIn their setting, algorithm has to wait $m$ time steps\nbefore seeing the relevant feedback. In our case, we do not even see\nthe actions taken by the heuristic and we need to find suitable actions on our\nown.\n\n> Can you point out anything interesting... Everything looks rather \"standard\"\n\nApproach from the previous work of Arora et al.\nwould lead to a regret of order $T^{2/3}$ instead of $OPT^{2/3}$,\nsee our response to Reviewer syMW, which is not useful for robustification.\nIn turn, our algorithm is more similar to the classical algorithm for bandit\nsetting alternating exploration and exploitation.\nHowever, there are three key differences, each of them is necessary to achieve\nour performance guarantees:\n\n* our algorithm makes improper steps (i.e., steps not taken by any of the\nheuristics)\n\n* we use MTS-style rounding to ensure bounded switching cost instead\nof independent random choice at each time step\n\n* exploration steps are not sampled independently since our setting requires $m\\geq 2$.\n\nIn particular, the last difference leads to much more involving analysis:\nWe cannot assume that we have an unbiased estimator of the loss vector\nand therefore we need to do a lot of conditioning on past events.\nMoreover, the cost of only one of the $m>2$ time steps during each exploration can\nbe directly charged to the expected loss of the internal full-feedback algorithm\nand the trivial bound of $2D$ is insufficient to achieve regret sublinear in OPT.\nWe exploit stability property of the internal full-feedback algorithm\nin order to relate the costs incurred during the $m$ steps of each exploration.\n\n## Answers to more specific comments:\n\n> Is there no constraint on number of heuristics and delay length with respect to the input length?\n\nIn the usual setting of online learning, the number $\\ell$ of experts (or\narms, etc) is fixed while the time horizon $T$ is increasing towards infinity.\nIn Section 1, we also state our theorems with $\\ell, m, D$ constant which\nwe consider the most natural setting.\nHowever, our bounds hold as far as\n$D\\ell m\\leq o(OPT^{1/3})$, see Theorems 3.9 and 3.10 for the formal statement.\nOur analysis extends to higher $m$, giving a regret depending on $m^{3/2}$.\n\n> hyperparameters\n\nOptimal choice of the hyperparameters of our algorithms is established at the end\nof the proof of each upper bound (Theorems 3.9 and 3.10).\nNote that $\\eta = -\\log (1-\\gamma)$ in our notation.\nThe hyperparameters are chosen based on $D, \\ell, m$ which are all known beforehand,\nand OPT, which can be guessed by the standard doubling techniques.\nWe will include the details of guessing OPT in our revised manuscript.\n\n> Initialization of $X$ and $E$\n\nAlgorithm 1 starts with $X$ and $E$ being empty sets.\n\nWe will use your comments to improve our manuscript.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I skimmed the proofs. They look reasonable.", "experimental_designs_or_analyses": "No experiments as it is a theoretical paper.", "relation_to_broader_scientific_literature": "This work would be of interest to the bandit and expert selection communities.", "essential_references_not_discussed": "Not that I am aware of", "other_strengths_and_weaknesses": "# Strengths\n- Asymptotically matching regret bounds were proven (Theorem 1.1 and 1.3) for the problem studied\n# Weaknesses\n- I do not believe that this work fits into the learning-augmented algorithms framework. It fits much more closely to the bandit or expert selection framework. Typically, a work in this area would require one to prove robustness guarantees showing the performance of the algorithm when the predictor is of arbitrarily poor quality; in this case, one would expect a result showing that the expected cost of ALG degrades back into predictor-free guarantee of $O(\\log^2 n)$ when all heuristic predictors are arbitrarily bad. However, the paper only gives bounds with respect to the performance of the best predictor (which could be arbitrarily bad), which is precisely what the bandit or expert selection literature measures against.\n- The problem setting of \"m-delayed bandit access to heuristics\" feels made up just to introduce additional constraints to distinguish itself from the settings of prior works. For instance, I don't see anything algorithmically or theoretically interesting about this m-delay feedback beyond trivially being forced to repeat the same choice m times (see Algorithm 1) and incurring a corresponding factor m in the analyses.", "other_comments_or_suggestions": "- In Proposition 2.2, you should write \"There is an online randomized algorithm Round...\" so that it makes sense to refer to the algorithm here as Round subsequently.\n- Given that your method uses HEDGE and SHARE as black-boxes, you should provide a description and discussion of them either in the main paper or at least in the appendix.", "questions_for_authors": "- Is there no constraint on number of heuristics $\\ell$ and delay length $m$ with respect to the input length? What if we don't even get to execute some heuristic?\n- How are the hyperparameters such as $\\eta$ in Property 2.3 and $\\varepsilon$ in Algorithm 1 determined in practice? How should someone using your algorithm set them? Where does $\\eta$ show up in your actual algorithm?\n- What are $X$ and $E$ in Algorithm 1? They are undefined and uninitialized, but they should be sets, right?\n- Can you point out anything interesting about the algorithms or proof techniques used to obtain your results? Everything looks rather \"standard\" to me, modulo some minor tweaking to accommodate the m-delay setting (which feels made up to me). I am happy to upgrade my score if I am sufficiently convinced by the rebuttal (or the reviews given by other reviewers) that there is something substantially interesting going on in the paper that I have missed.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "NIL"}}, {"review_id": "gULbrkGQah", "reviewer": "Reviewer_uNsW", "summary": "The paper studied the learning-augmented metrical task system (MTS) problem and gave near-tight bounds of $\\tilde{\\Theta}(\\text{OPT}^{2/3})$. The problem is similar to the adversarial bandits with $T$ days; however, the ``switching’’ between bandits would involve a cost, which is measured by the distance between two states in a metric space. Let $s_t$ and $s_{t+1}$ be the states (arms) we commit to on time step $t$ and $t+1$, the cost of this step is defined as $c_t(s_t)+d(s_{t}, s_{t+1})$, where $c_t$ is a cost function only known on time step $t$.\n \nIn the learning-augmented setting, there are $\\ell$ online ML models (known as the ``heuristics’’), and each ML model $i$ would recommend a prediction $s^i_t$ at time $t$. Importantly, we cannot observe the full cost since we do not know what will be the state $s^i_{t+1}$ for model $i$ to switch to in step $t+1$. The goal is to be competitive with the best ML model in hindsight. As standard in the literature, we define the extra additive error as regret.\n\nThe main contributions of the paper are as follows:\n- An algorithm that achieves $O(\\text{OPT}^{2/3})$ regret for the learning-augmented MTS problem (assuming constant $\\ell$ and range of the metric space). \n- A near-matching lower bound such that any algorithm has to suffer $\\tilde{\\Omega}(\\text{OPT}^{2/3})$ regret.\n- The generalization of the results, including results in a setting where the signal delay is $m\\geq 2$ and the setting where the algorithm could make at most $k$ switches.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your feedback and for highlighting the strengths of our\ncontribution. We will incorporate your suggestions in the next revision\nof our manuscript.", "claims_and_evidence": "The theoretical results are with full proofs and/or external references.", "methods_and_evaluation_criteria": "N/A, no experiments included.", "theoretical_claims": "The main techniques used in this paper are heavily connected to the existing work of ADT [ICML’12] and DDKP [STOC’14]. At a high level, the algorithm tosses a coin to decide whether to follow $m$ steps of exploration or take the next step from an MWU-type of algorithm (e.g., the HEDGE algorithm). Running this algorithm would result in a distribution over the actions at each time step, and we can run a standard rounding algorithm to get the actual action sequence. The bounds on regret intuitively follow from the bounded loss argument in the online learning literature, although there are some additional technical steps for the formal argument. The lower bound was built on the foundation of the lower bound instance in DDKP [STOC’14], and the paper did more work to incorporate the metric switching cost into the argument.\n\nThe proofs look intuitively correct to me, although I did not check their correctness in detail.", "experimental_designs_or_analyses": "N/A, theoretical paper without experiments.", "relation_to_broader_scientific_literature": "This paper has significance in both machine learning and theoretical computer science. There could also be many applications in online learning.", "essential_references_not_discussed": "Nothing essential is missing, although I think the paper could expand the discussion on adversarial bandits and learning-augmented algorithms for graph problems.", "other_strengths_and_weaknesses": "In general, I believe the problem studied in the paper is well-motivated, and the results are interesting. I have worked in both learning-augmented algorithms and online learning, and it is great to see connections between the areas. The analyses are non-trivial, and the paper is written in a relatively clean and coherent manner such that the intuitions are well-explained. The results also demonstrate a nice comparison with ACEPS [ICML’23] and show the importance of the extra information in that work. \n\nOn the flip side, I think that although the paper has already made reasonable effort to clarify the problem and the existing work, I still doubt whether people unfamiliar with the literature would find the paper hard to follow. This is partially attributed to the fact that the paper is a follow-up of a long line of existing work. However, maybe the authors should consider an expanded discussion (maybe in the appendix) to help readers less familiar with the literature to understand the problem and the techniques.", "other_comments_or_suggestions": "See above.", "questions_for_authors": "N/A, I do not have additional questions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PabWK5FgHf", "reviewer": "Reviewer_FnST", "summary": "The paper studies the online metrical task system (MTS) problem in a learning-augmented variant. Given a metric space and an initial state $s_0$ (point), at each time a cost function $c_t$ over points is revealed, and an algorithm needs to select a state $s_t$ and pays cost equal to $d(s_{t-1},s_t) + c_t(s_t)$. The goal is to minimize the total cost.\n\nThe present paper studies MTS in a setting with expert advice: an online algorithm has access to $\\ell$ heuristics, and the goal is to achieve a good performance compared to the best heuristic in hindsight.\nSpecifically, an algorithm only has bandit access to the heuristics, which means that it does not see the state of each heuristic at every timestep, but can only query the state of at most one heuristic. Moreover, they assume that an algorithm needs to query a heuristic for $m$ consecutive timestep before the current state will be revealed.\n\nThe authors present an algorithm with sublinear regret and prove that it is best-possible. Their algorithm reduces the bandit setting to a black box full feedback setting, with a tradeoff between exploration and exploitation. This gives a fraction solution. The authors then present an online rounding scheme.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and for your suggestions. We will incorporate them in\nour manuscript.", "claims_and_evidence": "All claims are proven formally.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "I checked the proofs in the main part of the paper and they seem correct to me.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The key contribution of the paper is the presentation and exhaustive study of a new interesting model within the area of multiple predictions for learning-augmented algorithms. I believe that the results are non-trivial and add valuable insights to this area. Also, the contribution of upper and lower regret bound builds a nice package.", "essential_references_not_discussed": "As far as I see, all relevant literature is being discussed.", "other_strengths_and_weaknesses": "Strengths\n- The paper is well written\n- Broadens the discussions on multiple predictions\n- Gives tight results, hence answers the research question completely", "other_comments_or_suggestions": "- page 1, line 18 right: replace $x_t$ with $s_t$\n- references: there are several arxiv references, for which conference versions exist. I suggest to update them.", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: Reviewers' scores are all positive, with most agreeing that the problem under study is well-motivated and the results are interesting. Some reviewers initially questioned the naturalness of "m-delayed bandit access to heuristics," but the authors’ response effectively addressed these concerns, convincing the reviewers and leading to scores being increased.
Decision: Accept (poster)