Aller au contenu
ELECTRONICS ENGINEERINGelectronics-engineering.com
Apprentissage par renforcement et par imitation

Monte Carlo et différences temporelles : SARSA et Q-learning sur l'exemple de la falaise

Apprendre des valeurs à partir de l'expérience : Monte Carlo, TD(0), conditions de convergence, SARSA sur la politique et Q-learning hors politique, l'exemple de la falaise avec chemin sûr et optimal, code vérifié.

https://www.electronics-engineering.com/fr/differences-temporelles-sarsa-q-learning-falaise/

Pas encore de vote : soyez le premier à noter cette page.

Les équations de Bellman exigent de connaître les probabilités de transition P et les récompenses R. On ne les connaît presque jamais : un robot n’a pas de formule pour savoir comment il glissera sur le sol, un jeu ne dit pas à l’avance les coups de l’adversaire. On peut cependant essayer et observer ce qui se passe. Cette leçon présente les méthodes qui apprennent des valeurs à partir de l’expérience : Monte Carlo, qui attend la fin de l’épisode, et les différences temporelles (TD), qui mettent à jour à chaque pas. On en tire SARSA et le Q-learning, que nous comparons sur l’exemple classique de la falaise, avec du code et des résultats.

Monte Carlo : la moyenne des retours

La valeur est une moyenne : V^\pi(s) = \mathbb E[G_t \mid s_t = s]. La façon la plus directe de l’estimer est de jouer de nombreux épisodes en suivant \pi, de calculer le retour G_t chaque fois que s est visité et de faire la moyenne. Sous forme incrémentale, après chaque retour observé :

    \[ V(s) \leftarrow V(s) + \alpha\,\big(G_t - V(s)\big) \]

avec \alpha le taux d’apprentissage. Avec \alpha = 1/n (n nombre de visites), c’est exactement la moyenne arithmétique. Monte Carlo ne fait aucune hypothèse sur l’environnement, mais il doit attendre la fin de l’épisode et ses estimations ont une forte variance : G_t additionne de nombreuses récompenses aléatoires.

Les différences temporelles

L’idée de Sutton (1988) est de remplacer le vrai retour, connu seulement à la fin, par une estimation construite avec l’équation de Bellman : G_t = r_{t+1} + \gamma G_{t+1} \approx r_{t+1} + \gamma V(s_{t+1}). La mise à jour TD(0) est

    \[ V(s_t) \leftarrow V(s_t) + \alpha\,\underbrace{\big(r_{t+1} + \gamma V(s_{t+1}) - V(s_t)\big)}_{\delta_t,\ \text{TD error}} \]

L’apprentissage se fait à chaque pas, même dans des tâches sans fin. L’estimation utilise une autre estimation (on dit qu’elle fait du bootstrap) : elle a moins de variance que Monte Carlo, parce qu’elle dépend d’une seule récompense aléatoire, mais elle est biaisée tant que V est fausse. Le compromis biais-variance entre Monte Carlo et TD se règle avec les retours à n pas et le paramètre \lambda (TD(\lambda), et dans sa version moderne le GAE utilisé par PPO).

Convergence. Avec un tableau, si chaque état est visité infiniment souvent et que les pas vérifient les conditions de Robbins-Monro, \sum_t\alpha_t = \infty et \sum_t\alpha_t^2 \lt  \infty (par exemple \alpha_t = 1/t), TD(0) converge vers V^\pi avec une probabilité 1. L’idée de la démonstration : en moyenne, la mise à jour applique l’opérateur de Bellman, qui est une contraction ; la première condition permet d’arriver n’importe où, la seconde éteint le bruit.

De la valeur à l’action : SARSA et Q-learning

