Apprenez à agir avec SARSA et Q-learning

Retour au lac gelé, mais cette fois sans tricher : le robot n’a plus accès à env.unwrapped.P. Il ne peut que faire env.step(action) et regarder ce qui arrive. Pourra-t-il quand même trouver le chemin de 14 pas que value iteration avait calculé en partie 1 ?

Oui, et ce chapitre montre comment. Vous avez tous les ingrédients : l’itération sur les politiques (chapitres 3 et 4), les différences temporelles (chapitre 5) et l’exploration ε-greedy (chapitre 6). Il ne reste qu’à les assembler. Le résultat, ce sont les deux algorithmes les plus célèbres de l’apprentissage par renforcement tabulaire : SARSA et Q-learning.

Le contrôle sans modèle : estimer Q, agir ε-greedy

Le schéma général reste celui de l’itération généralisée sur les politiques : on alterne une étape d’évaluation et une étape d’amélioration. Deux changements le rendent utilisable sans modèle :

1. On estime $Q(s, a)$ plutôt que $V(s)$. L’amélioration consiste alors à prendre $\arg\max_a Q(s, a)$, ce qui ne demande pas de connaître $P$.
2. On agit avec une politique ε-greedy par rapport à $Q$, pour que toutes les actions continuent d’être essayées.

Et plutôt que d’évaluer complètement une politique avant de l’améliorer, on fait les deux en même temps, à chaque pas : chaque mise à jour de $Q$ modifie aussitôt la politique ε-greedy qui en découle. C’est l’équivalent sans modèle de value iteration, qui améliorait à chaque balayage.

Toute la question est alors : vers quelle cible faut-il corriger $Q(s, a)$ après une transition ? Les deux algorithmes de ce chapitre ne diffèrent que sur ce point.

SARSA : apprendre la valeur de ce que l’on fait

SARSA applique TD(0) à la fonction $Q$. Après avoir fait l’action $a$ dans l’état $s$, reçu $r$ et atteint $s'$, l’agent choisit déjà son action suivante $a'$ avec sa politique ε-greedy, puis met à jour :

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

• $r + \gamma Q(s', a')$ est la cible : la récompense reçue, plus la valeur estimée de l’action réellement choisie ensuite ;
• si $s'$ est terminal, la cible se réduit à $r$.

Le nom vient du quintuplet utilisé à chaque mise à jour : $(s, a, r, s', a')$, soit State, Action, Reward, State, Action.

SARSA est dit on-policy (sur politique) : il évalue et améliore la politique qu’il suit réellement, exploration comprise. Si l’agent explore une fois sur dix, SARSA apprend la valeur d’un agent qui explore une fois sur dix.

Q-learning : apprendre la valeur de la meilleure conduite

Q-learning change un seul symbole dans la cible : au lieu de l’action réellement choisie ensuite, il prend la meilleure action possible dans $s'$ :

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

Reconnaissez-vous la cible ? C’est l’équation de Bellman d’optimalité pour $Q^*$ (chapitre 2), dans laquelle l’espérance sur $s'$ est remplacée par un seul échantillon. Q-learning est donc une value iteration échantillonnée, sur $Q$ au lieu de $V$.

Q-learning est dit off-policy (hors politique) : il apprend la valeur de la politique gloutonne, optimale, alors qu’il agit avec une autre politique (ε-greedy, qui explore). On distingue la politique de comportement, qui choisit les actions, et la politique cible, dont on apprend la valeur. Sous des conditions classiques (toutes les paires état-action visitées indéfiniment, taux d’apprentissage décroissant de façon appropriée), $Q$ converge vers $Q^*$ quelle que soit la politique de comportement.

Exemple

L’agent est dans l’état $s$ avec $Q(s, a) = 0{,}5$. Il fait l’action $a$, reçoit $r = 0$ et arrive en $s'$, où ses estimations sont $Q(s', \cdot) = (0{,}2 ; 0{,}6 ; 0{,}4 ; 0{,}1)$ pour gauche, bas, droite, haut. Sa politique ε-greedy tire, par exploration, l’action gauche en $s'$. On prend $\alpha = 0{,}1$ et $\gamma = 0{,}9$.

