Résultats

Les résultats expérimentaux concernent les points suivants:

1. les particularités de l'algorithme CbL
2. un comparatif des performances de l'algorithme CbL avec la méthode du Q-Learning avec trace d'éligibilité

Commençons par le point 1. Une première expérience donne un exemple d'apprentissage. Celle-ci consiste à effectuer un unique apprentissage, comportant 1000 essais, en initialisant l'état du système sur la même case, pour chaque essai. L'environnement est celui présenté dans les graphes (a), (b) et (c) de la figure 2.5. L'état initial est indiqué par un carré noir (en haut, à gauche du graphe (a) ). Nous remarquons que l'exploration du labyrinthe n'est pas totale (graphe (c) ). Cela est dû au fait que, dès que le système va découvrir la cible, l'ensemble des marquages des états explorés jusqu'à ce moment vont être modifiés pour respecter la contrainte d'équilibre. Comme l'ensemble de ces états peuvent conduire vers la cible, ils auront tous un marquage strictement positif. D'après l'algorithme de choix de la commande, les autres états (ayant un marquage nul) ne seront plus explorés à partir de ce moment. Un bénéfice induit par cette modification massive des marquages au moment de la découverte de la cible est que, à partir de ce moment, si on initialise le système dans un état déjà exploré, il conduira vers la cible. Le graphe (a) illustre ce fait: en effet, à partir de n'importe quelle case du labyrinthe, le choix d'une action, symbolisé par une flèche dans le graphe (a), permet au système de se rapprocher de la cible. De plus, dans notre cas particulier, la politique de commande induit un trajet de longueur minimale à partir de n'importe quel état du système (le choix d'une commande a toujours comme résultat de se rapprocher de la cible). Le graphe (d) montre la particularité de l'algorithme CbL: la modification des marquages est massive dès que le système découvre la cible (juste après l'essai 300). Le graphe (e) montre qu'à partir de cet instant, le nombre d'itérations pour aller à la cible est constant et minimal.

Figure: Particularités de l'algorithme CbL (1)

Commentaires: Les graphes (a), (b) et (c) sont obtenus après le même apprentissage, dans un environnement possédant une unique cible (représentée par un cercle). Le carré en haut à gauche du graphe (a) indique l'état d'initialisation du système au début de chaque essai d'apprentissage. Le graphe (a) indique la politique de commande obtenue. Les cases ne possédant pas de flèche n'ont jamais été explorées, ce qui peut être retrouvé sur le graphe d'exploration (c) et sur le graphe (b), montrant des marquages de valeur nulle pour les états non explorés. Sur le graphe (a), si on choisit une case et qu'on suit de proche en proche une des flèches indiquant les commandes possibles, on aboutit de manière certaine à la cible. Cela peut être visualisé dans le graphe (b) par l'existence d'un gradient au niveau des marquages, qui peut être remonté jusqu'à la valeur maximum 1 (sur la cible). Le graphe (d) montre qu'il existe une modification massive des marquages juste après le 300ème essai, ce qui correspond précisément au moment où la cible est découverte (graphe (e)).

Les graphes (a) et (c) de la figure 2.6, illustrent le fait que l'optimalité de la politique de commande dépend de l'exploration des états qui a été effectuée avant la découverte de la cible. Les graphes (a) et (c) donnent les résultats d'apprentissage à partir d'un même environnement, possédant deux cibles. L'état initial est choisi aléatoirement à chaque essai. Le graphe (b) de la figure 2.6 illustre l'exploration des états correspondant à l'apprentissage du graphe (a). Mais le graphe (c) est obtenu à partir d'un graphe d'états initial (au début de l'apprentissage) possédant l'intégralité des transitions possibles (à l'exclusion des transitions menant aux états terminaux). Nous remarquons que la politique de commande pour (a) n'est pas optimale, alors qu'elle l'est pour (c). Cela est dû au manque d'exploration ( montré par le graphe (b) ).

Figure: Particularités de l'algorithme CbL (2)

