Introduction à l'algorithme Double DQN

L'algorithme Double Deep Q-Network (Double DQN) est une amélioration de la méthode Deep Q-Network (DQN) en apprentissage par renforcement. Il vise à réduire le biais de surestimation présent dans DQN, où les valeurs Q sont souvent surestimées lors de la mise à jour. Double DQN utilise deux réseaux de neurones séparés pour la sélection d'actions et l'évaluation des cibles, améliorant ainsi la stabilité et la convergence de l'algorithme.

Contexte et motivation

Dans l'apprentissage par renforcement, Q-learning classique utilise une table de valeurs Q pour représenter les paires état-action. Cependant, pour des espaces d'états ou d'actions de grande dimension, DQN introduit des réseaux neuronaux pour approximer la fonction Q. Malgré son succès, DQN souffre du biais de surestimation : l'opérateur max dans la mise à jour peut conduire à une surestimation des valeurs Q, car le même réseau sélectionne et évalue les actions, ce qui entraîne une instabilité.

Problème de surestimation

La mise à jour de DQN utilise la formule :

Q(s, a) ← r + γ * max_a' Q_target(s', a')

Ici, max_a' utilise le réseau cible pour choisir et évaluer simultanément les actions, amplifiant les erreurs d'approximation neuronale. Cela peut rendre la stratégie trop agressive et ralentir la convergence.

Inspiration de Double Q-Learning

Double Q-Learning réduit ce biais en séparant la sélection d'actions et l'évaluation des cibles. Il utilise deux tables Q indépendantes : une pour choisir l'action, l'autre pour calculer la valeur cible. La formule devient :

Q(s, a) ← r + γ * Q_B(s', argmax_a' Q_A(s', a'))

Cette séparation évite que les erreurs de sélection n'affectent directement l'évaluation.

Adaptation à Double DQN

Double DQN étend cette idée aux réseaux profonds. Il utilise un réseau en ligne pour sélectionner les actions et un réseau cible pour évaluer les valeurs Q. La formule cible est :

Q_target(s, a) ← r + γ * Q_target(s', argmax_a' Q_online(s', a'))

Cela réduit le biais de surestimation en distinguant les rôles des deux réseaux.

Concept fondamental de Double DQN

Le noyau de Double DQN réside dans la séparation des fonctions :

• Le réseau en ligne (online network) sélectionnne l'action optimale pour l'état suivant.
• Le réseau cible (target network) évalue la valeur Q de cette action pour calculer la cible.

Cette architecture diminue les erreurs d'estimation et améliore la fiabilité de l'apprentissage.

Processus algorithmique

L'algorithme Double DQN suit ces étapes :

1. Initialisation : Créer deux réseaux neuronaux, réseau en ligne et réseau cible. Les paramètres du réseau cible sont synchronisés périodiquement avec ceux du réseau en ligne.
2. Sélection d'action : Dans l'état courant, choisir une action en utilisant une politique epsilon-greedy avec le réseau en ligne.
3. Stockage des expériences : Enregistrer les transitions (état, action, récompense, état suivant, indicateur de fin) dans un tampon de replay.
4. Échantillonnage : Prélever un mini-batch aléatoire du tampon de replay.
5. Calcul de la cible : Utiliser le réseau en ligne pour sélectionner l'action optimale dans l'état suivant, puis le réseau cible pour calculer la valeur Q cible.
6. Mise à jour du réseau en ligne : Minimiser l'erreur quadratique moyenne entre les valeurs Q prédites et les cibles via une descente de gradient.
7. Mise à jour du réseau cible : Copier les paramètres du réseau en ligne vers le réseau cible à intervalles réguliers.

Dérivation des formules

Soit s l'état actuel, a l'action, r la récompense immédiate, γ le facteur d'actualisation, et s' l'état suivant. La cible Q dans DQN classique est :

