Méthode d'optimisation récursive pour des problèmes de décision multi‑étapes qui décompose le problème en sous‑problèmes qui se recouvrent, utilise une représentation d'état et le principe d'optimalité pour exprimer la valeur d'un état en fonction des états successeurs, et calcule des politiques optimales par itération de la valeur ou de la politique, mémoïsation ou induction rétrograde.

Principe

Une solution optimale d'un problème multi‑étapes peut être construite à partir de solutions optimales de ses sous‑problèmes (principe d'optimalité) ; le calcul d'une fonction de valeur sur un espace d'états convenable fournit des décisions globalement optimales lorsque la séparabilité par étapes et la propriété de Markov sont satisfaites.

Démonstration

Scénario illustratif : routage au temps minimal sur un réseau orienté acyclique. Situation : chaque nœud est une étape, les arêtes ont des coûts par étape. Reconnaissance : les coûts sont additives par étapes et les coûts futurs ne dépendent que du nœud courant. Action : calculer le coût minimal jusqu'à la destination pour tous les nœuds par induction rétrograde (mémoïser les résultats). Conséquence : la politique calculée donne le chemin le plus court sans énumérer toutes les routes complètes.

Mauvaise application

Considérer qu'un problème est traitable par programmation dynamique alors que l'état choisi n'encode pas tout l'historique pertinent (violation de la propriété de Markov) ou que les sous‑problèmes ne se recouvrent pas ; cela produit des décisions incorrectes ou une explosion d'états rendant le calcul impraticable.

Conséquence

Lorsque c'est applicable, la programmation dynamique donne des politiques optimalement prouvées et réduit souvent les calculs répétés par mémoïsation ; mal appliquée, elle produit des optima incorrects ou une charge de calcul prohibitive (malédiction de la dimension).

Inversion

Si la séparabilité par étapes, l'additivité des coûts ou la propriété de Markov n'est pas satisfaite (par exemple, si les coûts futurs dépendent des trajectoires passées complètes ou d'objectifs non séparables), la méthode doit être remplacée ou complétée par une reformulation, une approximation ou une extension de l'état pour inclure l'historique.

Limite

Clairement inclus : processus de décision markovien à horizon fini avec coûts additives par étape et états bien définis. Cas limite : problèmes stochastiques partiellement observables nécessitant une transformation vers l'état de croyance. Clairement exclu : optimisation monostade sans structure séquentielle ou problèmes dont l'optimalité dépend d'un passé non borné.

Tension sémantique

Optimalité versus faisabilité — atteindre l'optimalité globale par énumération d'états s'oppose aux limites de mémoire et de calcul, forçant souvent des approches approximatives.

Synthèse

La programmation dynamique exploite la structure du problème (décomposition en étapes et définition compacte de l'état) pour le rendre soluble : son efficacité dépend essentiellement d'une représentation d'état rendant les coûts futurs markoviens tout en gardant l'espace d'états gérable.