Delayed Bandits: When Do Intermediate Observations Help?

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

Dokumenter

  • Fulltext

    Forlagets udgivne version, 6,71 MB, PDF-dokument

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.
OriginalsprogEngelsk
TitelProceedings of the 40 th International Conference on Machine Learnin
Antal sider22
ForlagPMLR
Publikationsdato2023
Sider9374-9395
StatusUdgivet - 2023
Begivenhed40th International Conference on Machine Learning, - Honolulu, Hawaii, USA
Varighed: 23 jul. 202329 jul. 2023

Konference

Konference40th International Conference on Machine Learning,
LandUSA
By Honolulu, Hawaii
Periode23/07/202329/07/2023
NavnProceedings of Machine Learning Research
Vol/bind202
ISSN2640-3498

Links

ID: 383100935