Résumé Technique : Réexamen de l'Optimisation de Politique Régularisée pour un Apprentissage par Renforcement Stable et Efficace dans les Jeux à Deux Joueurs

Énoncé du Problème

Les jeux à deux joueurs à somme nulle, en particulier les jeux de plateau, ont servi de références traditionnelles pour l'apprentissage par renforcement (RL). Bien que les méthodes basées sur la recherche, telles qu'AlphaZero (Silver et al., 2018), aient atteint des performances surhumaines en combinant des réseaux de neurones profonds avec une recherche à l'avance (par exemple, la recherche d'arbre Monte-Carlo, MCTS), elles engendrent des coûts computationnels substantiels. L'entraînement d'AlphaZero, par exemple, nécessiterait selon les rapports plus de 10 années-GPU (Silver et al., 2018 ; Tian et al., 2019). Cette intensité des ressources entrave la reproductibilité et l'application pratique dans des environnements aux ressources limitées (Zhao et al., 2022).

Bien que des études récentes aient tenté de réduire la charge computationnelle des méthodes basées sur la recherche en limitant la profondeur de l'arbre ou le nombre de simulations (rollouts) (Hessel et al., 2021 ; Danihelka et al., 2022), elles reposent toujours fondamentalement sur la recherche à l'avance. À l'inverse, les méthodes de RL sans modèle (model-free), qui sont efficaces en robotique et dans le contrôle continu, n'ont pas été pleinement explorées dans les jeux de plateau en raison d'une instabilité perçue dans les contextes d'auto-jeu multi-agents. La question centrale abordée par ce travail est la suivante : Un algorithme de RL purement sans modèle peut-il atteindre un apprentissage stable et compétitif dans les jeux à deux joueurs avec des ressources d'entraînement significativement inférieures à celles des méthodes basées sur la recherche ?

Méthodologie

Les auteurs proposent KLENT (Optimisation de Politique Régularisée par KL et Entropie), un algorithme de RL sans modèle qui élimine le besoin de MCTS pendant l'entraînement. L'approche repose sur la réévaluation de l'optimisation de politique régularisée avec deux composantes spécifiques : la régularisation de Kullback-Leibler (KL) inverse et la régularisation par entropie.

1. Règle de Mise à Jour de la Politique

Le cœur de KLENT est un problème d'optimisation de politique régularisée défini comme suit :
$$\max_{\pi'} \mathbb{E}_{A \sim \pi'(\cdot|s)}[Q^\pi(s, A)] - \beta D_{KL}(\pi'(\cdot|s) \parallel \pi(\cdot|s)) + \alpha H(\pi'(\cdot|s))$$
où :

