Les méthodes de l'arène, expliquées

TD(λ) : apprendre de proche en proche

Valeur · Sutton (1988), Tesauro (1994) · Puissance 4

L'idée. Pour savoir si une position est bonne, on n'attend pas la fin de la partie : on compare son estimation à celle de la position suivante. Si la suivante semble meilleure qu'on ne le croyait, la position actuelle l'était aussi. C'est la différence temporelle. Le λ décide jusqu'où l'erreur remonte dans le passé : avec λ = 0, seule la position précédente est corrigée ; avec λ = 1, toutes celles de la partie, comme si on attendait le résultat final.

La règle

δ = r + γ·V(s') − V(s)          erreur de différence temporelle
e ← γ·λ·e + ∇V(s)               trace d'éligibilité : qui a contribué récemment ?
w ← w + α·δ·e                   chaque poids est corrigé selon sa part de responsabilité

Dans l'arène

Le réseau joue contre lui-même (self-play), comme TD-Gammon. V(s) note la position du point de vue du joueur qui doit y jouer, entre −1 et +1. Le trait changeant à chaque coup, la cible de V(sₜ) est −V(sₜ₊₁), ou le résultat si le coup finit la partie. Un seul réseau sert donc aux deux camps. Pour jouer, on choisit le coup qui laisse la pire position à l'adversaire, avec une part ε de coups au hasard pendant l'entraînement.

Pour aller plus loin : Sutton et Barto, chapitres 6 et 12 (livre gratuit) · Sutton, « Learning to predict by the methods of temporal differences » (1988) · Tesauro, « Temporal difference learning and TD-Gammon » (1995) · le code du Puissance 4 expliqué.

Le réseau n-tuple : une table plutôt qu'un réseau

Valeur · Szubert et Jaśkowski (2014) · 2048

L'idée. Pas de neurones : on découpe le plateau en petits groupes de 4 cases, et chaque configuration possible d'un groupe a sa propre case dans une table. La valeur d'un plateau est la somme des cases lues. Apprendre, c'est corriger ces nombres. Les tables sont énormes, mais chaque mise à jour ne touche qu'une poignée de cases : c'est très rapide.

La règle

V(plateau) = Σ_groupes Σ_symétries  table_groupe[ adresse(4 tuiles) ]
on joue    a = argmax_a  points(a) + V(après-état(a))
puis       V(après-état) ← V(après-état) + α·( points' + V(après-état') − V(après-état) )

Dans l'arène

Cinq groupes de 4 cases (les deux premières lignes, trois carrés 2 × 2), chacun lu dans les 8 symétries du plateau qui partagent la même table : ce qui est appris dans un coin sert dans les autres. 5 tables de 65 536 nombres. La valeur porte sur l'après-état (le plateau juste après le glissement, avant l'apparition de la nouvelle tuile) : le hasard de la tuile n'entre ainsi pas dans le choix du coup. Pas d'exploration ajoutée : le hasard des tuiles suffit, comme dans l'article.

Pour aller plus loin : Szubert et Jaśkowski, « Temporal difference learning of N-tuple networks for the game 2048 » (2014) · Jaśkowski, « Mastering 2048 with delayed temporal coherence learning… » (2016) · la page du 2048.

DQN : la valeur de chaque action, apprise sur une mémoire

Valeur, hors-politique · Mnih et al. (2015), van Hasselt et al. (2016) · Snake, 2048

L'idée. Un réseau prend l'état et rend Q(s, a) pour chaque action : on joue la plus haute. C'est le Q-learning des années 1990, avec un réseau à la place d'une table, et deux astuces qui l'empêchent de diverger : une mémoire de rejeu (on apprend sur des transitions tirées au hasard dans le passé, pas sur la dernière seulement) et un réseau cible qui évolue lentement et fournit des cibles stables.

La règle (double DQN)