Pour choisir des actions sans modèle, il faut Q(s, a), non V(s) : avec V, il faudrait savoir où mène chaque action. En explorant avec une politique ε-gloutonne (meilleure action selon Q avec une probabilité 1 - \varepsilon, aléatoire avec une probabilité \varepsilon), on met à jour Q après chaque transition (s, a, r, s', a') :

    \[ \textbf{SARSA:}\quad Q(s, a) \leftarrow Q(s, a) + \alpha\big(r + \gamma\,Q(s', a') - Q(s, a)\big) \]

    \[ \textbf{Q-learning:}\quad Q(s, a) \leftarrow Q(s, a) + \alpha\big(r + \gamma\max_{a''}Q(s', a'') - Q(s, a)\big) \]

La seule différence est la cible. SARSA utilise l’action a' que l’agent va réellement prendre (exploration comprise) : il apprend la valeur de la politique qu’il suit, et s’appelle sur la politique (on-policy). Le Q-learning utilise le maximum, c’est-à-dire l’action que prendrait la politique optimale : il apprend Q^* quelle que soit la façon dont il explore, et s’appelle hors politique (off-policy, Watkins, 1989). Être hors politique est justement ce qui permet de réutiliser une vieille expérience ou une expérience recueillie par d’autres, et c’est la base du DQN.

L’exemple de la falaise

Une grille 4×12 : le départ est en bas à gauche, la sortie en bas à droite, et les cases du bas entre les deux sont une falaise : tomber donne -100 et renvoie au départ. Chaque pas coûte -1. Le plus court chemin longe le bord de la falaise (13 pas) ; un chemin plus sûr passe plus haut.

La falaise et les deux chemins appris
La ligne rouge en bas est la falaise ; S est le départ, G la sortie. Le Q-learning apprend le chemin optimal le long du bord, en orange, long de 13 pas ; SARSA apprend un chemin plus éloigné du bord, en bleu, long de 19 pas.

Avec \alpha = 0.5, \varepsilon = 0.1 et 500 épisodes (moyenne sur 20 graines aléatoires) :

chemin apprisretour moyen sur les 100 derniers épisodes
SARSAsûr, 19 pas−28,1
Q-learningoptimal, 13 pas−48,0

Le Q-learning trouve le meilleur chemin, mais gagne moins pendant qu’il apprend : en marchant sur le bord, le mouvement aléatoire de 10 % le fait tomber souvent. SARSA sait qu’il va explorer et préfère rester loin du bord. C’est une leçon qui s’applique aux systèmes réels : un robot qui apprend sur une installation réelle doit tenir compte de sa propre exploration, et les algorithmes sur la politique ou « prudents » sont souvent préférables ; en simulation, où tomber ne coûte rien, on peut utiliser le Q-learning puis éteindre l’exploration.

Retour par épisode pendant l'apprentissage
Moyenne sur 20 graines, avec une moyenne mobile sur 10 épisodes : SARSA, en bleu, se stabilise autour de moins 30 ; le Q-learning, en orange, reste autour de moins 48 parce que l’exploration le fait tomber de la falaise.

Le code

import numpy as np

ROWS, COLS = 4, 12
START, EXIT = (3, 0), (3, 11)
MOVES = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def step(pos, a):
    r = min(max(pos[0] + MOVES[a][0], 0), ROWS - 1)
    c = min(max(pos[1] + MOVES[a][1], 0), COLS - 1)
    if r == 3 and 1 <= c <= 10:            # cliff: -100 and back to the start
        return START, -100.0, False
    return (r, c), -1.0, (r, c) == EXIT

def learn(method, episodes=500, alpha=0.5, eps=0.1, seed=0):
    rng = np.random.default_rng(seed)
    Q = np.zeros((ROWS, COLS, 4))
    def choose(p):                          # epsilon-greedy (tiny noise to break ties)
        return rng.integers(4) if rng.random() < eps else int(np.argmax(Q[p] + 1e-9 * rng.random(4)))
    returns = []
    for _ in range(episodes):
        p, tot = START, 0.0
        a = choose(p)
        for _ in range(1000):
            p2, r, done = step(p, a)
            tot += r
            a2 = choose(p2)
            if method == "sarsa":
                target = r if done else r + Q[p2][a2]               # action actually chosen
            else:
                target = r if done else r + np.max(Q[p2])           # best action
            Q[p][a] += alpha * (target - Q[p][a])
            p, a = p2, a2
            if done:
                break
        returns.append(tot)
    return np.array(returns), Q

for method in ("sarsa", "qlearning"):
    curves = np.array([learn(method, seed=s)[0] for s in range(20)])
    _, Q = learn(method, seed=0)
    p, length, done = START, 0, False
    while not done and length < 50:         # final greedy path
        p, _, done = step(p, int(np.argmax(Q[p])))
        length += 1
    print(f"{method:9s}: last 100 episodes {curves[:, -100:].mean():6.1f}, path of {length} steps")

L’exécution affiche -28.1 et 19 pas pour SARSA, -48.0 et 13 pas pour le Q-learning. Un tableau avec une case par couple état-action fonctionne tant que les états se comptent en milliers ; pour CartPole (états continus) ou un jeu vidéo (états faits de pixels), il faut une approximation : le tableau Q devient un réseau de neurones, le DQN de la leçon suivante.

S’abonner
Notifier de
guest
1 commentaire
Le plus ancien
Plus récent Les plus votés
1
0
Vous avez apprécié cet article ? Merci de laisser un commentaire.x