• $\pi'$ est la nouvelle politique, et $\pi$ est la politique antérieure.
• $D_{KL}(\pi' \parallel \pi)$ est la divergence KL inverse, favorisant des mises à jour de politique progressives pour gérer la non-stationnarité dans l'auto-jeu.
• $H(\pi')$ est l'entropie, encourageant une exploration soutenue pour prévenir le surapprentissage à la politique de l'agent lui-même.
• $\alpha$ et $\beta$ sont des hyperparamètres non négatifs.

Étant donné l'espace d'actions fini des jeux de plateau, la politique optimale $\pi'$ admet une solution analytique sous forme fermée :
$$\pi'(a|s) = \frac{1}{Z(s)} \exp\left( \frac{Q^\pi(s, a) + \beta \log \pi(a|s)}{\alpha + \beta} \right)$$
Dans KLENT, un réseau de neurones $\pi_\theta$ est entraîné pour minimiser l'entropie croisée entre sa sortie et cette cible $\pi'$ dérivée analytiquement.

2. Apprentissage de la Fonction de Valeur

Contrairement aux méthodes basées sur la recherche qui estiment les valeurs d'actions via des retours MCTS, KLENT paramétrise directement la fonction de valeur d'action $Q^\pi(s, a)$ à l'aide d'un réseau de neurones. Pour stabiliser l'apprentissage et gérer le compromis biais-variance, l'algorithme utilise les retours $\lambda$ ($G^\lambda$) comme cible d'apprentissage pour la fonction de valeur, plutôt que les retours Monte Carlo standard ($\lambda=1$). Des expériences préliminaires ont indiqué qu'un $\lambda$ intermédiaire $\in (0, 1)$ minimise la somme du biais au carré et de la variance mieux que $\lambda=1$.

3. Structure de l'Algorithme

KLENT alterne entre une phase d'auto-jeu (collecte de données sur la politique) et une phase d'ajustement (mise à jour des paramètres du réseau). La fonction de perte optimise simultanément les réseaux de politique et de valeur d'action :
$$L(\theta) = \mathbb{E}_D \left[ -\sum_{a \in A} \pi'(a|S) \log \pi_\theta(a|S) + (Q_\theta(S, A) - G^\lambda)^2 \right]$$
Crucialement, KLENT ne nécessite aucune recherche d'arbre pendant l'entraînement, reposant uniquement sur les prédictions du réseau de neurones et la mise à jour analytique de la politique.

Contributions Clés

L'article fait trois contributions principales, se concentrant sur la caractérisation théorique et empirique de cette combinaison spécifique de régularisation plutôt que sur la proposition d'ingrédients algorithmiques entièrement nouveaux :

1. Formulation Algorithmique : Les auteurs dérivent un algorithme de RL sans modèle pratique (KLENT) basé sur la combinaison de la régularisation KL inverse et de la régularisation par entropie, fournissant une règle de mise à jour de politique sous forme fermée.
2. Garanties Théoriques : De nouvelles garanties de convergence sont fournies pour la règle de mise à jour de la politique dans deux contextes :
   • Jeux sous forme normale : L'article prouve une convergence linéaire locale vers un point fixe unique sous la condition $\alpha(\alpha + 2\beta) > \|R\|_2^2/4$. Cette condition couvre une plage plus large de coefficients de régularisation que les résultats précédents (par exemple, Sokota et al., 2022).
   • Jeux de longueur finie : Les auteurs prouvent que la politique KLENT converge vers une politique optimale régularisée par l'entropie (Équilibre de Réponse Quantale) par induction arrière, en supposant un horizon de jeu fini.
3. Validation Empirique : Des expériences approfondies sur cinq jeux de plateau (Shogi Animal, Échecs Gardner, Go 9x9, Hex et Othello) démontrent que KLENT atteint une efficacité d'entraînement significativement supérieure aux méthodes basées sur la recherche et aux références sans modèle existantes.

Résultats

Efficacité de l'Entraînement

Les expériences montrent que KLENT apprend plus efficacement que les méthodes existantes dans tous les environnements testés.

• Gain de Performance : En moyenne, KLENT a atteint une efficacité d'entraînement jusqu'à 4 fois supérieure par rapport à Gumbel AlphaZero (la référence basée sur la recherche la plus forte de l'étude). Par exemple, Gumbel AlphaZero nécessitait 300 millions d'évaluations de simulateur pour atteindre un taux de victoire de 50 %, alors que KLENT n'en nécessitait que 75 millions.
• Évolutivité : L'écart d'efficacité s'élargit dans les jeux avec des facteurs de branchement plus élevés (par exemple, Go 9x9, Hex), où les méthodes basées sur la recherche nécessitent des budgets de simulateur substantiels. L'avantage de KLENT est attribué à l'évitement de la recherche à l'avance et à l'utilisation de retours $\lambda$ stables.
• Performance à Grande Échelle : Dans le Go 19x19, KLENT a maintenu une efficacité d'apprentissage compétitive par rapport à AlphaZero, malgré la complexité accrue.

Études d'Ablation

L'étude valide la nécessité de trois techniques clés :

• Régularisation KL Inverse : Le retrait de celle-ci (en fixant $\beta=0$) conduit à des mises à jour de politique abruptes et à une dégradation des performances, en particulier dans le Go 9x9.
• Régularisation par Entropie : Le retrait de celle-ci (en fixant $\alpha=0$) provoque une politique devenant trop déterministe (l'entropie chute près de zéro), entraînant un apprentissage instable et un effondrement des performances.
• Retours $\lambda$ : Le remplacement des retours $\lambda$ par des retours à une étape ou des retours Monte Carlo a entraîné une baisse de performance, confirmant l'importance de l'équilibre entre biais et variance.

Performance au Moment du Test

Lorsqu'ils sont équipés de MCTS au moment du test (800 simulations), les agents KLENT ont atteint des taux de victoire élevés contre les références, surpassant AlphaZero et Gumbel AlphaZero dans des matchs directs sur le Go 9x9 et le Go 19x19.

Signification et Revendications

Les auteurs positionnent ce travail comme une démonstration que réexaminer correctement les techniques de régularisation existantes peut conduire à un apprentissage stable et efficace dans des domaines longtemps dominés par les méthodes basées sur la recherche.

• Revendications Modérées : L'article indique explicitement que sa contribution principale n'est pas un nouvel ingrédient algorithmique, mais une nouvelle caractérisation théorique et empirique de l'optimisation de politique régularisée dans les jeux à deux joueurs.
• Limites : Les auteurs reconnaissent que, bien que KLENT atteigne une haute efficacité, il ne garantit pas nécessairement une performance asymptotique supérieure lorsque des ressources computationnelles illimitées sont disponibles. Ils n'excluent pas l'efficacité des approches basées sur la recherche comme AlphaZero lorsque des ressources massives (par exemple, des milliers de GPU) sont accessibles.
• Impact Plus Large : Les auteurs suggèrent que l'hypothèse sous-jacente (MDP à actions finies) s'applique à des problèmes réels tels que l'optimisation discrète, la découverte algorithmique et la preuve mathématique, où les méthodes basées sur la recherche sont actuellement prédominantes. Ils espèrent que ce travail encouragera l'extension de telles approches sans modèle et efficaces à d'autres domaines.

En résumé, KLENT offre une alternative computationnellement efficace au RL basé sur la recherche pour les jeux de plateau, atteignant des performances compétitives avec une fraction des ressources d'entraînement en exploitant la stabilité de la régularisation KL inverse et de la régularisation par entropie.