États de croyance et mise à jour

Tous les problèmes de décision vus jusqu’ici laissaient l’agent voir où il se trouve. Les processus de décision markoviens donnaient une politique $\pi(s)$ - consulter l’état, lire l’action. Cette leçon supprime la consultation : l’état est caché, et seules en arrivent des perceptions bruitées.

Un seul ajout, et tout change

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

L’ajout paraît mince et il casse l’objet central. Une politique ne peut plus être une fonction de l’état, puisque l’agent ne peut pas l’évaluer. 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 faire des choses différentes.

L’objet qui remplace l’état

La solution est de raisonner sur la distribution des états compatibles avec tout ce qui a été fait et perçu. Cette distribution est l’état de croyance, noté $b$, où $b(s)$ est la probabilité d’être dans l’état $s$.

Le mouvement qui fait fonctionner cela est presque trop simple pour se remarquer : l’état de croyance est toujours observable par l’agent. C’est un résumé de sa propre histoire, non du monde. Une politique $\pi(b)$ est donc quelque chose que l’agent peut réellement exécuter, là où $\pi(s)$ ne l’est pas.

C’est aussi une statistique exhaustive de l’histoire. Parce que les modèles de transition et de capteur sont markoviens - l’état suivant ne dépend que de l’état et de l’action courants, la perception que de l’état courant - tout ce que le passé a à dire du futur est déjà dans la distribution actuelle. L’agent peut donc jeter son histoire et ne porter que $b$, ce qui rend la planification possible tout court.

La maintenir

Étant donné une croyance, une action $a$ et la perception $e$ qui suit, la nouvelle croyance vaut

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

Trois étapes. Prédire : pousser la croyance à travers le modèle de transition de l’action prise. Pondérer : multiplier chaque successeur candidat par la vraisemblance qu’y aurait la perception observée. Normaliser : $\alpha$ fait sommer le tout à un.

C’est exactement l’étape avant du filtrage des modèles de Markov cachés du parcours sur les modèles temporels. La seule addition est que le modèle de transition dépend désormais du choix de l’agent - ce qui signifie que l’agent influence non seulement où il va mais ce qu’il apprendra.

Un monde assez petit pour être vu

Deux états, 0 et 1, avec $R(0) = 0$ et $R(1) = 1$. Deux actions : persister garde l’état avec probabilité 0,9, basculer le change avec probabilité 0,9. Le capteur annonce le bon état avec probabilité 0,6 - à peine mieux qu’une pièce.

Comme il y a deux états, une croyance est un nombre : $b(1)$, $b(0)$ étant son complément. Tout l’espace des croyances est l’intervalle $[0, 1]$.

Partez de $b(1) = 1/2$ et agissez. Les résultats méritent qu’on s’y arrête :

L’action n’a rien changé. Depuis une croyance uniforme, persister envoie une prédiction uniforme sur une prédiction uniforme, et basculer aussi - l’une persiste avec 0,9 et l’autre bascule avec 0,9, ce qui depuis un partage 50/50 revient au même. La perception fait tout le travail, et 0,6 contre 0,4 donne exactement 3/5.

Cette coïncidence mérite d’être nommée, car elle 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 est visible. En général les deux comptent à la fois, et une action peut valoir la peine uniquement pour ce qu’elle révèle.

La confiance se perd plus vite qu’elle ne s’acquiert

Poussez une croyance assurée contre une seule lecture contradictoire :

Une croyance de 0,99 tombe à 0,846 en une seule étape, mais le capteur y est pour moins qu’il n’y paraît. La fuite de Rester conduit à elle seule 0,99 à une prédiction de 0,892 : dix des quatorze points sont donc partis avant l’arrivée de la perception ; la perception 0 en retire ensuite 0,046 de plus, et même une perception 1 confirmative laisserait la croyance à 0,925. Poussez maintenant dans l’autre sens, en persistant et en voyant la perception 1 encore et encore depuis $b(1) = 1/2$ :

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

Huit confirmations consécutives n’atteignent que 0,817218. La montée ralentit, et elle ne s’arrête pas à 1.

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 un capteur unilatéral : chaque perception multiplie ou divise la cote par le même $0{,}6 / 0{,}4 = 1{,}5$, quelle que soit la croyance. C’est la fuite de Rester, qui tout près du plafond a déjà annulé l’essentiel de ce qu’une confirmation rapporte.

Le plafond

Itérer cette mise à jour converge vers $0{,}827934423$, et résoudre symboliquement l’équation de point fixe donne la forme close

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

Deux forces s’y équilibrent. Chaque perception tire la croyance vers l’extérieur, puisque le capteur porte de l’information. Chaque transition la repousse vers le milieu, puisque persister laisse fuir 0,1 de probabilité vers l’autre état à chaque pas. Le point fixe est là où elles s’annulent exactement, et au-delà les indices supplémentaires n’achètent rien, car ils arrivent moins vite que le monde n’oublie.

La conséquence est tout le sujet. La certitude est inatteignable : un agent qui attend de savoir où il est attend indéfiniment. Il doit planifier en restant incertain - et c’est la croyance, non l’état, qui est l’objet de sa planification.

Le raccourci tentant, et pourquoi il échoue

Une réaction naturelle est de tout sauter : suivre la croyance, prendre l’état le plus probable, et le passer à une politique MDP ordinaire. C’est bon marché, facile à implémenter, et faux d’une façon précise qui mérite d’être comprise.

Un agent qui s’engage sur sa meilleure hypothèse traite sa propre incertitude comme un bruit à arrondir. Il ne valorisera donc jamais une action pour ce qu’elle révélerait. Offrez-lui une mesure bon marché - sans récompense mais levant une ambiguïté - il y voit une action sans bénéfice, puisque l’état qu’il se croit occuper ne change pas. Il ne regarde donc jamais avant de sauter, et exécutera avec assurance un plan juste dans l’état deviné et désastreux dans celui qu’il a écarté à 45 %.

La formulation par croyances n’a pas ce trou, parce que la croyance est l’état. Une action qui affûte la distribution mène l’agent à un meilleur état de croyance, et la machinerie valorise ce déplacement comme n’importe quel autre. La valeur de l’information, que le parcours de théorie de la décision traitait comme un calcul à part, arrive ici gratuitement, par le simple fait d’avoir choisi la bonne variable d’état.

Avant le quiz

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 : une distribution sur les états, toujours observable par l’agent, et statistique exhaustive de toute l’histoire. Il se maintient par prédire-pondérer-normaliser, la même récursion que le filtrage des modèles de Markov cachés avec l’action choisie par l’agent. Et avec un capteur bruité il sature - ici exactement à $(3 + \sqrt{105})/16$ - si bien que planifier sous incertitude n’est pas un pis-aller mais la condition permanente.