En remplaçant l’étape d’évaluation de la politique dans l’algorithme standard d’itération de politique par les techniques d’estimation Monte Carlo décrites dans le chapitre précédent, il est déjà possible de dériver une nouvelle variante de l’itération de politique—une qui repose sur l’expérience échantillonnée plutôt que sur la programmation dynamique.

Cependant, il existe une limitation majeure. Dans l’itération de politique traditionnelle, l’étape d’amélioration de la politique dépend de la disponibilité d’un modèle complet de l’environnement. Plus précisément, pour mettre à jour la politique, on utilise l’expression suivante :

Cette équation suppose que l’on connaît les probabilités de transition $p(s', r | s, a)$. Mais c’est précisément là le problème : les méthodes Monte Carlo sont conçues pour des contextes sans modèle, où la dynamique de transition de l’environnement est inconnue. Si un modèle complet est disponible, il serait alors préférable d’utiliser la programmation dynamique partout, y compris pour l’évaluation de la politique, car cela serait plus efficace et précis.

Ainsi, bien que le remplacement des méthodes d’estimation de la valeur par Monte Carlo constitue une avancée vers l’apprentissage par renforcement sans modèle, il est également nécessaire de trouver un moyen d’effectuer l’amélioration de la politique sans dépendre de la connaissance du modèle. Cela implique de passer de la fonction de valeur d’état à la fonction de valeur d’action.

Pourquoi les valeurs d’action ?

En utilisant les valeurs d’action, il devient possible d’effectuer l’amélioration de la politique sans nécessiter de modèle de l’environnement. Au lieu de s’appuyer sur les probabilités de transition pour calculer les retours attendus, il suffit de sélectionner directement les actions qui semblent offrir la valeur la plus élevée. L’étape d’amélioration de la politique devient alors :

Il n’est pas difficile de démontrer que la nouvelle politique n’est pas moins performante que l’ancienne, car le théorème d’amélioration de la politique reste applicable :

Comme avec la programmation dynamique, ce théorème garantit que soit $\pi_{k+1}$ est meilleure que $\pi_k$, soit elles sont toutes deux égales et optimales.

Estimation de la fonction de valeur d'action

Le processus d'estimation est presque identique à celui de la fonction de valeur d'état. Toutes les idées utilisées pour estimer les valeurs d'état peuvent être appliquées à l'estimation des valeurs d'action.

Pseudocode

Ainsi, avec un nombre suffisant d'itérations, les valeurs d'action estimées devraient se rapprocher des véritables valeurs d'action.

Avec cela, il est déjà possible de construire une méthode similaire à l'itération de politique qui ne dépend pas d'un modèle. Pour ce faire, il suffit de remplacer les étapes d'évaluation de la politique et d'amélioration de la politique par les processus décrits ci-dessus.

Optimisation

Bien que l'étape d'évaluation puisse être réalisée à l'aide de l'estimation Monte Carlo comme décrit précédemment, elle tend à être peu efficace sur le plan computationnel. Comme vous l'avez déjà constaté, les méthodes Monte Carlo nécessitent généralement un grand nombre d'échantillons pour produire des estimations suffisamment précises. Si l'on suit une structure similaire à celle de l'itération de politique, cette inefficacité est amplifiée : après chaque amélioration de la politique, il faut relancer l'estimation Monte Carlo pour réévaluer la nouvelle politique — ce qui entraîne une surcharge importante et un apprentissage lent.

Une alternative plus naturelle consiste à mettre à jour la politique immédiatement après le traitement de chaque épisode. Au lieu d'attendre la fin d'un cycle complet d'évaluation de la politique, l'agent peut affiner son comportement épisode par épisode, en utilisant les estimations les plus récentes des valeurs d'action.

Cela aboutit à une méthode qui ressemble davantage à l'itération de valeur : elle combine les aspects d'évaluation et d'amélioration en une seule étape. Cela augmente l'efficacité de l'échantillonnage et accélère la vitesse de calcul.

Pseudocode

Cet algorithme suit un cadre GPI (Generalized Policy Iteration), car il comporte des étapes d'évaluation de la politique et d'amélioration de la politique, et il est appelé contrôle Monte Carlo. Le principal inconvénient de cette implémentation spécifique est l'hypothèse des démarrages exploratoires. Dans les prochains chapitres, vous verrez pourquoi cela pose problème et comment y remédier.