We investigate a nonstochastic bandit setting in which the loss of an action is not immediately charged to the player, but rather spread over the subsequent rounds in an adversarial way. The instantaneous loss observed by the player at the end of each round is then a sum of many loss components of previously played actions. This setting encompasses as a special case the easier task of bandits with delayed feedback, a well-studied framework where the player observes the delayed losses individually. Our first contribution is a general reduction transforming a standard bandit algorithm into one that can operate in the harder setting: We bound the regret of the transformed algorithm in terms of the stability and regret of the original algorithm. Then, we show that tphe transformation of a suitably tuned FTRL with Tsallis entropy has a regret of order √(d+1)KT ($\sqrt{(d+1)KT}$), where d is the maximum delay, K is the number of arms, and T is the time horizon. Finally, we show that our results cannot be improved in general by exhibiting a matching (up to a log factor) lower bound on the regret of any algorithm operating in this setting.

Nonstochastic Bandits with Composite Anonymous Feedback / N. Cesa Bianchi, T.R. Cesari, R. Colomboni, C. Gentile, Y. Mansour. - In: JOURNAL OF MACHINE LEARNING RESEARCH. - ISSN 1533-7928. - 23:(2022 Aug), pp. 277.1-277.24. ((Intervento presentato al 31. convegno Conference on Learning Theory (COLT) tenutosi a Stockholm nel 2018.

### Nonstochastic Bandits with Composite Anonymous Feedback

#### Abstract

We investigate a nonstochastic bandit setting in which the loss of an action is not immediately charged to the player, but rather spread over the subsequent rounds in an adversarial way. The instantaneous loss observed by the player at the end of each round is then a sum of many loss components of previously played actions. This setting encompasses as a special case the easier task of bandits with delayed feedback, a well-studied framework where the player observes the delayed losses individually. Our first contribution is a general reduction transforming a standard bandit algorithm into one that can operate in the harder setting: We bound the regret of the transformed algorithm in terms of the stability and regret of the original algorithm. Then, we show that tphe transformation of a suitably tuned FTRL with Tsallis entropy has a regret of order √(d+1)KT ($\sqrt{(d+1)KT}$), where d is the maximum delay, K is the number of arms, and T is the time horizon. Finally, we show that our results cannot be improved in general by exhibiting a matching (up to a log factor) lower bound on the regret of any algorithm operating in this setting.
##### Scheda breve Scheda completa Scheda completa (DC)
Multi-armed bandits; non-stochastic losses; composite losses; delayed feedback; online learning
Settore INF/01 - Informatica
PRIN201719NCESA_01 - Algorithms, Games, and Digital Markets (ALGADIMAR) - CESA BIANCHI, NICOLO' ANTONIO - PRIN2017 - PRIN bando 2017 - 2019
H20_RIA20NCESA_01 - European Learning and Intelligent Systems Excellence (ELISE) - CESA BIANCHI, NICOLO' ANTONIO - H20_RIA - Horizon 2020_Research & Innovation Action/Innovation Action - 2020
http://jmlr.org/papers/v23/21-1443.html
Article (author)
File in questo prodotto:
File
21-1443.pdf

accesso aperto

Tipologia: Publisher's version/PDF
Dimensione 446.26 kB
Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/939315