Agir quand on ne voit pas l’état

Les processus de décision markoviens supposent que l’agent sait où il est. Cette hypothèse travaille plus qu’il n’y paraît, et l’abandonner change complètement le problème - non parce que les mathématiques deviennent accessoirement plus dures, mais parce que l’objet central d’un MDP, une politique indexée par l’état, cesse d’être quelque chose que l’agent puisse exécuter.

Cet article déroule ce qui la remplace, sur un monde assez petit pour que chaque nombre soit calculable exactement.

A. Un seul ajout

Un MDP partiellement observable possède tout ce qu’a un MDP - modèle de transition, actions, récompenses - plus un modèle de capteur $P(e \mid s)$ : la probabilité de percevoir l’indice $e$ dans l’état $s$.

La conséquence est immédiate. Une politique $\pi(s)$ exige de consulter l’état, et l’agent ne peut pas. Pire, l’action optimale ne dépend plus seulement de l’endroit où est l’agent mais de ce qu’il sait : deux agents dans le même état, l’un certain et l’autre perdu, devraient souvent agir différemment.

B. L’état de croyance

Le remplaçant est la distribution sur les états compatibles avec tout ce qui a été fait et perçu : l’état de croyance $b$, où $b(s)$ est la probabilité d’être en $s$.

Deux propriétés en font le bon objet. Il est toujours observable par l’agent - il résume l’histoire de l’agent, non le monde - si bien que $\pi(b)$ est exécutable là où $\pi(s)$ ne l’est pas. Et c’est une statistique exhaustive : les transitions et perceptions étant markoviennes, tout ce que le passé dit du futur est déjà dans la distribution actuelle, et l’histoire peut donc être jetée.

Il se maintient par une récursion :

$$b'(s') = \alpha \; P(e \mid s') \sum_{s} P(s' \mid s, a) \, b(s) .$$

Prédire par le modèle de transition, pondérer par la vraisemblance de la perception, normaliser. C’est l’étape avant du filtrage des modèles de Markov cachés, à une addition près : le modèle de transition dépend du choix de l’agent, si bien que l’agent influence non seulement où il va mais ce qu’il apprendra.

C. Un monde assez petit pour être vu

Deux états, 0 et 1, avec $R(0) = 0$ et $R(1) = 1$. Persister garde l’état avec probabilité 0,9, basculer le change avec probabilité 0,9. Le capteur est correct avec probabilité 0,6. Une croyance est un nombre, $b(1)$, si bien que tout l’espace des croyances est $[0, 1]$.

Depuis $b(1) = 1/2$, chaque couple action-perception :

L’action n’a rien changé. Depuis une croyance uniforme, persister et basculer laissent tous deux la prédiction uniforme - l’un persiste avec 0,9, l’autre bascule avec 0,9, ce qui depuis 50/50 revient au même - la perception fait donc tout le travail. Cela sépare les deux tâches d’une action dans un POMDP : changer le monde, et changer ce que l’on en sait. Ici la première s’annule et seule la seconde se voit.

D. Le plafond de la certitude

La confiance se perd plus vite qu’elle ne s’acquiert. Une croyance de 0,99 qui persiste puis rencontre une perception contradictoire tombe à $446/527 = 0{,}846300$, l’essentiel venant de la fuite de Rester, qui conduit à elle seule 0,99 à une prédiction de 0,892. Dans l’autre sens, en persistant et en voyant la perception 1 de façon répétée depuis 1/2 :

$$0{,}600, \; 0{,}674, \; 0{,}727, \; 0{,}762, \; 0{,}786, \; 0{,}801, \; 0{,}811, \; 0{,}817, \ldots$$

Elle n’atteint pas 1. L’itération converge vers $0{,}827934423$, et résoudre symboliquement l’équation de point fixe donne

$$b^{*} = \frac{3 + \sqrt{105}}{16} = 0{,}827934 .$$

