Strategic Choices: Small Budgets and Simple Regret

Cheng-Wei Chou 1 Ping-Chiang Chou 2 Chang-Shing Lee 3 David L. Saint-Pierre 4 Olivier Teytaud 5, 6 Mei-Hui Wang 7 Li-Wen Wu 8 Shi-Jim Yen 1
Institute of CSIE - Institute of Computer Science and Information Engineering [Taiwan]
5 TAO - Machine Learning and Optimisation
CNRS - Centre National de la Recherche Scientifique : UMR8623, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LRI - Laboratoire de Recherche en Informatique
Abstract : In many decision problems, there are two levels of choice: The first one is strategic and the second is tactical. We formalize the difference between both and discuss the relevance of the bandit literature for strate- gic decisions and test the quality of different bandit algorithms in real world examples such as board games and card games. For exploration- exploitation algorithm, we evaluate the Upper Confidence Bounds and Exponential Weights, as well as algorithms designed for simple regret, such as Successive Reject. For the exploitation, we also evaluate Bern- stein Races and Uniform Sampling. As for the recommandation part, we test Empirically Best Arm, Most Played, Lower Confidence Bounds and Empirical Distribution. In the one-player case, we recommend Up- per Confidence Bound as an exploration algorithm (and in particular its variants adaptUCBE for parameter-free simple regret) and Lower Confi- dence Bound or Most Played Arm as recommendation algorithms. In the two-player case, we point out the commodity and efficiency of the EXP3 algorithm, and the very clear improvement provided by the truncation algorithm TEXP3. Incidentally our algorithm won some games against professional players in kill-all Go (to the best of our knowledge, for the first time in computer games).
Type de document :
Communication dans un congrès
TAAI, 2012, Hualien, Taiwan. 2012
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger
Contributeur : Olivier Teytaud <>
Soumis le : lundi 18 mars 2013 - 09:00:31
Dernière modification le : jeudi 5 avril 2018 - 12:30:12
Document(s) archivé(s) le : jeudi 20 juin 2013 - 15:56:04


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-00753145, version 2



Cheng-Wei Chou, Ping-Chiang Chou, Chang-Shing Lee, David L. Saint-Pierre, Olivier Teytaud, et al.. Strategic Choices: Small Budgets and Simple Regret. TAAI, 2012, Hualien, Taiwan. 2012. 〈hal-00753145v2〉



Consultations de la notice


Téléchargements de fichiers