La boucle agent–environnement

L'apprentissage supervisé apprend à partir d'exemples étiquetés ; l'apprentissage par renforcement (RL) apprend à partir de conséquences. Un agent observe l'état \(s_t\) de son environnement, choisit une action \(a_t\), puis reçoit une récompense \(r_{t+1}\) et un nouvel état \(s_{t+1}\). Aucune « bonne réponse » n'est fournie : seul un signal scalaire, souvent rare et différé, guide l'apprentissage.

Un exemple fondateur : le tic-tac-toe

Sutton et Barto ouvrent leur livre avec un exemple d'une simplicité désarmante : apprendre à jouer au tic-tac-toe contre un adversaire imparfait, sans connaître sa stratégie. L'idée : attribuer à chaque configuration du plateau une valeur \(V(s)\) — la probabilité estimée de gagner depuis \(s\) — puis, après chaque coup glouton menant de \(s\) à \(s'\), rapprocher la valeur de départ de celle d'arrivée : \[V(s) \leftarrow V(s) + \alpha\,\big[V(s') - V(s)\big].\]

Cette petite règle contient déjà l'ADN du domaine : apprendre pendant l'interaction, sans modèle de l'adversaire, en propageant l'information des états terminaux (victoire = 1, défaite = 0) vers les états qui les précèdent. C'est la première mise à jour par différence temporelle — celle que nous retrouverons, généralisée, dans le Q-learning.

Bandits à k bras : explorer ou exploiter

Avant même de parler d'états, le dilemme central du RL se pose dans sa forme la plus pure : le bandit à k bras (Sutton & Barto, chap. 2). Une machine à sous à \(k\) leviers ; chaque levier \(a\) verse une récompense aléatoire de moyenne inconnue \(q_*(a)\). Quel levier tirer, sachant que chaque essai informe autant qu'il rapporte ?

L'estimateur naturel est la moyenne empirique des récompenses reçues : \[Q_t(a) = \frac{\sum_{i=1}^{t-1} R_i \,\mathbb{1}_{A_i = a}}{\sum_{i=1}^{t-1} \mathbb{1}_{A_i = a}},\] qui converge vers \(q_*(a)\) par la loi des grands nombres. La politique gloutonne \(A_t = \arg\max_a Q_t(a)\) exploite sans jamais explorer — et reste souvent bloquée sur un levier médiocre. La stratégie \(\varepsilon\)-gloutonne corrige cela en jouant au hasard avec probabilité \(\varepsilon\). Plus fine encore, la règle UCB (Upper Confidence Bound) explore en priorité ce qui est incertain : \[A_t = \arg\max_a \left[\, Q_t(a) + c\,\sqrt{\frac{\ln t}{N_t(a)}} \,\right],\] où \(N_t(a)\) compte les tirages du levier \(a\) : le bonus d'exploration fond à mesure que l'incertitude se résorbe.

Processus de décision markoviens

Le cadre mathématique standard est le processus de décision markovien (MDP), un quintuplet \((\mathcal{S}, \mathcal{A}, P, R, \gamma)\) : espace d'états, espace d'actions, noyau de transition \(P(s' \mid s, a)\), fonction de récompense \(R(s,a)\) et facteur d'actualisation. L'hypothèse de Markov exige que l'état résume tout le passé pertinent : \[\mathbb{P}(s_{t+1} \mid s_t, a_t, s_{t-1}, a_{t-1}, \ldots) = \mathbb{P}(s_{t+1} \mid s_t, a_t).\]

Une politique \(\pi(a \mid s)\) est une distribution sur les actions conditionnée par l'état. Résoudre un MDP, c'est trouver la politique \(\pi^*\) qui maximise le retour espéré — un problème d'optimisation sur un espace de fonctions, où le hasard des transitions rend l'objectif stochastique.

Fonctions de valeur et équations de Bellman

La fonction de valeur d'état mesure « à quel point il fait bon vivre » en \(s\) sous la politique \(\pi\) : \[V^\pi(s) = \mathbb{E}_\pi\!\left[\, G_t \mid s_t = s \,\right].\] La structure récursive du retour \(G_t = r_{t+1} + \gamma\, G_{t+1}\) donne immédiatement l'équation de Bellman : \[V^\pi(s) = \sum_a \pi(a \mid s) \sum_{s'} P(s' \mid s, a)\left[\, R(s,a) + \gamma\, V^\pi(s') \,\right].\]

Pour la politique optimale, la somme sur les actions devient un maximum — l'équation d'optimalité de Bellman : \[V^*(s) = \max_a \sum_{s'} P(s' \mid s, a)\left[\, R(s,a) + \gamma\, V^*(s') \,\right].\]

Itération sur les valeurs, en images

Quand le modèle \(P\) est connu, on peut appliquer \(\mathcal{T}\) de façon répétée : \(V_{k+1} = \mathcal{T}V_k\). C'est l'itération sur les valeurs, un pur exercice de programmation dynamique. Dans le monde-grille ci-dessous, la valeur « diffuse » depuis la case objectif (verte, \(+1\)) en contournant le piège (rouge, \(-1\)) et le mur, atténuée par \(\gamma\) à chaque pas. Une fois \(V^*\) obtenue, la politique gloutonne \(\pi^*(s) = \arg\max_a \mathbb{E}[R + \gamma V^*(s')]\) se lit directement — et l'agent la suit.

Q-learning : apprendre sans modèle

En pratique, \(P\) et \(R\) sont inconnus — on ne peut qu'interagir. La parade consiste à estimer la fonction de valeur état–action \(Q(s,a)\) directement à partir des transitions observées. Après chaque pas \((s_t, a_t, r_{t+1}, s_{t+1})\), le Q-learning effectue la mise à jour par différence temporelle : \[Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha \left[\, \underbrace{r_{t+1} + \gamma \max_{a'} Q(s_{t+1}, a')}_{\text{cible TD}} - Q(s_t, a_t) \,\right].\]

Deux idées se cachent ici. D'abord, c'est une approximation stochastique de l'équation d'optimalité de Bellman : on remplace l'espérance sur \(P\) par un échantillon. Ensuite, l'agent doit arbitrer entre exploration et exploitation — la stratégie \(\varepsilon\)-gloutonne choisit une action aléatoire avec probabilité \(\varepsilon\), qu'on fait décroître au fil des épisodes.

Cliff Walking : SARSA contre Q-learning

L'exemple 6.6 de Sutton & Barto rend la distinction on/off-policy visible. Un agent doit relier le départ S à l'objectif G en longeant une falaise : chaque pas coûte \(-1\), tomber dans la falaise coûte \(-100\) et renvoie instantanément au départ. SARSA met à jour avec l'action réellement choisie ensuite : \[Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha\big[r_{t+1} + \gamma\, Q(s_{t+1}, a_{t+1}) - Q(s_t, a_t)\big],\] là où le Q-learning utilise \(\max_{a'} Q(s_{t+1}, a')\).

Conséquence, tant que l'exploration \(\varepsilon\)-gloutonne est maintenue (\(\varepsilon = 0{,}1\)) : le Q-learning apprend la politique optimale — raser la falaise — mais ses embardées exploratoires le font régulièrement chuter, et son retour moyen en ligne est pire. SARSA, qui « sait » qu'il explore, apprend le chemin sûr par le haut. Optimalité de la politique apprise et performance pendant l'apprentissage sont deux choses distinctes — une leçon qui vaut bien au-delà des mondes-grilles, du trading algorithmique au contrôle industriel.

Vers le Deep RL

Une table \(Q(s,a)\) devient impraticable dès que l'espace d'états explose (images, systèmes continus, écoulements fluides…). Le Deep RL remplace la table par un réseau de neurones \(Q_\theta(s,a)\) ou une politique paramétrée \(\pi_\theta(a \mid s)\). Deux grandes familles dominent :

• Méthodes de valeur (DQN et descendants) : minimiser l'erreur de Bellman \(\; \mathcal{L}(\theta) = \mathbb{E}\big[(r + \gamma \max_{a'} Q_{\theta^-}(s',a') - Q_\theta(s,a))^2\big]\), stabilisée par un réseau cible \(\theta^-\) et un tampon de rejeu qui casse les corrélations temporelles.
• Méthodes de politique : monter le gradient de la performance \(\; \nabla_\theta J = \mathbb{E}\big[\nabla_\theta \log \pi_\theta(a \mid s)\, A^\pi(s,a)\big]\) (théorème du gradient de politique), où l'avantage \(A^\pi\) réduit la variance. PPO et ses variantes acteur–critique en sont les représentants modernes.

Le RL rejoint alors le contrôle optimal : l'équation de Bellman est la version en temps discret de l'équation de Hamilton–Jacobi–Bellman, et le Q-learning peut se lire comme une résolution stochastique et sans modèle de cette équation. C'est ce pont — programmation dynamique, approximation stochastique, optimisation non convexe — qui rend le domaine si riche mathématiquement. Pour une application concrète au contrôle d'écoulements, voir l'article compagnon sur l'apprentissage automatique fondé sur la physique.

Du backgammon à Go : trois jalons

TD-Gammon (Tesauro, 1992) fut le premier choc : un réseau de neurones entraîné par TD(\(\lambda\)) en jouant contre lui-même, parti de poids aléatoires, atteignit le niveau des meilleurs joueurs mondiaux de backgammon — au point de modifier la théorie humaine de certaines ouvertures. DQN (2015) appliqua le Q-learning profond à 49 jeux Atari, à partir des seuls pixels, avec un même réseau et les mêmes hyperparamètres, atteignant un niveau humain sur la majorité d'entre eux. AlphaGo puis AlphaGo Zero (2016–2017) combinèrent réseaux de politique et de valeur avec la recherche arborescente Monte-Carlo ; Zero, entraîné uniquement par auto-jeu, sans aucune partie humaine, surpassa toutes les versions précédentes.

Le fil conducteur de ces jalons (Sutton & Barto, chap. 16) est exactement celui de cet article : une fonction de valeur apprise par différence temporelle, une politique améliorée vis-à-vis de cette valeur, et l'auto-jeu comme générateur inépuisable d'expérience.

Reproduire ces animations avec Manim

Les animations ci-dessus tournent en direct dans le navigateur (canvas), mais leur esthétique vient de Manim. Voici un squelette ManimCE qui rend l'animation 2 en vidéo — à adapter et rendre avec manim -pqh rl_scenes.py ValueIteration :

# rl_scenes.py — itération sur les valeurs dans un monde-grille
from manim import *
import numpy as np

class ValueIteration(Scene):
    def construct(self):
        rows, cols, gamma = 5, 8, 0.9
        V = np.zeros((rows, cols)); V[1, 6] = 1.0; V[2, 6] = -1.0
        squares = VGroup(*[
            Square(0.75).move_to(RIGHT*(c-3.5)*0.8 + UP*(2-r)*0.8)
            for r in range(rows) for c in range(cols)
        ])
        self.play(Create(squares, lag_ratio=0.02))
        for sweep in range(12):
            V = self.bellman_sweep(V, gamma)          # V ← max_a E[R + γV']
            self.play(*[
                sq.animate.set_fill(
                    interpolate_color(BLUE_E, YELLOW, float(np.clip(v, 0, 1))),
                    opacity=0.85)
                for sq, v in zip(squares, V.flatten())
            ], run_time=0.5)
        self.wait()

Le dépôt Manim-Examples (scènes SquareToCircle, CreateGraph, displayEquations) fournit tous les gabarits nécessaires : self.play, Transform, Write pour les équations LaTeX, et le rendu Jupyter. Le dépôt officiel ManimCE ajoute une galerie complète (docs/source/examples.rst) et les scènes example_scenes/ — Axes, ValueTracker et always_redraw y suffisent pour reproduire le bandit et la falaise en vidéo.