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−−−√)O((λK)1/3T2/3+KT), where TT is the time horizon and KK 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)O((λK)2/3T1/3+ln⁡T)∑i≠i∗Δi−1), where ΔiΔi are suboptimality gaps and i∗i∗ is the unique optimal arm. In the special case of λ=0λ=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.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    An Algorithm for Stochastic and Adversarial Bandits with Switching Costs



    Erscheinungsdatum :

    2021-01-01


    Medientyp :

    Aufsatz/Kapitel (Buch)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Klassifikation :

    DDC:    629



    An algorithm for stochastic and adversarial bandits with switching costs

    Rouyer, Chloé / Seldin, Yevgeny / Cesa-Bianchi, Nicolò | BASE | 2021

    Freier Zugriff

    THE LAST WORD One-armed bandits

    British Library Online Contents | 2005


    Air traffic cop eyes `bandits', too

    Engineering Index Backfile | 1967



    Risk-Aware Multi-Armed Bandits for Vehicular Communications

    Wirth, Maximilian / Klein, Anja / Ortiz, Andrea | IEEE | 2022