Identification de l'action Maximin : Un nouveau cadre de bandit pour les jeux.

Résumé Nous étudions un problème original d'exploration pure dans un modèle de bandit stratégique motivé par la recherche d'arbres de Monte Carlo. Il consiste à identifier la meilleure action dans un jeu, lorsque le joueur peut échantillonner les résultats aléatoires de paires d'actions choisies séquentiellement. Nous proposons deux stratégies pour le cadre de confiance fixe : Maximin-LUCB, basée sur des limites de confiance inférieure et supérieure, et Maximin-Racing, qui fonctionne en éliminant successivement les actions sous-optimales. Nous discutons de la complexité d'échantillonnage des deux méthodes et comparons leurs performances de manière empirique. Nous esquissons une analyse des bornes inférieures, et des connexions possibles à un algorithme optimal.