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
3 OASE
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).
Document type :
Conference papers
Complete list of metadatas

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-00753145
Contributor : Olivier Teytaud <>
Submitted on : Monday, March 18, 2013 - 9:00:31 AM
Last modification on : Thursday, April 5, 2018 - 12:30:12 PM
Long-term archiving on : Thursday, June 20, 2013 - 3:56:04 PM

File

taai2012_sanstruc.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00753145, version 2

Collections

Citation

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-00753145v2⟩

Share

Metrics

Record views

889

Files downloads

406