Le « reinforcement learning » ou apprentissage par renforcement, est une méthode de Machine Learning permettant de réaliser des tâches complexes de façon autonome.
Encore récemment, cette famille d’algorithme a fait parler d’elle dans le domaine de l’e-sport lors de la sortie de AlphaStar, un algorithme développé pour défier les meilleurs joueurs du monde à StarCarft. Ces algorithmes ont un fort potentiel mais s’avèrent parfois très longs à construire et paramétrer. L’objectif de cet article est de vous permettre de comprendre ce qu’est le Q-learning et de gagner du temps lors de l’implémentation de ce type de solution.
Définitions
Qu'est ce que le reinforcement learning ?
Le reinforcement learning est une méthode de machine learning dont l’objectif est de permettre à un agent (entité virtuelle : robot, programme, etc.), placé dans un environnement interactif (ses actions modifient l’état de l’environnement), de choisir des actions maximisant des récompenses quantitatives. L’agent fait des essais et améliore sa stratégie d’action en fonction des récompenses fournies par l’environnement.
Qu'est-ce que le Q-learning ?
Il existe de nombreux algorithmes de reinforcement learning catégorisés en plusieurs sous-familles. Le Q-learning est à la fois relativement simple et permet en même temps de comprendre des mécanismes d’apprentissage communs à beaucoup d’autres modèles.
Pour illustrer de manière introductive, un algorithme de Q-learning fonctionne pour résoudre un problème basique. Par exemple, dans le jeu du labyrinthe, l’objectif du jeu est d’apprendre au robot à sortir du labyrinthe le plus rapidement possible alors qu’il est placé aléatoirement sur l’une des cases blanches. Pour cela, il y a trois étapes centrales dans le processus d’apprentissage :
- Connaitre : définir une fonction action-valeur Q ;
- Renforcer ses connaissances : mettre à jour la fonction Q ;
- Agir : adopter une stratégie d’actions PI
Ainsi, le Q-learning est un algorithme d’apprentissage par renforcement qui cherche à trouver la meilleure action à entreprendre compte tenu de l’état actuel. Il est considéré comme hors politique parce que la fonction de Q-learning apprend des actions qui sont en dehors de la politique actuelle, comme prendre des actions aléatoires, et donc une politique n’est pas nécessaire. Plus précisément, le Q-learning cherche à apprendre une politique qui maximise la récompense totale.
Le « Q » de Q-learning est synonyme de qualité. Dans ce cas, la qualité représente l’utilité d’une action donnée pour obtenir une récompense future.
Q-learning : mise en place concrète
Création d'un tableau Q
Lorsque l’apprentissage est réalisé, nous créons ce que l’on appelle une table ou une matrice de type q qui suit la forme [état, action] et nous initialisons nos valeurs à zéro. Nous mettons ensuite à jour et stockons nos q-valeurs après chaque épisode. Ce tableau de valeurs devient une table de référence pour notre agent qui sélectionne la meilleure action en fonction des valeurs de cette matrice.
import numpy as np
# Initialize q-table values to 0
Q = np.zeros((state_size, action_size))
Q-learning et mise à jour
L’étape suivante consiste simplement pour l’agent à interagir avec l’environnement et à effectuer des mises à jour des paires état-action dans notre tableau Q[state, action].
• Agir : Explorer ou Exploiter
Un agent interagit avec l’environnement de deux manières. La première consiste à utiliser la table Q comme référence et à visualiser toutes les actions possibles pour un état donné. L’agent sélectionne alors l’action basée sur la valeur maximale de ces actions. C’est ce qu’on appelle l’exploitation puisque nous utilisons les informations dont nous disposons pour prendre une décision.
La deuxième manière consiste à agir de façon aléatoire. C’est ce qu’on appelle l’exploration. Au lieu de sélectionner des actions en fonction de la récompense future maximale, nous choisissons une action au hasard. Agir au hasard est important car cela permet à l’agent d’explorer et de découvrir de nouveaux états qui, autrement, pourraient ne pas être sélectionnés pendant le processus d’exploitation.
Vous pouvez équilibrer l’exploration / exploitation en utilisant epsilon (ε) et en fixant la valeur de la fréquence à laquelle vous souhaitez explorer ou exploiter. Voici un code approximatif qui dépendra de la façon dont l’état et l’espace d’actions sont configurés.
import random
# Set the percent you want to explore
epsilon = 0.2
if random.uniform(0, 1) < epsilon:
"""
Explore: select a random action
"""
else:
"""
Exploit: select the action with max value (future reward)
"""
• Mise à jour du q-tableau
Les mises à jour ont lieu après chaque étape ou action et se terminent lorsqu’un épisode est terminé. Dans ce cas, « terminé » signifie que l’agent a atteint un point terminal. Par exemple, un état terminal peut atterrir sur une page de paiement ou réaliser un objectif souhaité. Avec suffisamment d’exploration (étapes et épisodes), l’agent sera capable de converger et apprendre les valeurs optimales de q ou q-star (Q∗).
Voici les 3 étapes de base :
- L’agent commence dans un état (s1) prend une action (a1) et reçoit une récompense (r1).
- L’agent choisit l’action en se référant à la table Q avec la valeur la plus élevée (max) OU au hasard (epsilon, ε).
- Mise à jour des q-valeurs
Voici la règle de mise à jour de base pour le Q-learning :
# Update q values
Q[state, action] = Q[state, action] + lr * (reward + gamma * np.max(Q[new_state, :]) — Q[state, action])
Dans la mise à jour ci-dessus, il y a quelques variables que nous n’avons pas encore mentionnées. Ce qui se passe ici, c’est que nous ajustons nos valeurs q en fonction de la différence entre les nouvelles valeurs actualisées et les anciennes. Nous actualisons les nouvelles valeurs en utilisant le gamma et nous ajustons notre taille de pas en utilisant le taux d’apprentissage (lr).
Quelques Références
- Taux d’apprentissage : lr, souvent appelé alpha, peut être défini comme le degré d’acceptation de la nouvelle valeur par rapport à l’ancienne. Ci-dessus, nous prenons la différence entre la nouvelle et l’ancienne valeur, puis nous multiplions cette valeur par le taux d’apprentissage. Cette valeur est ensuite ajoutée à notre valeur q précédente, ce qui la fait évoluer dans la direction de notre dernière mise à jour.
- Gamma : gamma ou γ est un facteur d’actualisation. Il est utilisé pour équilibrer la récompense immédiate et future. Dans notre règle de mise à jour ci-dessus, vous pouvez voir que nous appliquons la décote à la récompense future. En général, cette valeur peut varier entre 0,8 et 0,99.
- Récompense : la récompense (reward) est la valeur reçue après avoir effectué une certaine action à un état donné. Une récompense peut survenir à n’importe quel pas de temps donné ou seulement au pas de temps terminal.
- Max : np.max() utilise la bibliothèque numpy et prend le maximum de la récompense future et l’applique à la récompense de l’état actuel. Cela a pour effet d’influencer l’action actuelle par la récompense future possible. En effet, grâce au Q-learning, nous sommes capables d’allouer la récompense future aux actions actuelles pour aider l’agent à sélectionner l’action la plus rentable à tout état donné.
