Exploitabilité approximative : Apprendre la meilleure réponse dans les grands jeux

Résumé :

Une métrique standard utilisée pour mesurer l'optimalité approximative des politiques dans les jeux à information imparfaite est l'exploitabilité, c'est-à-dire la performance d'une politique contre son adversaire dans le pire des cas. Cependant, l'exploitabilité est difficile à calculer dans les grands jeux car elle nécessite une traversée complète de l'arbre de jeu pour calculer la meilleure réponse à la politique donnée. Nous introduisons une nouvelle métrique, l'exploitabilité approximative, qui calcule une métrique analogue en utilisant une meilleure réponse approximative ; l'approximation est faite en utilisant la recherche et l'apprentissage par renforcement. Il s'agit d'une généralisation de la meilleure réponse locale, une métrique d'évaluation spécifique au domaine utilisée au poker. Nous fournissons des résultats empiriques pour une instance spécifique de la méthode, démontrant que notre méthode converge vers l'exploitabilité dans les paramètres d'approximation tabulaire et de fonction pour les petits jeux. Dans les grandes parties, notre méthode apprend à exploiter les agents forts et faibles, en apprenant à exploiter un agent AlphaZéro.