Apprentissage par renforcement : Q-learning et SARSA

Dans le domaine de l'intelligence artificielle, l'apprentissage par renforcement est une méthode qui permet à un agent d'apprendre à atteindre des objectifs en interagissant avec l'environnement.

Imaginez que vous apprenez une nouvelle commande à un chiot : lorsqu'il effectue une action (comme s'asseoir), vous lui donnez une récompense (une friandise), et il apprend progressivement à répondre correctement lorsqu'il entend la commande. Q-learning et SARSA sont deux algorithmes classiques et cruciaux de l'apprentissage par renforcement ; ils sont les outils essentiels pour que l'agent apprennequelle action est la meilleure dans quel étatoutils essentiels.


Bases de l'apprentissage par renforcement et des processus de décision markoviens

Avant de plonger dans Q-learning et SARSA, nous devons comprendre le cadre théorique commun qu'ils partagent.

Concepts fondamentaux

Les problèmes d'apprentissage par renforcement sont généralement modélisés commeun processus de décision markovien. Il contient les éléments clés suivants :

  • Agent: L'entité qui prend des décisions et apprend.
  • Environnement: Le monde extérieur avec lequel l'agent interagit.
  • État: Une description de l'environnement à un moment donné.
  • Action: Une opération que l'agent peut effectuer dans un état donné.
  • Récompense: Signal de gain immédiat renvoyé par l'environnement après que l'agent effectue une action.
  • Politique: Règle selon laquelle l'agent sélectionne des actions dans un état donné ; c'est la cible d'apprentissage.

Objectifs et fonctions de valeur

L'objectif ultime de l'agent est de maximiser la récompense cumulative à long terme, et pas seulement la récompense immédiate. À cette fin, nous introduisonsles fonctions de valeur.。

  • Fonction de valeur d'état V(s): Représente, à partir de l'états, la récompense cumulative attendue pouvant être obtenue en suivant une politique spécifique.
  • Fonction de valeur d'action Q(s, a): Représente, dans l'étatsen effectuant l'actiona, puis en suivant une politique spécifique, la récompense cumulative attendue qui peut être obtenue.Le cœur de Q-learning et SARSA est d'apprendre cette fonction Q.

Pour équilibrer les récompenses immédiates et futures, nous utilisonsle facteur d'actualisation γ(généralement dans l'intervalle [0, 1]). La récompense à l'étape future k est multipliée par γ^k, ce qui signifie que l'agent accorde plus d'importance aux récompenses à court terme.


Q-learning : Apprentissage par différence temporelle hors politique

Q-learning est un algorithmehors politique, proposé par Watkins en 1989. Son idée centrale est que l'agent trouve indirectement la politique optimale en apprenant une table de valeurs Q optimale.

Cœur de l'algorithme : formule de mise à jour de la valeur Q

Le processus d'apprentissage du Q-learning est guidé par la formule suivante :Q(s_t, a_t) ← Q(s_t, a_t) + α * [ r_{t+1} + γ * max_{a} Q(s_{t+1}, a) - Q(s_t, a_t) ]

Décomposons cette formule :

  • Q(s_t, a_t)Q(s, a) : à l'instant tt, dans l'état ss_ten effectuant l'action aa_t, l'estimation actuelle.
  • α: Le taux d'apprentissage αcontrôle la mesure dans laquelle les nouvelles informations remplacent les anciennes (0 < α ≤ 1).
  • r_{t+1}r : après avoir exécuté une actiona_t, la récompense immédiate obtenue.
  • γ: Le facteur d'actualisation γmesure l'importance des récompenses futures.
  • max_{a} Q(s_{t+1}, a)max Q(s', a') : dans l'état suivant s_{t+1}, la plus grande valeur Q parmi toutes les actions possibles. Cela représente le meilleur retour futur possible estimé à partir de la table Q actuelle.
  • [ r_{t+1} + γ * max_{a} Q(s_{t+1}, a) - Q(s_t, a_t) ]Erreur TD : appeléeerreur de différence temporelle. C’est la différence entre la « valeur cible » (récompense immédiate plus la meilleure estimation future) et l’« estimation actuelle ». L’algorithme met à jour Q en réduisant cette erreur.

