Introduction au Q-learning : un tutoriel pour débuter

L’apprentissage par renforcement (RL) est la branche de l’apprentissage automatique où un agent apprend en interagissant avec son environnement afin de découvrir la stratégie optimale pour atteindre ses objectifs. Cela diffère nettement des algorithmes supervisés, qui nécessitent d’ingérer et de traiter des données d’entraînement. L’apprentissage par renforcement n’exige pas de données préalables : il apprend de l’environnement et d’un système de récompenses pour prendre de meilleures décisions.

Par exemple, dans un jeu vidéo Mario, si le personnage effectue une action aléatoire (p. ex. aller à gauche), il peut recevoir une récompense en fonction de cette action. Après l’action, l’agent (Mario) se retrouve dans un nouvel état, et le processus se répète jusqu’à ce que le personnage atteigne la fin du niveau ou perde une vie. 

Cet épisode se répète de nombreuses fois, jusqu’à ce que Mario apprenne à naviguer dans l’environnement en maximisant les récompenses. 

Image de l’auteur

On peut décomposer l’apprentissage par renforcement en cinq étapes simples :

1. L’agent se trouve à l’état initial dans un environnement.
2. Il choisit une action selon une stratégie donnée.
3. Il reçoit une récompense (ou une pénalité) en fonction de cette action.
4. Il apprend des actions passées et optimise progressivement sa stratégie. 
5. Le processus se répète jusqu’à trouver une stratégie optimale. 

Pour en savoir plus, consultez notre tutoriel Introduction to Reinforcement Learning. Vous y explorerez le fonctionnement du RL avec des exemples de code. 

Dans ce tutoriel, nous allons présenter le Q-learning et comprendre pourquoi le Deep Q-learning est nécessaire. Nous verrons également comment implémenter et entraîner des algorithmes de Q-learning from scratch avec Numpy et Gymnasium.

Remarque : si vous débutez en machine learning, nous vous recommandons de suivre notre parcours Machine Learning Scientist with Python pour mieux comprendre l’apprentissage par renforcement et le Q-learning. 

Qu’est-ce que le Q-learning ?

Le Q-learning est un algorithme sans modèle, fondé sur la valeur, et off-policy, qui identifie la meilleure suite d’actions à partir de l’état courant de l’agent. Le « Q » signifie quality (qualité). La qualité mesure la valeur d’une action pour maximiser les récompenses futures.  

Les algorithmes avec modèle utilisent des fonctions de transition et de récompense pour estimer la politique optimale et construire un modèle. À l’inverse, les algorithmes sans modèle apprennent les conséquences de leurs actions par l’expérience, sans fonction de transition ni de récompense explicite. 

Les méthodes fondées sur la valeur entraînent une fonction de valeur pour déterminer quels états sont les plus utiles et quelle action entreprendre. Les méthodes fondées sur la politique, elles, entraînent directement la politique afin d’apprendre quelle action prendre dans un état donné.

En off-policy, l’algorithme évalue et met à jour une politique différente de celle utilisée pour agir. À l’inverse, un algorithme on-policy évalue et améliore la même politique que celle employée pour agir.  

Terminologie clé du Q-learning

Avant de voir le fonctionnement du Q-learning, passons quelques notions utiles pour en maîtriser les fondamentaux. 

• États (s) : position actuelle de l’agent dans l’environnement. 
• Action (a) : décision effectuée par l’agent dans un état donné. 
• Récompenses : à chaque action, l’agent reçoit une récompense ou une pénalité. 
• Épisodes : fin d’un parcours, lorsque l’agent ne peut plus agir (objectif atteint ou échec). 
• Q(S_t+1, a) : valeur Q optimale attendue pour une action donnée dans un état donné. 
• Q(S_t, A_t) : estimation courante de Q(S_t+1, a).
• Q-table : table que l’agent maintient, associant ensembles d’états et d’actions.
• Différences temporelles (TD) : méthode d’estimation de la valeur attendue de Q(S_t+1, a) à partir des états et actions présents et passés. 

Comment fonctionne le Q-learning ?

Nous allons détailler le fonctionnement du Q-learning à l’aide de l’exemple du lac gelé. Dans cet environnement, l’agent doit traverser le lac gelé du départ à l’objectif sans tomber dans les trous. La meilleure stratégie consiste à atteindre l’objectif par le chemin le plus court. 

