Several works consider stochastic models for incorporating time-varying requests [1]}, [2]}, [3]}, , , using frameworks such as Markov Decision Processes (MDPs), Reinforcement Learning and Multi-Armed Bandits to address scenarios where system parameters such as service popularity or task request rates are unknown. On the other hand, we focus on the case of arbitrary request arrival processes and provide `worst-case' guarantees on the performance of our proposed schemes instead of `average' performance guarantees. This can be vital in scenarios where the arrival patterns change frequently over time, making it difficult to predict demand or model it well as a stochastic process.
