Un algorithme pour résoudre des problèmes de décision séquentielle (typiquement des processus de décision markoviens) qui alterne l'évaluation de la valeur d'une politique courante et l'amélioration de cette politique de façon gloutonne par rapport à cette valeur jusqu'à convergence vers une politique optimale.

Principe

Alterner évaluation de politique (exacte ou approximée) et amélioration de politique : calculer les valeurs d'états ou d'état-action pour la politique actuelle, puis mettre à jour la politique en choisissant des actions qui maximisent ces valeurs, répéter jusqu'à l'absence d'amélioration.

Démonstration

Dans un processus de décision markovien à états finis, débuter par une politique déterministe quelconque, calculer la fonction de valeur de la politique en résolvant les équations linéaires de Bellman, puis produire une nouvelle politique en choisissant les actions qui maximisent le gain espéré à un pas ; itérer jusqu'à stabilisation.

Mauvaise application

Utiliser l'itération de politique complète avec une évaluation exacte sur des espaces d'état très grands ou continus sans approximation peut être irréalisable en calcul et en mémoire ; appliquer une amélioration gloutonne lorsque l'évaluation est fortement biaisée peut provoquer des oscillations.

Conséquence

Appliquée correctement aux MDP finis ou avec des approximations stables, l'itération de politique converge en un nombre fini d'étapes vers une politique optimale et nécessite en général moins d'itérations que l'itération de valeur naïve.

Inversion

L'inversion du concept donne l'itération de valeur : appliquer répétitivement les mises à jour d'optimalité de Bellman sur les estimations de valeur sans maintenir une politique évaluée explicitement, et extraire une politique après convergence des valeurs.

Limite

S'applique aux processus décisionnels séquentiels où politiques et fonctions de valeur sont bien définies ; exclut les problèmes d'optimisation non séquentiels, les jeux adversariaux sans reformulation, et les contextes sans structure markovienne ni probabilités de transition bien définies.

Tension sémantique

Tension entre l'évaluation exacte (stable mais coûteuse) et l'évaluation approximée ou par échantillon (scalable mais pouvant introduire biais et instabilité lors de l'amélioration).

Synthèse

L'itération de politique est un schéma d'alternance : évaluer une règle de décision fixe, puis améliorer cette règle en sélectionnant gloutonnement selon les valeurs évaluées ; l'alternance répétée conduit à des décisions séquentielles optimales sous le modèle supposé.