An algorithm for stochastic and adversarial bandits with switching costs

Chloé Rouyer*, Yevgeny Seldin, Nicolò Cesa-Bianchi

*Corresponding author af dette arbejde

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningpeer review

25 Downloads (Pure)

Abstract

We propose an algorithm for stochastic and adversarial multiarmed bandits with switching costs, where the algorithm pays a price λ every time it switches the arm being played. Our algorithm is based on adaptation of the Tsallis-INF algorithm of Zimmert and Seldin (2021) and requires no prior knowledge of the regime or time horizon. In the oblivious adversarial setting it achieves the minimax optimal regret bound of O((λK)1/3T2/3+KT−−−√), where T is the time horizon and K is the number of arms. In the stochastically constrained adversarial regime, which includes the stochastic regime as a special case, it achieves a regret bound of O((λK)2/3T1/3+lnT)∑i≠i∗Δ−1i), where Δi are suboptimality gaps and i∗ is the unique optimal arm. In the special case of λ=0 (no switching costs), both bounds are minimax optimal within constants. We also explore variants of the problem, where switching cost is allowed to change over time. We provide experimental evaluation showing competitiveness of our algorithm with the relevant baselines in the stochastic, stochastically constrained adversarial, and adversarial regimes with fixed switching cost.
OriginalsprogEngelsk
TitelProceedings of the 38th International Conference on Machine Learning (ICML)
ForlagPMLR
Publikationsdato2021
Sider9127-9135
StatusUdgivet - 2021
Begivenhed38th International Conference on Machine Learning (ICML) - Virtual
Varighed: 18 jul. 202124 jul. 2021

Konference

Konference38th International Conference on Machine Learning (ICML)
ByVirtual
Periode18/07/202124/07/2021
NavnProceedings of Machine Learning Research
Vol/bind139
ISSN1938-7228

Citationsformater