Module 5 — Différence temporelle et Q-learning

Monte-Carlo attend la fin d'un épisode pour apprendre ; la programmation dynamique exige de connaître la dynamique. La différence temporelle — TD — combine le meilleur des deux : apprendre pas à pas, à partir d'échantillons, sans modèle. C'est l'idée centrale de tout le renforcement moderne, et le Q-learning en est l'incarnation la plus connue.

La mise à jour TD, en une ligne

À partir d'une transition observée $(s, a, r, s')$, l'estimation courante $V(s)$ est corrigée vers une cible qui utilise l'estimation existante de l'état suivant :

$$V(s) \leftarrow V(s) + \alpha \left[\underbrace{r + \gamma V(s')}_{\text{cible TD}} - V(s)\right]$$

Le terme entre crochets est l'erreur TD, $\delta = r + \gamma V(s') - V(s)$. C'est la seule chose qui compte : quand elle est positive, la valeur de $s$ était sous-estimée ; quand elle est négative, surestimée. Le pas $\alpha \in (0, 1]$ contrôle la vitesse d'ajustement.

Trois différences décisives avec Monte-Carlo. Pas besoin d'attendre la fin de l'épisode. Pas besoin de connaître $P$. La cible utilise une seule récompense et une estimation, ce qui réduit énormément la variance — au prix d'un biais qui disparaît en convergence.

SARSA et Q-learning : la différence qui compte

Sur les $Q$, deux algorithmes cousins existent, et leur différence tient à un seul terme.

SARSA — pour $(s, a, r, s', a')$ — apprend la politique qu'il joue réellement, y compris son exploration :

$$Q(s, a) \leftarrow Q(s, a) + \alpha \left[r + \gamma\, Q(s', a') - Q(s, a)\right]$$

Q-learning apprend la politique optimale, indépendamment de la politique jouée :

$$Q(s, a) \leftarrow Q(s, a) + \alpha \left[r + \gamma \max_{a'} Q(s', a') - Q(s, a)\right]$$

La différence est le max sur $a'$. SARSA utilise l'action qui sera effectivement jouée ensuite (souvent une exploration aléatoire) ; Q-learning utilise l'action optimale selon $Q$, qu'elle soit jouée ou non. Cette petite différence a une grande conséquence.

Sur politique contre hors politique

SARSA est sur politique (on-policy) : la politique évaluée est la politique jouée. Q-learning est hors politique (off-policy) : il évalue la politique gloutonne alors qu'il joue une politique exploratoire.

Le célèbre exemple du cliff walking l'illustre. Un agent doit longer un précipice pour atteindre un objectif ; tomber coûte -100. Q-learning apprend le chemin optimal, qui longe le bord au plus près. SARSA, en tenant compte de son exploration $\varepsilon$-gloutonne qui peut le faire tomber occasionnellement, apprend un chemin plus éloigné du bord — sous-optimal en théorie, mais plus sûr en pratique.

Aucun des deux n'est meilleur dans l'absolu. Quand l'agent final n'explorera plus (déploiement), Q-learning est le bon choix. Quand la politique reste exploratoire à cause du bruit du monde, SARSA est plus fiable.

Q-learning tabulaire sur FrozenLake

import numpy as np
import gymnasium as gym

env = gym.make("FrozenLake-v1", is_slippery=True)
nS, nA = env.observation_space.n, env.action_space.n

Q = np.zeros((nS, nA))
alpha = 0.1
gamma = 0.99
epsilon = 1.0
epsilon_min = 0.05
decroissance = 0.9995

recompenses = []

for episode in range(20_000):
    s, _ = env.reset(seed=episode)
    total = 0.0
    while True:
        if np.random.rand() < epsilon:
            a = np.random.randint(nA)                # exploration
        else:
            a = int(np.argmax(Q[s]))                 # exploitation
        s2, r, termine, tronque, _ = env.step(a)
        # Mise a jour Q-learning : on utilise le max, pas l'action reellement jouee ensuite
        cible = r + (0 if termine else gamma * np.max(Q[s2]))
        Q[s, a] += alpha * (cible - Q[s, a])
        s = s2
        total += r
        if termine or tronque:
            break
    recompenses.append(total)
    epsilon = max(epsilon_min, epsilon * decroissance)

# Politique gloutonne finale
politique = np.argmax(Q, axis=1)

Une centaine de lignes qui résolvent un MDP inconnu de l'agent. La courbe de récompense par épisode monte lentement, avec beaucoup de bruit dû à la glissance, puis se stabilise autour du taux de succès de la politique optimale.

Les deux hyperparamètres à connaître

Le taux d'apprentissage $\alpha$ contrôle la vitesse d'oubli du passé. Trop élevé, chaque nouvelle transition efface les anciennes estimations. Trop faible, la convergence traîne. Les valeurs usuelles vont de 0,01 à 0,3 ; la décroissance progressive de $\alpha$ garantit la convergence en théorie mais est peu utilisée en pratique.

L'actualisation $\gamma$ n'est pas un simple paramètre d'algorithme : elle change le problème. Passer $\gamma$ de 0,9 à 0,999 sur FrozenLake déplace le compromis entre chemin court et chemin sûr. Ne pas la choisir au hasard — elle traduit une préférence temporelle réelle du concepteur.

Ce que l'erreur TD révèle

Tracer la norme moyenne de l'erreur TD par épisode. Sur un problème sain, elle décroît et se stabilise près de zéro. Une erreur TD qui reste grande signale, soit un taux d'apprentissage trop faible pour rattraper les changements, soit une politique qui varie encore trop pour être proche de son point fixe. C'est un des rares diagnostics fiables du renforcement tabulaire.

En résumé

• La mise à jour TD corrige $V(s)$ par $\alpha (r + \gamma V(s') - V(s))$ ; elle apprend pas à pas, sans modèle, sans attendre la fin de l'épisode.
• SARSA apprend la politique qu'il joue (sur politique) ; Q-learning apprend la politique optimale via un max (hors politique).
• Sur cliff walking, Q-learning trouve le chemin optimal, SARSA un chemin plus prudent — le bon choix dépend de la présence d'exploration au déploiement.
• Le taux d'apprentissage $\alpha$ et l'actualisation $\gamma$ dominent les autres réglages ; $\gamma$ change le problème et se choisit en priorité.

Module suivant : la question laissée en suspens, comment décider entre exploration et exploitation à chaque pas.