Total: 1
Combining algorithms is one of the key techniques in learning-augmented algorithms.We consider the following problem:We are given $\ell$ heuristicsfor Metrical Task Systems (MTS), where each might be tailored to a different typeof 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 thatthe cost paid by a heuristic at time $t$ cannot be estimatedunless the same heuristic was also queried at time $t-1$.This is related to Bandit Learning against memory boundedadversaries (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 constructionof Dekel et al. (2013).