Commençons par revisiter un concept familier : la fonction de valeur d'état, notée $v_\pi(s)$. Elle peut être définie comme

L'objectif de ce chapitre est d'estimer cette fonction à partir de données, en supposant qu'une politique fixe $\pi$ est donnée mais sans accès au modèle de l'environnement.

Estimation Monte Carlo

Les méthodes Monte Carlo abordent cette tâche d'estimation en échantillonnant des épisodes d'expérience sous la politique $\pi$, puis en utilisant ces échantillons pour former des estimations empiriques de $v_\pi(s)$.

En général, le processus peut être divisé en étapes suivantes :

1. Générer un épisode en utilisant la politique $\pi$ ;
2. Enregistrer la valeur de retour obtenue pour chaque état apparaissant dans l'épisode ;
3. Répéter les étapes 1-2 pendant un certain temps ;
4. Calculer les nouvelles valeurs en moyennant les retours pour chaque état.

Collecte des rendements

L'estimation Monte Carlo de la fonction de valeur nécessite la collecte des rendements issus des épisodes générés. Pour calculer ces rendements, deux approches principales peuvent être utilisées :

• Première visite : pour chaque état $s$ rencontré dans un épisode, seul le rendement suivant sa première apparition est pris en compte. Les occurrences ultérieures du même état au sein du même épisode sont ignorées pour l'estimation ;
• Chaque visite : chaque occurrence d'un état $s$ dans un épisode est utilisée. Autrement dit, le rendement suivant chaque visite de l'état est inclus dans l'estimation, même si l'état apparaît plusieurs fois dans le même épisode.

Exploration des départs

Imaginez un monde simple unidimensionnel représenté par une ligne qui s'étend de -10 à +10. L'agent commence à la position 0, et sa politique actuelle dicte qu'il se déplace toujours vers la droite à chaque étape temporelle.

Si l'on tente de générer des épisodes sous cette politique, que se passe-t-il ? L'agent se déplacera continuellement vers l'extrémité positive de la ligne — visitant des états comme 1, 2, 3, etc. — mais il ne visitera jamais d'états négatifs. Par conséquent, il est impossible d'estimer les fonctions de valeur pour les états situés à gauche de l'origine, simplement parce que l'agent ne les expérimente jamais.

Le principal problème est donc le suivant : si certaines parties de l'espace des états ne sont jamais explorées, leurs estimations de valeur resteront inexactes ou indéfinies. Une solution courante à ce problème est l'utilisation des démarrages exploratoires.

Avec les démarrages exploratoires, chaque épisode ne commence pas dans un état de départ fixe comme 0, mais dans un état sélectionné aléatoirement. Une fois l'épisode commencé, l'agent suit sa politique actuelle comme d'habitude. Au fil du temps, en commençant à partir de nombreux points différents dans l'espace des états, l'agent est capable de visiter tous les états — pas seulement ceux vers lesquels sa politique le conduirait naturellement. Cela permet à la méthode de Monte Carlo de produire des estimations de valeur plus précises et complètes pour l'ensemble de l'espace des états.

Pseudocode

Ce pseudocode utilise l’approche chaque-visite associée aux démarrages exploratoires.