Learning-Augmented Algorithms for MTS with Bandit Access to Multiple Predictors
This addresses a challenge in online learning with limited feedback for scenarios like resource allocation, though it is incremental as it builds on prior work in bandit learning and MTS.
The paper tackles the problem of achieving performance comparable to the best heuristic in Metrical Task Systems with bandit access to multiple predictors, where only one heuristic can be queried per time step and costs are not directly observable. It shows an algorithm achieving O(OPT^{2/3}) regret and proves a matching lower bound.
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).