Gif de l’auteur

Q-table

L’agent utilise une Q-table pour choisir la meilleure action possible selon la récompense attendue pour chaque état de l’environnement. En clair, une Q-table est une structure de données qui liste les couples actions/états, et l’algorithme de Q-learning met à jour les valeurs de cette table. 

Fonction Q

La fonction Q s’appuie sur l’équation de Bellman et prend en entrée un état (s) et une action (a). Cette équation simplifie le calcul des valeurs d’état et des valeurs état–action. 

Image tirée de freecodecamp.org

Algorithme de Q-learning

Image de l’auteur

Initialiser la Q-table

On commence par initialiser la Q-table. Les colonnes correspondent au nombre d’actions et les lignes au nombre d’états.

Dans notre exemple, le personnage peut se déplacer vers le haut, le bas, la gauche et la droite. Nous avons donc quatre actions possibles et quatre états (départ, inactif, mauvais chemin et fin). On peut assimiler le mauvais chemin au fait de tomber dans un trou. Nous initialisons la Q-table avec des zéros. 

Image de l’auteur

Choisir une action

La deuxième étape est simple. Au début, l’agent choisit une action aléatoire (bas ou droite), puis lors des passages suivants, il s’appuie sur la Q-table mise à jour pour sélectionner l’action. 

Exécuter une action

Choisir puis exécuter une action se répète plusieurs fois jusqu’à la fin de la boucle d’entraînement. La première action et le premier état sont sélectionnés via la Q-table. Dans notre cas, toutes les valeurs de la Q-table valent 0. 

Ensuite, l’agent se déplace vers le bas et met à jour la Q-table en appliquant l’équation de Bellman. À chaque déplacement, nous mettons à jour les valeurs de la Q-table et nous l’utilisons pour déterminer la meilleure décision suivante. 

Au départ, l’agent est en mode exploration et choisit des actions aléatoires pour découvrir l’environnement. La stratégie epsilon-greedy est une méthode simple pour équilibrer exploration et exploitation. Epsilon représente la probabilité d’explorer ; lorsqu’elle est faible, l’agent privilégie l’exploitation. 

Au début, le taux d’epsilon est élevé : l’agent explore. À mesure qu’il explore l’environnement, epsilon diminue et l’agent commence à exploiter. Pendant l’exploration, à chaque itération, l’agent devient plus confiant dans l’estimation des valeurs Q.

Image de l’auteur

Dans l’exemple du lac gelé, l’agent ne connaît pas l’environnement et commence donc par une action aléatoire (descendre). Comme on le voit ci-dessus, la Q-table est mise à jour avec l’équation de Bellman.

Mesurer les récompenses

Après chaque action, nous mesurons le résultat et la récompense. 

• Récompense pour atteindre l’objectif : +1
• Récompense pour un mauvais chemin (tomber dans un trou) : 0
• Récompense pour rester sur le lac gelé ou être inactif : 0. 

Mettre à jour la Q-table

Nous mettons à jour la fonction Q(S_t, A_t) avec la formule. Elle utilise les valeurs Q estimées à l’épisode précédent, le taux d’apprentissage et l’erreur de différence temporelle. Cette erreur se calcule avec la récompense immédiate, la récompense future maximale actualisée attendue, et l’ancienne estimation Q. 

On répète le processus jusqu’à ce que la Q-table se stabilise et que la fonction de valeur Q soit maximisée. 

Image de l’auteur | Visualisation de l’équation : Thomas Simonini

Au début, l’agent explore l’environnement pour mettre à jour la Q-table. Une fois la Q-table suffisamment renseignée, il passe à l’exploitation et prend de meilleures décisions. 

Image de l’auteur

Dans le cas du lac gelé, l’agent apprend à emprunter le chemin le plus court vers l’objectif en évitant les trous. 

Tutoriel Python sur le Q-learning 

Dans cette section, nous allons construire un modèle de Q-learning from scratch avec l’environnement Gymnasium, Pygame et Numpy. Le tutoriel Python est une adaptation du Notebook de Thomas Simonini. Nous verrons l’initialisation de l’environnement et de la Q-table, la définition d’une politique greedy, le paramétrage des hyperparamètres, la création et l’exécution de la boucle d’entraînement et d’évaluation, ainsi que la visualisation des résultats.   

