Cadre d'optimisation récursif qui décompose des problèmes de décision à étapes multiples en sous-problèmes chevauchants résolus par induction arrière ou avant, centralisant la fonction de valeur qui encode les gains optimaux futurs.

Principe

Principe d'optimalité de Bellman : une politique optimale a la propriété que, quel que soit l'état initial et la première décision, les décisions restantes constituent une politique optimale pour l'état résultant ; la récursion sur les fonctions de valeur met cela en œuvre.

Démonstration

En contrôle optimal à horizon fini, calculer le coût restant V_t(x) par induction arrière : V_T(x)=coût terminal et V_t(x)=min_u{ coût_étape(x,u)+V_{t+1}(f(x,u)) } jusqu'à t=0, ce qui donne une suite optimale de commandes.

Mauvaise application

Considérer des problèmes non markoviens comme markoviens sans augmentation d'état, ou tenter une programmation dynamique tabulaire exacte dans des espaces de très haute dimension sans approximation (malédiction de la dimension), conduit à des solutions incorrectes ou infaisables.

Conséquence

Une application correcte fournit des politiques et fonctions de valeur optimales, des décompositions exploitables pour de nombreux problèmes structurés et des fondations pour des algorithmes de contrôle et d'apprentissage par renforcement, mais peut exiger des approximations à grande échelle.

Inversion

Les méthodes gloutonnes ou myopes font des choix localement optimaux sans résoudre la récursion et échouent souvent à trouver des stratégies globalement optimales lorsque les coûts futurs influencent fortement les décisions actuelles.

Limite

S'applique lorsque le problème admet une décomposition par étape et une structure de transition markovienne ou une augmentation d'état équivalente ; exclut directement les problèmes partiellement observés ou les objectifs non séparables sans reformulation.

Tension sémantique

Tension avec la programmation dynamique approximée et l'apprentissage par renforcement : la PD offre une récursion exacte et des garanties lorsque faisable, tandis que les approximations échangent optimalité contre faisabilité et généralisation aux environnements de grande dimension.

Synthèse

Programmation Dynamique = utiliser l'optimalité de Bellman pour exprimer l'optimisation multistade globale comme des sous-problèmes récursifs sur les fonctions de valeur, résoudre par induction arrière/avant ou sauvegardes itératives, et maîtriser la complexité par approximation si nécessaire.