Q-Learning : Guide Complet — Apprentissage par Renforcement

Résumé

Le Q-Learning est l’un des algorithmes fondateurs de l’apprentissage par renforcement. Introduit par Christopher Watkins en 1989, il permet à un agent d’apprendre une politique optimale — c’est-à-dire la meilleure séquence d’actions à entreprendre dans chaque situation — sans connaître au préalable la dynamique de l’environnement. Son principe est à la fois élégant et puissant : l’agent maintient une table de valeurs, appelée Q-table, qui associe à chaque couple (état, action) une estimation de la récompense future cumulative attendue. Grâce à l’équation de Bellman, cette table est mise à jour de manière itérative à chaque interaction avec l’environnement, convergeant progressivement vers les valeurs optimales. Le Q-Learning est un algorithme model-free : il ne nécessite aucune connaissance préalable des probabilités de transition entre états. Cette caractéristique le rend particulièrement adapté aux environnements complexes où la modélisation analytique est impossible ou trop coûteuse.

Principe mathématique du Q-Learning

La Q-table : mémoire de l’agent

Au cœur du Q-Learning se trouve la table Q (Q-table), une structure de données qui stocke pour chaque état s et chaque action possible a la valeur Q(s, a). Cette valeur représente l’estimation de la récompense cumulative future que l’agent peut espérer obtenir en exécutant l’action a depuis l’état s, puis en suivant ensuite la politique optimale.

Formellement, la Q-table est une matrice de dimensions |S| × |A|, où S est l’ensemble des états et A est l’ensemble des actions. Initialement, toutes les valeurs sont fixées à zéro (ou à des valeurs aléatoires). À mesure que l’agent explore l’environnement, ces valeurs sont ajustées pour refléter l’expérience accumulée.

L’équation de Bellman

La mise à jour de la Q-table repose sur l’équation de Bellman, qui constitue le fondement théorique du Q-Learning. À chaque transition de l’état s vers l’état s’ après avoir appliqué l’action a et reçu la récompense r, la valeur Q(s, a) est mise à jour selon la formule suivante :

Q(s, a) ← Q(s, a) + α · [r + γ · max_a’ Q(s’, a’) − Q(s, a)]

Décomposons chaque terme de cette équation fondamentale :

• Q(s, a) : la valeur actuelle estimée pour le couple état-action.
• α (alpha) : le taux d’apprentissage (learning rate), compris entre 0 et 1. Il détermine l’importance accordée à la nouvelle information par rapport à l’ancienne estimation. Une valeur élevée (proche de 1) signifie que l’agent accorde une grande importance aux expériences récentes, tandis qu’une valeur faible (proche de 0) privilégie la stabilité des estimations existantes.
• r : la récompense immédiate reçue après l’exécution de l’action a dans l’état s.
• γ (gamma) : le facteur d’actualisation (discount factor), compris entre 0 et 1. Il pondère l’importance des récompenses futures par rapport aux récompenses immédiates. Lorsque γ est proche de 0, l’agent est « myope » et privilégie les récompenses immédiates. Lorsque γ est proche de 1, l’agent planifie à long terme.
• max_a’ Q(s’, a’) : la valeur Q maximale parmi toutes les actions possibles dans le nouvel état s’. Ce terme représente la meilleure estimation de la récompense future que l’agent peut espérer depuis le nouvel état.
• [r + γ · max_a’ Q(s’, a’) − Q(s, a)] : l’erreur de TD (Temporal Difference error), qui mesure l’écart entre l’estimation précédente et la nouvelle estimation intégrant la récompense observée.

L’équation de Bellman effectue donc une moyenne pondérée entre l’ancienne estimation et la nouvelle information. Cette approche incrémentale garantit que les valeurs convergent vers l’optimalité à condition que chaque couple (état, action) soit visité un nombre suffisant de fois.

La politique epsilon-greedy : équilibrer exploration et exploitation

Un défi central en apprentissage par renforcement est le dilemme exploration-exploitation : l’agent doit-il exploiter les connaissances actuelles pour maximiser les récompenses immédiates, ou explorer de nouvelles actions pour potentiellement découvrir de meilleures stratégies ?

Le Q-Learning résout ce dilemme grâce à la politique epsilon-greedy :

• Avec une probabilité ε (epsilon %), l’agent choisit une action aléatoire (exploration). Cela lui permet de découvrir des états et des actions qu’il n’a pas encore suffisamment explorés.
• Avec une probabilité (1 − ε) %, l’agent choisit l’action qui maximise la valeur Q dans l’état courant, c’est-à-dire argmax_a Q(s, a) (exploitation). Il utilise alors sa connaissance actuelle pour prendre la meilleure décision possible.

