Strategic Choices: Small Budgets and Simple Regret - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2012

Strategic Choices: Small Budgets and Simple Regret

Résumé

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).
Fichier principal
Vignette du fichier
taai2012_sanstruc.pdf (487.65 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-00753145 , version 1 (19-11-2012)
hal-00753145 , version 2 (18-03-2013)

Identifiants

  • HAL Id : hal-00753145 , version 1

Citer

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. ⟨hal-00753145v1⟩
639 Consultations
429 Téléchargements

Partager

Gmail Facebook X LinkedIn More