Position du problème

L'environnement est un rectangle découpé en un ensemble régulier de cases, chacune associée à un état du système. Chaque case est soit vide, soit occupée par un mur ou par une cible. On suppose que le système possède quatre commandes possibles: aller dans la case adjacente de droite, de gauche, en haut ou en bas. De plus, on suppose qu'il connaît exactement l'état dans lequel il se trouve à tout moment. Mais, il ne sait pas a priori où sont les obstacles et les cibles (les bords du labyrinthe sont considérés comme des obstacles, dans lesquels le système peut se cogner). L'objectif est d'apprendre à atteindre une des cibles présentes dans le ``labyrinthe'' en utilisant les quatre commandes de base. Le contexte d'apprentissage est un cas typique pour lequel ( $P_{\epsilon }$) est respecté.
Voici comment nous allons représenter le graphe d'états du système. La figure 2.4 résume l'ensemble des types de graphes que nous allons utiliser. Les graphes (a) et (b) concernent la politique de commande générée à partir du graphe d'états. Les cases sont représentées par les lignes en trait fin. Prenons le graphe (a). La direction des flèche indique l'action à entreprendre. Celle-ci correspond à l'état transitoire possédant le marquage le plus élevé (et strictement positif). Lorsque le marquage maximum est inférieur ou égal à 0, aucune flèche n'est indiquée. Lorsque plusieurs flèches existent dans une même case, cela signifie que plusieurs actions possèdent le même marquage maximum. Le graphe (b) donne, pour le même exemple, la valeur précise du marquage des états. Le graphe (c) indique l'ensemble des transitions créées dans le graphe d'états: pour chaque état, des flèches partant du centre de la case correspondant à celui-ci indiquent l'existence d'une transition vers la case du haut, du bas, de gauche ou de droite.

Figure: Exemples de graphes pour le problème du labyrinthe.

Commentaires:
Dans l'ensemble des graphes, les traits fins correspondent à la limitation des cases du labyrinthe, alors que les traits épais signifient la présence d'un mur ou d'une bordure du labyrinthe. La ou les cibles sont représentées par un cercle. Chaque case représente un état du système.
Le graphe (a) montre un exemple de politique de commande établie après un apprentissage. Les flèches centrées sur les cases du labyrinthe indiquent les commandes associées à un marquage maximum strictement positif. Dans le cas où une case ne possède pas de flèche, cela signifie que le marquage associé à chacune des commandes issues de cette case est inférieur ou égal à 0. Lorsque plusieurs flèches sont issues du centre d'une case, plusieurs commandes possèdent un marquage maximum, donc plusieurs commandes sont susceptibles d'être exécutées par l'algorithme de choix de la commande.
Le graphe (b) est issu du même apprentissage que le graphe (a). Il montre, pour chacun des états, la valeur du marquage qui lui est associé.
Le graphe (c) montre l'exploration des états du système après l'apprentissage montré par les graphes (a) et (b). Les flèches centrées sur les cases indiquent que les commandes correspondantes ont été essayées au moins une fois.
Les graphes de type (a) ou (c) ayant le même aspect, nous préciserons à chaque fois s'ils représentent la politique de commande ou l'exploration de l'espace d'états.