Notations

Soit un ensemble de signaux d'entrée du système $X_{1}, X_{2}, ..., X_{p}$. Nous supposons que le système dispose, à tout moment, d'une information r (signal de renforcement), qui prend ses valeurs dans l'ensemble 0,1,-1. Lorsque r vaut 1, cela signifie que l'objectif est atteint; lorsque r vaut -1, le système est sorti de sa zone de viabilité; dans les autres cas, r vaut 0.
D'autre part, on considère que le système possède un ensemble fini $A$ d'actions: $A = \{a_{1},a_{2},...,a_{q}\}$. Ces actions lui permettent d'agir sur son environnement.
On fait également l'hypothèse que les données d'entrée du système sont catégorisées de manière à produire un ensemble fini d'états $e_{1},e_{2},...,e_{n}$ dont la topologie est spécifiées a priori. Il existe, en plus, deux états ``terminaux'' $e_{S}$ et $e_{E}$. Lorsque r vaut 0, le système se trouve dans un des états $e_{1},e_{2},...,e_{n}$, alors que si r vaut 1, le système se trouve dans l'état terminal $e_{S}$ et si r vaut -1, le système se trouve dans l'état terminal $E_{E}$.
On suppose enfin que l'exécution d'une action $a_{k}$ à partir de l'état $e_{i}$, à l'instant t, amenant à l'état $e_{j}$ à l'instant t+1, se traduit par le passage du système dans un état transitoire, noté $e_{i,k}$, entre les instants t et t+1. Donc, entre les instants t et t+1, deux transitions sont franchies: l'une de $e_{i}$ vers $e_{i,k}$ et l'autre de $e_{i,k}$ vers $e_{j}$ (figure 2.1)

Figure: Les deux catégories d'états du système.

Les états perceptifs $e_{i}$ sont représentés par des cercles, alors que les états transitoires $e_{i,k}$ sont représentés par des carrés. Dans cet exemple, le système possède trois actions. À l'instant t, le système est dans l'état $e_{1}$, qui est lié à trois états transitoires (dépendant du choix entre trois actions possibles). Les transitions (en pointillé) sont le résultat des expériences passées du système, liant l'exécution de chacune de ces actions à un certain nombre d'états perceptifs.
La propriété ( $P_{\epsilon }$) se traduit sur ce graphe par l'existence, en pratique, d'une unique transition entre un état transitoire et un état perceptif.

Chaque état de type $e_{i}$ ou de type $e_{i,k}$ est associé à un marquage, nommé $M_{i}$ pour $e_{i}$ et $M_{i,k}$ pour $e_{i,k}$. Ces marquages prennent leur valeur dans un ensemble S fini. Nous considérons l'ensemble S suivant:

$$S = S(\alpha,d) = \{-1, 0, 1, \alpha, \alpha^{2}, ..., \alpha^{d}\}$$

Avec $d \ge 1$ et $\alpha \in ]0,1]$. Nous considérerons que lorsque $\alpha = 1$, S = S(1) = {-1,0,1}.
L'algorithme CbL engendré lorsque $\alpha < 1$ sera noté CbL($\alpha$). Dans le cas où $\alpha = 1$, on notera CbL(1).
Le déroulement d'un apprentissage comporte les mêmes phases que pour l'AR (voir le chapitre 1). Nous ne redéfinirons pas les termes ``itération'', ``essai'' et ``apprentissage'', spécifiés dans le chapitre précédent. Il nous faudra cependant préciser les points suivants:

• apprentissage: comment modifier la valeur ``qualité'' associée à chaque état du système ?
• initialisation: comment initialiser ces valeurs ``qualité'' ?
• choix d'une action