En pratique, ε est initialement élevé (par exemple 1,0 soit 100 % d’exploration) puis décroît progressivement au fil des épisodes selon un decay rate. Ainsi, l’agent explore massivement au début, puis exploite de plus en plus ses connaissances acquises. Cette stratégie garantit à la fois la couverture de l’espace d’états et la convergence vers la politique optimale.

Intuition : le rat dans le labyrinthe

Pour comprendre le Q-Learning de manière intuitive, imaginons un rat lâché dans un labyrinthe avec du fromage placé à la sortie. Le rat ne connaît pas le plan du labyrinthe : il doit apprendre par essais et erreurs.

Chaque fois que le rat tourne à gauche et trouve un mur, il subit une petite « punition » (un choc, une frustration). Il mémorise alors que « dans cette situation précise, tourner à gauche est une mauvaise idée ». La prochaine fois qu’il se retrouve dans le même carrefour, il évitera probablement cette direction.

En revanche, chaque fois qu’il emprunte un couloir qui le rapproche du fromage, il reçoit une récompense positive. Il mémorise que « cette direction est profitable ». Peu à peu, le rat construit dans sa tête une carte mentale des bons et mauvais chemins — c’est exactement ce qu’est la Q-table !

Au début, le rat explore au hasard : il tourne à gauche, à droite, fait demi-tour, se cogne dans les murs. Mais à chaque essai, il met à jour sa carte mentale selon l’équation de Bellman. Après plusieurs centaines de tentatives, il a acquis suffisamment d’expérience pour choisir systématiquement le chemin le plus court vers le fromage.

Le paramètre ε joue un rôle crucial dans cette analogie : un ε élevé signifie que le rat est curieux et essaie régulièrement de nouveaux chemins (même s’il connaît déjà un chemin fonctionnel). Un ε faible signifie que le rat suit sa carte mentale avec confiance. En faisant décroître ε progressivement, on simule un rat qui devient de plus en plus expert dans son labyrinthe, tout en conservant une petite part de curiosité pour vérifier occasionnellement s’il n’existe pas un meilleur chemin.

Cette métaphore illustre parfaitement pourquoi le Q-Learning est si puissant : il ne nécessite aucun plan préalable du labyrinthe, aucune connaissance des probabilités de transition. Il apprend purement par l’expérience, exactement comme un être vivant apprendrait dans le monde réel.

Implémentation Python

Q-Learning sur FrozenLake avec Gym

L’environnement FrozenLake de la bibliothèque OpenAI Gym est un cas d’école idéal pour le Q-Learning. Il s’agit d’une grille 4×4 où l’agent doit naviguer de la case de départ (S) jusqu’à la case d’arrivée (G) en évitant les trous (H) parsemés sur la glace (F). La glace étant glissante, les actions ne sont pas toujours exécutées avec certitude : cela introduit de l’aléa et rend le problème plus réaliste.

Voici une implémentation complète du Q-Learning sur FrozenLake :

import numpy as np
import gym
import matplotlib.pyplot as plt

def q_learning(
    n_episodes=10000,
    alpha=0.1,
    gamma=0.99,
    epsilon=1.0,
    epsilon_decay=0.995,
    epsilon_min=0.01,
    env_name="FrozenLake-v1",
    is_slippery=True,
    seed=42
):
    """
    Implémentation complète du Q-Learning sur l'environnement FrozenLake.

    Paramètres :
        n_episodes : nombre d'épisodes d'entraînement
        alpha : taux d'apprentissage
        gamma : facteur d'actualisation
        epsilon : taux d'exploration initial
        epsilon_decay : taux de décroissance d'epsilon
        epsilon_min : valeur minimale d'epsilon
        env_name : nom de l'environnement Gym
        is_slippery : si True, la glace est glissante (aléatoire)
        seed : graine aléatoire pour la reproductibilité

    Retourne :
        q_table : la table Q apprise
        rewards_history : historique des récompenses par épisode
    """

    # Initialisation de l'environnement
    env = gym.make(env_name, is_slippery=is_slippery)
    np.random.seed(seed)
    env.reset(seed=seed)

    n_states = env.observation_space.n
    n_actions = env.action_space.n

    # Initialisation de la Q-table : toutes les valeurs à zéro
    q_table = np.zeros((n_states, n_actions))

    # Suivi des récompenses pour la visualisation de la convergence
    rewards_history = []

    for episode in range(n_episodes):
        state = env.reset()[0]
        total_reward = 0
        done = False

        while not done:
            # Politique epsilon-greedy
            if np.random.random() < epsilon:
                action = env.action_space.sample()  # Exploration aléatoire
            else:
                action = np.argmax(q_table[state])  # Exploitation du meilleur Q

            # Exécution de l'action dans l'environnement
            next_state, reward, terminated, truncated, _ = env.step(action)
            done = terminated or truncated

            # Mise à jour de la Q-table selon l'équation de Bellman
            best_next_q = np.max(q_table[next_state])
            q_table[state][action] = q_table[state][action] + alpha * (
                reward + gamma * best_next_q - q_table[state][action]
            )

            state = next_state
            total_reward += reward

        rewards_history.append(total_reward)

        # Décroissance d'epsilon après chaque épisode
        epsilon = max(epsilon_min, epsilon * epsilon_decay)

    env.close()
    return q_table, rewards_history


