Regret bound for Narendra-Shapiro bandit algorithms

Sébastien Gadat (), Fabien Panloup and Sofiane Saadane

No 15-556, TSE Working Papers from Toulouse School of Economics (TSE)

Abstract: Narendra-Shapiro (NS) algorithms are bandit-type algorithms that were introduced in the 1960s in view of applications to Psychology or clinical trials. The long time behavior of such algorithms has been studied in depth but it seems that few results exist in a non-asymptotic setting, which can be of primary interest for applications. In this paper, we focus on the study of the regret of NS-algorithms and address the following question: are the Narendra-Shapiro (NS) bandit algorithms competitive from this non-asymptotic point of view? In our main result, we show that some competitive bounds can be obtained in their penalized version (introduced in [14]). More precisely, up to a slight modification, the regret of the penalized two-armed bandit algorithm is uniformly bounded by C \sqrt{n} (where C is a positive constant made explicit in the paper). We also generalize existing convergence and rate of convergence results to the multi-armed case of the over-penalized bandit algorithm, including the convergence toward the invariant measure of a Piecewise Deterministic Markov Process (PDMP) after a suitable renormalization. Finally, ergodic properties of this PDMP are given in the multi-armed case.

Keywords: Regret; Stochastic Bandit Algorithms; Piecewise Deterministic Markov Processes (search for similar items in EconPapers)
Date: 2015-02, Revised 2016-05
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.tse-fr.eu/sites/default/files/TSE/documents/doc/wp/2016/556_bis.pdf Full text (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:tse:wpaper:29077

Access Statistics for this paper

More papers in TSE Working Papers from Toulouse School of Economics (TSE) Contact information at EDIRC.
Bibliographic data for series maintained by ().