Réduction de la variance dans la minimisation du regret contrefactuel de Monte-Carlo (VR-MCCFR) pour les jeux de forme extensive utilisant des lignes de base

Résumé

L'apprentissage de stratégies pour les jeux à information imparfaite à partir d'échantillons d'interaction est un problème difficile. Une méthode courante dans ce contexte, la minimisation des regrets contrefactuels de Monte Carlo (MCCFR), peut présenter des taux de convergence lents à long terme en raison d'une variance élevée. Dans cet article, nous introduisons une technique de réduction de la variance (VR-MCCFR) qui s'applique à toute variante d'échantillonnage de la MCCFR. Grâce à cette technique, les valeurs estimées par péritération et les mises à jour sont reformulées en fonction des valeurs échantillonnées et des lignes de base de l'action d'état, de manière similaire à leur utilisation dans l'apprentissage par renforcement du gradient de politique. La nouvelle formulation permet d'amorcer les estimations à partir d'autres estimations dans le même épisode, propageant les avantages des lignes de base le long de la trajectoire échantillonnée ; les estimations restent non biaisées même lorsqu'elles sont amorcées à partir d'autres estimations. Enfin, nous montrons qu'avec une ligne de base parfaite, la variance des estimations de valeur peut être réduite à zéro. L'évaluation expérimentale montre que le VR-MCCFR apporte une accélération d'un ordre de grandeur, tandis que la variance empirique diminue de trois ordres de grandeur. La diminution de la variance permet pour la première fois d'utiliser CFR+ avec l'échantillonnage, ce qui augmente la vitesse de deux ordres de grandeur.