Si vous rencontrez des difficultés pour créer et exécuter votre boucle d’entraînement, consultez le code source accompagné de sa sortie.   

Mise en place

Configurer un affichage virtuel

Nous allons d’abord installer les dépendances nécessaires pour générer une vidéo de relecture (Gif). Il nous faut un écran virtuel (pyvirtualdisplay) pour rendre l’environnement et enregistrer les images. 

Remarque : avec %%capture, nous masquons la sortie de la cellule Jupyter. 

%%capture
!pip install pyglet==1.5.1
!apt install python-opengl
!apt install ffmpeg
!apt install xvfb
!pip3 install pyvirtualdisplay

# Virtual display
from pyvirtualdisplay import Display

virtual_display = Display(visible=0, size=(1400, 900))
virtual_display.start()

Installer les dépendances

Installons maintenant les dépendances qui nous aideront à créer, exécuter et évaluer la boucle d’entraînement. 

• gymnasium : pour initialiser l’environnement FrozenLake-v1.
• pygame : pour l’interface de FrozenLake-v1.
• numPy : pour créer et manipuler la Q-table.

%%capture
!pip install gymnasium
!pip install pygame
!pip install numpy

!pip install imageio imageio_ffmpeg

Importer les packages

Importons maintenant les bibliothèques nécessaires. 

• Imageio sert à créer l’animation. 
• tqdm sert à afficher des barres de progression. 

import numpy as np
import gymnasium as gym
import random
import imageio
from tqdm.notebook import trange

Environnement Gymnasium frozen lake 

Nous allons créer un environnement 4x4 non glissant avec la bibliothèque Frozen Lake de Gymnasium. 

• Deux tailles de grille existent : « 4x4 » et « 8x8 ».
• Si is_slippery=True, l’agent peut ne pas aller dans la direction voulue à cause du caractère glissant du lac gelé. 

Après l’initialisation, nous procédons à une analyse de l’environnement. 

env = gym.make("FrozenLake-v1",map_name="4x4",is_slippery=False)

print("Observation Space", env.observation_space)
print("Sample observation", env.observation_space.sample()) # display a random observation

L’environnement comporte 16 espaces (états) uniques affichés à des positions aléatoires. 

Observation Space Discrete(16)
Sample observation 15

Découvrons le nombre d’actions et affichons une action aléatoire. 

Espace d’actions :

• 0 : aller à gauche
• 1 : descendre
• 2 : aller à droite
• 3 : monter

Fonction de récompense :

• Atteindre l’objectif : +1
• Tomber dans un trou : 0
• Rester sur le lac gelé : 0

print("Action Space Shape", env.action_space.n)
print("Action Space Sample", env.action_space.sample())

Action Space Shape 4
Action Space Sample 1

Créer et initialiser la Q-table

La Q-table a pour colonnes les actions et pour lignes les états. Avec Gymnasium, on récupère la taille de l’espace d’actions et de l’espace d’états, puis on crée la Q-table. 

state_space = env.observation_space.n
print("There are ", state_space, " possible states")

action_space = env.action_space.n
print("There are ", action_space, " possible actions")

There are  16  possible states
There are  4  possible actions

Pour l’initialisation, nous créons un tableau Numpy de dimensions espace d’états × espace d’actions. Ici, un tableau 16 × 4. 

def initialize_q_table(state_space, action_space):
  Qtable = np.zeros((state_space, action_space))
  return Qtable

Qtable_frozenlake = initialize_q_table(state_space, action_space)

Politique epsilon-greedy

Précédemment, nous avons vu la stratégie epsilon-greedy qui gère le compromis exploration/exploitation. Avec une probabilité de 1 − ɛ, on exploite, et avec la probabilité ɛ, on explore. 

Dans epsilon_greedy_policy :

1. On génère un nombre aléatoire entre 0 et 1.
2. S’il est supérieur à epsilon, on exploite : l’agent choisit l’action de plus forte valeur pour l’état courant.
3. Sinon, on explore (action aléatoire). 

def epsilon_greedy_policy(Qtable, state, epsilon):
  random_int = random.uniform(0,1)
  if random_int > epsilon:
    action = np.argmax(Qtable[state])
  else:
    action = env.action_space.sample()
  return action

