Lignes de base à faible variance et à variance nulle pour les jeux à forme extensive

Résumé :

Les jeux de forme extensive (EFG) sont un modèle courant d'interactions multi-agents avec des informations imparfaites. Les algorithmes de pointe pour résoudre ces jeux effectuent généralement des marches complètes de l'arbre de jeu, ce qui peut s'avérer excessivement lent pour les jeux de grande taille. Les méthodes basées sur l'échantillonnage, telles que la minimisation des regrets contrefactuels de Monte Carlo, effectuent une ou plusieurs trajectoires à travers l'arbre, ne touchant qu'une fraction des nœuds à chaque itération, au prix d'un plus grand nombre d'itérations nécessaires pour converger en raison de la variance des valeurs échantillonnées. Dans cet article, nous étendons les travaux récents qui utilisent les estimations de base pour réduire cette variance. Nous introduisons un cadre de valeurs corrigées par la ligne de base dans les EFG qui généralise les travaux précédents. Dans ce cadre, nous proposons de nouvelles fonctions de base qui permettent de réduire considérablement la variance par rapport aux techniques existantes. Nous montrons qu'un choix particulier d'une telle fonction - la ligne de base prédictive - est manifestement optimal dans certains schémas d'échantillonnage. Cela permet de calculer efficacement des estimations de valeur à variance nulle, même le long de trajectoires échantillonnées.