L'hypothèse des exploring starts est utile pour garantir que tous les états (paires état-action) soient 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 l'ensemble de l'espace des états — les exploring starts peuvent être appliqués sans problème. Mais plus couramment, 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, cela reste souvent peu pratique.

Approches alternatives d'exploration

Si commencer à partir d'un état aléatoire (paire état-action) n'est pas possible, l'alternative consiste à garantir que chaque action ait une probabilité non nulle d'être sélectionnée dans chaque état. Cela garantit qu'au fil du 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 l'action la mieux connue, mais sélectionne plutôt les actions avec un certain degré d'aléa. Une stratégie courante pour cela est la politique $\varepsilon$-greedy familière, 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.