Exemples de contextes vérifiant ou ne vérifiant pas ( $P_{\epsilon }$)

Le problème type respectant ( $P_{\epsilon }$) est celui du labyrinthe, découpé en un ensemble de cases, pour lequel les actions permises sont de se déplacer sur une case adjacente à la case courante (voir la figure 1.3). Dans un cadre plus général, une machine de Turing respecte ( $P_{\epsilon }$) car l'évolution de l'état du système est régie par un ensemble de règles, permettant pour chaque état du système de déterminer l'état suivant à partir de l'action exécutée (voir la figure 1.4).

Figure: Cas d'un problème type vérifiant la propriété ( $P_{\epsilon }$)

Chaque action mène à un état unique (c'est-à-dire à une case unique) et, si on connaît la case d'arrivée, on peut déterminer sans ambiguïté l'action qui vient d'être exécutée.

Figure 1.4: Principe de la machine de Turing

Par contre, la manière dont nous construisons les états dans le problème du pendule inversé, proposé dans la section suivante, engendre un contexte d'apprentissage qui ne respecte pas ( $P_{\epsilon }$), même si les données d'entrée sont parfaites.