def policy_extraction(q_table, n_states=16):
    """
    Extrait la politique optimale de la Q-table.
    Affiche la grille avec les actions recommandées.

    Mapping d'actions : 0=Gauche, 1=Bas, 2=Droite, 3=Haut
    """
    arrows = ['←', '↓', '→', '↑']
    grid_size = 4

    print("Politique optimale extraite de la Q-table :")
    print("=" * 30)

    policy = np.argmax(q_table, axis=1)
    grid = []

    for i in range(n_states):
        grid.append(arrows[policy[i]])
        if (i + 1) % grid_size == 0:
            print("  ".join(grid[-grid_size:]))
            grid = grid[:-grid_size]

    print("=" * 30)
    return policy


def visualize_convergence(rewards_history, window_size=100):
    """
    Visualise la convergence de l'apprentissage avec une moyenne mobile.

    Paramètres :
        rewards_history : liste des récompenses par épisode
        window_size : taille de la fenêtre pour la moyenne mobile
    """
    rewards = np.array(rewards_history)

    # Calcul de la moyenne mobile
    cumsum = np.cumsum(np.insert(rewards, 0, 0))
    moving_avg = (cumsum[window_size:] - cumsum[:-window_size]) / window_size

    # Création du graphique
    fig, ax = plt.subplots(figsize=(12, 6))

    ax.plot(rewards, alpha=0.3, color='gray', label='Récompense par épisode')
    ax.plot(range(window_size - 1, len(rewards)), moving_avg,
            color='blue', linewidth=2, label=f'Moyenne mobile ({window_size} épisodes)')

    ax.set_xlabel("Épisode", fontsize=12)
    ax.set_ylabel("Récompense cumulative", fontsize=12)
    ax.set_title("Convergence du Q-Learning sur FrozenLake", fontsize=14)
    ax.legend(fontsize=11)
    ax.grid(True, alpha=0.3)
    ax.set_ylim(-0.1, 1.1)

    plt.tight_layout()
    plt.savefig("qlearning_convergence.png", dpi=150)
    plt.show()

    return moving_avg


# --- Exécution principale ---
if __name__ == "__main__":
    # Entraînement du modèle
    q_table, rewards = q_learning(
        n_episodes=10000,
        alpha=0.1,
        gamma=0.99,
        epsilon=1.0,
        epsilon_decay=0.995,
        epsilon_min=0.01
    )

    # Extraction et affichage de la politique optimale
    policy = policy_extraction(q_table)

    # Taux de réussite sur les 100 derniers épisodes
    success_rate = np.mean(rewards[-100:])
    print(f"Taux de réussite (100 derniers épisodes) : {success_rate:.1%}")

    # Visualisation de la convergence
    moving_avg = visualize_convergence(rewards)

Introduction au Deep Q-Network (DQN)

Le Q-Learning classique fonctionne remarquablement bien pour des environnements avec un nombre restreint d’états discrets. Cependant, lorsque l’espace d’états devient très grand — ou continu, comme dans les jeux vidéo avec des images en entrée — la Q-table devient impraticable. Imaginez une table avec des milliards voire des trillions de lignes !

C’est ici qu’intervient le Deep Q-Network (DQN), introduit par DeepMind en 2013. L’idée centrale est brillante dans sa simplicité : au lieu de stocker la Q-table dans une matrice explicite, on utilise un réseau de neurones profond pour approximer la fonction Q. Le réseau prend l’état en entrée (par exemple, les pixels d’un écran de jeu) et produit en sortie les valeurs Q pour chaque action possible.

