Delayed Bandits: When Do Intermediate Observations Help?
Emmanuel Esposito Saeed Masoudian Hao Qiu Dirk van der Hoeven Nicolò Cesa-Bianchi Yevgeny Seldin
We study a $K$-armed bandit with delayed feedback and intermediate
observations. We consider a model where intermediate observations have a form
of a finite state, which is observed immediately after taking an action,
whereas the loss is observed after an adversarially chosen delay. We show that
the regime of the mapping of states to losses determines the complexity of the
problem, irrespective of whether the mapping of actions to states is stochastic
or adversarial. If the mapping of states to losses is adversarial, then the
regret rate is of order $\sqrt{(K+d)T}$ (within log factors), where $T$ is the
time horizon and $d$ is a fixed delay. This matches the regret rate of a
$K$-armed bandit with delayed feedback and without intermediate observations,
implying that intermediate observations are not helpful. However, if the
mapping of states to losses is stochastic, we show that the regret grows at a
rate of $\sqrt{\big(K+\min\{|\mathcal{S}|,d\}\big)T}$ (within log factors),
implying that if the number $|\mathcal{S}|$ of states is smaller than the
delay, then intermediate observations help. We also provide refined
high-probability regret upper bounds for non-uniform delays, together with
experimental validation of our algorithms.