Contribution à la Résolution des Processus
Décisionnels de Markov Décentralisés

Les algorithmes de résolution

Cette partie traite la résolution des modèles markoviens représentant des problèmes de prise de décision mono-agent (à savoir les MDPs). Cette section nous semble importante pour deux raisons. D’une part, ces techniques constituent le fondement des approches utilisées pour résoudre les DEC-POMDPs et DEC-MDPs comme nous le verrons dans le prochain chapitre. D’autre part, nous souhaitons utiliser des techniques de construction de comportement individuel pour construire des comportements collectifs. Nous serons amenés à réutiliser ces techniques dans nos contributions. Déterminer la politique optimale d’un MDP revient à calculer la valeur de la politique optimale en se basant sur l’équation de Bellman présentée à la section 2.2.1.3. 21 L’exécution d’une politique 𝜋 correspond à la boucle perception-action d’un agent [Russell and Norvig, 2003]. Pour un tuple 𝑆, 𝐴, 𝑃, 𝑅 donné elle est constituée de cycle de 4 étapes (figure 2.2) [Thomas, 2005]:  L’agent observe l’état 𝑠0 de l’environnement (figure 2.2 (a))  Il détermine l’action 𝑎 qu’il souhaite entreprendre en fonction de sa politique 𝜋, 𝑎 ← 𝜋(𝑠0) (figure 2.2 (b))  Il effectue cette action et l’état du monde s’en trouve modifié 𝑠1 ← 𝑃 𝑠1 |𝑠0 , 𝑎 (cette dernière expression cache en réalité une réalisation selon la densité de probabilité 𝑃 𝑠0 , 𝑎 ) (figure 2.2 (c))  Il reçoit une récompense 𝑟 ← 𝑅 𝑠0 , 𝑎 (figure 2.2 (d)) 𝑠0 𝑠0 𝜋 𝑠1 𝑎 𝑃 𝑠1 𝑅 (a) (b) (c) (d) Figure 2.2 Exécution d’une politique d’un MDP constituée de plusieurs étapes: a) état initial, b) étape de décision, c) étape d’exécution de l’action, d) étape de modification de l’état, une récompense est reçue Nous allons à présent décrire deux algorithmes pour la résolution de ces problèmes décisionnels. Il faut noter que ces algorithmes supposent que le modèle du système soit connu. En particulier, la fonction de transition 𝑃 et la fonction de récompense 𝑅 doivent être connues à l’avance.   L’algorithme Value Iteration (VI) L’équation de Bellman constitue la base de l’algorithme Value Iteration, l’un des algorithmes les plus utilisés pour la résolution des MDPs à horizons finis ou infinis. Le principe de base de cet algorithme de programmation dynamique décrit par Bellman [Bellman, 1957] consiste en une amélioration itérative de la valeur de chaque état du MDP. Le principe consiste en des réévaluations approximatives successives de chaque état. A partir d’une valeur initiale arbitraire de chaque état, Value Iteration améliore itérativement l’évaluation des états en utilisant l’équation de Bellman. La valeur d’un état à l’itération 𝑡 est calculée à partir de sa valeur à l’itération 𝑡 − 1. En pratique plusieurs conditions d’arrêt de l’itération peuvent être envisagées. La plus classique consiste à stopper l’itération lorsque la différence entre deux fonctions de valeurs successives 𝑉𝑡 − 𝑉𝑡−1 est inférieur à 𝜖 où 𝜖 est un seuil d’erreur fixé a priori [Kaelbling et al., 1998]. La convergence de l’algorithme vers une fonction de valeur optimale est garantie étant donné que l’équation de Bellman est une équation de point fixe. A partir de la valeur 𝑉𝑡 obtenue par cet algorithme, nous pouvons déduire une politique 𝜋𝑡 optimale à 𝜖 près. En pratique, cette politique s’avère généralement être la politique optimale du MDP qui est souvent obtenue bien avant que l’algorithme ne s’arrête. Les dernières itérations sont consacrées à une amélioration de la fonction de valeur. 23 Complexité La complexité en temps de l’algorithme dépend de la complexité de chaque itération et du nombre d’itérations. Une itération nécessite 𝐴 |𝑆| 2 opérations. Par ailleurs, le nombre d’itérations nécessaires pour converger est, au pire cas, polynomial en |𝑆|, |𝐴|, 𝛾 et 𝐵 où 𝐵 est le nombre total de bits requis pour représenter les données du problème [Beynier, 2006]. Sutton et Barto [Sutton and Barto, 1998] ont montré que des MDPs d’un million d’états pouvaient facilement être résolus par l’algorithme Value Iteration. De plus, cet algorithme possède des propriétés anytime c’est-à-dire que la qualité de la solution augmente de façon monotone à chaque itération et l’amélioration est décroissante au cours du temps. L’algorithme est également interruptible : si nous l’arrêtons avant qu’il ait atteint son point de convergence, nous disposerons quand même d’une solution. 𝑉𝑡 𝑠 = max 𝑎∈𝐴 [𝑅 𝑠, 𝑎 + 𝛾 𝑃 𝑠 ′ |𝑎, 𝑠 𝑉𝑡−1(𝑠′) 𝑠′∈𝑆 ] Algorithme 1 : Value Iteration Entrées : un MDP 𝑆, 𝐴, 𝑃, 𝑅 un paramètre de précision 𝜖 un facteur d’escompte 𝛾 une valeur initiale 𝑉0arbitraire 1 𝑡 ← 0 2 Pour tous les 𝒔 ∈ 𝑺 faire 3 𝑉0(𝑠) ← 𝑉0 4 fin 5 répéter 6 𝑡 ← 𝑡 + 1 7 Pour tous les 𝒔 ∈ 𝑺 faire 8 9 fin 10 jusqu’à max𝑠∈𝑆 𝑉𝑡 𝑠 − 𝑉𝑡−1 𝑠 < 𝜖 ; Sorties : 𝑉𝑛 l’approximation de 𝑉 ∗ à 2𝜖𝛾 𝛾−1 près 24 Value Iteration calcule une politique 𝜖-optimale pour n’importe quel état initial. Ceci peut constituer un avantage si nous souhaitons calculer une politique sans connaître a priori la situation initiale de l’agent. Cependant, lorsque les états initiaux sont connus, l’algorithme n’en tire pas avantage ce qui conduit à l’évaluation de trajectoires non atteignables. En ce qui concerne la complexité en espace, Value Iteration est linéaire en |𝑆||𝐴| [Beynier, 2006].  L’algorithme Policy Iteration (PI) A l’instar de Value Iteration, l’algorithme Policy Iteration utilise le principe d’optimalité de Bellman afin de résoudre des MDPs à horizons finis ou infinis. La différence entre ces deux algorithmes réside dans la manière dont la politique optimale est trouvée. VI calcule une valeur puis déduit une politique. PI construit directement la politique optimale. Cet algorithme décrit par Howard en 1960 [Howard, 1960] propose d’actualiser, à 𝜖 près, les valeurs de l’équation de Bellman 𝑉 𝑠 , entre deux itérations sur la politique contruite. L’algorithme part d’une politique initiale arbitraire 𝜋0 , et est divisé en deux phases. Une phase d’évaluation de la politique courante qui utilise l’équation de Bellman et une phase d’amélioration qui consiste à mettre à jour la politique courante en utilisant les valeurs calculées lors de la phase d’évaluation. L’algorithme converge lorsqu’aucune modification de la politique n’est plus possible, soit 𝜋𝑡+1 𝑠 = 𝜋𝑡 𝑠 ∀ 𝑠 ∈ 𝑆 et fournir ainsi une politique optimale. Howard a montré que chaque itération améliorait la politique : la valeur de chaque état à l’itération 𝑡 + 1 est supérieure ou égale à celle de l’itération 𝑡 et elle est strictement supérieure pour au moins un état. Chaque itération dans policy iteration demande alors plus de ressources calculatoires qu’une itération dans value iteration [Putterman, 1994]. Cependant, policy iteration a statistiquement besoin de moins d’itérations pour converger vers la politique optimale. 25 Complexité La complexité de l’algorithme PI est en 𝑂 𝐴 𝑆 2 + 𝑂 𝑆 3 par itération avec un nombre maximum d’itération polynomial en 𝑆 , 𝐴 à 𝛾 constant [Papadimitriou and Tsitsiklis, 1987; Garcia, 2008]. Le nombre d’itérations de l’algorithme dépend fortement de la politique initiale 𝜋0 . Il existe |𝐴| |𝑆|politiques possibles. Étant donné qu’à chaque itération la politique mise à jour domine strictement la politique précédente, le nombre d’itérations sera, au pire cas, exponentiel en nombre d’états. Toutefois, il a été prouvé que la borne supérieure concernant le nombre d’itérations était bien inférieure [Beynier, 2006]. En effet, Algorithme 2 : Policy Iteration Entrées : un MDP 𝑆, 𝐴, 𝑃, 𝑅 un facteur d’escompte 𝛾 une politique initiale 𝜋0arbitraire 1 𝑡 ← 0 2 𝜋𝑡+1 ← 𝜋0 3 répéter 4 𝜋𝑡 ← 𝜋𝑡+1 5 𝑡 ← 𝑡 + 1 // Phase d’évaluation 6 Pour tous les 𝒔 ∈ 𝑺 faire 7 Calculer 𝑉𝜋𝑡 (𝑠) 8 Fin // Phase d’amélioration 9 Pour tous les 𝒔 ∈ 𝑺 faire 10 Si ∃𝑎 ∈ 𝐴 tel que 𝑅 𝑠, 𝑎 + 𝛾 𝑃 𝑠 ′ , 𝑎, 𝑠 𝑉𝜋𝑡 𝑠′∈𝑆 (𝑠′) > 𝑉𝜋𝑡 (𝑠) alors 11 𝜋𝑡+1 𝑠 = 𝑎 12 sinon 13 𝜋𝑡+1 𝑠 = 𝜋𝑡(𝑠) 14 fin 15 fin 16 jusqu’à 𝜋𝑡 𝑠 = 𝜋𝑡+1 𝑠 ∀𝑠 ∈ 𝑆 ; Sorties : 𝜋 𝑡+1 la politique optimale 26 Puterman [Puterman, 1994] a montré que l’algorithme ne converge pas moins vite que Value Iteration, pour les problèmes à horizon infini avec facteur d’escompte. Policy Iteration a besoin de moins d’itérations pour converger vers la politique optimale que Value Iteration. Ceci s’explique par le fait que Value Iteration continue à itérer tant que la valeur de la politique peut être améliorée, et ce même si la politique ne change pas. En revanche, une itération de Policy Iteration consomme plus de temps qu’une itération de Value Iteration. 