Définir la politique greedy

Le Q-learning est un algorithme off-policy : la politique utilisée pour agir diffère de celle utilisée pour la mise à jour. 

Dans cet exemple, la politique epsilon-greedy est la politique d’action, tandis que la politique greedy sert à la mise à jour. 

La politique greedy sera aussi la politique finale une fois l’agent entraîné. Elle sélectionne l’action de plus forte valeur pour un état donné dans la Q-table.

def greedy_policy(Qtable, state):
  action = np.argmax(Qtable[state])
  return action

Hyperparamètres du modèle

Ces hyperparamètres sont utilisés dans la boucle d’entraînement ; leur réglage fin améliore les résultats. 

L’agent doit explorer suffisamment l’espace des états pour apprendre de bonnes approximations de valeur ; il faut donc un décroissance progressive d’epsilon. Si le taux de décroissance est trop élevé, l’agent risque de se bloquer car il n’aura pas assez exploré.

• 10 000 épisodes d’entraînement et 100 épisodes d’évaluation.
• Taux d’apprentissage : 0,7.
• Environnement « FrozenLake-v1 » avec 99 pas maximum par épisode.
• Gamma (taux d’actualisation) : 0,95.
• eval_seed : graine d’évaluation pour l’environnement.
• Probabilité d’exploration epsilon au départ : 1,0 ; probabilité minimale : 0,05.
• Taux de décroissance exponentiel d’epsilon : 0,0005.

# Training parameters
n_training_episodes = 10000
learning_rate = 0.7        

# Evaluation parameters
n_eval_episodes = 100      

# Environment parameters
env_id = "FrozenLake-v1"   
max_steps = 99             
gamma = 0.95               
eval_seed = []             

# Exploration parameters
max_epsilon = 1.0           
min_epsilon = 0.05           
decay_rate = 0.0005           

Entraînement du modèle 

Dans la boucle d’entraînement, nous allons :

1. Créer une boucle sur les épisodes d’entraînement.
2. Réduire epsilon au début de chaque épisode, car nous voulons moins d’exploration et plus d’exploitation au fil du temps. 
3. Réinitialiser l’environnement.
4. Créer une boucle imbriquée sur le nombre maximal de pas.
5. Choisir l’action avec la politique epsilon-greedy. 
6. Exécuter l’action (A_t) et observer la récompense attendue (R_t+1) et le nouvel état (S_t+1).
7. Prendre l’action (a) et observer l’état résultant (s’) et la récompense (r).
8. Mettre à jour la fonction Q avec la formule. 
9. Si done=True, terminer l’épisode et sortir de la boucle.
10. Mettre à jour l’état courant avec le nouvel état. 
11. Après tous les épisodes d’entraînement, la fonction renvoie la Q-table mise à jour. 

def train(n_training_episodes, min_epsilon, max_epsilon, decay_rate, env, max_steps, Qtable):
  for episode in trange(n_training_episodes):
 
    epsilon = min_epsilon + (max_epsilon - min_epsilon)*np.exp(-decay_rate*episode)
    # Reset the environment
    state = env.reset()
    step = 0
    done = False

    # repeat
    for step in range(max_steps):
   
      action = epsilon_greedy_policy(Qtable, state, epsilon)

   
      new_state, reward, done, info = env.step(action)

   
      Qtable[state][action] = Qtable[state][action] + learning_rate * (reward + gamma * np.max(Qtable[new_state]) - Qtable[state][action])

      # If done, finish the episode
      if done:
        break
     
      # Our state is the new state
      state = new_state
  return Qtable

Il nous a fallu 3 secondes pour terminer 10 000 épisodes d’entraînement. 

Qtable_frozenlake = train(n_training_episodes, min_epsilon, max_epsilon, decay_rate, env, max_steps, Qtable_frozenlake)

Comme on le voit, la Q-table entraînée contient désormais des valeurs, et l’agent va s’y référer pour naviguer dans l’environnement et atteindre l’objectif.  

Qtable_frozenlake