a* = argmax_a Q(s', a)                        le réseau appris choisit l'action…
y  = r + γ·Q_cible(s', a*)                     …le réseau cible l'évalue (0 si la partie est finie)
perte = Huber( Q(s, a) − y )                   sur un lot tiré dans la mémoire
Q_cible ← τ·Q + (1 − τ)·Q_cible               moyenne glissante

Séparer celui qui choisit et celui qui évalue, c'est le « double » : le DQN d'origine surestime systématiquement les valeurs, parce que le max d'estimations bruitées est biaisé vers le haut.

Dans l'arène

Exploration ε-gloutonne : ε part de 1 (tout au hasard) et descend à 0,02 sur les premiers 10 % du budget. Les actions interdites (au 2048, un coup qui ne bouge rien) sont masquées partout : au choix du coup, dans l'exploration et dans le max de la cible. Perte de Huber, optimiseur Adam.

Pour aller plus loin : Mnih et al., « Human-level control through deep reinforcement learning » (Nature, 2015) et la version 2013 · van Hasselt et al., « Deep RL with double Q-learning » · docs Stable-Baselines3 et CleanRL (implémentation en un fichier, commentée).

PPO : corriger la politique, mais pas trop

Acteur-critique, sur-politique · Schulman et al. (2017) · course, Snake, atterrissage

L'idée. On apprend directement la politique : rendre plus probables les actions qui ont mieux marché que prévu, moins probables les autres. Le « mieux que prévu » est l'avantage A = retour obtenu − V(s), donné par un second réseau, le critique. Le danger est de trop corriger d'un coup et de détruire une politique qui marchait : PPO rogne (clip) la correction dès que la nouvelle politique s'éloigne de plus de 20 % de l'ancienne.

La règle

ρ = π_nouveau(a | s) / π_ancien(a | s)
objectif = moyenne( min( ρ·A ,  clip(ρ, 1 − ε, 1 + ε)·A ) )      ε = 0,2
critique : minimise ( V(s) − retour )²
avantage : GAE(λ),  Â = Σₖ (γλ)ᵏ δₜ₊ₖ   avec  δₜ = rₜ + γ·V(sₜ₊₁) − V(sₜ)

Pseudo-code

répéter jusqu'au budget :
    jouer N pas avec la politique actuelle (le « lot »)
    calculer les avantages GAE et les retours
    faire K passes sur le lot, par mini-lots :
        monter le gradient de l'objectif rogné (acteur)
        descendre l'erreur de valeur (critique)
    jeter le lot

Dans l'arène

Acteur et critique sont deux réseaux séparés. Actions discrètes (Snake) : softmax sur des logits, avec masquage. Actions continues (course, atterrissage) : une gaussienne dont l'acteur donne la moyenne et dont l'écart-type est appris mais indépendant de l'état. Observations normalisées en continu. Une fois entraînée, la politique joue sans hasard : l'action la plus probable, ou la moyenne de la gaussienne. C'est ce que rejoue le navigateur.

Pour aller plus loin : Schulman et al., « Proximal Policy Optimization Algorithms » · Schulman et al., GAE · Spinning Up (OpenAI) · « The 37 implementation details of PPO », indispensable si vous l'écrivez vous-même · docs Stable-Baselines3 et CleanRL · Lilian Weng, « Policy Gradient Algorithms ».

SAC : un acteur-critique qui aime l'imprévu

Acteur-critique, hors-politique, actions continues · Haarnoja et al. (2018) · atterrissage

L'idée. Comme DQN, on garde une mémoire de rejeu et on apprend un critique Q(s, a) ; comme PPO, un acteur produit l'action. La nouveauté : l'acteur ne maximise pas seulement la récompense, mais récompense + α × entropie. Il est payé pour rester imprévisible tant que ça ne coûte rien, ce qui le pousse à explorer, et la température α s'ajuste toute seule.

La règle

critiques : y = r + γ·( min(Q1_cible, Q2_cible)(s', a') − α·log π(a' | s') ),   a' ~ π(· | s')
acteur    : minimise  α·log π(a | s) − min(Q1, Q2)(s, a),   a = tanh(μ(s) + σ(s)·bruit)
température : α monte si l'entropie passe sous la cible (− nombre de dimensions d'action)

Dans l'arène

Deux critiques dont on prend le minimum, contre la surestimation (la même idée que le double DQN), avec leurs copies cibles en moyenne glissante. L'acteur est une gaussienne « écrasée » par tanh, pour rester dans [−1, 1]. Le gradient de Q par rapport à l'action traverse le critique, puis tanh, puis la moyenne et l'écart-type : c'est l'« astuce de reparamétrisation ». Une fois entraîné, l'acteur joue tanh(μ), sans hasard.

Pour aller plus loin : Haarnoja et al., « Soft Actor-Critic » (2018) et « SAC Algorithms and Applications », qui ajoute le réglage automatique de α · Spinning Up · docs Stable-Baselines3 et CleanRL · le jeu qui a inspiré l'atterrissage : LunarLander (Gymnasium).