• SARSA utilise l’action choisie, gauche : cible $0 + 0{,}9 \times 0{,}2 = 0{,}18$, donc $Q(s, a) \leftarrow 0{,}5 + 0{,}1 \times (0{,}18 - 0{,}5) = 0{,}468$.
• Q-learning utilise la meilleure action, bas : cible $0 + 0{,}9 \times 0{,}6 = 0{,}54$, donc $Q(s, a) \leftarrow 0{,}5 + 0{,}1 \times (0{,}54 - 0{,}5) = 0{,}504$.

SARSA « paie » le pas d’exploration à venir ; Q-learning l’ignore et raisonne comme si l’agent allait désormais jouer parfaitement.

Même transition, deux cibles : SARSA prend l'action réellement tirée (gauche, 0,2), Q-learning la meilleure (bas, 0,6). Avec α = 0,1, chacun ne fait qu'un dixième du chemin vers sa cible.

À retenir

SARSA vise $r + \gamma Q(s', a')$ avec l’action $a'$ réellement choisie : il est on-policy et apprend la valeur de la politique qui explore. Q-learning vise $r + \gamma \max_{a'} Q(s', a')$ : il est off-policy et apprend directement $Q^*$, la valeur de la politique optimale, tout en explorant.

On-policy ou off-policy : la falaise

La différence entre les deux algorithmes se voit sur un exemple classique, la marche au bord de la falaise (cliff walking). Une grille, un départ et une arrivée séparés par une falaise ; chaque pas coûte $-1$, tomber coûte $-100$ et renvoie au départ. Le chemin le plus court longe le bord de la falaise.

• Q-learning apprend ce chemin le plus court, car c’est la politique optimale si l’on n’explore plus. Mais pendant l’apprentissage, l’agent explore une fois sur dix, et un pas au hasard au bord du vide le fait tomber régulièrement. Ses récompenses pendant l’apprentissage sont donc mauvaises.
• SARSA apprend la valeur de l’agent qui explore : il « sait » qu’un pas au hasard près du bord est dangereux, et il apprend un chemin plus sûr, un peu en retrait. Chemin plus long, mais moins de chutes pendant l’apprentissage.

Chemins gloutons appris après 500 épisodes (ε = 0,1). Q-learning apprend le plus court, juste au-dessus du vide ; SARSA, qui tient compte de ses propres pas au hasard, passe loin du bord.

Pendant l'apprentissage, la politique « optimale » de Q-learning rapporte moins : un pas d'exploration au bord de la falaise coûte −100. SARSA, plus prudent, tombe rarement.

Aucun des deux n’est meilleur dans l’absolu. Si l’on n’a le droit de se tromper qu’en simulation et qu’on déploie ensuite une politique gloutonne, Q-learning vise la bonne cible. Si l’agent apprend en conditions réelles (un robot qui ne doit pas tomber), la prudence de SARSA est précieuse. Quand $\varepsilon$ décroît vers 0, les deux convergent vers la politique optimale.

	SARSA	Q-learning
Cible	$r + \gamma Q(s', a')$, $a'$ choisie	$r + \gamma \max_{a'} Q(s', a')$
Type	on-policy	off-policy
Ce qu’il apprend	la valeur de la politique ε-greedy suivie	$Q^*$, la valeur de la politique optimale
Comportement pendant l’apprentissage	plus prudent	plus risqué
Équation sous-jacente	Bellman d’espérance	Bellman d’optimalité

Attention

Le $\max$ de Q-learning a un effet pervers : quand les estimations sont bruitées, le maximum de plusieurs estimations est en moyenne plus grand que le vrai maximum. Q-learning a donc tendance à surestimer les valeurs (biais de maximisation). Le double Q-learning corrige ce biais en utilisant deux estimations : l’une choisit la meilleure action, l’autre l’évalue. Cette idée reviendra dans le deep RL.

Résoudre le lac gelé avec Q-learning

Voici Q-learning sur le lac 8x8 non glissant du TP, sans jamais consulter le modèle. L’agent ne voit que ce que lui renvoie env.step : le nouvel état, la récompense, et deux indicateurs de fin (épisode terminé dans un trou ou sur l’objectif, ou tronqué au bout de 200 pas).