Chaque perception tire la croyance vers l’extérieur ; chaque transition laisse fuir 0,1 de probabilité vers le milieu. Le point fixe est là où elles s’annulent. La certitude est inatteignable, donc un agent qui attend de savoir où il est attend indéfiniment - il doit planifier en restant incertain.

C’est aussi pourquoi le raccourci tentant échoue. Suivre la croyance, prendre l’état le plus probable, le donner à une politique MDP ordinaire : bon marché, facile, et cela ne valorise jamais une action pour ce qu’elle révélerait. Offrez à un tel agent une mesure gratuite : il n’y voit aucun bénéfice, puisque l’état qu’il a deviné ne change pas. Il ne regarde jamais avant de sauter.

Voici tout l’espace des croyances - l’intervalle - avec la croyance dessus, en un seul point. Appuyez sur « Rester, vu 1 » et continuez. Les pas rétrécissent à vue d’œil, la montée s’infléchit vers la ligne pointillée, et s’y arrête. Appuyez ensuite une fois sur « Rester, vu 0 » depuis le haut : une seule lecture d’un capteur faux 40 % du temps coûte plus que n’avaient rapporté deux confirmations. Cette asymétrie n’est pas une bizarrerie de ces nombres-là ; c’est ce que fait toujours une preuve contraire à une croyance assurée.

E. La réduction

Voici le gain. Les croyances se mettent à jour de façon déterministe à partir de l’action et de la perception, et la probabilité de chaque perception est calculable : nous pouvons donc définir un MDP dont les états sont des croyances - et une politique optimale pour lui est optimale pour le POMDP. La réduction est exacte.

La facture : ce MDP a un espace d’états continu. Pour le monde en grille 4×3 à onze états, une croyance est un point d’un continuum de dimension dix (onze probabilités de somme un). Aucun algorithme MDP standard n’énumère cela.

La compensation : parce qu’une action déplace la croyance et pas seulement le monde, elle est valorisée en partie pour l’information qu’elle produit. La valeur de l’information cesse d’être un calcul séparé et devient une part de la décision ordinaire.

F. Pourquoi la fonction de valeur est calculable en principe

Fixez un plan conditionnel - une première action, puis quoi faire après chaque perception, jusqu’à une certaine profondeur. Il ne prend aucune décision en chemin, si bien que son utilité espérée dans l’état vrai $s$ est un nombre. Rassemblez-les dans $\alpha_p$, et

$$U_p(b) = \sum_s b(s) \, \alpha_p(s)$$

est un produit scalaire : linéaire en $b$, un hyperplan. 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. La convexité dit quelque chose : les points bas sont les croyances de plus grande incertitude, c’est donc l’incertitude qui coûte.

Pour les plans à une étape avec $\gamma = 1$ :

$$\alpha_{[\text{persister}]} = (0{,}1\,;\, 1{,}9), \qquad \alpha_{[\text{basculer}]} = (0{,}9\,;\, 1{,}1),$$

croisés en $b(1) = 1/2$ où tous deux valent exactement 1. Basculer en dessous, persister au-dessus - la politique intuitive, arrivant comme un calcul avec le point de bascule fixé exactement.

Les plans à deux étapes sont $2 \times 2 \times 2 = 8$, et balayer l’intervalle des croyances montre que quatre seulement dominent l’enveloppe : $(0{,}28\,;\,2{,}72)$, $(0{,}68\,;\,2{,}48)$, $(1{,}48\,;\,1{,}68)$, $(1{,}72\,;\,1{,}28)$. Les quatre autres sont en dessous partout : les supprimer ne change $U(b)$ nulle part.

Voici ces huit plans en huit droites, la fonction de valeur étant leur enveloppe supérieure. Les quatre que la récursion conserve sont en gras, et les quatre dominés sont tracés en pâle plutôt que supprimés : c'est justement qu'ils existent et ne servent à rien, chacun restant sous l'enveloppe à toute croyance. Passez à un pas pour voir les deux droites se croiser exactement à un demi, où elles valent 1 toutes deux.

