Algorithmes de Résolution des MDPPO (Processus de Décision Markovien
Partiellement Observable)
Les Processus de Décision Markovien Partiellement Observable (MDPPO) modélisent des
situations où l'état complet du système n'est pas directement observable. Résoudre ces problèmes
nécessite des algorithmes spécifiques adaptés à leur complexité. Voici une vue détaillée des
principales approches :
4.1. Programmation Dynamique
La programmation dynamique est une approche fondamentale pour résoudre les MDPPO. Elle
repose sur l’itération des politiques et des valeurs pour trouver une solution optimale.
4.1.1. Formulation Standard :
Équation de Bellman généralisée :
Pour les MDPPO, une fonction de valeur dépend de la distribution de croyance (une
estimation probabiliste de l'état actuel).
4.1.2. Algorithmes Typiques :
1. Value Iteration (Itération sur les valeurs) :
o Approche récursive pour mettre à jour la fonction de valeur jusqu’à convergence.
o Complexité élevée en raison de la gestion de la distribution de croyance.
2. Policy Iteration (Itération sur les politiques) :
o Alterne entre évaluation et amélioration de la politique.
o Convient pour les espaces d’états observables réduits.
Limites :
Inapplicable directement dans les grands espaces d'états en raison de la taille
exponentielle de la distribution de croyance.
4.2. Méthodes d’Approximation
Les méthodes d’approximation sont essentielles pour résoudre des MDPPO à grande échelle où la
programmation dynamique classique est inapplicable.
4.2.1. Approximation par Échantillonnage :
1. Point-Based Value Iteration (PBVI) :
o Approche basée sur des points d’échantillonnage dans l’espace de croyance.
oCalcule la valeur approximative pour un sous-ensemble représentatif de
croyances.
o Réduit le coût computationnel.
2. Monte Carlo Sampling :
o Utilise des simulations aléatoires pour évaluer les politiques et les récompenses
moyennes.
o Bien adapté aux systèmes stochastiques avec des états complexes.
4.2.2. Apprentissage par Renforcement (RL) :
1. Q-learning Partiellement Observable :
o Apprend une fonction Q(b,a) approximée où b est la croyance.
o Nécessite de nombreux épisodes pour converger.
2. Deep RL pour MDPPO :
o Utilisation de réseaux de neurones pour approximer la fonction de valeur ou la
politique.
o Exemple : Deep Q-Networks (DQN) adaptés pour des espaces d’états
partiellement observables.
4.3. Algorithmes de Planification
Les algorithmes de planification visent à déterminer une séquence d'actions optimale dans un
horizon donné, en tenant compte des incertitudes.
4.3.1. Recherche Arborescente (Tree Search) :
1. Monte Carlo Tree Search (MCTS) :
o Génère un arbre de recherche basé sur des simulations aléatoires pour estimer la
qualité des actions.
o Utilisé dans des problèmes tels que les jeux ou les systèmes à espace d'action
complexe.
o Bien adapté aux MDPPO en combinant des modèles de transition et des
croyances.
2. Partially Observable Tree Search (POMCP) :
o Variante de MCTS optimisée pour les MDPPO.
o Intègre une modélisation basée sur des croyances et des échantillons.
4.3.2. Approches Basées sur des Politiques :
Policy Search :
o Recherche directe dans l’espace des politiques au lieu des valeurs d’état.
o Convient pour les scénarios complexes où les approches basées sur les valeurs
sont coûteuses.
Références
1. Livres :
o Kaelbling, L.P., Littman, M.L., & Cassandra, A.R. (1998). Planning and Acting in
Partially Observable Stochastic Domains.
o Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction.
2. Articles :
o Silver, D., & Veness, J. (2010). Monte-Carlo Planning in Large POMDPs.
Advances in Neural Information Processing Systems.
o Pineau, J., Gordon, G., & Thrun, S. (2003). Point-based value iteration: An
anytime algorithm for POMDPs. IJCAI.
3. Ressources en ligne :
o OpenAI Blog : Introduction to MDPs and POMDPs.
o Tutorials sur Deep RL : [Link]
Algorithmes de Résolution des MDPPO : Détails Approfondis
Les MDPPO (Processus de Décision Markovien Partiellement Observable) sont complexes car ils
combinent incertitude et décision séquentielle. Voici une description détaillée des principaux
algorithmes.
4.1 Programmation Dynamique
4.1.1. Value Itération pour MDPPO
Principe :
Approximer la valeur optimale V(b) pour chaque distribution de croyance b.
L'équation de Bellman devient :
Où b′ est la croyance mise à jour selon P(b′∣b,a,o).
Étapes :
1. Initialiser V(b) avec une estimation (ex. V(b)=0).
2. Répéter jusqu’à convergence :
Calculer la mise à jour Bellman pour chaque b.
Itérer sur les actions a et observations o.
Avantages :
o Théoriquement optimal.
o Base pour de nombreuses variantes.
Inconvénients :
o La dimension exponentielle de l’espace des croyances rend l’algorithme
impraticable pour des systèmes réels complexes.
4.1.2. Itération de la politique
Principe :
Alterne entre l’évaluation et l’amélioration de politique pour converger vers une politique
optimale.
Étapes :
1. Évaluation de la politique :
Évaluer la valeur de la politique courante π\pi :
2. Amélioration de la politique :
Choisir une meilleure action pour maximiser V(b) :
Avantages
Converge généralement plus vite que Value Iteration.
Inconvénients :
o Nécessite une évaluation précise de la politique, ce qui peut être coûteux.
4.2 Méthodes d’Approximation
4.2.1. Point-Based Value Iteration (PBVI)
Principe :
Approximer V(b) pour un sous-ensemble de croyances {B} représentatives de l’espace
complet.
Étapes :
1. Générer un ensemble de points de croyances {B} via échantillonnage ou
heuristiques.
2. Calculer les mises à jour Bellman uniquement pour {B}.
3. Ajuster les points {B} en fonction des résultats.
Avantages :
o Réduit considérablement la complexité.
o Bonne approximation dans les systèmes réels.
Inconvénients :
o La qualité de l’approximation dépend fortement des points sélectionnés.
4.2.2. Monte Carlo Sampling
Principe :
Utiliser des simulations aléatoires pour estimer la fonction de valeur V(b) ou la qualité
des politiques.
Étapes :
1. Simuler plusieurs trajectoires aléatoires dans l’espace de croyance.
2. Utiliser les récompenses observées pour estimer V(b).
3. Ajuster la politique en fonction des résultats.
Avantages :
o Applicable dans des environnements stochastiques complexes.
o Pas besoin de modélisation exacte.
Inconvénients :
o Nécessite de nombreux échantillons pour une précision acceptable.
4.2.3. Deep Reinforcement Learning (Deep RL)
Principe :
Utiliser des réseaux de neurones pour approximer Q(b,a) ou V(b).
Techniques populaires :
o Deep Q-Network (DQN) :
Approxime Q(b,a) à l’aide d’un réseau neuronal, entraîné via l’algorithme de Q-
learning.
o Actor-Critic :
Combine un acteur (politique) et un critique (évaluation de la politique).
Avantages :
o Bien adapté aux environnements à grande échelle.
o Flexible pour gérer des croyances complexes.
Inconvénients :
o Formation exigeante en données et en temps.
4.3 Algorithmes de Planification
4.3.1. Monte Carlo Tree Search (MCTS)
Principe :
Construire un arbre de recherche où chaque nœud correspond à une croyance, une action
ou une observation.
Étapes :
1. Sélection :
Parcourir l’arbre en suivant une politique (ex. Upper Confidence Bound).
2. Expansion :
Ajouter de nouveaux nœuds à l’arbre.
3. Simulation :
Simuler des trajectoires aléatoires pour estimer la qualité d’une action.
4. Mise à jour :
Mettre à jour les valeurs des nœuds en remontant l’arbre.
Avantages :
o Convient aux grands espaces d’états.
o Flexibilité pour s’adapter à des scénarios partiellement observables.
Inconvénients :
o Performances limitées sans optimisations spécifiques.
4.3.2. Partially Observable Monte Carlo Planning (POMCP)
Principe :
Variante de MCTS adaptée aux MDPPO.
Différences clés :
o Utilise un modèle de transition basé sur les croyances.
o Approximations probabilistes pour traiter l’incertitude.
Avantages :
o Performances exceptionnelles dans des environnements complexes.
o Combine la puissance de MCTS avec des modèles de croyances.
Références
o Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction.
o Kaelbling, L.P., Littman, M.L., & Cassandra, A.R. (1998). Planning and Acting in
Partially Observable Stochastic Domains.
o Silver, D., & Veness, J. (2010). Monte-Carlo Planning in Large POMDPs.
Advances in Neural Information Processing Systems.
o Pineau, J., Gordon, G., & Thrun, S. (2003). Point-based value iteration: An
anytime algorithm for POMDPs. IJCAI.
o OpenAI Spinning Up : [Link]
o Tutorials sur MDPPO : AI Wiki et DeepMind.