import numpy as np
import gymnasium as gym

env = gym.make("FrozenLake-v1", map_name="8x8", is_slippery=False)
rng = np.random.default_rng(0)
n_etats, n_actions = env.observation_space.n, env.action_space.n

Q = np.zeros((n_etats, n_actions))
alpha, gamma, n_episodes = 0.1, 0.9, 5000

def epsilon_greedy(s, eps):
    if rng.random() < eps:
        return int(rng.integers(n_actions))                 # exploration
    meilleures = np.flatnonzero(Q[s] == Q[s].max())
    return int(rng.choice(meilleures))                      # égalités tranchées au hasard

for episode in range(n_episodes):
    eps = max(0.05, 1 - episode / (0.8 * n_episodes))       # de 1 à 0,05
    s, _ = env.reset()
    termine = tronque = False
    while not (termine or tronque):
        a = epsilon_greedy(s, eps)
        s_suiv, r, termine, tronque, _ = env.step(a)
        cible = r if termine else r + gamma * Q[s_suiv].max()   # Bellman d'optimalité échantillonnée
        Q[s, a] += alpha * (cible - Q[s, a])
        s = s_suiv

# On déroule la politique gloutonne apprise
s, _ = env.reset()
for pas in range(1, 101):
    s, r, termine, tronque, _ = env.step(int(Q[s].argmax()))
    if termine or tronque:
        break
print(f"Fin après {pas} pas, récompense {r}, max Q(S, .) = {Q[0].max():.3f}")

Avec ces réglages, on s’attend à ce que l’agent trouve un chemin de 14 pas jusqu’à l’objectif, et à ce que $\max_a Q(S, a)$ s’approche de $0{,}9^{13} \approx 0{,}254$ : la valeur $V^*(S)$ que value iteration calculait en partie 1 avec le modèle complet. Pour obtenir SARSA, il suffit de choisir l’action suivante avant la mise à jour et de remplacer Q[s_suiv].max() par Q[s_suiv, a_suiv]. SARSA trouve aussi le chemin, mais son estimation de $Q(S, \cdot)$ reste un peu plus basse, car elle tient compte des pas d’exploration qui font parfois tomber dans un trou.

Le code du chapitre, rejoué sans gymnasium (graine 0). Rien ne se passe tant que l'objectif n'a pas été trouvé ; ensuite Q-learning retrouve exactement 0,9¹³ ≈ 0,254, et SARSA reste plus bas car il compte les pas d'exploration.

Trois détails de ce code comptent beaucoup :

• Les égalités tranchées au hasard. Au début, toutes les valeurs sont nulles. Avec argmax, l’agent choisirait toujours « gauche » en exploitation et buterait contre le bord. Tirer au hasard parmi les meilleures actions évite ce blocage.
• La décroissance de $\varepsilon$. La récompense est très rare (une seule case sur 64) : il faut beaucoup explorer au début pour la trouver une première fois, puis la propager.
• La distinction terminé / tronqué. Si l’épisode est terminé, il n’y a pas de suite, et la cible est $r$. S’il est seulement tronqué par la limite de temps, l’état suivant a une vraie valeur, et on continue à faire du bootstrap.

Piège

Ne mettez pas la valeur de l’état suivant à zéro quand l’épisode est seulement tronqué par une limite de pas : l’agent n’est pas dans un état terminal, il a juste manqué de temps. Confondre les deux fausse les cibles et dégrade l’apprentissage. C’est pour cela que gymnasium renvoie séparément terminated et truncated.

Sur le lac glissant, le même code fonctionne, mais l’apprentissage est beaucoup plus lent et bruité : une même action peut mener à trois cases différentes, et il faut de nombreuses visites de chaque paire (état, action) pour que $Q$ moyenne correctement ces issues. Un taux d’apprentissage plus faible et davantage d’épisodes deviennent nécessaires.

En entretien

