Titre :

Maximin Action Identification: A New Bandit Framework for Games

Auteur(s) :

Garivier, Aurélien [Auteur]
Institut de Mathématiques de Toulouse UMR5219 [IMT]
Kaufmann, Emilie [Auteur]
Sequential Learning [SEQUEL]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Centre National de la Recherche Scientifique [CNRS]
Koolen, Wouter [Auteur]
Centrum Wiskunde & Informatica [CWI]

Titre de la manifestation scientifique :

29th Annual Conference on Learning Theory (COLT)

Ville :

New-York

Pays :

Etats-Unis d'Amérique

Date de début de la manifestation scientifique :

2016-06-23

Titre de la revue :

JMLR Workshop and Conference Proceedings

Mot(s)-clé(s) en anglais :

racing
LUCB
multi-armed bandit problems
games
best-arm identification

Discipline(s) HAL :

Mathématiques [math]/Statistiques [math.ST]
Statistiques [stat]/Machine Learning [stat.ML]
Informatique [cs]/Informatique et théorie des jeux [cs.GT]

Résumé en anglais : [en]

We study an original problem of pure exploration in a strategic bandit model motivated by Monte Carlo Tree Search. It consists in identifying the best action in a game, when the player may sample random outcomes of ...
Lire la suite >We study an original problem of pure exploration in a strategic bandit model motivated by Monte Carlo Tree Search. It consists in identifying the best action in a game, when the player may sample random outcomes of sequentially chosen pairs of actions. We propose two strategies for the fixed-confidence setting: Maximin-LUCB, based on lower-and upper-confidence bounds; and Maximin-Racing, which operates by successively eliminating the sub-optimal actions. We discuss the sample complexity of both methods and compare their performance empirically. We sketch a lower bound analysis, and possible connections to an optimal algorithm.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Projet ANR :

Apprentissage Adaptatif pour le Crowdsourcing Intelligent et l'Accès à l'Information
Statistique Semi-Paramétrique pour l'Allocation Dynamique de Ressources et l'Optimisation

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL