Un principe de programmation dynamique indiquant qu'une politique optimale possède la propriété suivante : quelle que soit l'état initial et la décision prise, les décisions restantes constituent une politique optimale pour l'état résultant de la première décision ; autrement dit, les solutions optimales présentent une optimalité par sous‑structure.

Principe

Qu'un problème peut être décomposé en sous‑problèmes dont les solutions optimales se combinent pour produire un optimum global lorsque la représentation d'état du système capture toutes les informations pertinentes (propriété de Markov / optimalité par sous‑structure).

Démonstration

Exemple concret : plus court chemin dans un graphe orienté acyclique — le plus court chemin de A à D passant par B contient le plus court chemin de B à D ; la programmation dynamique calcule les distances en résolvant d'abord les sous‑chemins et en les composant.

Mauvaise application

Supposer que le principe de Bellman s'applique alors que l'état ne capture pas tout l'historique nécessaire ou que les coûts dépendent de propriétés globales (non‑Markovien ou coûts dépendant du parcours), ce qui conduit à une mauvaise décomposition et à des résultats sous‑optimaux.

Conséquence

Quand il s'applique, il justifie des algorithmes qui construisent des solutions optimales en résolvant et mémorisant des sous‑problèmes (programmation dynamique, itération de la valeur dans les processus de décision markoviens), réduisant souvent une recherche exponentielle en calcul polynomial.

Inversion

La situation inverse est un problème sans sous‑structure optimale : les solutions optimales globales ne peuvent pas se composer à partir de solutions optimales de sous‑problèmes, la programmation dynamique n'est pas applicable et des choix localement optimaux peuvent échouer globalement.

Limite

S'applique lorsque l'espace d'états est défini de sorte que les coûts futurs dépendent uniquement de l'état courant et de la décision, et lorsque les coûts se combinent (par exemple de façon additive) permettant la composition ; exclut les dépendances non‑Markoviennes, les contraintes globales strictes ou les objectifs non décomposables.

Tension sémantique

Tension entre modéliser pour rétablir la sous‑structure optimale (élargir l'état pour récupérer la propriété) et le coût/complexité d'une telle modélisation ; entre la programmation dynamique exacte et les méthodes approximatives ou heuristiques quand l'optimalité stricte est inatteignable.

Synthèse

Le principe d'optimalité de Bellman affirme que si la sous‑structure optimale tient — c'est‑à‑dire si l'état capture toute l'information pertinente pour le futur — l'optimisation globale se réduit à résoudre et composer des sous‑problèmes optimaux, permettant l'usage de la programmation dynamique mais échouant pour les problèmes dépendant du parcours ou globalement contraints.