D’autres méthodes de résolution des MDPs

Les algorithmes classiques de programmation dynamique comme VI et PI, résolvent un MDP d’une manière optimale en mettant à jour la valeur de chaque état d’une manière itérative, dans un ordre fixe, un état à chaque itération. Cela peut être inefficace, puisque la structure graphique du problème est négligée, ce qui peut fournir une information importante sur les dépendances entre les états. Récemment, les chercheurs ont développé des algorithmes de recherche heuristique qui utilisent les informations d’accessibilité et les fonctions heuristiques pour éviter certaines mises à jour (backups) qui ne sont pas nécessaires. Ces approches, telles que, ILAO* (Improved LAO*) [Hansen and Zilberstein, 2001], LRTDP [Bonnet and Geffner, 2003b], HDP [Bonnet and Geffner, 2003a], BRTDP [McMahan et al., 2005] et Bayesian RTDP [Sanner et al., 2009], dépassent fréquemment VI. Cependant, sur certains problèmes, les algorithmes de recherche heuristiques offrent un bénéfice minime et il est difficile de prédire quand est ce qu’ils sont excellents. [Dai et al., 2011] proposent deux algorithmes qui résolvent les MDPs d’une manière optimale et accélèrent la convergence de VI: topological Value Iteration (TVI) et Focused Topological Value Iteration (FTVI). TVI utilise la structure graphique du MDP. Il applique l’équation de mise à jour de Bellman dans un ordre plus intelligent, après avoir appliqué une analyse additionnelle de la topologie de l’espace d’états du MDP. Il a été prouvé que cet algorithme donne de bons résultats par rapport à VI et même les algorithmes de recherche heuristique dans certains domaines. FTVI adresse les points faibles de TVI. Il applique, en premier, une phase de recherche heuristique afin d’éliminer les actions probablement sous-optimales. Par la suite, il construit une 27 structure graphique informative basée sur les actions qui restent. Il a été prouvé que FTVI donne des résultats meilleurs que TVI et les algorithmes de recherche heuristique dans certains domaines. D’autres travaux ont abordé le problème des MDPs larges, qui ne peuvent pas être résolus d’une manière optimale mais plutôt approximative. Pour le faire, des relaxations déterministes du MDP et/ou les fonctions basiques ont été utilisés [Guestrin et al., 2003; Poupart et al., 2002; Patrascu et al., 2002; Yoon et al., 2007; Kolobov et al., 2009, 2010a, 2010b]. L’approche de planification en ligne est très différente des méthodes de résolution des MDPs standards considérées dans la programmation dynamique et l’apprentissage par renforcement. Ces dernières trouvent souvent une solution globale, contrairement à la planification en ligne qui trouve des actions sur demande, localement pour chaque état quand c’est nécessaire. Cependant, la planification en ligne est beaucoup moins dépendante de la taille de l’espace des états. Elle est généralement sous-optimale, mais des limites (bounds) utiles peuvent être posées sur sa sous-optimalité [Busoniu et al., 2012]. Un algorithme récent de la famille de la planification optimiste est UCB (Upper Confidence Bound) appliqué aux arbres (UCT, Upper Confidence Bound for Tree) [Kocsis and Szepesvari, 2006], qui a eu un grand impact dans le domaine de la planification grâce au résultat compétitif qu’il a donné dans les jeux tels que Go [Gelly et al., 2006]. UCT applique UCB à chaque nœud dans l’arbre de planification. Il parcourt un chemin optimiste tout au long l’arbre en choisissant des actions avec un UCB maximal sur les récompenses obtenues à partir du nœud courant, et échantillonne les états indépendamment.