La signification de l’approche hors-politique

Q-learning est appeléhors-politique, car lorsqu’il met à jour les valeurs Q, l’action utilisée pour évaluer la valeur future (max_{a} Q(s_{t+1}, a)) et l’action que l’agent exécute réellement pour l’explorationsont distinctes.。

  • Politique de comportement: la politique utilisée pour sélectionner les actions réellement effectuées (par exemple, ε-greedy, qui explore aléatoirement avec une certaine probabilité).
  • Politique cible: la politique utilisée pour mettre à jour les valeurs Q ; c’est une politique entièrement gloutonne (qui sélectionne toujours l’action ayant la plus grande valeur Q actuelle).

Cette séparation permet à Q-learning d’apprendre audacieusement en utilisant son estimation du chemin optimal, même lorsqu’il effectue actuellement une exploration aléatoire.

Procédure de l’algorithme


SARSA : Apprentissage par différence temporelle sur-politique

Le nom SARSA provient de la séquence état-action impliquée dans son processus de mise à jour :(S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1}). Il s’agit d’un algorithmesur-politique.

Cœur de l'algorithme : formule de mise à jour de la valeur Q

La formule de mise à jour de SARSA est très similaire à celle de Q-learning, mais il y a une différence clé :Q(s_t, a_t) ← Q(s_t, a_t) + α * [ r_{t+1} + γ * Q(s_{t+1}, a_{t+1}) - Q(s_t, a_t) ]

