Algorithme de programmation dynamique qui applique à plusieurs reprises l'opérateur d'optimalité de Bellman aux estimations de valeur d'état, effectuant des sauvegardes sur les états jusqu'à ce que la fonction de valeur converge vers l'optimum sous des propriétés de contraction.

Principe

Exploiter la propriété de contraction de l'opérateur d'optimalité de Bellman dans les MDP remisés : l'application itérative du backup V_{k+1}=T[V_k] converge vers le point fixe unique V* et fournit une politique optimale par extraction gloutonne.

Démonstration

Pour un MDP fini avec remise gamma∈(0,1), initialiser V0 arbitrairement et itérer V_{k+1}(s)=max_a{ R(s,a)+gamma sum_{s'} P(s'|s,a) V_k(s') } jusqu'à ce que sup_s |V_{k+1}(s)-V_k(s)| < tolérance, puis extraire une politique gloutonne.

Mauvaise application

Employer l'itération de valeur naïve avec une approximation de fonction inappropriée ou sur des problèmes non remisés sans garantir la contraction ; exécuter sur des espaces d'état très grands sans approximation conduit à des temps et mémoires impraticables.

Conséquence

Sous hypothèses usuelles l'itération de valeur converge vers la fonction de valeur optimale et fournit une politique optimale par sélection gloutonne ; elle constitue une référence classique pour planification et apprentissage par renforcement.

Inversion

L'itération de politique alterne évaluation explicite de la politique et amélioration et peut converger en moins d'itérations que l'itération de valeur, au prix d'étapes d'évaluation plus coûteuses par itération.

Limite

Garantie pour les MDP remisés ou les situations où l'opérateur de Bellman est un contraction ; prudence pour les espaces d'état continus, la non-observabilité partielle ou les régimes d'approximation de fonctions où les garanties théoriques s'affaiblissent.

Tension sémantique

Tension avec l'itération de politique et Q-learning : l'itération de valeur effectue des backups complets sur les valeurs et converge sous contraction, tandis que l'itération de politique met l'accent sur évaluation/amélioration alternées et Q-learning vise les valeurs d'action à partir d'échantillons.

Synthèse

Itération De La Valeur = calcul itératif du point fixe appliquant des backups de Bellman jusqu'à convergence vers V*, puis extraction gloutonne d'une politique optimale ; pratique lorsque le modèle d'état exact est disponible et que les conditions de contraction sont respectées.