Les domaines d’application des MDPs

Les MDPs ont été premièrement utilisés pour la gestion de route de l’état d’Arizona en 1978 [Golabi et al., 1982; Puterman, 1994; Mundhenk et al., 2000]. Depuis ces formalismes puissants ont attiré l’attention de plusieurs chercheurs dans différents domaines. 28 Dans [Puterman, 1994], la diversité des applications des MDPs a été présentée. En effet, ces modèles peuvent être utilisés pour la gestion de l’inventaire, remplacement de pièces et d’équipement, entretien des chaussées routières, les modèles de communication et le routage, ainsi que pour l’étude des phénomènes biologiques. Plus récemment ces modèles ont été appliqués dans la robotique [Kaelbling et al., 1998; Roy et al. 2000]. Les MDPs et POMDPs ont également été utilisés afin de résoudre des problèmes de navigation. Les chercheurs de La NASA utilisent les MDPs pour modéliser les problèmes de planification des robots envoyés sur Mars [Bresina et al., 2002; Feng and Zilberstein, 2004; Mausam et al., 2005; Meuleau et al., 2009]. Les MDPs sont également utilisés pour formuler les problèmes de planification des opérations militaires [Aberdeen et al., 2004] et dans le cadre des réseaux de capteurs sans fil [Abu Alsheikh et al., 2015].