Editions ENI Livres | Vidéos | e-Formations
L’apprentissage par renforcement
Introduction
L’apprentissage par renforcement est l’un des trois grands paradigmes d’apprentissage automatique, avec l’apprentissage supervisé et l’apprentissage non supervisé. Il ne s’agit donc pas d’un sous-domaine de l’intelligence artificielle comme le machine learning et le deep learning. On peut d’ailleurs faire de l’apprentissage par renforcement dans chacun de ces deux sous-domaines.
L’apprentissage par renforcement ajoute une notion de récompense quantitative au cours du temps. Autrement dit, les décisions de l’algorithme sont en quelque sorte "notées" ou "récompensées" au cours d’une série d’itérations. Une note positive indique à l’algorithme qu’il est sur la bonne voie, ce qui a pour effet de "renforcer" ses choix précédents. Une note négative lui indique que son choix est mauvais, ce qui l’incite à se modifier, un peu comme dans le contexte d’une probabilité conditionnelle.
L’apprentissage par renforcement cherche à converger vers une solution maximisant les notes positives au cours du temps. L’algorithme peut en quelque sorte anticiper les situations futures pour prendre des décisions permettant d’obtenir un nombre de points finals plus important. Dans le cas d’un jeu de stratégie...
Les bases de l’apprentissage par renforcement
L’apprentissage par renforcement est basé sur les concepts suivants :
-
Essai et erreur : il s’agit d’un problème de prise de décision séquentielle durant lequel le programme teste plusieurs approches et apprend de ses erreurs. Contrairement à l’apprentissage supervisé ou non supervisé, le choix du modèle ne se fait pas une fois pour toutes avant le lancement, mais est plutôt le fruit d’une construction interne du programme au fur et à mesure de ses essais et de ses erreurs.
-
Récompense différée : la récompense qu’obtient le programme n’est pas forcément immédiate. En effet, il faut parfois plusieurs actions (des centaines, des milliers ou bien plus) avant de l’obtenir. Pendant ce temps, le programme poursuit son exploration de l’espace de recherche.
-
Fonction de récompense : pour que le programme prenne des décisions, il faut formaliser son problème de façon rationnelle, ce qui implique la plupart du temps de donner au problème une forme mathématique. Dans ce cas, la récompense à obtenir prend la forme d’une fonction dépendant de l’état du programme et de son action future. Cette fonction de récompense tient également compte de la durée...
Les processus de décision markoviens
Pour réaliser un apprentissage par renforcement, les informaticiens ont eu besoin d’utiliser des modèles mathématiques permettant de décrire des problèmes de décisions séquentielles. L’une des solutions est basée sur les travaux d’Andreï Markov (1856-1922), mathématicien d’origine russe. Ce dernier met au point en 1906 ce qui sera appelé les chaînes de Markov. Les chaînes de Markov sont un type de processus markovien. Un processus markovien suit une succession d’états distincts dans le temps, et ceci en fonction de probabilités de transition. L’hypothèse de Markov consiste à dire que les probabilités de transition d’un état à un autre ne dépendent que des états précédents. Quel est le rapport avec l’apprentissage par renforcement ? Une chaîne de Markov peut être transformée en un problème décisionnel de Markov (PDM), qui est une manière de décrire formellement et rigoureusement (mathématiquement), les interactions entre un environnement et un agent autonome. Exactement ce dont nous avons besoin pour résoudre un problème d’apprentissage par renforcement.
Exemple d’algorithme par renforcement
Le Q-learning est un algorithme qui permet de réaliser des apprentissages par renforcement en convergeant vers une maximisation de la récompense totale. Il s’agit donc d’une solution au PDM. Un des points forts du Q-learning est qu’il ne nécessite pas de connaissance initiale de l’environnement pour converger vers cette solution optimale.
La lettre Q fait référence à la fonction de récompense pour un état donné du programme. La fonction engendre une action spécifique en fonction de l’état avec l’objectif de maximiser le score total au terme du processus. Ce score est la somme pondérée de l’espérance mathématique des scores de chaque étape future à partir de l’état actuel. Il est très utile de construire une Q table. Il s’agit tout simplement d’un tableau de recherche dans lequel seront indiquées les valeurs des récompences pour des états et des actions donnés de l’agent.
L’algorithme du Q-learning est notamment développé dans la thèse de Christopher John Watkins (http://www.cs.rhul.ac.uk/~chrisw/new_thesis.pdf) parue en mai 1989.
Ci-après un exemple d’implémentation de l’algorithme du Q-learning. L’agent, représenté par la lettre A, doit trouver le meilleur chemin possible pour atteindre sa cible à droite, lui-même se trouvant à gauche. Il doit pour cela améliorer sa stratégie au fur à...
Exemples d’applications
Les applications de l’apprentissage par renforcement sont très nombreuses. Google DeepMind a par exemple créé un algorithme appelé Alphago qui est capable de jouer à un jeu d’origine chinoise appelé go. Ce jeu, comparable aux échecs, possède bien plus de combinaisons possibles. Au début, les créateurs de l’algorithme l’entraînaient avec une méthode d’apprentissage supervisée en analysant des parties jouées par des humains, mais ils ont ensuite opté pour l’apprentissage par renforcement et entraîné l’algorithme à jouer contre lui-même. Résultat ? Le programme a réussi l’exploit de battre Lee Sedol, l’un des meilleurs joueurs mondiaux.
Les algorithmes d’apprentissage par renforcement ont également été en mesure d’apprendre à jouer à des jeux vidéo. Par exemple, des membres de l’université de Stanford ont développé un algorithme par renforcement qui joue au célèbre jeu vidéo Mario Kart (pour en savoir plus, consultez http://cs231n.stanford.edu/reports/2017/pdfs/624.pdf).
L’agent est Sonic, son état correspond à sa position après chaque déplacement, son environnement comprend les différents obstacles qu’il va rencontrer parmi lesquels son ennemi Robotnik. Sa récompence...