G. Pourquoi elle ne l’est pas en pratique

Les plans de profondeur $d$ sont au nombre de $|A|^{(|E|^{d}-1)/(|E|-1)}$ :

Doublement exponentiel, sur le plus petit POMDP intéressant qui soit. Élaguer les plans dominés est indispensable - et insuffisant. En exécutant l’itération exacte sur les valeurs avec $\gamma = 0{,}9$ et en ne gardant que les vecteurs dominant l’enveloppe, l’ensemble survivant croît balayage après balayage :

$$2, \; 4, \; 8, \; 16, \; 30, \; 52, \; 88 .$$

Il ne s’effondre jamais, parce que la fonction de valeur exacte acquiert véritablement davantage de morceaux linéaires à mesure que l’horizon s’allonge. L’algorithme est correct ; il ne termine simplement pas.

H. Discrétiser, puis vérifier en exécutant

L’espace des croyances est ici un intervalle : mettez-y une grille et exécutez une itération ordinaire sur les valeurs, en répartissant chaque croyance successeur entre ses deux voisines. Cette interpolation garde la mise à jour contractante, si bien qu’elle converge - en 281 balayages à 2 001 points :

$$U(0) = 6{,}822940, \quad U(0{,}5) = 5{,}886486, \quad U(1) = 6{,}822940 .$$

La plus basse au milieu : savoir où l’on est vaut ici $0{,}936454$. Et les deux extrémités sont égales, ce qui mérite vérification plutôt que supposition - depuis l’état 0 certain l’agent bascule et atteint l’état 1 avec probabilité 0,9 ; depuis l’état 1 certain il persiste et y reste avec probabilité 0,9. Même position au pas suivant, même valeur.

Raffiner la grille donne 6,822981 ; 6,822942 ; 6,822940 à 201, 801 et 2 001 points. Mais cela montre seulement l’approximation convergeant vers quelque chose - un schéma d’interpolation peut converger sagement vers une réponse biaisée et ressembler exactement à cela.

Alors exécutez la politique. Sur 30 000 trajectoires d’horizon 160 :

Le raffinement de la grille demande si l’approximation est cohérente avec elle-même. L’exécution demande si la politique rapporte réellement autant. Seule la seconde aurait pu attraper un biais d’interpolation systématique, et c’est celle qui compte.

Les deux moitiés sont dans la figure ci-dessous. Le nombre de plans est imprimé en entiers exacts, car à la profondeur six la réponse vaut 2^63, et si un flottant la stocke exactement, JavaScript l'affiche 9223372036854776000, un nombre que cette page ne contient pas. La fonction de valeur, à côté, est résolue sur la grille, et le curseur parcourt le tableau de raffinement : 6,822981 à 201 points, 6,822942 à 801, 6,822940 à 2001, en 281 balayages. Regardez les deux bouts rester égaux pendant que le milieu s'affaisse : c'est la convexité.

Points clés

• Un POMDP est un MDP plus un modèle de capteur, et ce seul ajout fait qu’une politique ne peut pas être indexée par l’état.
• L’état de croyance le remplace : toujours observable, et statistique exhaustive de toute l’histoire.
• Un capteur bruité sature la croyance au lieu de la résoudre - ici exactement à $(3 + \sqrt{105})/16$ - si bien que la planification sous incertitude est permanente.
• La réduction à un MDP sur les croyances est exacte, et coûte un espace d’états continu.
• La fonction de valeur est linéaire par morceaux et convexe, ce qui rend l’itération exacte possible et, de façon mesurée, impraticable.
• Approchez, puis vérifiez en exécutant la politique plutôt qu’en raffinant l’approximation.

Et ensuite

Toutes les méthodes vues ici supposaient les modèles connus. Apprendre les modèles de transition et de capteur à partir de l’expérience tout en agissant dessus est le même problème avec les paramètres cachés en plus - et l’algorithme EM se révèle être l’outil.