Regret bound for Narendra-Shapiro bandit algorithms

Panloup, Fabien, Saadane, Sofiane and Gadat, Sébastien (2018) Regret bound for Narendra-Shapiro bandit algorithms. Stochastics. pp. 886-926.

This is the latest version of this item.

Download (1MB) | Preview
Official URL: http://tse-fr.eu/pub/32571


Narendra-Shapiro (NS) algorithms are bandit-type algorithms developed in the 1960s which have been deeply studied in infinite horizon but for which scarce non-asymptotic results exist. In this paper, we focus on a non-asymptotic study of the regret and address the following question: are Narendra-Shapiro bandit algorithms competitive from this point of view? In our main result, we obtain some uniform explicit bounds for the regret of (over)-penalized-NS algorithms. We also extend to the multi-armed case some convergence properties of penalized-NS algorithms towards a stationary Piecewise Deterministic Markov Process (PDMP). Finally, we establish some new sharp mixing bounds for these processes.

Item Type: Article
Language: English
Date: May 2018
Refereed: Yes
Uncontrolled Keywords: Regret, Stochastic Bandit Algorithms, Piecewise Deterministic Markov Processes
Divisions: TSE-R (Toulouse)
Site: UT1
Date Deposited: 22 May 2018 11:32
Last Modified: 24 Jul 2019 11:35
OAI ID: oai:tse-fr.eu:32571
URI: http://publications.ut-capitole.fr/id/eprint/25888

Available Versions of this Item

Actions (login required)

View Item View Item


Downloads per month over past year