Apprenez de l'expérience avec Monte-Carlo et TD

Dans la partie 1, le robot du lac gelé avait un avantage énorme : il connaissait la carte et les probabilités de glissade. Un vrai robot n’a pas ce luxe. Il doit jouer, observer ce qui arrive, et en tirer des conclusions. Comment estimer la valeur d’une politique quand on ne peut plus calculer $\sum_{s'} P(s' \mid s, a) [\dots]$ ?

La réponse tient en un mot : échantillonner. Au lieu de calculer une espérance exacte, on la remplace par une moyenne d’expériences. Ce chapitre présente les deux grandes façons de le faire, Monte-Carlo et les différences temporelles, sur le problème de la prédiction : estimer $V^\pi$ pour une politique fixée.

Attention

Cette partie 2 va au-delà de notre TP, consacré à la programmation dynamique. Elle présente le programme habituel d’un cours d’apprentissage par renforcement, à partir de sources standard du domaine. Les résultats numériques qu’elle contient viennent de petits calculs et simulations reproductibles, pas de nos TP.

Apprendre sans modèle : le principe

Rappelez-vous la définition de la valeur : $V^\pi(s) = \mathbb{E}_\pi[G_t \mid s_t = s]$. C’est une espérance. Or une espérance inconnue, on sait l’estimer depuis le premier cours de statistiques : on observe plusieurs réalisations et on fait la moyenne. La loi des grands nombres garantit que cette moyenne converge vers l’espérance.

Pour garder des calculs faisables à la main, nous reprenons le couloir de la partie 1 : trois cases A, B et G, deux actions (gauche, droite), une récompense de $+1$ en atteignant G, $\gamma = 0{,}9$. On évalue la politique aléatoire uniforme, dont on connaît la valeur exacte : $V(A) \approx 0{,}647$ et $V(B) \approx 0{,}791$. La différence, c’est que l’agent n’a plus le droit de regarder le modèle. Il a seulement une fonction pas(etat, action) qui lui renvoie l’état suivant et la récompense, comme env.step dans gymnasium.

Monte-Carlo : moyenner des retours complets

La méthode de Monte-Carlo (MC) est la plus directe. On joue un épisode complet jusqu’à l’état terminal, on calcule le retour obtenu depuis chaque état visité, et on fait la moyenne de ces retours, état par état.

Exemple

Le robot joue l’épisode A → A → B → G : il va à gauche en A (il bute contre le mur et reste en A), puis à droite (il arrive en B), puis à droite (il atteint G). Les récompenses sont 0, 0 puis 1. On calcule les retours en partant de la fin :

• depuis B (instant 2) : $G_2 = 1$ ;
• depuis A (instant 1) : $G_1 = 0 + 0{,}9 \times 1 = 0{,}9$ ;
• depuis A (instant 0) : $G_0 = 0 + 0{,}9 \times 0{,}9 = 0{,}81$.

L’état A a été visité deux fois. En version première visite (first-visit), on ne garde que le retour de la première visite, 0,81. En version toutes les visites (every-visit), on les moyenne : $(0{,}81 + 0{,}9)/2 = 0{,}855$. Les deux versions convergent vers $V^\pi$ quand le nombre d’épisodes augmente.

Les retours se calculent en remontant l'épisode : G₂ = 1, puis chaque retour vaut la récompense plus 0,9 fois le suivant.

Plutôt que de stocker tous les retours, on met à jour la moyenne au fil de l’eau. Si $V_n$ est la moyenne des $n$ premiers retours et $G$ le nouveau retour :

$$V_{n+1} = V_n + \frac{1}{n+1} \big( G - V_n \big)$$

Cette forme « ancienne estimation + pas × (cible − ancienne estimation) » est la forme générale de presque toutes les mises à jour de ce cours. On remplace souvent $\frac{1}{n+1}$ par un taux d’apprentissage (learning rate) constant $\alpha$, qui donne plus de poids aux retours récents, utile quand la politique évolue :

