Data di Pubblicazione:
2022
Citazione:
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).
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.
Tipologia IRIS:
01 - Articolo su periodico
Keywords:
Multi-armed bandits; non-stochastic losses; composite losses; delayed feedback; online learning
Elenco autori:
N. Cesa Bianchi, T.R. Cesari, R. Colomboni, C. Gentile, Y. Mansour
Link alla scheda completa:
Link al Full Text: