Marquage des états du système

L'objectif de l'apprentissage est de découvrir une ou des séquences d'actions permettant d'éviter l'état terminal $e_{E}$ à tout moment, pour parvenir à l'état $E_{S}$. Pour cela, nous nous proposons d'établir un algorithme de marquage utilisant un ensemble fini de symboles S, comprenant au moins les trois symboles 0,1 et -1, pour marquer les états du système. Bien que le choix d'un ensemble de marquages fini puisse apparaître rudimentaire, nous montrerons que cela est suffisant si la propriété ( $P_{\epsilon }$) est respectée.
Les états $E_{S}$ et $E_{E}$ possèdent un marquage fixe (respectivement égal aux symboles 1 et -1). Le marquage associé aux autres états (les $e_{i}$ et les $e_{i,k}$) va être déterminé au cours de l'apprentissage et sera égal à l'un des symboles de S.
L'idée pour fixer le marquage des états est de rétro-propager les valeurs des états terminaux par l'intermédiaire des transitions existantes. Ce mécanisme va être fondé sur l'existence d'un invariant structurel décrit dans le paragraphe qui suit.