Exploration de l'espace d'états

La sous-section précédente a permis de montrer que la valeur du marquage associé à un état est discriminante dans le cadre du choix d'une commande fiable (sous les contraintes auxquelles la proposition 1 est associée). Le choix d'une action associée à une qualité 1 sera préféré à toutes les autres car, d'après la proposition 2, cette action permet d'arriver à un état menant à l'objectif à coup sûr. À un degré moindre, une action de qualité 0 sera choisie car, d'après la proposition 4, elle fait partie d'un cycle d'états viables ou elle n'a jamais été explorée. Toutes les commandes possédant la même qualité sont donc, d'une certaine manière, équivalentes du point de vue de la fiabilité de la politique de commande dans lesquelles elles s'inscrivent.
Comment le système explore-t-il l'espace d'états à partir de la connaissance des marquages ? L'exploration a lieu totalement au hasard lorsque l'ensemble des marquages associés aux $e_{i,k}$ sont égaux à 0. La découverte d'une transition vers l'état $E_{E}$ condamne certaines commandes en fixant des marquages à -1, alors que la découverte d'une transition vers l'état $E_{S}$ favorise d'autres commandes en fixant des marquages à 1. On se rend compte que, pour un état $e_{i}$ donné, lorsque la discrimination entre les commandes est effectuée, le choix se porte vers le même ensemble de commandes (ayant le marquage le plus élevé). Ce système revient à exécuter répétitivement la même séquence de commandes, jusqu'à ce que l'expérience montre un défaut dans la fiabilité de la politique de commande (ce qui aboutira à un changement du marquage associé à une partie des commandes, donc à un changement de la politique de commande). Une séquence est donc abandonnée si un unique cas d'échec est détecté. Et, si aucun défaut de fiabilité n'est constaté par l'expérience, il est probable que la politique de commande engendrée ne soit pas optimale, car deux commandes de qualité identique ne peuvent pas être discriminées.
Imaginons que l'algorithme ne trouve pas de politique de commande fiable. Est-on certain d'avoir exploré l'ensemble des séquences susceptibles de former une politique fiable ? La proposition suivante répond à cette question par l'affirmative:

Proposition _s   Le mécanisme d'exploration induit par l'algorithme de choix de commande conduit à une exploration exhaustive de l'espace d'états jusqu'à ce qu'une politique fiable soit trouvée.

Admettons qu'il existe une politique de commande fiable. D'après les propositions 2, 3 et 4 établissant une correspondance entre fiabilité et valeur des marquages, cela signifie qu'il existe un ensemble d'états $e_{i}$ et $e_{i,k}$, de valeur de marquage maximale (1 pour un problème d'atteinte d'objectif et 0 pour un problème de viabilité). Pour un problème de viabilité, la proposition 3 indique que les états/actions faisant partie d'une politique fiable ne peuvent en aucun cas posséder un marquage -1, à aucun moment de l'apprentissage: ces marquages restent donc constamment à 0. D'autre part, l'élimination de possibilités se fait par changement du marquage de 0 (marquage initial) à -1: la possibilité n'est plus jamais réessayée. Comme on sait qu'il reste obligatoirement des marquages à 0, cette élimination est limitée et conduit à la découverte d'une politique de commande fiable. Pour un problème d'atteinte d'objectif, si on sait qu'il existe une politique fiable, cela signifie avant tout qu'il est possible d'atteindre l'état $E_{S}$. Lorsque l'état $E_{S}$ n'est pas atteint, les valeurs des marquages ne sont pas discriminées et une exploration aléatoire de l'espace d'états est menée. Celle-ci est exhaustive et aboutit forcément à $E_{S}$ (puisqu'il existe une possibilité d'atteindre $E_{S}$). La propagation de la valeur 1 aux marquages associés aux états/actions menant à l'objectif est alors effectuée. On connaît alors une politique fiable d'atteinte d'objectif (par hypothèse ( $P_{\epsilon }$), une commande exécutée à partir d'un état $e_{i}$ aboutit à un unique état $e_{j}$.