L'hypothèse des exploring starts est utile pour garantir que tous les états (paires état-action) sont visités au fil du temps. Cependant, dans la plupart des tâches réelles, elle présente un inconvénient majeur : elle nécessite un modèle pour initialiser l'agent dans des états arbitraires.

Dans de rares cas — lorsque l'environnement commence naturellement les épisodes à partir d'états aléatoires couvrant tout l'espace des états — les exploring starts peuvent être appliqués sans problème. Mais le plus souvent, les tâches disposent d'un ensemble fixe ou limité d'états de départ, rendant une telle randomisation impossible sans un modèle partiel. Ce modèle doit au moins être capable de simuler une étape de l'environnement à partir de n'importe quel état. Bien que cela soit moins exigeant que de nécessiter un modèle complet, c'est souvent irréaliste.

Approches alternatives d'exploration

Si commencer à partir d’un état aléatoire (paire état-action) n’est pas possible, l’alternative consiste à s’assurer que chaque action a une probabilité non nulle d’être sélectionnée dans chaque état. Cela garantit qu’avec le temps, l’agent explorera toutes les parties accessibles de l’espace des états. Si un état peut être atteint par une séquence valide d’actions, il le sera éventuellement ; et s’il ne peut pas être atteint du tout selon la dynamique de l’environnement, il devient alors sans importance pour le processus d’apprentissage.

Cette idée conduit à l’utilisation de politiques stochastiques, où l’agent ne choisit pas toujours la meilleure action connue, mais sélectionne les actions avec un certain degré d’aléa. Une stratégie courante pour cela est la politique $\varepsilon$-gloutonne, qui choisit l’action gloutonne la plupart du temps, mais avec une probabilité $\varepsilon$, sélectionne une action aléatoire à la place. Cela assure une exploration continue tout en privilégiant les actions à forte valeur.

À ce stade, il est également utile de distinguer deux grandes classes de méthodes :

• Les méthodes on-policy évaluent et améliorent la même politique que celle utilisée pour générer les données ;
• Les méthodes off-policy évaluent et améliorent une politique, et génèrent les données avec une autre politique.