AlphaZero : apprendre à chercher

Recherche + apprentissage · Silver et al. (2017, 2018) · Puissance 4

L'idée. Un réseau donne, pour une position, une politique (quels coups ont l'air bons) et une valeur (qui va gagner). Au moment de jouer, une recherche arborescente Monte-Carlo (MCTS) explore les coups en suivant ces indications. La recherche joue mieux que le réseau seul : on entraîne alors le réseau à imiter la recherche, et le résultat de la partie à corriger la valeur. Le réseau s'améliore, donc la recherche aussi, et ainsi de suite.

La règle

choix dans l'arbre (PUCT) : argmax_a  Q(s, a) + c_puct · P(s, a) · √N(s) / (1 + N(s, a))
cible de politique        : π = visites de chaque coup à la racine, normalisées
cible de valeur           : z = résultat final de la partie (+1, 0, −1)
perte = entropie_croisée(π, P) + (z − V)²

Dans l'arène

Version « lite » : un petit perceptron au lieu d'un réseau convolutif résiduel, et peu de simulations par coup. Bruit de Dirichlet à la racine pendant le self-play, pour explorer ; les premiers coups sont tirés selon les visites plutôt que joués au mieux. Le budget compte les coups joués, comme pour les autres méthodes, mais les simulations du MCTS sont publiées à part : c'est là qu'est le vrai coût de calcul. Un témoin « AlphaZero non entraîné » (même recherche, réseau au hasard) dit ce que la recherche apporte seule.

Pour aller plus loin : Silver et al., « Mastering the game of Go without human knowledge » (Nature, 2017) · Silver et al., « Mastering Chess and Shogi by Self-Play… » (2017) · Browne et al., « A Survey of Monte Carlo Tree Search Methods » (2012) · pour l'alpha-bêta, autre recherche de l'arène : Chess Programming Wiki.

NEAT : faire évoluer les réseaux, forme comprise

Neuroévolution, sans gradient · Stanley et Miikkulainen (2002) · les cinq jeux

L'idée. Une population de réseaux joue ; les meilleurs ont des enfants, avec des mutations sur les poids mais aussi sur la forme : ajout d'un neurone, d'une connexion. On part de réseaux minimaux, qui ne grossissent que si ça paie. Pour protéger une innovation (un nouveau neurone, d'abord mal réglé), la population est découpée en espèces de réseaux semblables qui ne se font concurrence qu'entre eux.

Pseudo-code

population = réseaux minimaux (entrées reliées aux sorties)
répéter jusqu'au budget :
    jouer quelques épisodes avec chaque réseau → fitness
    regrouper en espèces (distance entre génomes)
    dans chaque espèce : garder les meilleurs, croiser, muter (poids, neurones, connexions)

Dans l'arène

neat-python 0.92, comme le reste du dépôt. Jeux à un joueur : le réseau est une politique, sa sortie la plus forte donne l'action (jeu discret) ou ses sorties sont les commandes (jeu continu) ; fitness = retour moyen sur quelques épisodes, dont les graines changent à chaque génération mais sont communes à toute la génération, pour que la comparaison soit juste. Puissance 4 : le réseau note les positions, fitness = points marqués contre un petit panel d'adversaires fixes. Tous les pas joués par tous les génomes comptent dans le budget : c'est pourquoi NEAT ne fait que quelques générations quand les parties sont longues.

Pour aller plus loin : Stanley et Miikkulainen, « Evolving Neural Networks through Augmenting Topologies » (2002, PDF) · documentation de neat-python · les autres jeux du site, tous appris par NEAT : les jeux des pandas.

CMA-ES : tâtonner, en apprenant dans quelles directions

Stratégie d'évolution, sans gradient · Hansen et Ostermeier (2001) · course, atterrissage

L'idée. Le réseau a une forme fixe ; on cherche seulement ses poids. On tire une population de jeux de poids autour d'une moyenne, selon une gaussienne. Les meilleurs déplacent la moyenne, et surtout déforment la gaussienne (sa matrice de covariance) : elle s'étire dans les directions qui ont payé et se resserre dans les autres. C'est presque un gradient du second ordre, estimé sans jamais dériver.

Pseudo-code

