Comme vous le savez, une fonction de valeur d'état d'une politique donnée peut être déterminée en résolvant une équation de Bellman :

Si un modèle complet de l'environnement est disponible (c'est-à-dire, si les probabilités de transition et les récompenses attendues pour toutes les paires état-action sont connues), les seules variables inconnues restantes dans l'équation sont les valeurs des états. Par conséquent, l'équation ci-dessus peut être reformulée comme un système de $|S|$ équations linéaires à $|S|$ inconnues.

Par exemple, si un MDP possède 2 états ($s_1$, $s_2$) et 2 actions (aller à $s_1$, aller à $s_2$), la fonction de valeur d'état pourrait être définie ainsi :

Ce système peut être résolu à l'aide de techniques standards d'algèbre linéaire.

Une solution unique à un tel système linéaire est garantie si au moins une des conditions suivantes est remplie :

• Le facteur d'actualisation satisfait $γ < 1$ ;
• La politique $\pi$, suivie à partir de n'importe quel état $s$, garantit que l'épisode se termine finalement.

Évaluation itérative de la politique

La solution peut être calculée directement, mais une approche itérative est plus couramment utilisée en raison de sa facilité d'implémentation. Cette méthode commence par attribuer des valeurs arbitraires à tous les états, sauf pour les états terminaux, qui sont fixés à 0. Les valeurs sont ensuite mises à jour itérativement en utilisant l'équation de Bellman comme règle de mise à jour :

La fonction de valeur d'état estimée $v_k$ converge finalement vers la véritable fonction de valeur d'état $v_\pi$ lorsque $k \to \infty$ si $v_\pi$ existe.

Stratégies de sauvegarde des valeurs

Lors de la mise à jour des estimations de valeur, les nouvelles estimations sont calculées à partir des valeurs précédentes. Le processus de conservation des estimations précédentes est appelé sauvegarde. Deux stratégies courantes existent pour effectuer des sauvegardes :

• Sauvegarde complète : cette méthode consiste à stocker les nouvelles estimations dans un tableau séparé, distinct de celui contenant les valeurs précédentes (sauvegardées). Par conséquent, deux tableaux sont nécessaires — un pour conserver les estimations précédentes et un autre pour stocker les nouvelles valeurs calculées ;
• Sauvegarde sur place : cette approche conserve toutes les valeurs dans un seul tableau. Chaque nouvelle estimation remplace immédiatement la valeur précédente. Cette méthode réduit l'utilisation de la mémoire, car un seul tableau est nécessaire.

En général, la méthode de sauvegarde sur place est privilégiée car elle nécessite moins de mémoire et converge plus rapidement, grâce à l'utilisation immédiate des dernières estimations.

Quand arrêter la mise à jour ?

Dans l'évaluation itérative de la politique, il n'existe pas de point précis auquel l'algorithme doit s'arrêter. Bien que la convergence soit garantie à la limite, poursuivre les calculs au-delà d'un certain point est inutile en pratique. Un critère d'arrêt simple et efficace consiste à suivre la différence absolue entre les estimations de valeur consécutives, $|v_{k+1}(s) - v_k(s)|$, et à la comparer à un petit seuil $\theta$. Si, après un cycle complet de mise à jour (où les valeurs de tous les états sont mises à jour), aucun changement ne dépasse $\theta$, le processus peut être arrêté en toute sécurité.

Pseudocode