English version available here !!!
Intelligence Artificielle - l'algorithme du Q-Learning.
Ne me considérant pas comme un expert en intelligence artificielle, mon propos n'est pas de rentrer dans le détail du fonctionnement de l'algorithme de Q-Learning, ni encore moins dans la preuve théorique de sa convergence (que l'on doit, si ma mémoire ne me fait pas défaut à J.C.Watkins). Cette page est donc volontairement simple ... Pour ceux qui cherchent à approfondir la question, rendez-vous à la rubrique Liens.
En quelque mots, disons que le Q-Learning est un algorithme d'apprentissage par renforcement non supervisé. En clair, cela signifie qu'il s'agit d'une technique informatique visant à créer un "agent logiciel" capable de contrôler de façon (quasi) optimale un certain système (dépendant du problème que l'on cherche à résoudre ...). Son atout principal est sa facilité d'implémentation (le coeur de la méthode n'excède pas 5 lignes de code !!! ) qui n'a hélas d'égal qu'avec la difficulté de son paramétrage ...
Les champs d'applications de cette méthode sont assez vastes, mais on peut dire que les pionniers en termes d'utilisation sont les roboticiens, désireux d'apprendre à leurs créatures artificielles à se comporter de manière "intelligente" dans leur environnement.
L'idée de l'apprentissage par renforcement, est, dans mon esprit, proche de la manière dont les jeunes enfants apprennent à parler. Il s'agit d'une suite d'expérimentations plus ou moins hasardeuses, engendrant une récompense ... variable, qui est mémorisée !!!. L'enjeu étant de découvrir, parmi toutes les tentatives effectuées, lesquelles sont les plus ... gratifiantes.
Illustration : Bébé commence à gazouiller. Tant qu'il pratique un charabia monosyllabique inintelligible (areuh, areuh, etc ...), ses parents ne présentent pas de réaction exacerbée. Tout au plus sont ils satisfaits que l'organe vocal de leur enfant fonctionne correctement (sauf vers 3h du matin, mais là c'est une autre histoire ...). La récompense du bébé est donc relativement faible (essais infructueux). Puis arrive le jour fatidique où bébé arrive à dire "papa", ou "maman", enclenchant une formidable réaction de joie (...) chez ses parents qui se manifestent en s'extasiant sur leur petit génie de rejeton (essai concluant, grosse récompense). L'enfant mémorise ce résultat, ce qui "renforce" sa connaissance du langage, et poursuit son apprentissage ...Vers la fin de ce dernier, l'enfant aura progressivement substitué une stratégie "aléatoire" (j'essaie d'enchainer des phonèmes au petit bonheur la chance...) par une stratégie de "contrôle" (je sais associer correctement les phonèmes pour bâtir certains mots ...). Même si cette vision des choses est infiniment trop simpliste (l'acquisition du langage me paraît être bien plus que de l'apprentissage par renforcement ...), elle permet d'illustrer assez grossièrement le principe de fonctionnement du Q-Learning.
On parle d'apprentissage non-supervisé car on ne fournit pas à l'algorithme une masse de données (souvent statistiques) à digérer afin de se constituer une "mémoire". En cela, il s'agit d'une méthode qui s'oppose aux méthodes classiquement répandues en intelligence artificielle, tels que les fameux réseaux de neurones, qui, pour la plupart relèvent de l'apprentissage supervisé. Il faut "alimenter" largement en données un réseau de neurones, et de plus, superviser le fait que ce dernier les "digèrent" bien. A contrario, pour un apprentissage non supervisé, aucune connaissance de base n'est requise. L'agent logiciel dispose d'une mémoire vierge, qu'il va faire évoluer au gré de ses expériences.
Bien sûr, il reste un point indispensable: nécessairement, l'agent doit être capable de déterminer la récompense engendrée par une quelconque de ses actions, en fonction de l'état dans lequel il se trouve, ce qui implicitement impose qu'il dispose de moyens de perception fonctionnels ... En très simplifié, il se "débrouille tout seul" ! Il s'agit là d'un avantage déterminant, lorsqu'on se retrouve à vouloir traiter un problème pour lequel on ne dispose pas de données statistiques conséquentes.
Un exemple valant mieux que de longs discours, j'ai écrit une applet JAVA de démonstration.
A moins d'être déjà informé, je vous conseille de prendre le temps de lire les quelques explications qui suivent afin de profiter pleinement de l'applet en question ...
RQUE: Il s'agit d'une applet utilisant swing (JApplet ...), vous devez donc disposer d'un plugin java récent (version >= 1.3) pour votre navigateur. N'hésitez pas à télécharger la dernière version sur le site adéquat.
Le problème que j'ai choisi de traiter ne brille pas par son originalité. Tout au plus, a-t-il le mérite d'être relativement simple et bien adapté au Q-Learning, dont le paramétrage est un "art" auquel il vaut mieux être initié en douceur ...
Contexte du problème :
Un robot (virtuel) - l'agent - est amené à se déplacer à l'intérieur d'un domaine carré, symbolisé par une carte de cases. On compte trois types de cases:
On suppose que le robot sait se déplacer suivant les quatre axes cardinaux (Nord, Est, Sud, Ouest), allant de case en case, en qu'en outre il dispose de moyens de détection lui permettant d'identifier la nature de la case sur laquelle il se trouve. Le domaine de déplacement est carré, et fermé (impossible de s'enfuir, mais rien n'interdit que le robot heurte les limites du domaine ...).
Le robot explore donc le domaine, et à chacun de ses déplacements, il reçoit une récompense :
A noter que, au lancement de l'apprentissage ou lorsque le robot a atteint une case cible, il est (re)déposé dans une case choisie au hasard parmi toutes les cases de la carte, et (re)commence à explorer le domaine (pour les matheux: c'est un problème cyclique en horizon fini ... En principe, le Q-Learning est destiné à traiter des problèmes de décision markoviens (MDP), en horizon infini, mais il s'avère qu'il fonctionne également pour les problèmes cycliques en horizon fini ... ).
Au démarrage de l'applet, vous devriez voir cela:
Pour commencer, on choisit la taille de la carte à utiliser : 10, 15 ou 20 cases (par côté), ce qui fait apparaître la carte en question, et rend le bouton d'apprentissage actif.
Ensuite, il s'agit de positionner sur la carte les cases cibles et les cases dangereuses.
Pour cela, il suffit de cliquer avec la souris sur la case choisie, avec le bouton gauche pour marquer une case dangereuse et le bouton droit pour une case cible (si vous vous trompez, un click sur le bouton du milieu ou sur la molette permet de remettre une case en position "normale"). Voici un exemple de mon cru :
Puis, après avoir éventuellement modifiée la valeur de certains des paramètres, on lance l'apprentissage par le bouton "Apprendre !". Cela ressemble à cela:
Si le nombre d'itérations sélectionné est raisonnable (proche de la valeur par défaut ...), et que vous disposez d'une machine récente, le résultat apparait au bout de quelques instants (à peine quelques secondes sur mon athlon xp1700+). Sinon ... armez vous de patience ! Le Q-Learning est connu pour être extrêmement vorace en ressources (mémoire, occupation du processeur, ...). Voici le résultat sur l'exemple:
Interprétation du résultat:
A la fin de l'exécution de l'algorithme, la carte se recouvre de flèches, symbolisant sur chaque case, ce que le robot considère comme étant le meilleur choix de déplacement possible. Le marquage des cases reste visible en transparence. Vous pouvez, en réappuyant sur le bouton "Apprendre !" relancer une séance d'apprentissage sur la même carte.
Ne soyez pas surpris si lors d'une succession de tests sur une carte donnée, les autres paramètres étant également inchangés, vous obtenez des résultats différents d'un test à l'autre. Cela tient à la nature de la convergence de l'algorithme. Les solutions obtenues sont en fait quasi-optimales. La preuve que l'algorithme de Q-Learning converge vers la solution optimale du problème existe (on la doit à J.C.Watkins), hélas, la convergence est assurée pourvu qu'on lui laisse effectuer une infinité d'itérations !!! (Impossible donc en pratique ...). Cependant, sile nombre d'itérations choisi est suffisament grand, on observe de grandes similitudes entre les solutions lors de tests successifs, ce qui permet de penser que l'on a obtenu des solutions quasi-optimales (stabilisation autour de l'optimum). Si les solutions successives diffèrent trop d'un test à l'autre, il faut augmenter le nombre d'itérations. N'oublions pas que les actions effectuées par l'agent pour se forger son expérience sont, pour la plupart, choisies aléatoirement !!! (voir à ce propos le paramétrage du taux d'exploration ci-après).
Enfin, une dernière remarque: comme vous l'avez peut être remarqué, le problème que l'on cherche à résoudre ressemble fortement à un problème de recherche de plus courts chemins sur un graphe. Bien sûr, il existe des algorithmes spécifiques pour ce type de problème, largement plus efficaces et rapides que le Q-Learning. Il ne s'agit que d'une illustration ... Il me paraît dérisoire de vouloir construire un pathfinder grace au Q-Learning !!!
Paramétrage:
Dans le panel des options de l'applet, figurent un certain nombre de paramètres réglables, certains étant liés à la nature du problème, d'autres étant des paramètres "typiques" au Q-Learning.
Outre la taille de la carte, il est donc possible de spécifier :
La page de l'applet :
Pour accéder à l'applet de démonstration, cliquer ICI.
Si vous désirez les sources JAVA, elles sont disponibles ici (bouton droit, "Save Target As...").
Liens : pour ceux qui veulent aller plus loin ... (je n'ai fais qu'effleurer le sujet :-( )
Le reinforcement learning repository de l'université du Massachussets : sûrement le site de référence pour tous ceux qui cherchent des ressources relatives à l'apprentissage par renforcement. En anglais, of course ...Permet d'accéder aux pages personnelles de nombreux chercheurs impliqués dans cette discipline, à leurs publications, etc, etc, ... Une sorte de "passage obligé" ...