Qu'est-ce que la programmation dynamique ?

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 d'application de la programmation dynamique

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

• Structure optimale de sous-problèmes : 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. Comme les décisions dans un MDP sont séquentielles, résoudre de 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 grands. Dans les MDP, cela se manifeste par le fait que la valeur d'un état est recalculée à plusieurs reprises au cours de 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 montre 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 illustre les sous-problèmes qui se recoupent, tandis que la solution de Fib(5) est construite à partir des solutions optimales de ses sous-problèmes, démontrant ainsi 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 recoupent, ils se prêtent particulièrement bien aux solutions basées sur la programmation dynamique.

Pourquoi utiliser la programmation dynamique en apprentissage par renforcement ?

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

Cependant, la programmation dynamique n'est pas réalisable pour les problèmes de grande taille en raison de sa dépendance à un modèle complet et de ses exigences computationnelles, ce qui conduit aux défis abordés dans la suite.

Défis et limitations de la programmation dynamique

Bien que la programmation dynamique (PD) 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 situations réelles :

• Complexité computationnelle : les méthodes de PD nécessitent des calculs pour chaque état de l'environnement. Lorsque l'espace des états augmente, le nombre de calculs requis croît de manière significative, rendant la PD impraticable pour les problèmes complexes ;
• Nécessité d'un modèle connu : la PD 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.