Q_target = r + γ * max_{a'} Q_target(s', a')

Dans Double DQN, la cible est ajustée pour séparer la sélection et l'évaluation :

Q_target = r + γ * Q_target(s', a*) où a* = argmax_{a'} Q_online(s', a')

Cela réduit la surestimation car Q_online et Q_target sont entraînés indépendamment, limitant la propagation des erreurs.

Implémentation en Python avec PyTorch

Voici une implémentation complète de Double DQN utilisant PyTorch. Le code est restructuré avec des noms de variables modifiés et des commentaires en français pour refléter une nouvelle perspective, tout en maintenant la correction algorithmique.

Importation des bibliothèques

import numpy as np
import torch
import torch.nn as nn
import torch.optim as optim
import random
from collections import deque
import gym

Paramètres hyperparamètres

# Hyperparamètres
GAMMA = 0.99  # Facteur d'actualisation
TAUX_APPRENTISSAGE = 0.001  # Taux d'apprentissage pour l'optimiseur
TAILLE_BATCH = 64  # Taille du mini-batch pour l'entraînement
CAPACITE_MEMOIRE = 10000  # Capacité maximale du tampon de replay
INTERVALLE_MAJ_CIBLE = 10  # Intervalle de mise à jour du réseau cible

Définition du réseau neuronal Q

class ReseauQ(nn.Module):
    def __init__(self, dim_etat, dim_action):
        super(ReseauQ, self).__init__()
        self.couche1 = nn.Linear(dim_etat, 128)
        self.couche2 = nn.Linear(128, 128)
        self.couche_sortie = nn.Linear(128, dim_action)
    
    def forward(self, entree):
        x = torch.relu(self.couche1(entree))
        x = torch.relu(self.couche2(x))
        x = self.couche_sortie(x)
        return x

Tampon de replay pour stocker les expériences

class TamponReplay:
    def __init__(self, capacite):
        self.tampon = deque(maxlen=capacite)
    
    def ajouter(self, etat, action, recompense, etat_suivant, termine):
        self.tampon.append((etat, action, recompense, etat_suivant, termine))
    
    def echantillonner(self, taille_batch):
        lot = random.sample(self.tampon, taille_batch)
        etats, actions, recompenses, etats_suivants, termines = zip(*lot)
        return (np.array(etats), np.array(actions), np.array(recompenses),
                np.array(etats_suivants), np.array(termines))
    
    def taille(self):
        return len(self.tampon)

Agent Double DQN

class AgentDoubleDQN:
    def __init__(self, dim_etat, dim_action):
        self.dim_etat = dim_etat
        self.dim_action = dim_action
        
        # Réseaux neuronaux
        self.reseau_en_ligne = ReseauQ(dim_etat, dim_action)
        self.reseau_cible = ReseauQ(dim_etat, dim_action)
        self.reseau_cible.load_state_dict(self.reseau_en_ligne.state_dict())
        self.reseau_cible.eval()
        
        self.optimiseur = optim.Adam(self.reseau_en_ligne.parameters(), lr=TAUX_APPRENTISSAGE)
        self.memoire = TamponReplay(CAPACITE_MEMOIRE)
        self.pas_total = 0
    
    def choisir_action(self, etat, epsilon):
        if random.random() < epsilon:
            return random.randint(0, self.dim_action - 1)
        else:
            etat_tensor = torch.FloatTensor(etat).unsqueeze(0)
            with torch.no_grad():
                valeurs_q = self.reseau_en_ligne(etat_tensor)
            return valeurs_q.argmax().item()
    
    def stocker_transition(self, etat, action, recompense, etat_suivant, termine):
        self.memoire.ajouter(etat, action, recompense, etat_suivant, termine)
    
    def mettre_a_jour(self):
        if self.memoire.taille() < TAILLE_BATCH:
            return
        
        etats, actions, recompenses, etats_suivants, termines = self.memoire.echantillonner(TAILLE_BATCH)
        etats_tensor = torch.FloatTensor(etats)
        actions_tensor = torch.LongTensor(actions).unsqueeze(1)
        recompenses_tensor = torch.FloatTensor(recompenses).unsqueeze(1)
        etats_suivants_tensor = torch.FloatTensor(etats_suivants)
        termines_tensor = torch.FloatTensor(termines).unsqueeze(1)
        
        # Calcul des valeurs Q actuelles
        valeurs_q = self.reseau_en_ligne(etats_tensor).gather(1, actions_tensor)
        
        # Calcul des cibles Q avec Double DQN
        with torch.no_grad():
            actions_suivantes = self.reseau_en_ligne(etats_suivants_tensor).argmax(dim=1, keepdim=True)
            valeurs_q_suivantes = self.reseau_cible(etats_suivants_tensor).gather(1, actions_suivantes)
            cibles_q = recompenses_tensor + (1 - termines_tensor) * GAMMA * valeurs_q_suivantes
        
        # Calcul de la perte et mise à jour
        perte = nn.MSELoss()(valeurs_q, cibles_q)
        self.optimiseur.zero_grad()
        perte.backward()
        self.optimiseur.step()
    
    def mettre_a_jour_reseau_cible(self):
        self.reseau_cible.load_state_dict(self.reseau_en_ligne.state_dict())

Entraînement sur l'environnement CartPole

env = gym.make('CartPole-v1')
dim_etat = env.observation_space.shape[0]
dim_action = env.action_space.n

agent = AgentDoubleDQN(dim_etat, dim_action)

nb_episodes = 500
epsilon_debut = 1.0
epsilon_fin = 0.01
epsilon_decroissance = 500

for episode in range(nb_episodes):
    etat = env.reset()
    termine = False
    recompense_totale = 0
    
    while not termine:
        epsilon = epsilon_fin + (epsilon_debut - epsilon_fin) * np.exp(-1. * agent.pas_total / epsilon_decroissance)
        action = agent.choisir_action(etat, epsilon)
        
        etat_suivant, recompense, termine, _ = env.step(action)
        recompense_totale += recompense
        
        agent.stocker_transition(etat, action, recompense, etat_suivant, termine)
        agent.mettre_a_jour()
        
        etat = etat_suivant
        agent.pas_total += 1
    
    if episode % INTERVALLE_MAJ_CIBLE == 0:
        agent.mettre_a_jour_reseau_cible()
    
    print(f"Épisode {episode}, Récompense totale : {recompense_totale}")

env.close()

Avantages et caractéristiques

Double DQN offre plusieurs améliorations par rapport à DQN classique :

• Réduction de la surestimation : La séparation des réseaux minimise le biais, menant à des estimations plus précises.
• Stabilité accrue : L'entraînement est plus fluide et converge plus rapidement grâce à des cibles fiables.
• Simplicité d'implémentation : L'ajout d'une logique de séparation des actions est facile à intégrer sur la base de DQN.

En comparaison avec DQN, Double DQN nécessite un calcul supplémentaire mais améliore significativement les performances dans des environnements complexes.