m = poids initiaux, σ = pas, C = identité
répéter :
    tirer λ candidats  xᵢ = m + σ·N(0, C)
    les noter sur des épisodes entiers, trier
    m ← moyenne pondérée des μ meilleurs
    C ← adapter vers les pas qui ont réussi (chemin d'évolution + rang μ)
    σ ← agrandir si les pas successifs vont dans le même sens, réduire sinon

Dans l'arène

Réglages par défaut de Hansen (taille de population 4 + 3 ln n pour n poids, pondération, vitesses d'adaptation) ; seuls le pas initial σ, la taille du réseau et le nombre d'épisodes par candidat sont réglés. Un petit perceptron (une couche cachée de 8 ou 16 neurones) : C est une matrice de la taille du nombre de poids au carré, ce qui interdit les grands réseaux.

Pour aller plus loin : Hansen, « The CMA Evolution Strategy: A Tutorial » (2016) · page de référence de CMA-ES (codes dans de nombreux langages, dont pycma) · Salimans et al., « Evolution Strategies as a Scalable Alternative to Reinforcement Learning » (2017).

ARS : la méthode la plus simple qui puisse marcher

Recherche aléatoire, sans gradient · Mania, Guy et Recht (2018) · course

L'idée. Une politique linéaire (action = matrice × observation normalisée). On essaie des perturbations au hasard des poids, chacune dans les deux sens (+ et −), et on avance dans la direction des perturbations qui ont fait la plus grande différence. L'article montrait que ce presque-rien rivalise avec les méthodes à gradient sur la locomotion MuJoCo : l'arène vérifie si c'est vrai ici.

La règle (V2-t)

tirer N directions δᵢ ;  rᵢ⁺ = retour(M + ν·δᵢ),  rᵢ⁻ = retour(M − ν·δᵢ)
garder les b directions où max(rᵢ⁺, rᵢ⁻) est le plus grand
M ← M + α / (b · σ_r) · Σ (rᵢ⁺ − rᵢ⁻)·δᵢ           σ_r = écart-type des retours gardés

Pour aller plus loin : Mania, Guy et Recht, « Simple random search provides a competitive approach to reinforcement learning » (2018) · la page de la course.

Les références, qui n'apprennent rien

Recherche et algorithmes écrits à la main · les cinq jeux

Toute la connaissance de ces joueurs est dans leur code. Ils ne s'améliorent pas en jouant, mais ils disent ce que vaut l'apprentissage : battre le hasard est facile, battre quelqu'un qui connaît le problème ne l'est pas.

Alpha-bêta (Puissance 4)

Le principe. On essaie tous ses coups, puis toutes les réponses de l'adversaire, et ainsi de suite jusqu'à une profondeur fixée (2, 4 ou 6 coups dans l'arène). Au bout, une formule écrite à la main note la position : des poids par case (le centre vaut plus que les bords) et 40 points par case gagnante disponible. On suppose que chacun joue au mieux pour lui : c'est le minimax, écrit ici sous sa forme négamax (la note d'un camp est l'opposé de celle de l'autre). L'élagage alpha-bêta évite d'explorer les branches dont on sait déjà qu'elles ne changeront pas le choix, ce qui permet, avec un bon ordre des coups, d'aller jusqu'à deux fois plus profond pour le même temps.

négamax(position, profondeur, α, β) :
    si un coup gagne tout de suite : renvoyer « gagné »
    si profondeur = 0 : renvoyer heuristique(position)
    pour chaque coup, du centre vers les bords :
        note = −négamax(position + coup, profondeur − 1, −β, −α)
        α = max(α, note)
        si α ≥ β : arrêter (l'adversaire n'entrera jamais dans cette branche)
    renvoyer la meilleure note

Ce n'est pas le solveur : à faible profondeur il se trompe, et c'est tout l'intérêt de la comparaison. Le solveur exact, qui sert de juge, explore l'arbre jusqu'au bout.

Pour aller plus loin : minimax et élagage alpha-bêta (Wikipédia) · négamax et alpha-bêta (Chess Programming Wiki) · le tutoriel du solveur de Puissance 4 de Pascal Pons.

MCTS (Puissance 4)

Le principe. Aucune formule de notation : pour juger un coup, on joue des parties au hasard jusqu'au bout et on compte les victoires. L'astuce est de ne pas répartir ces parties également : on construit un arbre, et à chaque simulation on descend vers les coups qui gagnent souvent, sans oublier ceux qu'on a peu essayés. C'est la règle UCT, un compromis entre exploiter et explorer.

répéter S fois (200 ou 800 dans l'arène) :
    descendre dans l'arbre : choisir l'enfant qui maximise  victoires/n + c·√(ln N / n)
    ajouter un coup jamais essayé
    finir la partie au hasard
    remonter le résultat le long du chemin
jouer le coup le plus visité

C'est la même recherche qu'AlphaZero, sans le réseau : comparer les deux mesure ce que le réseau appris apporte.

Pour aller plus loin : Kocsis et Szepesvári, « Bandit Based Monte-Carlo Planning » (2006), l'article d'UCT · Browne et al., « A Survey of Monte Carlo Tree Search Methods » (2012) · Wikipédia.

Expectimax (2048)

Le principe. Comme l'alpha-bêta, mais l'adversaire est le hasard : après chaque coup, on ne prend pas la pire tuile possible, on fait la moyenne sur toutes les tuiles qui peuvent apparaître (un 2 dans 90 % des cas, un 4 dans 10 %, sur chaque case vide). Les branches trop improbables (probabilité sous 1/10 000) ne sont pas explorées. Au bout, le plateau est noté par l'heuristique du solveur de nneonneo : cases vides, fusions possibles, lignes rangées dans l'ordre, pénalité sur les grosses tuiles.

max(plateau, p)    = max sur les coups  de  hasard(plateau après le coup, p)
hasard(plateau, p) = moyenne sur les cases vides de
                     0,9 · max(plateau + 2, p·0,9/n) + 0,1 · max(plateau + 4, p·0,1/n)
au bout de la profondeur (1 ou 2 coups), ou si p < 0,0001 : heuristique(plateau)

Pour aller plus loin : expectiminimax (Wikipédia, en anglais) · le solveur 2048-ai de nneonneo, dont l'heuristique est reprise.

Le cycle hamiltonien (Snake)

Le principe. Un circuit fermé qui passe exactement une fois par chaque case de la grille : ici, des allers-retours ligne par ligne, avec retour par la première colonne. Le serpent le suit aveuglément. Comme sa queue avance devant lui sur le même circuit, il ne peut jamais se mordre : il remplit toujours la grille, mais il peut devoir faire le tour complet pour chaque pomme.

Pour aller plus loin : graphe hamiltonien (Wikipédia).

Le glouton (Snake)

Le principe. Le plus court chemin vers la pomme, trouvé par un parcours en largeur (le corps est compté comme un mur fixe). S'il n'y en a pas, il va vers la case voisine qui laisse le plus de place libre. Il ne pense jamais au coup d'après la pomme : rapide au début, il finit par s'enfermer dans ses propres anneaux.

Pour aller plus loin : parcours en largeur (Wikipédia).

Le pilote de trajectoire (course)

Le principe. Il triche à sa façon : il lit la ligne centrale du circuit et sa courbure, que les IA ne voient jamais (elles n'ont que leurs capteurs). Pour la direction, il vise un point de la ligne centrale situé d'autant plus loin qu'il roule vite : c'est la poursuite pure des robots mobiles. Pour la vitesse, il cherche le virage le plus serré des prochains mètres et roule à la plus grande vitesse qui permet de le prendre sans dépasser l'adhérence (v² × courbure ≤ adhérence), avec une marge.

Pour aller plus loin : Coulter, « Implementation of the Pure Pursuit Path Tracking Algorithm » (Carnegie Mellon, 1992).

Le correcteur PID (atterrissage)

Le principe. Un correcteur PID corrige une erreur avec trois termes : Proportionnel à l'erreur, Intégral (la somme des erreurs passées, qui compense une poussée constante comme le vent), Dérivé (la vitesse de l'erreur, qui freine avant de dépasser). C'est ce qui pilote réellement les drones et les fusées. Ici, trois boucles emboîtées :

• horizontal : l'inclinaison voulue dépend de l'écart à la plateforme et de la vitesse horizontale ;
• rotation : les moteurs latéraux ramènent l'engin vers cette inclinaison ;
• vertical : la vitesse de descente voulue diminue près du sol et tant que l'engin est loin de la plateforme ; le moteur principal compense la gravité, plus une correction de vitesse.

Ses gains ont eu droit à 8 essais de réglage, comme les IA.

Pour aller plus loin : régulateur PID (Wikipédia).