array([[0.73509189, 0.77378094, 0.77378094, 0.73509189],
      [0.73509189, 0.        , 0.81450625, 0.77378094],
      [0.77378094, 0.857375  , 0.77378094, 0.81450625],
      [0.81450625, 0.        , 0.77378094, 0.77378094],
      [0.77378094, 0.81450625, 0.        , 0.73509189],
      [0.        , 0.        , 0.        , 0.        ],
      [0.        , 0.9025    , 0.        , 0.81450625],
      [0.        , 0.        , 0.        , 0.        ],
      [0.81450625, 0.        , 0.857375  , 0.77378094],
      [0.81450625, 0.9025    , 0.9025    , 0.        ],
      [0.857375  , 0.95      , 0.        , 0.857375  ],
      [0.        , 0.        , 0.        , 0.        ],
      [0.        , 0.        , 0.        , 0.        ],
      [0.        , 0.9025    , 0.95      , 0.857375  ],
      [0.9025    , 0.95      , 1.        , 0.9025    ],
      [0.        , 0.        , 0.        , 0.        ]])

Évaluation

La fonction evaluate_agent s’exécute pendant n_eval_episodes épisodes et renvoie la moyenne et l’écart type des récompenses. 

1. Dans la boucle, on vérifie d’abord s’il existe une graine d’évaluation. Sinon, on réinitialise l’environnement sans graine. 
2. La boucle imbriquée s’exécute jusqu’à max_steps.
3. L’agent choisit l’action à récompense future maximale attendue pour l’état courant via la Q-table. 
4. On calcule la récompense.
5. On met à jour l’état.
6. Si terminé (chute dans un trou ou objectif atteint), on sort de la boucle.
7. On stocke les résultats.
8. Enfin, on calcule la moyenne et l’écart type. 

def evaluate_agent(env, max_steps, n_eval_episodes, Q, seed):

  episode_rewards = []
  for episode in range(n_eval_episodes):
    if seed:
      state = env.reset(seed=seed[episode])
    else:
      state = env.reset()
    step = 0
    done = False
    total_rewards_ep = 0
   
    for step in range(max_steps):
      # Take the action (index) that have the maximum reward
      action = np.argmax(Q[state][:])
      new_state, reward, done, info = env.step(action)
      total_rewards_ep += reward
       
      if done:
        break
      state = new_state
    episode_rewards.append(total_rewards_ep)
  mean_reward = np.mean(episode_rewards)
  std_reward = np.std(episode_rewards)

  return mean_reward, std_reward

Comme vous le voyez, nous obtenons un score parfait avec un écart type nul : notre agent atteint l’objectif lors des 100 épisodes. 

# Evaluate our Agent
mean_reward, std_reward = evaluate_agent(env, max_steps, n_eval_episodes, Qtable_frozenlake, eval_seed)
print(f"Mean_reward={mean_reward:.2f} +/- {std_reward:.2f}")

Mean_reward=1.00 +/- 0.00

Visualiser le résultat

Jusqu’ici, nous avons surtout manipulé des nombres. Pour la démo, créons un Gif animé de l’agent depuis le départ jusqu’à l’objectif. 

1. On crée d’abord l’état en réinitialisant l’environnement avec un entier aléatoire entre 0 et 500. 
2. On rend l’environnement en mode rdb_array pour obtenir un tableau d’images. 
3. On ajoute ensuite img au tableau images. 
4. Dans la boucle, on effectue les pas déterminés par la Q-table et on rend une image à chaque étape. 
5. Enfin, on utilise ce tableau avec imageio pour créer un Gif à une image par seconde. 

def record_video(env, Qtable, out_directory, fps=1):
  images = [] 
  done = False
  state = env.reset(seed=random.randint(0,500))
  img = env.render(mode='rgb_array')
  images.append(img)
  while not done:
    # Take the action (index) that have the maximum expected future reward given that state
    action = np.argmax(Qtable[state][:])
    state, reward, done, info = env.step(action) # We directly put next_state = state for recording logic
    img = env.render(mode='rgb_array')
    images.append(img)
  imageio.mimsave(out_directory, [np.array(img) for i, img in enumerate(images)], fps=fps)

Si vous êtes dans un notebook Jupyter, vous pouvez afficher le Gif avec la fonction Image de IPython.display. 

video_path="/content/replay.gif"
video_fps=1
record_video(env, Qtable_frozenlake, video_path, video_fps)

from IPython.display import Image
Image('./replay.gif')

Vous pouvez désormais partager ces résultats avec vos collègues et vos camarades de classe, ou les publier sur les réseaux sociaux.