Thank you for your review and for your suggestions. We will incorporate them in our manuscript.

We thank you for your feedback and for highlighting the strengths of our contribution. We will incorporate your suggestions in the next revision of our manuscript.

We provide answers to your questions clarifying the framing of our work in the learning-augmented framework and the difficulties present in our setting compared to the previous works. We believe that these answers could also be valuable to other researchers as suggested by Reviewer uNsW. We will add a further discussion to our paper.

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...

In fact, our result can be used (and is intended) as a tool to robustify any learning-augmented algorithm (or any heuristic) with a negligible overhead. Let $A_0$ be a classical online algorithm and let $A_1$ be a heuristic with no worst-case guarantee. On any input sequence, our algorithm is never more than $(1+o(1))$ factor worse than the best of $A_0$ and $A_1$. I.e., if $A_0$ is $R$-competitive for the given MTS variant, our algorithm is guaranteed to be at most $(1+o(1))R$-competitive. However, if the cost of $A_1$ on the given input is only 1.01 times the offline optimum, our algorithm's cost will be only factor $(1+o(1))*1.01$ from offline optimum.

Here, it is crucial that our regret guarantees are in terms of $OPT$ instead of the time horizon $T$ as common in online learning literature, because $OPT$ can be much smaller than $T$ in general MTS inputs.

The problem setting of "m-delayed bandit access to heuristics" feels made up

Our results, in order to be meaningful in MTS setting, require $m\geq 2$ consecutive queries to the same heuristic when performing exploration. This is necessary to estimate the cost of the heuristic: imagine a heuristic which, at each time $t$, moves to a state $s_t$ such that $c_t(s_t)$ is 0. Typically, this is a very bad idea in MTS, since such algorithm would most likely pay very large movement costs. However, the movement cost can be calculated only if we know its previous state $s_{t-1}$, i.e., if we have queried the same heuristic in the previous time step.

Generalization to $m>2$ is inspired by Arora et al. In their setting, algorithm has to wait $m$ time steps before seeing the relevant feedback. In our case, we do not even see the actions taken by the heuristic and we need to find suitable actions on our own.

Can you point out anything interesting... Everything looks rather "standard"

Approach from the previous work of Arora et al. would lead to a regret of order $T^{2/3}$ instead of $OPT^{2/3}$, see our response to Reviewer syMW, which is not useful for robustification. In turn, our algorithm is more similar to the classical algorithm for bandit setting alternating exploration and exploitation. However, there are three key differences, each of them is necessary to achieve our performance guarantees:

• our algorithm makes improper steps (i.e., steps not taken by any of the heuristics)

• we use MTS-style rounding to ensure bounded switching cost instead of independent random choice at each time step

• exploration steps are not sampled independently since our setting requires $m\geq 2$.

In particular, the last difference leads to much more involving analysis: We cannot assume that we have an unbiased estimator of the loss vector and therefore we need to do a lot of conditioning on past events. Moreover, the cost of only one of the $m>2$ time steps during each exploration can be directly charged to the expected loss of the internal full-feedback algorithm and the trivial bound of $2D$ is insufficient to achieve regret sublinear in OPT. We exploit stability property of the internal full-feedback algorithm in order to relate the costs incurred during the $m$ steps of each exploration.

Answers to more specific comments:

Is there no constraint on number of heuristics and delay length with respect to the input length?

In the usual setting of online learning, the number $\ell$ of experts (or arms, etc) is fixed while the time horizon $T$ is increasing towards infinity. In Section 1, we also state our theorems with $\ell, m, D$ constant which we consider the most natural setting. However, our bounds hold as far as $D\ell m\leq o(OPT^{1/3})$, see Theorems 3.9 and 3.10 for the formal statement. Our analysis extends to higher $m$, giving a regret depending on $m^{3/2}$.

hyperparameters

Optimal choice of the hyperparameters of our algorithms is established at the end of the proof of each upper bound (Theorems 3.9 and 3.10). Note that $\eta = -\log (1-\gamma)$ in our notation. The hyperparameters are chosen based on $D, \ell, m$ which are all known beforehand, and OPT, which can be guessed by the standard doubling techniques. We will include the details of guessing OPT in our revised manuscript.

Initialization of $X$ and $E$

Algorithm 1 starts with $X$ and $E$ being empty sets.

We will use your comments to improve our manuscript.

References Not Discussed

Thank you for the references; we will include them in the revision of our paper.

In practice, OPT is often unknown beforehand.

We can guess OPT using the doubling technique, getting virtually the same bound, e.g. as in Cesa-Bianchi and Lugosi (Section 2.3) or Lattimore, Szepesvari (Section 28.5). We thank you for your question. We will add a detailed explanation in the revision of our paper.

Conversely, a strength that is not emphasized is the dependence on the number of heuristics in the theoretical bounds.

Thank you for pointing out this strength of our result. We will make it more prominent in the revision.

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?

In MTS, the losses are not a priori bounded. Therefore, we cannot blindly follow the advice of the explored heuristic, since its state can have arbitrary large cost. However, it is true that if a heuristic suggests a state with a very high cost, we can always find a different (improper) step as described in our paper, ensuring that our cost is bounded by $2D$. Having this, we can apply the algorithm of Arora, Dekel, Tewari (2021) for bandits with switching cost and achieve a regret of order $O(T^{2/3})$ in our setting.

Their result is formulated as a meta algorithm and proving a formal lower bound is not easy. However, we do not think that a refinement of their analysis would lead to an upper bound in terms of $OPT^{2/3}$. Here is a simple argument: Their algorithm splits the input sequence into blocks of size $\tau$ and let some MAB algorithm choose a single arm (or heuristic) for each block which is then played during the whole block. This is to limit the switching cost to $O(T/\tau)$. If we want it to be of order $OPT^{2/3}$, we need to choose the block size $\tau \geq T/OPT^{2/3}$. However, with blocks so large, already a single exploration of some very bad heuristic would cause a cost of order $\tau \gg OPT^{2/3}$ if $OPT$ is small.