Découvrez l'apprentissage par renforcement

Un robot doit traverser un lac gelé pour atteindre un trésor, sans tomber dans les trous. Personne ne lui fournit d’exemples étiquetés du type « dans cette case, il fallait aller à droite » : il ne reçoit qu’un signal, une récompense quand il atteint le trésor, et rien du tout sinon. Comment peut-il en déduire, case par case, la bonne décision ? C’est tout le sujet de l’apprentissage par renforcement (reinforcement learning, RL).

Dans ce chapitre, vous allez poser le cadre mathématique qui sert de socle à tout le cours : le processus de décision markovien. Notre fil rouge sera ce lac gelé, qui existe sous le nom de FrozenLake dans la bibliothèque Python gymnasium et que nous avons étudié en TP.

Un agent, un environnement, une récompense

L’apprentissage par renforcement met en scène deux acteurs qui dialoguent en boucle :

• l’agent est celui qui décide (le robot, un programme de jeu, un système de recommandation) ;
• l’environnement est tout le reste : le lac, ses trous, les lois qui le gouvernent.

À chaque instant $t$, l’agent observe l’état $s_t$ dans lequel il se trouve, choisit une action $a_t$, puis l’environnement lui renvoie une récompense $r_{t+1}$ (un nombre réel) et un nouvel état $s_{t+1}$. Et on recommence.

Qu’est-ce qui distingue ce cadre de l’apprentissage supervisé ? Trois choses.

1. Pas de bonne réponse fournie. La récompense dit si le résultat est bon, pas quelle action il aurait fallu prendre.
2. La récompense peut être très tardive. Au lac gelé, seule la dernière action (celle qui atteint le trésor) rapporte quelque chose. Les treize pas qui l’ont précédée n’ont rien rapporté sur le moment, et pourtant ils étaient indispensables. Attribuer le mérite aux bonnes décisions passées, c’est le problème de l’attribution du crédit (credit assignment).
3. Les données dépendent des décisions. Ce que l’agent observe demain dépend de ce qu’il fait aujourd’hui. Un agent qui ne va jamais à droite ne saura jamais ce qu’il y a à droite.

À retenir

En apprentissage par renforcement, un agent agit dans un environnement et reçoit des récompenses. Il ne cherche pas à imiter des exemples, mais à trouver une manière d’agir qui maximise la somme des récompenses à venir, même quand elles arrivent longtemps après les décisions qui les ont provoquées.

Le lac gelé, notre fil rouge

FrozenLake est une grille de 8 cases sur 8. Voici la carte utilisée en TP :

S F F F F F F F
F F F F F F F F
F F F H F F F F
F F F F F H F F
F F F H F F F F
F H H F F F H F
F H F F H F H F
F F F H F F F G

• S (start) : la case de départ, en haut à gauche ;
• F (frozen) : de la glace sûre ;
• H (hole) : un trou, l’épisode s’arrête et l’agent a perdu ;
• G (goal) : l’objectif, en bas à droite, qui rapporte une récompense de $+1$.

Toutes les autres transitions rapportent 0. L’agent dispose de 4 actions, numérotées comme dans gymnasium : 0 pour gauche, 1 pour bas, 2 pour droite, 3 pour haut. Une action qui pousse contre un bord laisse l’agent sur place.

Chaque case est un état, numéroté de 0 à 63 en lisant la grille ligne par ligne : la case de la ligne $i$ et de la colonne $j$ (en partant de 0) porte le numéro $8i + j$. Le départ est l’état 0, l’objectif l’état 63.

La carte du TP. Les numéros d'état se lisent ligne par ligne (8i + j) ; le chemin tracé est l'un des plus courts, 7 pas à droite et 7 vers le bas en contournant les trous.

La glace peut être glissante ou non. Dans la version glissante, l’agent qui veut aller à droite peut déraper et partir vers le haut ou le bas : le résultat d’une action est aléatoire. En TP, nous avons utilisé la version non glissante (is_slippery=False), où chaque action a une seule issue possible. On dit que l’environnement est déterministe.

