Algorithme d'apprentissage CbL

Si on suppose que la contrainte d'équilibre est respectée à un instant t pour chaque état, seul l'ajout d'une transition dans le graphe d'états (action de l'environnement) peut le rendre incohérent. La figure 2.2 illustre ce fait. Dans ce cas, il faut modifier la qualité associée à l'état incohérent. Le rétablissement de la cohérence sur cet état peut engendrer une incohérence sur au moins un des états en contact avec l'état incohérent. Il faut donc modifier également leur qualité: on perçoit ici un mécanisme de propagation.

Figure: L'apprentissage est provoqué par l'ajout d'une transition dans le graphe d'états.

La figure de gauche montre des états $e_{1}$, $e_{i,1}$ et $e_{i,2}$ dont les marquages sont cohérents. L'ajout d'une transition entre $e_{i,2}$ et $e_{j2}$ rompt cette cohérence, puisque le marquage de $e_{i,2}$ vaut 0 et n'est plus égal au minimum des marquages associés aux états voisins ($e_{j2}$). La figure de gauche montre le graphe après le rétablissement de la cohérence entre les marquages. On note que la valeur de $M_{i}$ a également été modifiée. Ce changement pourrait, à son tour, provoquer un changement des marquages associés aux états connectés à $e_{i}$, qui n'apparaissent pas sur le schéma.

L'apprentissage correspond à la mise en cohérence du graphe d'états, grâce au mécanisme de propagation décrit ci-dessus. Les détails de ce mécanisme d'apprentissage sont donnés par l'algorithme 2.1, s'appuyant sur les relations 2.1.


Deux points de l'algorithme d'apprentissage restent à aborder:

• l'initialisation de l'apprentissage
• le choix d'une action

Pour ce qui concerne l'initialisation, au début de l'apprentissage (avant le premier essai), on considère qu'il n'existe aucune transition entre les sommets $e_{i,k}$ et $e_{i}$ du graphe. La valeur ``qualité'' associée à chaque état est donc 0. Cette initialisation respecte la contrainte d'équilibre donnée par l'équation 2.1. Les transitions sont ajoutées au fur et à mesure de leur découverte, au cours des essais de l'apprentissage du système. L'ajout d'une transition peut provoquer le non respect de cette contrainte d'équilibre; si cela survient, on utilise l'algorithme 2.1 pour rétablir la cohérence.
Enfin, si le système est dans l'état $e_{i}$, l'action sera choisie selon la valeur du marquage $M_{i,k}$ lui étant associé. Nous utiliserons une politique ``gloutonne'': on sélectionnera l'action pour laquelle la valeur du marquage est maximum. Si plusieurs actions possèdent le même marquage de valeur maximum, on en choisira une au hasard parmi celles-ci.
Une vue de haut niveau du processus complet d'apprentissage CbL est donnée par l'algorithme 2.2. Cet algorithme est celui d'un essai d'apprentissage, qui se termine lorsque l'objectif est atteint (r=1), la zone de viabilité est quitée (r=-1) ou qu'un nombre maximum d'itérations est dépassé.