Elle est particulièrement utile en apprentissage par renforcement (RL) pour résoudre efficacement les processus de décision de Markov (MDP) lorsqu'un modèle complet de l'environnement est disponible.

Conditions requises pour l'application de la programmation dynamique

Tous les problèmes ne peuvent pas être résolus par la programmation dynamique. Deux caractéristiques essentielles sont nécessaires pour qu'un problème soit adapté à cette approche :

• Sous-structure optimale : la solution optimale d’un problème est obtenue à partir des solutions optimales de ses sous-problèmes. Dans les MDP, cela signifie que la politique optimale dans un état dépend des politiques optimales des états suivants. Étant donné que les décisions dans un MDP sont séquentielles, résoudre de plus petits sous-problèmes (trouver la meilleure action pour les états futurs) permet de résoudre le problème global (trouver la meilleure action pour l’état actuel) ;
• Chevauchement des sous-problèmes : les solutions des sous-problèmes sont réutilisées pour résoudre des problèmes plus vastes. Dans les MDP, cela se manifeste par le fait que la valeur d’un état est calculée à plusieurs reprises dans différentes séquences de décisions. Comme les états sont souvent revisités, les valeurs déjà calculées peuvent être stockées et réutilisées, ce qui réduit les calculs redondants et améliore l’efficacité.

Chaque nœud de l’image représente un appel récursif pour calculer Fib(n), et la structure arborescente illustre comment ces appels sont décomposés en sous-problèmes plus petits. Remarquez que des sous-problèmes comme Fib(2) et Fib(1) apparaissent plusieurs fois, ce qui démontre le chevauchement des sous-problèmes, tandis que la solution de Fib(5) est construite à partir des solutions optimales de ses sous-problèmes, illustrant la sous-structure optimale. Cette redondance est précisément ce que la programmation dynamique vise à éliminer en stockant et en réutilisant les résultats.

Puisque les MDP présentent à la fois une sous-structure optimale et des sous-problèmes qui se chevauchent, ils se prêtent particulièrement bien aux solutions basées sur la programmation dynamique.

Pourquoi utiliser la programmation dynamique (DP) en apprentissage par renforcement (RL) ?

• Garanties d'optimalité : les méthodes de DP garantissent la convergence vers la politique optimale lorsque le modèle complet est connu ;
• Efficacité pour des solutions générales : avec l'aide de la DP, des solutions générales peuvent être obtenues efficacement, ce qui signifie que la politique résultante sera optimale pour chaque état ;
• Fondement pour d'autres méthodes : les concepts issus de la DP servent de base à d'autres méthodes d'apprentissage par renforcement, telles que Monte Carlo et l'apprentissage par différence temporelle.

Cependant, la DP n'est pas réalisable pour les problèmes de grande échelle en raison de sa dépendance à un modèle complet et de ses exigences computationnelles, ce qui conduit aux défis abordés ci-après.

Défis et limitations de la programmation dynamique

Bien que la programmation dynamique (DP) offre un cadre élégant pour résoudre les problèmes d'apprentissage par renforcement, elle présente des défis importants qui limitent son applicabilité dans des scénarios réels :

• Complexité computationnelle : Les méthodes DP nécessitent des calculs pour chaque état de l'environnement. À mesure que l'espace d'états augmente, le nombre de calculs requis croît de manière significative, rendant la DP impraticable pour des problèmes complexes ;
• Nécessité d'un modèle connu : La DP suppose que les probabilités de transition et les récompenses de l'environnement sont connues à l'avance. Cependant, dans de nombreuses applications réelles de l'apprentissage par renforcement, ces informations ne sont pas disponibles, ce qui rend les approches sans modèle plus pratiques.