« Q-learning met à jour $Q(s, a)$ vers $r + \gamma \max_{a'} Q(s', a')$ : c’est l’équation de Bellman d’optimalité échantillonnée. Il est off-policy, il apprend la politique optimale tout en explorant. SARSA utilise l’action réellement jouée ensuite : il est on-policy, et donc plus prudent pendant l’apprentissage. »

En résumé

• Le contrôle sans modèle estime $Q(s, a)$, agit ε-greedy par rapport à $Q$ et améliore la politique à chaque pas.
• SARSA met à jour vers $r + \gamma Q(s', a')$, avec l’action $a'$ réellement choisie : il est on-policy.
• Q-learning met à jour vers $r + \gamma \max_{a'} Q(s', a')$ : il est off-policy et converge vers $Q^*$ sous des conditions classiques.
• Sur la falaise, Q-learning apprend le chemin optimal mais risqué, SARSA un chemin plus sûr qui tient compte de l’exploration.
• Le $\max$ de Q-learning surestime les valeurs bruitées ; le double Q-learning corrige ce biais.
• Au lac gelé non glissant, Q-learning retrouve sans modèle le chemin de 14 pas et une valeur de départ proche de 0,254.

Exercices

Exercice · Une mise à jour de chaque

facile

L’agent est en $s$ avec $Q(s, a) = 0{,}3$. Il fait $a$, reçoit $r = 1$ et atteint l’objectif (état terminal). Calculez la nouvelle valeur de $Q(s, a)$ avec SARSA puis avec Q-learning ($\alpha = 0{,}5$, $\gamma = 0{,}9$).

Voir la solution

L’état suivant est terminal : il n’y a pas d’action suivante, et les deux cibles se réduisent à $r = 1$. Les deux algorithmes donnent la même mise à jour : $Q(s, a) \leftarrow 0{,}3 + 0{,}5 \times (1 - 0{,}3) = 0{,}65$. SARSA et Q-learning ne diffèrent que par la façon d’estimer la suite, et ici il n’y a pas de suite.

En code

Python

alpha, gamma = 0.5, 0.9
Q_sa, r = 0.3, 1.0
# État suivant terminal : pas de Q(s', a') ni de max, la cible se réduit à r
cible_sarsa = r
cible_qlearning = r
print(round(Q_sa + alpha * (cible_sarsa - Q_sa), 3), round(Q_sa + alpha * (cible_qlearning - Q_sa), 3))   # 0.65 0.65

R

alpha <- 0.5; gamma <- 0.9
Q_sa <- 0.3; r <- 1
# État suivant terminal : pas de Q(s', a') ni de max, la cible se réduit à r
cible_sarsa <- r
cible_qlearning <- r
c(Q_sa + alpha * (cible_sarsa - Q_sa), Q_sa + alpha * (cible_qlearning - Q_sa))   # 0.65 0.65

Exercice · Expected SARSA

moyen

Une variante, Expected SARSA, remplace $Q(s', a')$ par l’espérance de $Q(s', \cdot)$ sous la politique ε-greedy : $\sum_{a'} \pi(a' \mid s') Q(s', a')$. Reprenez l’exemple du chapitre ($Q(s, a) = 0{,}5$, $r = 0$, $Q(s', \cdot) = (0{,}2 ; 0{,}6 ; 0{,}4 ; 0{,}1)$, $\alpha = 0{,}1$, $\gamma = 0{,}9$) avec $\varepsilon = 0{,}2$ et 4 actions. Calculez la mise à jour. Pourquoi cette variante a-t-elle moins de variance que SARSA ?

Voir la solution

La politique ε-greedy donne $0{,}85$ à l’action gloutonne (bas) et $0{,}05$ à chacune des trois autres. L’espérance vaut $0{,}05 \times 0{,}2 + 0{,}85 \times 0{,}6 + 0{,}05 \times 0{,}4 + 0{,}05 \times 0{,}1 = 0{,}545$.

Cible : $0 + 0{,}9 \times 0{,}545 = 0{,}4905$. Mise à jour : $Q(s, a) \leftarrow 0{,}5 + 0{,}1 \times (0{,}4905 - 0{,}5) \approx 0{,}499$.

SARSA utilise l’action $a'$ tirée au hasard : selon le tirage, sa cible vaut 0,18 ou 0,54 (ou 0,36, ou 0,09). Expected SARSA remplace ce tirage par sa moyenne exacte, qu’on sait calculer puisqu’on connaît sa propre politique. Une source d’aléa disparaît, donc la variance diminue. Remarquez qu’avec $\varepsilon = 0$, Expected SARSA devient exactement Q-learning.

En code

Python

import numpy as np

alpha, gamma, eps = 0.1, 0.9, 0.2
Q_sa, r = 0.5, 0.0
Q_suiv = np.array([0.2, 0.6, 0.4, 0.1])       # gauche, bas, droite, haut

pi = np.full(4, eps / 4)
pi[np.argmax(Q_suiv)] += 1 - eps              # [0.05 0.85 0.05 0.05]
esperance = pi @ Q_suiv
cible = r + gamma * esperance
print(round(esperance, 4), round(cible, 4), round(Q_sa + alpha * (cible - Q_sa), 4))
# 0.545 0.4905 0.499

# Les cibles possibles de SARSA selon l'action tirée, et leur dispersion
cibles_sarsa = r + gamma * Q_suiv
print(cibles_sarsa.round(3), round(pi @ cibles_sarsa, 4))   # [0.18 0.54 0.36 0.09], moyenne 0.4905
print(round(np.sqrt(pi @ (cibles_sarsa - cible) ** 2), 3))  # écart-type 0.126 (0 pour Expected SARSA)

R

alpha <- 0.1; gamma <- 0.9; eps <- 0.2
Q_sa <- 0.5; r <- 0
Q_suiv <- c(0.2, 0.6, 0.4, 0.1)               # gauche, bas, droite, haut

pi <- rep(eps / 4, 4)
pi[which.max(Q_suiv)] <- pi[which.max(Q_suiv)] + 1 - eps   # 0.05 0.85 0.05 0.05
esperance <- sum(pi * Q_suiv)
cible <- r + gamma * esperance
c(esperance, cible, Q_sa + alpha * (cible - Q_sa))   # 0.545 0.4905 0.49905

# Les cibles possibles de SARSA selon l'action tirée, et leur dispersion
cibles_sarsa <- r + gamma * Q_suiv            # 0.18 0.54 0.36 0.09
sum(pi * cibles_sarsa)                        # moyenne 0.4905
round(sqrt(sum(pi * (cibles_sarsa - cible)^2)), 3)   # écart-type 0.126 (0 pour Expected SARSA)

Exercice · Diagnostiquer un agent bloqué

difficile

Un camarade lance Q-learning sur le lac 8x8 non glissant avec $\varepsilon = 0{,}01$ constant, $Q$ initialisée à 0 et une sélection de l’action gloutonne par np.argmax(Q[s]). Après 5 000 épisodes, $Q$ est encore entièrement nulle et l’agent n’a jamais atteint l’objectif. Expliquez pourquoi, et proposez trois corrections.

Voir la solution

Tant que l’objectif n’a jamais été atteint, toutes les récompenses sont nulles et $Q$ reste à 0. Avec des valeurs toutes égales, np.argmax renvoie toujours la première action, « gauche ». En exploitation (99 % du temps), l’agent va donc à gauche et bute contre le bord gauche, ou erre à peine. Les 1 % d’actions aléatoires ne suffisent pas à parcourir les 14 pas minimaux vers G, en évitant les trous, avant que l’épisode ne s’arrête (trou ou limite de 200 pas). La récompense n’est jamais découverte, donc rien ne s’apprend.

Corrections possibles :

1. Explorer beaucoup plus au début : $\varepsilon$ partant de 1 et décroissant progressivement, comme dans le code du chapitre.
2. Trancher les égalités au hasard parmi les actions de valeur maximale, pour que l’exploitation ne se réduise pas à « toujours gauche ».
3. Initialiser $Q$ de façon optimiste (par exemple à 1) : chaque action essayée qui ne rapporte rien voit sa valeur baisser, ce qui pousse l’agent vers les actions encore inexplorées.

On peut aussi remodeler la récompense (par exemple une petite pénalité par pas), mais cela change le problème et demande de la prudence.

En code

Python

import numpy as np

CARTE = "SFFFFFFF" "FFFFFFFF" "FFFHFFFF" "FFFFFHFF" "FFFHFFFF" "FHHFFFHF" "FHFFHFHF" "FFFHFFFG"
DI, DJ = [0, 1, 0, -1], [-1, 0, 1, 0]            # gauche, bas, droite, haut

def pas(s, a):
    """Lac 8x8 non glissant : renvoie (état suivant, récompense, terminé)."""
    i, j = min(max(s // 8 + DI[a], 0), 7), min(max(s % 8 + DJ[a], 0), 7)
    s2 = 8 * i + j
    return s2, float(CARTE[s2] == "G"), CARTE[s2] in "GH"

def q_learning(eps_debut, egalites_au_hasard, q_init=0.0, n_episodes=5000, alpha=0.1, gamma=0.9):
    rng, Q, succes = np.random.default_rng(0), np.full((64, 4), q_init), 0
    for ep in range(n_episodes):
        eps = max(0.01, eps_debut * (1 - ep / (0.8 * n_episodes)))  # constant si eps_debut = 0.01
        s = 0
        for t in range(200):                                        # troncature à 200 pas
            if rng.random() < eps:
                a = int(rng.integers(4))
            elif egalites_au_hasard:
                a = int(rng.choice(np.flatnonzero(Q[s] == Q[s].max())))
            else:
                a = int(np.argmax(Q[s]))                            # toujours « gauche » si égalité
            s2, r, fini = pas(s, a)
            Q[s, a] += alpha * ((r if fini else r + gamma * Q[s2].max()) - Q[s, a])
            succes += r
            s = s2
            if fini:
                break
    return int(succes), round(float(Q[0].max()), 3)   # nombre de succès, max Q(S, .)

print(q_learning(0.01, False))               # (0, 0.0) : jamais de succès, Q reste nulle
print(q_learning(1.0, True))                 # (2622, 0.254) : corrections 1 et 2
print(q_learning(0.01, False, q_init=1.0))   # (4748, 0.254) : correction 3, Q optimiste

R

carte <- strsplit(paste0("SFFFFFFF", "FFFFFFFF", "FFFHFFFF", "FFFFFHFF",
                         "FFFHFFFF", "FHHFFFHF", "FHFFHFHF", "FFFHFFFG"), "")[[1]]
di <- c(0, 1, 0, -1); dj <- c(-1, 0, 1, 0)       # gauche, bas, droite, haut

pas <- function(s, a) {       # états 0 à 63, actions 1 à 4 ; lac non glissant
  i <- min(max(s %/% 8 + di[a], 0), 7); j <- min(max(s %% 8 + dj[a], 0), 7)
  s2 <- 8 * i + j
  list(s2 = s2, r = as.numeric(carte[s2 + 1] == "G"), fini = carte[s2 + 1] %in% c("G", "H"))
}

q_learning <- function(eps_debut, egalites_au_hasard, q_init = 0, n_episodes = 5000,
                       alpha = 0.1, gamma = 0.9) {
  set.seed(0); Q <- matrix(q_init, 64, 4); succes <- 0
  for (ep in 0:(n_episodes - 1)) {
    eps <- max(0.01, eps_debut * (1 - ep / (0.8 * n_episodes)))  # constant si eps_debut = 0.01
    s <- 0
    for (t in 1:200) {                                           # troncature à 200 pas
      q <- Q[s + 1, ]
      a <- if (runif(1) < eps) sample(4, 1)
           else if (egalites_au_hasard) { m <- which(q == max(q)); m[sample(length(m), 1)] }
           else which.max(q)                                     # « gauche » si égalité
      res <- pas(s, a)
      cible <- if (res$fini) res$r else res$r + gamma * max(Q[res$s2 + 1, ])
      Q[s + 1, a] <- Q[s + 1, a] + alpha * (cible - Q[s + 1, a])
      succes <- succes + res$r; s <- res$s2
      if (res$fini) break
    }
  }
  c(succes = succes, maxQ_S = round(max(Q[1, ]), 3))
}

q_learning(0.01, FALSE)                # 0 succès, max Q(S, .) = 0 : bloqué
q_learning(1, TRUE)                    # 2794 succès, 0.254 : corrections 1 et 2
q_learning(0.01, FALSE, q_init = 1)    # 4743 succès, 0.254 : correction 3