Lipschitz Bandits with Arbitrary Feedback Delays

The Lipschitz bandit problem extends the traditional multi-armed bandit framework to continuous action spaces by assuming that the reward functions satisfy a Lipschitz condition. This work investigates Lipschitz bandits under arbitrary feedback delays, where reward signals are not received immediately upon taking an action but after an arbitrarily chosen delay. We consider both stochastic and adversarial reward settings, and propose an elimination-based algorithm and an EXP3-based algorithm, respectively. For both settings, our algorithms achieve a regret bound of $\tilde{O}(T^{\frac{d_z+1}{d_z+2}}+\sqrt{D})$ over a time horizon $T$ with total delay $D$, where the definition of the zooming dimension $d_z$ is different for distinct settings. Our bounds match existing delay-free regret guarantees for Lipschitz bandits and reveal an additional regret penalty of $\tilde{O}(\sqrt{D})$ incurred by feedback delays. To the best of our knowledge, this work provides the first regret guarantees for Lipschitz bandits with arbitrary delays and expands the theoretical frontier of online decision making with delayed feedback. We further provide numerical experiments demonstrating the robustness of our algorithms to feedback delays and adversarial reward sequences.