Thompson Sampling Guided Stochastic Searching on the Line for Adversarial Learning

Abstract : The multi-armed bandit problem has been studied for decades. In brief, a gambler repeatedly pulls one out of N slot machine arms, randomly receiving a reward or a penalty from each pull. The aim of the gambler is to maximize the expected number of rewards received, when the probabilities of receiving rewards are unknown. Thus, the gambler must, as quickly as possible, identify the arm with the largest probability of producing rewards, compactly capturing the exploration-exploitation dilemma in reinforcement learning. In this paper we introduce a particular challenging variant of the multi-armed bandit problem, inspired by the so-called N-Door Puzzle. In this variant, the gambler is only told whether the optimal arm lies to the “left” or to the “right” of the one pulled, with the feedback being erroneous with probability 1 − p. Our novel scheme for this problem is based on a Bayesian representation of the solution space, and combines this representation with Thompson sampling to balance exploration against exploitation. Furthermore, we introduce the possibility of traitorous environments that lie about the direction of the optimal arm (adversarial learning problem). Empirical results show that our scheme deals with both traitorous and non-traitorous environments, significantly outperforming competing algorithms.
Type de document :
Communication dans un congrès
Richard Chbeir; Yannis Manolopoulos; Ilias Maglogiannis; Reda Alhajj. 11th IFIP International Conference on Artificial Intelligence Applications and Innovations (AIAI 2015), Sep 2015, Bayonne, France. IFIP Advances in Information and Communication Technology, AICT-458, pp.307-317, 2015, Artificial Intelligence Applications and Innovations. 〈10.1007/978-3-319-23868-5_22〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01385366
Contributeur : Hal Ifip <>
Soumis le : vendredi 21 octobre 2016 - 11:43:13
Dernière modification le : vendredi 1 décembre 2017 - 01:16:44

Fichier

978-3-319-23868-5_22_Chapter.p...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Sondre Glimsdal, Ole-Christoffer Granmo. Thompson Sampling Guided Stochastic Searching on the Line for Adversarial Learning. Richard Chbeir; Yannis Manolopoulos; Ilias Maglogiannis; Reda Alhajj. 11th IFIP International Conference on Artificial Intelligence Applications and Innovations (AIAI 2015), Sep 2015, Bayonne, France. IFIP Advances in Information and Communication Technology, AICT-458, pp.307-317, 2015, Artificial Intelligence Applications and Innovations. 〈10.1007/978-3-319-23868-5_22〉. 〈hal-01385366〉

Partager

Métriques

Consultations de la notice

27

Téléchargements de fichiers

1