Commentaires:
Les graphes (a), (b) et (c) traitent de l'influence de l'exploration sur la qualité de la politique de commande. Les graphes (a) et (b) montrent la politique de commande issue de deux apprentissages différents. Pour (a), on part, au début de l'apprentissage, d'un graphe d'états ne possédant aucune transition (l'exploration au bout de l'apprentissage est donnée par le graphe (b)), alors que pour (c), on part d'un graphe possédant l'intégralité des transitions réalisables. Le résultat est que le graphe (c) donne une politique de commande optimale (nombre minimal de commandes pour rejoindre une des deux cibles à partir de n'importe quel état). Ce n'est pas le cas pour le graphe (a).
Les graphes (d) et (e) donnent les politiques de commandes obtenues après apprentissage, en fixant la valeur du paramètre d à 10. Cela signifie qu'un état ne pourra avoir un marquage strictement positif que s'il faut moins de 10 commandes à partir de ce dernier pour atteindre l'objectif. Les différences entre (d) et (e) sont les mêmes qu'entre (a) et (c). Dans ces conditions, le graphe (e) montre une politique de commande optimale (tous les états à partir desquels on peut rejoindre une des deux cibles en moins de 10 commandes possèdent un marquage strictement positif, indiqué par la présence d'au moins une flèche). On voit que cela n'est pas vrai pour le graphe (d).

L'algorithme CbL assure que si un état possède un marquage strictement positif, alors l'algorithme de choix de la commande permet d'aboutir à coup sûr à au moins une cible. Ainsi, les cibles peuvent être vues comme des points d'attraction. Chaque état possédant un marquage strictement positif peut être classifié en fonction de la ou des cibles vers lesquelles l'algorithme de choix de commande ``attire'' le système à partir de cet état. Nous pouvons ainsi dégager des zones d'attraction pour les deux cibles. Dans le cas du graphe (a), la zone d'attraction de la cible située dans la partie ``sinueuse'' du labyrinthe est limitée à une case; l'ensemble des autres cases explorées sont dans la zone d'attraction de la deuxième cible. Pour le graphe (d), les deux zones sont séparées de manière optimale: à partir de chaque état, on se dirige vers la cible la plus proche, et si un état est à la même distance (en terme de nombre de commandes) des deux cibles, la politique de commande peut amener le système soit vers une cible, soit vers l'autre, d'une manière équiprobable.
Enfin, nous montrons l'influence du paramètre d (fixé à 100 jusqu'ici). Nous rappelons qu'il indique le nombre maximum de marquages strictement positifs autres que 1. Il délimite l'étendue du bassin d'attraction d'une cible, c'est-à-dire l'existence d'un guide vers l'objectif menant à celui-ci au maximum en d itérations. Dans les cas précédents, la valeur de d était largement suffisante. Nous allons revenir à l'exemple précédent, en fixant la valeur de d à 10. Les graphes (d) et (e) sont les mêmes que (a) et (c), mais avec un paramètre d beaucoup plus petit. Les bassins d'attraction sont visibles (les flèches indiquent l'existence d'un marquage strictement positif). On se rend compte que la réduction du bassin d'attraction de la deuxième cible a permis d'augmenter le nombre d'états compris dans celui de la première cible: cela est dû au fait que l'exploration s'est poursuivie autour de la première cible, puisque les états proches de celle-ci sont à plus de 10 cases de l'autre cible (donc ne peuvent pas être marqués positivement à cause d'elle). On remarque que le graphe (d) n'induit pas un bassin d'attraction maximal pour la deuxième cible, pour des raisons de manque d'exploration des transitions possibles. Le graphe (e) montre au contraire que le bassin d'attraction autour des deux cibles comporte l'intégralité des états à partir desquels il faut, au plus, 10 commandes pour atteindre une cible.
En conclusion, ces résultats expérimentaux montrent clairement que le dilemme exploration/exploitation existe en utilisant l'algorithme CbL: si on souhaite un résultat optimal, il est nécessaire de dissocier la phase d'exploration (construction du graphe d'états sans prendre en compte les transitions vers les états terminaux) et la phase d'exploitation (construire les transitions vers les états terminaux). Cela signifie qu'on renonce à changer la valeur des marquages dans la phase d'exploration, ce qui peut augmenter considérablement le temps d'apprentissage. À l'inverse, notre algorithme de choix de la commande implique qu'on passe directement à la phase d'exploitation dès qu'une cible est détectée, ce qui entraîne une non optimalité de la politique de commande résultante. Ainsi, l'ensemble des exemples présentés ci-dessus montre l'aspect capital de la topologie du graphe d'états - c'est-à-dire des liens possibles entre les états - pour la détermination d'une politique de commande.
Nous allons, à présent, passer au point 2. Le protocole expérimental indique le mode opératoire. Nous avons utilisé deux environnements différents, que nous noterons ``environnement 1'' et ``environnement 2'' (voir respectivement les figures 2.7, page , et 2.8, page ): ils se différencient par le nombre d'obstacles et la probabilité d'atteindre une cible en choisissant les commandes au hasard. Commençons par les résultats concernant l'environnement 1, qui est le plus simple. L'ensemble des graphes pour cet environnement est donné sur la figure 2.7. Les graphes (a) et (b) montrent les qualités associées à chaque état, respectivement pour CbL et pour la méthode du Q-Learning. Ils sont les résultats du dernier essai du dernier apprentissage. Les graphes (c) et (d) montrent les convergences respectives des l'algorithmes CbL et Q-Learning, alors que le graphe (e) compare les nombres moyens d'itérations pour parvenir à l'objectif et le graphe (f) montre l'évolution comparée du nombre moyen d'erreurs par essai. Nous remarquons les faits suivants:

• la méthode du Q-Learning permet de trouver une meilleure politique de commande que CbL. En effet, le graphe (e) montre que le nombre moyen d'itérations au bout de 5000 essais est d'environ 8 pour le Q-Learning, alors qu'il est d'environ 11 pour CbL (voir la zone intéressante C sur ce graphe).
• CbL converge plus rapidement que Q-Learning: l'évolution comparée des graphes (c) et (d) montre ce fait. Plus aucune modification de marquage n'est détectée à partir du 200ième essai (zone A) pour CbL, alors que la somme moyenne des modifications des qualités n'est jamais nulle pour Q-Learning au 5000ième essai (zone B du graphe (d)).
• CbL devient fiable beaucoup plus rapidement que Q-Learning: le graphe (f) montre ce fait. Plus aucune erreur n'est détectée après le 200ième essai pour Cbl (zone D), alors qu'il faut plus de 1000 essais pour obtenir le même résultat avec le Q-Learning.

Le graphe (a) montre la non optimalité de la politique de commande avec CbL, ce qui a été expliqué dans la première série d'expériences. Alors que le graphe (b) montre que la politique de commande est presque optimale après l'apprentissage utilisant le Q-Learning. Elle est due au manque d'exploration après que des chemins vers les cibles aient été trouvés. La convergence rapide est montrée par le graphe (c). Celui-ci met en évidence un pic (traduisant le nombre moyen d'itérations qu'il faut pour découvrir les cibles) qui se situe à la 20ième itération, puis une décroissance très rapide des modifications qui deviennent nulles (en moyenne, donc pour tous les essais) après la 200ième itération. Le graphe (d) donne des résultats identiques mais obtenus au bout d'un nombre d'itérations plus importants, pour la méthode du Q-Learning: le pic se situe vers la 300ième itération et la moyenne des sommes des modifications n'est jamais nul (très faible à la 5000ième itération, mais non nulle).

Figure: Résultats pour l'environnement 1

L'environnement 2, plus complexe, amplifie les résultats que nous venons de donner. L'ensemble des graphes est donné par la figure 2.8. Dans ce cas, la politique de commande pour le QL n'est pas satisfaisante à l'issue des 5000 essais, car l'apprentissage est loin d'être achevé. Nous n'avons pas inclus les données concernant le Q-Learning, car elles ne sont pas représentatives d'un apprentissage achevé ou sur le point de l'être, pour ce nombre d'essais. L'algorithme CbL permet, quant à lui, de trouver une politique de commande satisfaisante (graphe (a) ) en un nombre d'itérations limité. Au bout de 200 itérations en moyenne, la cible est atteinte pour la première fois, permettant une modification massive des marquages associés aux états (on relève un pic important sur le graphe (b), suivi d'une chute rapide et d'une annulation du nombre moyen de marquages modifiés (zone A)). Le nombre moyen d'erreurs sur les 1000 essais devient nul après la 200ième itération (graphe (d), zone C), et l'algorithme a convergé dans tous les cas avant la 200ième itération. Le nombre moyens d'itérations pour atteindre l'objectif est constant après la 200ième itération (zone B du graphe (c)). L'ensemble de ces résultats doivent être comparés avec l'absence de résultats satisfaisants pour l'algorithme du Q-Learning au bout du 5000ième essai. Le gain de rapidité de l'apprentissage, qui était d'environ 10 pour l'environnement simple précédent, devient beaucoup plus important pour un environnement plus complexe. D'autre part, on constate (graphe (e)) que l'exploration a été quasiment totale (pour l'exemple d'apprentissage considéré), ce qui signifie que la politique de commande donnée par le graphe (a) est optimale (comme nous l'avons déjà montré au cours des premières expériences).

Figure: Résultats pour l'environnement 2

Nous venons donc de montrer le gain de temps d'apprentissage de l'algorithme CbL par rapport au Q-Learning et la fiabilité de la politique de commande obtenue (il n'y a plus d'erreur au bout d'un certain nombre d'essais). Il nous reste un point très intéressant: tester les capacités d'adaptation du système à une modification de l'environnement. L'ensemble des résultats est donné par la figure 2.9. On confronte le même système, en train d'apprendre par CbL, à un environnement pour lequel on va ajouter successivement une cible ou un mur (la succession des environnements est donnée par les graphes allant de (a) à (f)). Pour chacun des six environnements, on effectue 500 essais d'apprentissage. On passe d'un environnement à l'autre sans réinitialiser les marquages du système. L'apprentissage total comporte donc 3000 essais. Au début du premier essai de l'unique apprentissage (donc au début de l'essai 1 pour l'environnement (a)), on suppose que le graphe d'états possède l'ensemble des transitions possibles d'un état à l'autre, en excluant les transitions vers les états terminaux: nous avons vu que c'est une manière d'obtenir une politique de commande optimale après l'apprentissage. Les graphes allant de (a) à (f) indiquent la politique de commande du système à l'issue de l'apprentissage d'un environnement.

Figure: Adaptation à des modifications successives de l'environnement

Commentaires:
Les graphes (a) à (f) montrent la politique de commande obtenue après 500 essais d'apprentissage, pour chaque environnement pris successivement. Le graphe (g) montre un phénomène ``classique'' de l'algorithme CbL: la découverte d'une cible ou d'un mur alors qu'elle n'était pas prévue provoque une modification d'un nombre important de marquages. La majorité des modifications ont lieu juste après l'introduction d'un nouvel élément dans l'environnement, ce qui se traduit par des pics autour des itérations 1, 501, 1001, 2001 et 2501.

L'ensemble des graphes montrent une adaptation parfaite à l'ajout d'une cible ou d'un mur, dans la majorité des cas: en effet, la politique de commande à la fin des 500 essais donnés pour chaque ajout d'une cible ou d'un mur est optimale pour les graphes (a),(b),(e),(f). Cependant, on constate que l'ajout des cibles des graphes (c) et (d) ne donne pas une politique de commande optimale: certaines ne sont atteintes à partir d'aucun état du système. Ce phénomène s'explique: lorsque l'ajout d'une nouvelle cible se situe sur un état qui n'est atteint à partir d'aucun autre état (aucune flèche n'arrive sur cet état), il ne s'ensuit aucune modification de la politique de commande. Dans la partie théorique, ce cas avait été prévu: le changement du marquage d'un état est dû à une modification dans le marquage des états entre lui et un état terminal. Dans notre exemple, il n'existe pas de transition menant aux cibles et il existe déjà un état terminal. L'ensemble des états pour lesquels ce phénomène se produit sont ceux pour lesquels le marquage est minimum localement (tous les états voisins possèdent un marquage strictement supérieur). Le graphe (e) est intéressant car il montre que le ``minimum local'' des marquages, sur lequel se trouvent les deux cibles non atteintes, peut être enlevé en rajoutant une nouvelle cible (graphe (e)). Et le graphe (f) indique que l'adaptation a lieu également lorsqu'un nouvel obstacle est ajouté. Enfin, les graphes (g) et (h) indiquent que l'adaptation du système s'effectue en moins de 500 essais pour chaque nouvel environnement. Les pics du graphe (g) sont caractéristiques des modifications massives, limitées dans le temps; on constate qu'elles ont lieu peu après la présentation d'une nouvelle cible dans l'environnement.