Une partie, du départ jusqu’à un trou ou à l’objectif, s’appelle un épisode. Les cases H et G sont des états terminaux : une fois dedans, l’épisode est fini.

Le cadre formel : le processus de décision markovien

Pour raisonner proprement, on modélise ce genre de problème par un processus de décision markovien (Markov decision process, MDP). C’est un quintuplet $(S, A, P, R, \gamma)$ :

• $S$ est l’ensemble des états (les 64 cases) ;
• $A$ est l’ensemble des actions (les 4 directions) ;
• $P(s' \mid s, a)$ est la probabilité de transition : la probabilité d’arriver en $s'$ quand on fait l’action $a$ depuis l’état $s$ ;
• $R(s, a, s')$ est la récompense reçue lors de cette transition ;
• $\gamma \in [0, 1]$ est le facteur d’actualisation (discount factor), sur lequel nous reviendrons dans un instant.

Dans le lac non glissant, $P(s' \mid s, a)$ vaut 1 pour une seule case $s'$ et 0 pour toutes les autres. Dans le lac glissant, la probabilité se répartit sur plusieurs cases voisines.

Pourquoi « markovien » ? Parce que ce modèle suppose la propriété de Markov : la suite ne dépend que de l’état et de l’action présents, pas du chemin suivi pour arriver là. Peu importe que le robot soit passé par le bord ou par le milieu du lac : ce qui compte pour la suite, c’est la case où il se trouve.

Si vous avez suivi le cours de modèles stochastiques, vous reconnaissez les chaînes de Markov. Un MDP, c’est une chaîne de Markov à laquelle on ajoute deux ingrédients : des actions qui modifient les probabilités de transition, et des récompenses. Dès que l’agent fixe sa manière de choisir les actions, on retombe exactement sur une chaîne de Markov.

En entretien

« Un MDP est un quintuplet $(S, A, P, R, \gamma)$ : des états, des actions, des transitions qui ne dépendent que de l’état et de l’action courants, des récompenses et un facteur d’actualisation. L’agent cherche la façon d’agir qui maximise la somme actualisée des récompenses qu’il peut espérer. »

Dans gymnasium, le modèle du lac est directement accessible. Pour chaque état s et chaque action a, env.unwrapped.P[s][a] est une liste de transitions possibles, chacune sous la forme (probabilité, état suivant, récompense, terminé) :

import gymnasium as gym

# Le lac 8x8 du TP, version non glissante (déterministe)
env = gym.make("FrozenLake-v1", map_name="8x8", is_slippery=False)

print(env.observation_space.n)   # 64 états
print(env.action_space.n)        # 4 actions

# Depuis la case 62 (juste à gauche de l'objectif), aller à droite (action 2)
print(env.unwrapped.P[62][2])    # [(1.0, 63, 1.0, True)] : on atteint G, récompense 1

Une seule transition, de probabilité 1 : c’est la signature d’un environnement déterministe. Avec is_slippery=True, la même commande renverrait trois transitions de probabilité $1/3$ chacune.

Depuis la case 62, « droite » n'a qu'une issue sur la glace non glissante. Sur la glace glissante, la même action a trois issues de probabilité 1/3, dont le trou juste au-dessus.

Le retour et le facteur d’actualisation

L’agent ne cherche pas à maximiser la prochaine récompense, mais tout ce qui va suivre. Cette quantité s’appelle le retour (return) :

$$G_t = r_{t+1} + \gamma \, r_{t+2} + \gamma^2 \, r_{t+3} + \dots = \sum_{k=0}^{\infty} \gamma^k \, r_{t+k+1}$$

• $G_t$ est le retour à partir de l’instant $t$ ;
• $r_{t+k+1}$ est la récompense reçue $k+1$ pas plus tard ;
• $\gamma^k$ est le poids de cette récompense : plus elle est lointaine, moins elle compte (si $\gamma < 1$).

Le facteur $\gamma$ joue deux rôles. D’abord, il traduit une préférence pour le présent : un euro aujourd’hui vaut plus qu’un euro dans dix ans. Avec $\gamma$ proche de 0, l’agent est myope et ne regarde que la récompense immédiate ; avec $\gamma$ proche de 1, il est patient et tient compte d’un avenir lointain. Ensuite, il garantit que le retour reste fini : si toutes les récompenses valent au plus $r_{max}$, alors $G_t \leq r_{max} / (1 - \gamma)$, par la somme d’une série géométrique.

Exemple

Le plus court chemin de S à G compte 14 pas (7 vers la droite et 7 vers le bas, en contournant les trous). La seule récompense non nulle, $+1$, arrive au 14e pas. Le retour depuis le départ vaut donc :

$$G_0 = 0 + \gamma \times 0 + \dots + \gamma^{12} \times 0 + \gamma^{13} \times 1 = \gamma^{13}$$

Avec $\gamma = 0{,}9$, cela donne $0{,}9^{13} \approx 0{,}254$. Un chemin plus long de 16 pas rapporterait seulement $0{,}9^{15} \approx 0{,}206$.

Plus γ est petit, plus une récompense lointaine pèse peu. Avec γ = 0,9, le chemin de 14 pas rapporte 0,254, celui de 16 pas 0,206 et celui de 20 pas 0,135 ; avec γ = 1, tous valent 1.

Voyez-vous ce que cela implique ? Dans le lac, toutes les réussites rapportent la même récompense brute, $+1$. C’est l’actualisation qui rend les chemins courts plus intéressants que les longs. Sans elle ($\gamma = 1$), un détour de cent pas vaudrait autant que le chemin direct. Nous verrons au chapitre 4 que ce détail a des conséquences très concrètes.

Attention

Le facteur $\gamma$ fait partie de la définition du problème, pas seulement du réglage de l’algorithme. Changer $\gamma$, c’est changer ce que l’agent cherche à optimiser, donc potentiellement la meilleure façon d’agir.

La politique : une règle de décision

Ce que l’agent doit finalement produire, c’est une politique (policy), notée $\pi$ : une règle qui dit quoi faire dans chaque état.

• Une politique stochastique donne une probabilité pour chaque action : $\pi(a \mid s)$ est la probabilité de choisir $a$ dans l’état $s$, et $\sum_a \pi(a \mid s) = 1$.
• Une politique déterministe choisit une seule action par état : on écrit alors $\pi(s) = a$.

En code, on représente souvent une politique par une matrice de taille $\lvert S \rvert \times \lvert A \rvert$ (64 lignes, 4 colonnes au lac), dont chaque ligne est une loi de probabilité. La politique aléatoire uniforme, point de départ du TP, met $1/4$ partout. Une politique déterministe met un 1 dans la colonne de l’action choisie et des 0 ailleurs.

import numpy as np

n_etats, n_actions = 64, 4

# Politique aléatoire uniforme : chaque action avec probabilité 1/4
politique_aleatoire = np.ones((n_etats, n_actions)) / n_actions

# Politique déterministe « toujours à droite » : un 1 dans la colonne 2
politique_droite = np.zeros((n_etats, n_actions))
politique_droite[:, 2] = 1.0

print(politique_aleatoire.sum(axis=1)[:3])   # chaque ligne somme à 1

La politique « toujours à droite » est mauvaise : depuis la case de départ, elle longe la première ligne et reste bloquée contre le bord droit sans jamais atteindre G. La politique aléatoire n’est guère meilleure : elle finit presque toujours dans un trou. Tout le travail des chapitres suivants consiste à mesurer la qualité d’une politique, puis à l’améliorer jusqu’à la meilleure possible, la politique optimale $\pi^*$.

« Toujours à droite » bute contre le bord droit sans jamais descendre. La marche aléatoire finit dans un trou dans 99,8 % des cas, surtout dans le trou le plus proche du départ (50 %).

Piège

Ne confondez pas la récompense et le retour. La récompense $r_{t+1}$ est le signal immédiat d’une seule transition ; le retour $G_t$ est la somme actualisée de toutes les récompenses futures. Au lac, presque toutes les récompenses valent 0, alors que le retour depuis une case proche de l’objectif est élevé.

Planifier ou apprendre ?

Une dernière distinction va structurer tout le cours. L’agent connaît-il $P$ et $R$ ?

• Oui : on peut calculer la meilleure politique sans jamais jouer, par un raisonnement sur le modèle. On parle de planification, et les méthodes de programmation dynamique (partie 1 de ce cours, celle du TP) en sont l’exemple type. C’est notre situation avec env.unwrapped.P.
• Non : l’agent doit jouer, observer ce qui se passe et apprendre de ses essais. C’est l’apprentissage par renforcement sans modèle (model-free), objet de la partie 2 : Monte-Carlo, différences temporelles, Q-learning.

	Planification (programmation dynamique)	Apprentissage sans modèle
Ce qu’on connaît	$P$ et $R$ en entier	rien, on interagit
Ce qu’on fait	calculer des espérances exactes	estimer à partir d’échantillons
Exemple	value iteration sur FrozenLake	Q-learning sur un jeu vidéo
Coût	proportionnel à la taille de $S$	proportionnel au nombre d’interactions

En résumé

• Un agent choisit des actions, l’environnement répond par un nouvel état et une récompense ; l’agent cherche à maximiser les récompenses futures.
• Un MDP $(S, A, P, R, \gamma)$ formalise ce cadre ; la propriété de Markov dit que la suite ne dépend que de l’état et de l’action présents.
• Le retour $G_t = \sum_k \gamma^k r_{t+k+1}$ est la somme actualisée des récompenses futures ; $\gamma$ règle la patience de l’agent et garantit un retour fini.
• Au lac gelé, le plus court chemin (14 pas) rapporte $\gamma^{13}$, soit environ 0,254 pour $\gamma = 0{,}9$ : c’est l’actualisation qui favorise les chemins courts.
• Une politique $\pi(a \mid s)$ dit quoi faire dans chaque état ; on la représente par une matrice $\lvert S \rvert \times \lvert A \rvert$.
• Si l’on connaît $P$ et $R$, on planifie (programmation dynamique) ; sinon, on apprend par interaction (méthodes sans modèle).

Exercices

Exercice · Identifier les éléments d'un MDP

facile

Un thermostat intelligent décide toutes les dix minutes d’allumer ou d’éteindre le chauffage. Il connaît la température de la pièce (arrondie au degré, entre 10 et 30 °C). Il est pénalisé de 1 par tranche de dix minutes où la température est hors de la plage 19 à 21 °C, et de 0,1 à chaque fois qu’il chauffe (coût de l’énergie).

Décrivez les états, les actions et la récompense de ce MDP. La propriété de Markov vous semble-t-elle raisonnable ?

Voir la solution

• États : la température arrondie, soit 21 valeurs possibles (de 10 à 30 °C).
• Actions : deux, « chauffer » et « ne pas chauffer ».
• Récompense : $-1$ si la température est hors de la plage 19 à 21 °C, à quoi s’ajoute $-0{,}1$ si le chauffage est allumé. Les récompenses sont ici des pénalités : maximiser le retour revient à minimiser l’inconfort et la consommation.

La propriété de Markov n’est qu’approximative : l’évolution de la température dépend aussi de la température extérieure, de l’inertie des murs ou d’une fenêtre ouverte, qui ne figurent pas dans l’état. Si ces facteurs comptent beaucoup, il faut les ajouter à l’état (par exemple la température extérieure et la tendance des dernières mesures) pour retrouver un modèle markovien.

En code

Python

import numpy as np

temperatures = np.arange(10, 31)          # 21 états : de 10 à 30 °C
actions = ["ne pas chauffer", "chauffer"] # 2 actions

def recompense(temp, chauffe):
    r = -1.0 if (temp < 19 or temp > 21) else 0.0   # inconfort
    return r - 0.1 * chauffe                         # coût de l'énergie

print(len(temperatures), len(actions))               # 21 2
for temp in [17, 20, 23]:
    print(temp, [recompense(temp, c) for c in (0, 1)])
# 17 [-1.0, -1.1]
# 20 [0.0, -0.1]
# 23 [-1.0, -1.1]

R

temperatures <- 10:30                          # 21 états : de 10 à 30 °C
actions <- c("ne pas chauffer", "chauffer")    # 2 actions

recompense <- function(temp, chauffe) {
  r <- if (temp < 19 || temp > 21) -1 else 0   # inconfort
  r - 0.1 * chauffe                            # coût de l'énergie
}

length(temperatures); length(actions)          # 21  2
for (temp in c(17, 20, 23))
  cat(temp, recompense(temp, 0), recompense(temp, 1), "\n")
# 17 -1 -1.1
# 20 0 -0.1
# 23 -1 -1.1

Exercice · Calculer des retours

moyen

Au lac gelé, on compare deux trajectoires qui atteignent l’objectif : l’une en 14 pas, l’autre en 20 pas.

1. Calculez leurs retours depuis le départ pour $\gamma = 0{,}9$ et pour $\gamma = 1$.
2. Un agent reçoit une récompense de 1 à chaque pas, pour toujours. Que vaut son retour avec $\gamma = 0{,}9$ ? Avec $\gamma = 0{,}99$ ? Avec $\gamma = 1$ ?

Voir la solution

1. La récompense $+1$ arrive au dernier pas, donc le retour vaut $\gamma^{13}$ pour 14 pas et $\gamma^{19}$ pour 20 pas. Avec $\gamma = 0{,}9$ : $0{,}9^{13} \approx 0{,}254$ et $0{,}9^{19} \approx 0{,}135$ ; le chemin court est nettement préféré. Avec $\gamma = 1$ : les deux retours valent exactement 1, et rien ne distingue les deux chemins.
2. C’est une série géométrique : $\sum_{k \geq 0} \gamma^k = 1/(1-\gamma)$. Avec $\gamma = 0{,}9$, le retour vaut 10 ; avec $\gamma = 0{,}99$, il vaut 100. Avec $\gamma = 1$, la somme diverge : le retour est infini, ce qui rend toute comparaison impossible. C’est pourquoi on impose $\gamma < 1$ dans les tâches sans fin, alors qu’on peut prendre $\gamma = 1$ quand les épisodes se terminent toujours.

En code

Python

import numpy as np

def retour(recompenses, gamma):
    """G_0 = somme des gamma^k * r_(k+1)."""
    r = np.asarray(recompenses, dtype=float)
    return np.sum(gamma ** np.arange(len(r)) * r)

court = [0] * 13 + [1]            # 14 pas, +1 au dernier
long_ = [0] * 19 + [1]            # 20 pas
for gamma in (0.9, 1.0):
    print(gamma, round(retour(court, gamma), 3), round(retour(long_, gamma), 3))
# 0.9 0.254 0.135
# 1.0 1.0 1.0

# Récompense 1 à chaque pas : série géométrique 1 / (1 - gamma)
for gamma in (0.9, 0.99):
    print(gamma, round(1 / (1 - gamma), 3), round(retour([1] * 5000, gamma), 3))
# 0.9 10.0 10.0
# 0.99 100.0 100.0   (avec gamma = 1, la somme diverge)

R

retour <- function(recompenses, gamma) {
  sum(gamma^(seq_along(recompenses) - 1) * recompenses)
}

court <- c(rep(0, 13), 1)          # 14 pas, +1 au dernier
long  <- c(rep(0, 19), 1)          # 20 pas
for (gamma in c(0.9, 1))
  cat(gamma, round(retour(court, gamma), 3), round(retour(long, gamma), 3), "\n")
# 0.9 0.254 0.135
# 1 1 1

# Récompense 1 à chaque pas : série géométrique 1 / (1 - gamma)
for (gamma in c(0.9, 0.99))
  cat(gamma, 1 / (1 - gamma), round(retour(rep(1, 5000), gamma), 3), "\n")
# 0.9 10 10
# 0.99 100 100

Exercice · Lire le modèle de gymnasium

moyen

Dans le lac glissant, une action réussit avec probabilité $1/3$ et fait déraper l’agent sur l’une des deux directions perpendiculaires avec probabilité $1/3$ chacune. L’agent est sur la case 62 (ligne 7, colonne 6) et choisit d’aller à droite.

1. Quelles sont les trois transitions possibles (état suivant, récompense, terminé) ?
2. Quelle est la récompense moyenne de cette action ?

Voir la solution

1. Les directions perpendiculaires à « droite » sont « haut » et « bas ».
   • Droite (probabilité $1/3$) : l’agent arrive en 63, l’objectif. Récompense 1, épisode terminé.
   • Haut (probabilité $1/3$) : il arrive en 54 (ligne 6, colonne 6). Sur la carte, c’est un trou H : récompense 0, épisode terminé.
   • Bas (probabilité $1/3$) : il est sur la dernière ligne et bute contre le bord, il reste en 62. Récompense 0, épisode non terminé.
2. La récompense moyenne vaut $\tfrac{1}{3} \times 1 + \tfrac{1}{3} \times 0 + \tfrac{1}{3} \times 0 = \tfrac{1}{3}$. Dans la version glissante, même la case voisine de l’objectif est risquée : une fois sur trois, l’agent tombe dans le trou juste au-dessus.

En code

Python

CARTE = ["SFFFFFFF", "FFFFFFFF", "FFFHFFFF", "FFFFFHFF",
         "FFFHFFFF", "FHHFFFHF", "FHFFHFHF", "FFFHFFFG"]
DEPLACEMENTS = {0: (0, -1), 1: (1, 0), 2: (0, 1), 3: (-1, 0)}  # gauche, bas, droite, haut

def transitions_glissantes(s, a):
    """Liste (proba, état suivant, récompense, terminé), comme env.unwrapped.P[s][a]."""
    i, j = divmod(s, 8)
    resultat = []
    for b in [(a - 1) % 4, a, (a + 1) % 4]:           # dérapage ou réussite, 1/3 chacun
        di, dj = DEPLACEMENTS[b]
        ni, nj = min(max(i + di, 0), 7), min(max(j + dj, 0), 7)   # les bords bloquent
        case = CARTE[ni][nj]
        resultat.append((1 / 3, 8 * ni + nj, float(case == "G"), case in "GH"))
    return resultat

trans = transitions_glissantes(62, 2)               # case 62, action droite
for t in trans:
    print(t)
# (0.333, 62, 0.0, False)   dérapage vers le bas : bute contre le bord
# (0.333, 63, 1.0, True)    réussite : l'objectif
# (0.333, 54, 0.0, True)    dérapage vers le haut : le trou
print(sum(p * r for p, _, r, _ in trans))           # 0.333

R

carte <- c("SFFFFFFF", "FFFFFFFF", "FFFHFFFF", "FFFFFHFF",
           "FFFHFFFF", "FHHFFFHF", "FHFFHFHF", "FFFHFFFG")
di <- c(0, 1, 0, -1); dj <- c(-1, 0, 1, 0)   # actions 0 à 3 : gauche, bas, droite, haut

transitions_glissantes <- function(s, a) {
  i <- s %/% 8; j <- s %% 8
  res <- NULL
  for (b in c((a - 1) %% 4, a, (a + 1) %% 4)) {        # 1/3 chacune
    ni <- min(max(i + di[b + 1], 0), 7)                 # les bords bloquent
    nj <- min(max(j + dj[b + 1], 0), 7)
    case <- substr(carte[ni + 1], nj + 1, nj + 1)
    res <- rbind(res, data.frame(proba = 1/3, suivant = 8 * ni + nj,
                                 r = as.numeric(case == "G"), termine = case %in% c("G", "H")))
  }
  res
}

trans <- transitions_glissantes(62, 2)   # case 62, action droite
print(trans)
#   suivant 62 (r 0, non terminé), 63 (r 1, terminé), 54 (r 0, terminé : le trou)
sum(trans$proba * trans$r)               # 0.333