$$V(s) \leftarrow V(s) + \alpha \big( G_t - V(s) \big)$$

Monte-Carlo a deux qualités : il ne suppose rien sur le modèle, et il est sans biais, puisque $G_t$ est un échantillon exact de ce qu’on veut estimer. Mais il a deux défauts. Il doit attendre la fin de l’épisode pour apprendre quoi que ce soit, ce qui exclut les tâches sans fin. Et ses estimations ont une forte variance : un retour dépend de toutes les actions et transitions aléatoires de l’épisode, qui s’accumulent.

Les différences temporelles : apprendre à chaque pas

Et si l’on n’attendait pas la fin de l’épisode ? Après un seul pas, de $s$ vers $s'$ avec la récompense $r$, on dispose déjà d’une estimation du retour : la récompense observée, plus la valeur estimée de l’état d’arrivée. C’est l’idée de l’apprentissage par différences temporelles (temporal difference, TD). La méthode la plus simple, TD(0), fait :

$$V(s) \leftarrow V(s) + \alpha \big[\, r + \gamma \, V(s') - V(s) \,\big]$$

• $r + \gamma V(s')$ est la cible TD : un pas réel, puis l’estimation actuelle pour la suite ;
• $\delta = r + \gamma V(s') - V(s)$ est l’erreur TD : l’écart entre ce qu’on attendait et ce qu’on vient d’observer ;
• $\alpha$ est le taux d’apprentissage.

Reconnaissez-vous la cible ? C’est l’équation de Bellman d’espérance, dans laquelle l’espérance sur $s'$ est remplacée par un seul échantillon. TD(0) est en quelque sorte une programmation dynamique échantillonnée.

On dit que TD fait du bootstrap : il met à jour une estimation à partir d’une autre estimation ($V(s')$). C’est ce qui lui permet d’apprendre à chaque pas, sans attendre la fin de l’épisode.

Exemple

Supposons les estimations actuelles $V(A) = 0{,}5$ et $V(B) = 0{,}8$, avec $\alpha = 0{,}1$ et $\gamma = 0{,}9$. Le robot va de A vers B, avec une récompense nulle.

• Cible TD : $0 + 0{,}9 \times 0{,}8 = 0{,}72$.
• Erreur TD : $\delta = 0{,}72 - 0{,}5 = 0{,}22$.
• Mise à jour : $V(A) \leftarrow 0{,}5 + 0{,}1 \times 0{,}22 = 0{,}522$.

L’observation « depuis A, on arrive en B, qui semble valoir 0,8 » a fait remonter un peu l’estimation de A, avant même la fin de l’épisode.

Une mise à jour TD ne va pas jusqu'à la cible : elle parcourt une fraction α de l'écart, ici 10 % des 0,22 qui séparent V(A) de la cible.

À retenir

Monte-Carlo met à jour $V(s)$ vers le retour complet observé $G_t$ ; TD(0) la met à jour vers la cible $r + \gamma V(s')$, construite à partir d’un seul pas et de l’estimation suivante. Les deux méthodes apprennent sans modèle, à partir de l’expérience.

Monte-Carlo contre TD : biais et variance

Les deux méthodes convergent vers $V^\pi$ (sous des conditions raisonnables sur $\alpha$), mais elles ne se comportent pas de la même façon en chemin. On retrouve le compromis biais-variance de l’apprentissage supervisé.

	Monte-Carlo	TD(0)
Cible	retour complet $G_t$	$r + \gamma V(s')$
Biais	aucun	oui, tant que $V(s')$ est mal estimée
Variance	forte (toute la trajectoire)	faible (un seul pas aléatoire)
Quand apprend-il ?	à la fin de l’épisode	à chaque pas
Tâches sans fin	impossible	possible
Sensibilité à la propriété de Markov	faible	forte (le bootstrap s’appuie dessus)

Ce que chaque méthode utilise pour une mise à jour : toutes les issues d'un pas (avec le modèle), un épisode entier, ou un seul pas complété par l'estimation V(s′).

En pratique, TD converge souvent plus vite, grâce à sa faible variance. Monte-Carlo reste utile quand l’état ne résume pas bien la situation (propriété de Markov douteuse), car il ne s’appuie pas sur les estimations des états suivants. Entre les deux, on peut regarder $n$ pas en avant avant de faire du bootstrap (méthodes TD à $n$ pas, et TD($\lambda$), qui mélange tous les horizons).

Sur le couloir, à α égal, TD démarre plus lentement (sa cible s'appuie sur des estimations encore fausses) mais se stabilise plus bas que Monte-Carlo, dont les retours complets fluctuent davantage.

Voici les deux méthodes côte à côte sur le couloir. Le code n’utilise que la bibliothèque standard de Python.

import random

gamma = 0.9

def pas(etat, action):
    """Couloir A (0), B (1), G : renvoie (état suivant, récompense, terminé)."""
    if etat == 0:
        return (0, 0.0, False) if action == 0 else (1, 0.0, False)
    return (0, 0.0, False) if action == 0 else (None, 1.0, True)

def episode():
    """Joue un épisode depuis A avec la politique aléatoire."""
    etat, trajectoire = 0, []
    while True:
        action = random.randint(0, 1)            # gauche ou droite, 1 chance sur 2
        suivant, r, fini = pas(etat, action)
        trajectoire.append((etat, r, suivant, fini))
        if fini:
            return trajectoire
        etat = suivant

def monte_carlo(n_episodes):
    somme, compte = [0.0, 0.0], [0, 0]
    for _ in range(n_episodes):
        traj, G = episode(), 0.0
        for etat, r, _, _ in reversed(traj):     # on remonte l'épisode
            G = r + gamma * G                    # retour depuis cet instant
            somme[etat] += G                     # (version « toutes les visites »)
            compte[etat] += 1
    return [somme[s] / compte[s] for s in (0, 1)]

def td0(n_episodes, alpha=0.01):
    V = [0.0, 0.0]
    for _ in range(n_episodes):
        for etat, r, suivant, fini in episode():
            cible = r + (0.0 if fini else gamma * V[suivant])
            V[etat] += alpha * (cible - V[etat])     # correction vers la cible
    return V

random.seed(0)
print("Monte-Carlo :", [round(v, 3) for v in monte_carlo(5000)])
print("TD(0)       :", [round(v, 3) for v in td0(5000)])

Avec cette graine, on obtient $(0{,}646 ; 0{,}790)$ pour Monte-Carlo et $(0{,}655 ; 0{,}780)$ pour TD(0), à comparer aux valeurs exactes $(0{,}647 ; 0{,}791)$. Sans jamais consulter les probabilités de transition, les deux méthodes retrouvent la valeur calculée par Bellman au chapitre 2. Avec un $\alpha$ constant, l’estimation TD continue de fluctuer légèrement autour de la vraie valeur ; faire décroître $\alpha$ au fil du temps supprime ces fluctuations.

Le code du chapitre, graine 0. Monte-Carlo, qui moyenne des retours exacts, est juste presque tout de suite mais par sauts ; TD(0) avec α = 0,01 part de 0 et monte plus lentement, puis fluctue autour des valeurs exactes.

Piège

Un taux d’apprentissage trop grand fait osciller les estimations sans jamais les stabiliser ; un taux trop petit les fait converger avec une lenteur désespérante. Pour les méthodes à $\alpha$ constant, l’estimation ne converge pas exactement : elle fluctue autour de la cible, d’autant plus que $\alpha$ est grand.

De la prédiction au contrôle

Estimer $V^\pi$, c’est bien, mais le but reste de trouver une bonne politique. Pourquoi ne pas faire comme en partie 1 : estimer $V$, puis rendre la politique gloutonne ? Parce que l’amélioration gloutonne à partir de $V$ demande de calculer $\sum_{s'} P(s' \mid s, a)[\dots]$ pour comparer les actions, donc de connaître le modèle.

La solution consiste à estimer directement $Q(s, a)$ au lieu de $V(s)$. Avec $Q$, l’amélioration ne demande plus le modèle : il suffit de prendre $\arg\max_a Q(s, a)$. Les versions de Monte-Carlo et de TD qui estiment $Q$ s’appellent respectivement Monte-Carlo control et SARSA (ou Q-learning), et font l’objet du chapitre 7.

Il reste un obstacle, et il est de taille. Si l’agent agit toujours de façon gloutonne, il ne visite que les actions qu’il croit déjà bonnes, et n’apprend jamais la valeur des autres. Il lui faut explorer. C’est le sujet du chapitre suivant.

En entretien

« Monte-Carlo estime la valeur en moyennant des retours complets : sans biais, mais forte variance et il faut des épisodes finis. TD met à jour à chaque pas vers $r + \gamma V(s')$ : un peu de biais à cause du bootstrap, mais beaucoup moins de variance, et il fonctionne en ligne. »

En résumé

• Sans modèle, on remplace les espérances exactes par des moyennes d’expériences : on apprend en jouant.
• Monte-Carlo moyenne les retours complets observés depuis chaque état ; il est sans biais mais a une forte variance et doit attendre la fin des épisodes.
• La mise à jour générale s’écrit $V \leftarrow V + \alpha\,(\text{cible} - V)$, avec un taux d’apprentissage $\alpha$.
• TD(0) vise la cible $r + \gamma V(s')$ : c’est une équation de Bellman échantillonnée, qui fait du bootstrap et apprend à chaque pas.
• MC et TD illustrent le compromis biais-variance ; TD converge souvent plus vite.
• Pour passer au contrôle sans modèle, on estime $Q(s, a)$ plutôt que $V(s)$, et on doit explorer.

Exercices

Exercice · Calculer des retours Monte-Carlo

facile

Dans le couloir ($\gamma = 0{,}9$), le robot joue l’épisode B → A → B → G (gauche depuis B, puis droite, puis droite). Donnez les retours depuis chaque instant, puis les estimations Monte-Carlo « première visite » et « toutes les visites » de $V(A)$ et $V(B)$ après ce seul épisode.

Voir la solution

Récompenses : 0, 0, 1. En partant de la fin :

• instant 2 (B) : $G_2 = 1$ ;
• instant 1 (A) : $G_1 = 0{,}9 \times 1 = 0{,}9$ ;
• instant 0 (B) : $G_0 = 0{,}9 \times 0{,}9 = 0{,}81$.

A n’est visité qu’une fois : $V(A) = 0{,}9$ dans les deux versions. B est visité aux instants 0 et 2 : en première visite, $V(B) = 0{,}81$ ; en toutes les visites, $V(B) = (0{,}81 + 1)/2 = 0{,}905$.

En code

Python

gamma = 0.9
etats = ["B", "A", "B"]            # épisode B -> A -> B -> G
recompenses = [0, 0, 1]

# Retours calculés en partant de la fin
G, retours = 0.0, [0.0] * 3
for t in reversed(range(3)):
    G = recompenses[t] + gamma * G
    retours[t] = G
print([round(g, 3) for g in retours])          # [0.81, 0.9, 1.0]

for s in ("A", "B"):
    obs = [g for e, g in zip(etats, retours) if e == s]
    print(s, "première visite :", round(obs[0], 3),
          "toutes les visites :", round(sum(obs) / len(obs), 3))
# A première visite : 0.9 toutes les visites : 0.9
# B première visite : 0.81 toutes les visites : 0.905

R

gamma <- 0.9
etats <- c("B", "A", "B")          # épisode B -> A -> B -> G
recompenses <- c(0, 0, 1)

# Retours calculés en partant de la fin
retours <- numeric(3); G <- 0
for (t in 3:1) { G <- recompenses[t] + gamma * G; retours[t] <- G }
retours                            # 0.81 0.90 1.00

for (s in c("A", "B")) {
  obs <- retours[etats == s]
  cat(s, "première visite :", obs[1], "toutes les visites :", mean(obs), "\n")
}
# A première visite : 0.9 toutes les visites : 0.9
# B première visite : 0.81 toutes les visites : 0.905

Exercice · Dérouler TD(0)

moyen

On part de $V(A) = V(B) = 0$, avec $\alpha = 0{,}5$ et $\gamma = 0{,}9$. Le robot joue l’épisode A → B → G. Appliquez TD(0) à chaque transition. Rejouez ensuite le même épisode une deuxième fois. Que remarquez-vous sur la façon dont l’information se propage ?

Voir la solution

Premier épisode :

• A → B, $r = 0$ : cible $0 + 0{,}9 \times 0 = 0$, donc $V(A)$ reste à 0.
• B → G, $r = 1$ : cible $1$ (G est terminal), donc $V(B) \leftarrow 0 + 0{,}5 \times (1 - 0) = 0{,}5$.

Deuxième épisode :

• A → B : cible $0{,}9 \times 0{,}5 = 0{,}45$, donc $V(A) \leftarrow 0 + 0{,}5 \times 0{,}45 = 0{,}225$.
• B → G : cible 1, donc $V(B) \leftarrow 0{,}5 + 0{,}5 \times 0{,}5 = 0{,}75$.

Au premier épisode, seule la valeur de B a bougé : A ne pouvait pas encore profiter de la récompense, car $V(B)$ valait 0 au moment de sa mise à jour. L’information remonte d’un état par épisode, exactement comme elle remontait d’une case par balayage en programmation dynamique. Monte-Carlo, lui, aurait mis à jour A dès le premier épisode, avec le retour complet 0,9.

En code

Python

alpha, gamma = 0.5, 0.9
V = {"A": 0.0, "B": 0.0, "G": 0.0}        # G terminal : valeur 0
episode = [("A", 0, "B"), ("B", 1, "G")]  # (état, récompense, état suivant)

for numero in (1, 2):
    for s, r, s_suiv in episode:
        cible = r + gamma * V[s_suiv]
        V[s] += alpha * (cible - V[s])     # mise à jour TD(0)
    print(numero, round(V["A"], 3), round(V["B"], 3))
# 1 0.0 0.5
# 2 0.225 0.75

R

alpha <- 0.5; gamma <- 0.9
V <- c(A = 0, B = 0, G = 0)                    # G terminal : valeur 0
episode <- list(list(s = "A", r = 0, suiv = "B"),
                list(s = "B", r = 1, suiv = "G"))

for (numero in 1:2) {
  for (tr in episode) {
    cible <- tr$r + gamma * V[[tr$suiv]]
    V[[tr$s]] <- V[[tr$s]] + alpha * (cible - V[[tr$s]])   # mise à jour TD(0)
  }
  cat(numero, V[["A"]], V[["B"]], "\n")
}
# 1 0 0.5
# 2 0.225 0.75

Exercice · Choisir entre Monte-Carlo et TD

moyen

Pour chacune des situations suivantes, dites si vous privilégieriez Monte-Carlo ou TD, et pourquoi.

1. Un agent de trading qui gère un portefeuille en continu, sans fin d’épisode naturelle.
2. Un jeu de cartes où l’état observé par l’agent (sa main) ne contient pas toute l’information utile (les cartes des adversaires).
3. Un robot dont chaque essai dure plusieurs heures.

Voir la solution

1. TD : Monte-Carlo a besoin d’épisodes qui se terminent pour calculer les retours. TD apprend à chaque pas.
2. Monte-Carlo est plus robuste : l’état observé n’est pas markovien, et le bootstrap de TD s’appuie sur des estimations $V(s')$ qui supposent que l’état résume la situation. Monte-Carlo n’utilise que les retours réellement obtenus.
3. TD : attendre plusieurs heures avant la moindre mise à jour est très lent. TD corrige ses estimations à chaque action, ce qui accélère beaucoup l’apprentissage quand les épisodes sont longs.