Cette approche présente plusieurs avantages majeurs. Premièrement, elle permet de généraliser : le réseau peut estimer les valeurs Q pour des états qu’il n’a jamais vus auparavant, en se basant sur la similarité avec des états connus. Deuxièmement, elle élimine le besoin de mémoire explicite proportionnelle au nombre d’états. Troisièmement, elle rend possible l’application du Q-Learning à des problèmes de perception directe, comme jouer à des jeux vidéo à partir des pixels bruts de l’écran.

Le DQN introduit également deux innovations techniques importantes pour stabiliser l’apprentissage : le replay buffer, qui stocke les expériences passées et les réutilise de manière aléatoire pour briser les corrélations temporelles, et le target network, une copie périodiquement mise à jour du réseau principal qui fournit des cibles stables pour l’équation de Bellman. Le DQN a atteint des performances surhumaines sur de nombreux jeux Atari, démontrant la puissance de cette approche.

Les hyperparamètres du Q-Learning

Le bon fonctionnement du Q-Learning dépend étroitement du réglage de ses hyperparamètres. Comprendre leur rôle est essentiel pour obtenir de bonnes performances.

α — Le taux d’apprentissage (learning rate)

Le paramètre α contrôle la vitesse à laquelle l’agent intègre les nouvelles informations. Avec α = 1, chaque nouvelle expérience remplace complètement l’ancienne estimation. Avec α = 0.1, l’agent n’ajuste ses croyances que progressivement, ce qui rend l’apprentissage plus stable mais plus lent.

En pratique, une valeur typique se situe entre 0.01 et 0.2. Pour les environnements bruyants, il est préférable d’utiliser un α faible pour éviter que des récompenses aberrantes ne perturbent excessivement la Q-table. On peut également faire décroître α au fil du temps, de manière similaire à ε.

γ — Le facteur d’actualisation (discount factor)

Le paramètre γ détermine l’horizon temporel de l’agent. Avec γ = 0, l’agent est uniquement motivé par la récompense immédiate, ignorant les conséquences futures de ses actions. Avec γ = 0.99, l’agent planifie sur le très long terme, accordant presque autant d’importance aux récompenses lointaines qu’aux récompenses immédiates.

Le choix de γ dépend de la nature de l’environnement. Pour des problèmes où les récompenses sont principalement immédiates (par exemple, un robot qui doit éviter des obstacles en temps réel), un γ faible (0.8–0.9) est approprié. Pour des problèmes où les récompenses sont différées (par exemple, un jeu d’échecs où la victoire n’intervient qu’après des dizaines de coups), un γ élevé (0.95–0.99) est nécessaire.

ε — Le taux d’exploration initial

Le paramètre ε fixe la probabilité d’exploration au début de l’entraînement. Généralement, on initialise ε à 1.0 (exploration totale) pour que l’agent explore librement l’environnement au début. Si l’agent partait directement en mode exploitation avec une Q-table vide, il resterait piégé dans une politique sous-optimale sans jamais découvrir de meilleures alternatives.

decay_rate — Le taux de décroissance d’epsilon

Le decay_rate détermine la vitesse à laquelle ε diminue. Avec un decay_rate = 0.995, ε est multiplié par 0.995 après chaque épisode. Sur 10 000 épisodes, ε passe de 1.0 à environ 10⁻²² — ce qui signifie qu’au bout de suffisamment d’épisodes, l’agent exploite presque exclusivement ses connaissances.

Un decay_rate trop élevé conduit à une exploration insuffisante : l’agent arrête d’explorer avant d’avoir découvert toutes les régions importantes de l’espace d’états. Un decay_rate trop faible ralentit inutilement la convergence. Une valeur typique se situe entre 0.99 et 0.999.

n_episodes — Le nombre d’épisodes

Le nombre d’épisodes détermine la durée totale de l’entraînement. Pour des environnements simples comme FrozenLake 4×4, 5 000 à 10 000 épisodes suffisent généralement. Pour des environnements plus complexes, des centaines de milliers d’épisodes peuvent être nécessaires.

Un indicateur utile pour déterminer si le nombre d’épisodes est suffisant est la convergence de la moyenne mobile des récompenses : lorsqu’elle se stabilise, l’agent a probablement appris la politique optimale (ou au moins une politique de qualité satisfaisante).

Avantages et limites du Q-Learning