Remarquez la seconde partie :

  • Q-learning utilise max_{a'} Q(s', a'): γ * max_{a} Q(s_{t+1}, a)
  • SARSA utilise Q(s', a'): γ * Q(s_{t+1}, a_{t+1})

Dans SARSA, l'agent dansl'état suivants_{t+1}va réellement effectuer une actiona_{t+1}dont la valeur Q est utilisée pour estimer la valeur future.

La signification de On-Policy

SARSA est appeléon-policy, car la politique qu'il utilise pour mettre à jour les valeurs Q (politique cible) et la politique qu'il utilise pour sélectionner les actions (politique de comportement)sont les mêmes, toutes deux étant généralement la politique ε-greedy.

  • Il évalue et optimise la politique qu'ilexécute actuellement.
  • Ce qu'il apprend est une politique qui tient compte du risque d'exploration future, elle est donc généralement plus « conservatrice ».

Comparaison de Q-learning et SARSA

Comprendre la différence entre les deux est essentiel pour les maîtriser. Le tableau ci-dessous résume clairement les différences fondamentales :

Fonctionnalité Q-learning SARSA
Type de politique Hors-politique Sur-politique
Cible de mise à jour Basé sur l'action optimale :r + γ * max Q(s', a') Basé sur l'action réelle :r + γ * Q(s', a_{t+1})
Objectif d'apprentissage Learnla politique optimale. Learnla politique de comportement (par ex., ε-greedy).
Propension au risque Plus "audacieux", suppose que des actions optimales seront prises à l'avenir Plus "conservateur", prend en compte le risque que l'exploration future peut présenter
Moment de la mise à jour Dans(s, a, r, s')peut être mis à jour immédiatement après (S, A, R, S') nécessite(s, a, r, s', a')le quintuplet (S, A, R, S', A') pour la mise à jour.
Applications typiques Environnements discrets, recherchant la solution optimale globale Environnements à exigences de sécurité élevées, où les états dangereux doivent être évités

Exemple classique de Cliff Walking

Cet exemple illustre de manière vivante la différence entre les deux. Supposons un monde en grille où l'agent se déplace du départ S à l'objectif G ; en dessous se trouve une falaise. Une chute entraîne une forte récompense négative et ramène au départ.

  • Q-learningQ-learning : comme il suppose que l'avenir empruntera toujours le chemin optimal (le plus sûr), il apprend rapidement le chemin le plus court le long du bord de la falaise (chemin 1), parce qu'il "croit" qu'il ne tombera pas.
  • SARSASARSA : comme il considère qu'il existe encore une probabilité ε d'exploration aléatoire dans le futur, il peut tomber de la falaise. Par conséquent, il apprend un chemin plus sûr plus haut (chemin 2). Bien que plus long, son retour attendu à long terme est plus élevé.

Conclusion: Dans les environnements où l’exploration et l’exploitation doivent être équilibrées et où les erreurs sont coûteuses, SARSA apprend généralement une politique plus sûre et plus robuste.


Exercice de code : Implémenter Q-learning et SARSA en Python

Nous allons utiliser un simple4x4monde en grille pour démontrer les deux algorithmes. L’objectif est que l’agent se déplace du coin supérieur gauche(0,0)vers le coin inférieur droit(3,3)。

Configuration de l'environnement

Exemple

import numpy as np
import random

class GridWorld:
    def __init__(self, size=4):
        self.size = size
        self.state = (0, 0) # Point de départ
        self.goal = (size-1, size-1) # Point d’arrivée
        self.actions = ['up', 'down', 'left', 'right']
        self.action_map = {'up': (-1, 0), 'down': (1, 0), 'left': (0, -1), 'right': (0, 1)}

    def reset(self):
        """Réinitialiser l’environnement au point de départ"""
        self.state = (0, 0)
        return self.state

    def step(self, action):
        """Exécuter l'action, renvoyer (état suivant, récompense, terminé)"""
        move = self.action_map[action]
        next_state = (self.state[0] + move[0], self.state[1] + move[1])

        # Vérification des limites : si hors limites, rester sur place
        if not (0 <= next_state[0] < self.size and 0 <= next_state[1] < self.size):
            next_state = self.state

        self.state = next_state

        # Configuration de la récompense : récompense 10 pour atteindre l'objectif, -1 pour les autres déplacements (encourager à atteindre rapidement)
        if next_state == self.goal:
            reward = 10
            done = True
        else:
            reward = -1
            done = False

        return next_state, reward, done

    def get_actions(self):
        return self.actions

Implémentation de l’algorithme Q-learning

Exemple

def q_learning(env, episodes=500, alpha=0.1, gamma=0.9, epsilon=0.1):
    """
Implémenter l’algorithme Q-learning
env : objet environnement
episodes : nombre d’épisodes d’entraînement
alpha : taux d’apprentissage
gamma : facteur d’actualisation
epsilon : probabilité d’exploration dans la politique ε-greedy
    """

    # Initialiser la table Q avec la forme [lignes de la grille, colonnes de la grille, nombre d'actions]
    q_table = np.zeros((env.size, env.size, len(env.actions)))

    for episode in range(episodes):
        state = env.reset()
        done = False

        while not done:
            # 1. Choisir une action en utilisant la politique ε-greedy
            if random.uniform(0, 1) < epsilon:
                action_idx = random.randint(0, len(env.actions)-1) # Exploration : choisir aléatoirement
            else:
                action_idx = np.argmax(q_table[state[0], state[1], :]) # Exploitation : choisir celle qui a la valeur Q maximale
            action = env.actions[action_idx]

            # 2. Exécuter l'action, obtenir le retour
            next_state, reward, done = env.step(action)

            # 3. Mise à jour centrale de Q-learning
            # Valeur Q de la paire état-action actuelle
            current_q = q_table[state[0], state[1], action_idx]
            # Valeur Q maximale de l'état suivant (clé pour le hors-politique)
            next_max_q = np.max(q_table[next_state[0], next_state[1], :])
            # Calculer la valeur Q cible
            target_q = reward + gamma * next_max_q
            # Mettre à jour la table Q
            q_table[state[0], state[1], action_idx] = current_q + alpha * (target_q - current_q)

            # Transition vers l'état suivant
            state = next_state

    return q_table

Implémentation de l'algorithme SARSA

Exemple

def sarsa(env, episodes=500, alpha=0.1, gamma=0.9, epsilon=0.1):
    """
Implémenter l'algorithme SARSA
La signification des paramètres est identique à celle de Q-learning
    """

    q_table = np.zeros((env.size, env.size, len(env.actions)))

    for episode in range(episodes):
        state = env.reset()
        done = False

        # SARSA doit d'abord choisir une action pour l'état initial
        if random.uniform(0, 1) < epsilon:
            action_idx = random.randint(0, len(env.actions)-1)
        else:
            action_idx = np.argmax(q_table[state[0], state[1], :])
        action = env.actions[action_idx]

        while not done:
            # 1. Exécuter l'action choisie à l'étape précédente
            next_state, reward, done = env.step(action)

            # 2. Choisir une action pour l'état suivant (on-policy, en utilisant toujours ε-greedy)
            if random.uniform(0, 1) < epsilon:
                next_action_idx = random.randint(0, len(env.actions)-1)
            else:
                next_action_idx = np.argmax(q_table[next_state[0], next_state[1], :])
            next_action = env.actions[next_action_idx]

            # 3. Mise à jour principale de SARSA
            current_q = q_table[state[0], state[1], action_idx]
            # Différence clé : utiliser la valeur Q de l'**action réelle à exécuter** dans l'état suivant
            next_q = q_table[next_state[0], next_state[1], next_action_idx]
            target_q = reward + gamma * next_q
            q_table[state[0], state[1], action_idx] = current_q + alpha * (target_q - current_q)

            # 4. Mettre à jour l'état et l'action pour l'itération suivante
            state = next_state
            action_idx = next_action_idx
            action = next_action

    return q_table

Test et visualisation de la politique

Exemple

def test_policy(env, q_table, episodes=10):
    """Tester la politique apprise"""
    total_rewards = []
    for _ in range(episodes):
        state = env.reset()
        done = False
        total_reward = 0
        steps = []

        while not done:
            # Utiliser une politique gloutonne pendant le test (aucune exploration)
            action_idx = np.argmax(q_table[state[0], state[1], :])
            action = env.actions[action_idx]
            next_state, reward, done = env.step(action)
            steps.append(action[0].upper()) # Enregistrer la première lettre de chaque action
            total_reward += reward
            state = next_state

        total_rewards.append(total_reward)
        print(f"Étapes de l'épisode : {steps}, Récompense totale : {total_reward}")

    print(f"Récompense moyenne : {np.mean(total_rewards):.2f}")

# Créer l'environnement
env = GridWorld(size=4)

print("=== Entraînement et test de Q-learning ===")
q_table_ql = q_learning(env, episodes=1000)
test_policy(env, q_table_ql)

print("\n"=== Entraînement et test de SARSA ===")
env.reset() # Réinitialiser l'état de l'environnement
q_table_sarsa = sarsa(env, episodes=1000)
test_policy(env, q_table_sarsa)

# Comparer simplement les politiques finales
print("\n=== Comparaison des politiques (actions depuis le point de départ (0,0)) ===)
start_q_values = q_table_ql[0, 0, :]
start_sarsa_values = q_table_sarsa[0, 0, :]
print(f"Valeurs Q de Q-learning : {dict(zip(env.actions, start_q_values))}")
print(f"Action recommandée : {env.actions[np.argmax(start_q_values)]}")
print(f"Valeurs Q de SARSA : {dict(zip(env.actions, start_sarsa_values))}")
print(f"Action recommandée : {env.actions[np.argmax(start_sarsa_values)]}")
Autres extensions