Comprendre MDP partiellement observable
Un MDP partiellement observable possède les mêmes modèle de transition, ensemble d’actions et fonction de récompense qu’un MDP, plus un modèle de capteur donnant la probabilité de chaque perception dans chaque état. L’ajout paraît mince et change complètement le problème : l’action optimale dépend désormais non seulement de l’endroit où se trouve l’agent mais de ce qu’il sait, si bien qu’une politique ne peut pas être une fonction de l’état.
La résolution consiste à en faire une fonction de la croyance. Comme l’état de croyance est une statistique exhaustive de l’histoire et reste toujours disponible pour l’agent, une politique optimale pour le MDP défini sur les états de croyance l’est aussi pour le problème d’origine. La réduction est exacte et non approchée - mais le MDP qu’elle produit a un espace d’états continu et généralement de grande dimension, si bien qu’itération sur les valeurs et itération sur les politiques ne peuvent pas simplement y être appliquées.
Ce qui rend le progrès possible, c’est la forme de la fonction de valeur. Exécuter un plan conditionnel fixé ne prend plus aucune décision : son utilité espérée est donc un produit scalaire entre la croyance et un vecteur d’utilités par état - un hyperplan sur l’espace des croyances. La fonction de valeur optimale retient le meilleur plan en chaque croyance : c’est donc un maximum d’hyperplans, linéaire par morceaux et convexe. Sa convexité est un énoncé sur l’incertitude, puisque ses points bas sont les croyances où l’agent sait le moins quoi faire.
Cette structure soutient un algorithme d’itération sur les valeurs portant sur des ensembles de vecteurs plutôt que sur des nombres, avec élagage des plans dominés à chaque étape. Il est exact et il ne passe pas à l’échelle : le nombre de plans conditionnels de profondeur d croît doublement exponentiellement, et l’élagage ralentit sans l’arrêter la croissance de l’ensemble à conserver. Le travail pratique discrétise donc l’espace des croyances, se restreint aux croyances atteignables, ou planifie en ligne par anticipation depuis la croyance courante avec un filtre particulaire qui la suit.
Comment calculer
U(b) = max_p Σ_s b(s) · α_p(s)
où
- b
- l’état de croyance courant - une distribution sur les états cachés
- p
- un plan conditionnel : une première action, puis quoi faire après chaque perception
- α_p(s)
- l’utilité espérée de l’exécution du plan p lorsque l’état vrai est s
- max_p
- l’enveloppe supérieure sur les plans, qui rend U linéaire par morceaux et convexe
Exemple : MDP partiellement observable
Dans un monde à deux états de récompenses 0 et 1, avec une action persistant avec probabilité 0,9 et l’autre basculant avec probabilité 0,9, et un capteur correct 60 % du temps, les deux plans à une étape ont pour vecteurs d’utilité (0,1 ; 1,9) et (0,9 ; 1,1). Les droites se croisent à une croyance de 1/2, où toutes deux valent exactement 1 : basculer en dessous, persister au-dessus.
Passer à deux étapes produit 8 plans conditionnels distincts, dont 4 seulement sont non dominés. Les comptes s’emballent ensuite - 128 à la profondeur trois et 32 768 à la profondeur quatre - et l’élagage ne les sauve pas : sur sept balayages d’itération exacte sur les valeurs, l’ensemble non dominé a tout de même crû 2, 4, 8, 16, 30, 52, 88.
Discrétiser l’intervalle des croyances et lancer une itération ordinaire sur les valeurs avec interpolation converge en 281 balayages, donnant 6,822940 aux deux croyances certaines et 5,886486 à la croyance uniforme - c’est l’incertitude qui coûte. Simuler la politique obtenue sur 30 000 trajectoires renvoie 6,8230 ± 0,0216 et 5,8769 ± 0,0188, ce qui est le contrôle indépendant que l’approximation n’a pas convergé sagement vers une mauvaise réponse.
Questions fréquentes
Pourquoi ne pas agir comme si l’état le plus probable était le vrai ?
Parce que cela jette précisément l’information dont le problème traite. Un agent qui s’engage sur sa meilleure hypothèse ne valorise jamais une action pour ce qu’elle révélerait : il ne prendra donc pas l’action de mesure bon marché qui lèverait une ambiguïté - et dans un POMDP la valeur de l’information fait partie de la décision, non d’une considération séparée.
Qu’est-ce qui rend les POMDP tellement plus durs que les MDP ?
L’espace d’états. Un MDP à 11 états est trivial ; l’espace des croyances correspondant est un continuum de dimension 10, puisque les 11 probabilités somment à un. La résolution exacte est irréalisable sauf sur des problèmes minuscules, et la vraie question est en général quelle approximation accepter plutôt que s’il faut approcher.
Comment les résout-on en pratique ?
Par approximation : discrétiser ou échantillonner l’espace des croyances, se restreindre aux croyances réellement atteignables depuis le départ, ou planifier en ligne - dérouler une anticipation bornée depuis la croyance courante pendant qu’un filtre particulaire la maintient, et replanifier après chaque perception.
En résumé
Un POMDP est un MDP plus un modèle de capteur, et se ramène exactement à un MDP sur les états de croyance - troquant un état discret caché contre un état continu observable. Cet échange rend la théorie propre et le calcul difficile : les systèmes réels suivent donc la croyance avec un filtre et planifient à courte distance depuis l’endroit où elle se trouve.