DeLTA seminar by Saeed Masoudian
Summary
Specifically, the adversarial regret guarantee is O(\sqrt{TK} + \sqrt{dT\log K}), where T is the time horizon, K is the number of arms, and d is the fixed delay, whereas the stochastic regret guarantee is O(\sum_{i eq i^*} (\log(T)/\Delta_i + d/(\Delta_{i}\log K)) + d K^{1/3}\log K), where \Delta_i are the suboptimality gaps. We also present an extension of the algorithm to the case of arbitrary delays, which is based on an oracle knowledge of the maximal delay d_{max} and achieves O(\sqrt{TK} + \sqrt{D\log K} + d_{max}K^{1/3} \log K) regret in the adversarial regime, where D is the total delay, and O(\sum_{i eq i^*} (\log(T)/\Delta_i + \sigma_{max}/(\Delta_{i}\log K)) + d_{max}K^{1/3}\log K) regret in the stochastic regime, where \sigma_{max} is the maximal number of outstanding observations. Finally, we present a lower bound that matches regret upper bound achieved by the skipping technique of Zimmert and Seldin (2020) in the adversarial setting. Based on joint work with Julian Zimmert and Yevgeny Seldin. Paper link: https://arxiv.org/pdf/2206.14906 (to appear in NeurIPS-2022)
Classifications
AskAI Classifications
LabelsLinked Companies