Avantages

• Simplicité conceptuelle : l’algorithme est relativement simple à comprendre et à implémenter. L’équation de Bellman tient en une ligne de code.
• Model-free : aucune connaissance préalable de la dynamique de l’environnement n’est requise. L’apprentissage se fait entièrement par interaction directe.
• Convergence garantie : sous certaines conditions (exploration suffisante, taux d’apprentissage décroissant correctement), le Q-Learning converge mathématiquement vers la fonction Q optimale Q*.
• Légèreté computationnelle : pour des environnements de taille modeste, l’algorithme est extrêmement rapide et nécessite peu de ressources mémoire.
• Polyvalence : applicable à de nombreux domaines, des jeux vidéo à la robotique, en passant par la gestion de portefeuilles financiers.
• Interprétabilité : la Q-table est directement lisible et compréhensible. On peut extraire et visualiser la politique optimale à tout moment.

Limites

• Malédiction de la dimensionalité : la taille de la Q-table croît exponentiellement avec le nombre d’états et d’actions. Pour des environnements complexes, la table devient ingérable.
• États continus : le Q-Learning classique ne fonctionne qu’avec des états discrets. Pour des espaces d’états continus, il faut soit discrétiser (avec une perte d’information), soit passer à des méthodes d’approximation fonctionnelle comme le DQN.
• Sensibilité aux hyperparamètres : le choix de α, γ, ε et du decay_rate influence fortement les performances. Un mauvais réglage peut conduire à une divergence ou à une convergence vers une politique sous-optimale.
• Sur-estimation : le Q-Learning a tendance à surestimer les valeurs Q, en particulier dans les environnements bruyants. Cette biais provient de l’utilisation du max dans l’équation de Bellman. Des variantes comme le Double Q-Learning ont été proposées pour corriger ce problème.
• Lenteur d’apprentissage : dans les environnements avec des récompenses différées ou clairsemées, l’agent peut mettre un temps prohibitif à découvrir les premières récompenses positives.
• Mémoire explicite : chaque couple (état, action) doit être stocké individuellement, ce qui pose des problèmes d’échelle pour les environnements à grand nombre d’états.

4 cas d’usage concrets du Q-Learning

1. Navigation autonome de robots mobiles

Un robot mobile dans un entrepôt logistique peut utiliser le Q-Learning pour apprendre à naviguer efficacement entre les rayons. Chaque position discrétisée de l’entrepôt constitue un état, les directions de déplacement sont les actions, et les récompenses sont attribuées en fonction de la proximité avec la destination et de l’évitement d’obstacles. Le robot apprend ainsi à optimiser ses trajets sans avoir besoin d’une carte précise de l’entrepôt, s’adaptant dynamiquement aux changements de configuration.

2. Optimisation des feux de circulation

Dans un réseau de feux tricolores urbains, chaque intersection peut être modélisée comme un état (configuration des feux et du trafic), les actions correspondent aux changements de phase des feux, et les récompenses sont inversement proportionnelles au temps d’attente moyen des véhicules. Le Q-Learning permet d’optimiser la synchronisation des feux en temps réel, réduisant significativement les embouteillages. Des études ont montré des réductions de 15 à 30 % du temps de trajet moyen grâce à cette approche.

3. Algorithmes de trading automatisé

En finance quantitative, le Q-Learning peut être appliqué à la prise de décision de trading. Les états représentent les configurations du marché (prix, volumes, indicateurs techniques), les actions sont « acheter », « vendre » ou « conserver », et les récompenses correspondent aux gains ou pertes réalisés. Bien que les marchés financiers soient notoirement non stationnaires et bruyants, des variantes avancées du Q-Learning combinées à des techniques de traitement du signal ont montré des résultats prometteurs pour certaines stratégies de trading à haute fréquence.

4. Recommandation personnalisée de contenu

Les plateformes de streaming et de commerce en ligne utilisent des approches inspirées du Q-Learning pour personnaliser leurs recommandations. Chaque utilisateur est dans un état (son profil et son historique de navigation), les actions sont les contenus proposés, et les récompenses sont les interactions observées (clic, temps de visionnage, achat). L’algorithme apprend ainsi à maximiser l’engagement de chaque utilisateur individuellement, s’adaptant en continu à l’évolution de ses préférences.

Voir aussi

• Maîtriser les Duodigits en Python : Guide Complet pour Optimiser vos Calculs Numériques
• Maîtriser les Permutations de Projet avec Python : Guide Complet pour Développeurs