Delayed Bandits: When Do Intermediate Observations Help?

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Documents

  • Fulltext

    Final published version, 6.71 MB, PDF document

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 (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 (K+min{|S|,d})T−−−−−−−−−−−−−−−−√ (within log factors), implying that if the number |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.
Original languageEnglish
Title of host publicationProceedings of the 40 th International Conference on Machine Learnin
Number of pages22
PublisherPMLR
Publication date2023
Pages9374-9395
Publication statusPublished - 2023
Event40th International Conference on Machine Learning, - Honolulu, Hawaii, United States
Duration: 23 Jul 202329 Jul 2023

Conference

Conference40th International Conference on Machine Learning,
LandUnited States
By Honolulu, Hawaii
Periode23/07/202329/07/2023
SeriesProceedings of Machine Learning Research
Volume202
ISSN2640-3498

ID: 383100935