🤖 AI

Toward Learning POMDPs Beyond Full-Rank Actions and State Observability

Cet article présente une méthode pour apprendre les matrices de transition et d'observation explicites d'un processus de décision markovien partiellement observable (POMDP) à partir de données séquentielles en exploitant des approches spectrales et la décomposition tensorielle sous de légères hypothèses de rang, permettant aux agents de planifier pour des objectifs divers tout en prouvant que l'apprentissage au-delà d'une partition d'état spécifique est théoriquement impossible.

Auteurs originaux : Seiji Shaw, Travis Manderson, Chad Kessens, Nicholas Roy

Publié 2026-07-22

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Seiji Shaw, Travis Manderson, Chad Kessens, Nicholas Roy

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous essayez d'apprendre à un robot à naviguer dans un manoir lugubre et plongé dans l'obscurité totale. Vous ne voyez pas les pièces, mais vous entendez des craquements, ressentez des courants d'air et vous cognez contre des meubles. Chaque fois que le robot fait un pas, il obtient un petit indice sur l'endroit où il pourrait se trouver. C'est le monde des systèmes « partiellement observables » : l'agent (le robot) sait quelles actions il peut entreprendre et ce qu'il peut percevoir, mais il ne connaît pas la véritable carte de la maison ni sa position exacte à un instant donné. Pour agir intelligemment, le robot doit construire un modèle mental de ce monde caché. Pendant des décennies, des scientifiques ont développé des moyens pour deviner ce modèle, mais ils se sont souvent heurtés à un mur : les modèles qu'ils construisaient étaient comme des « boîtes noires ». Ils pouvaient prédire ce qui allait se passer ensuite, mais ils ne pouvaient pas expliquer pourquoi ou changer facilement de plan si l'objectif changeait (comme passer de « trouver le chat » à « trouver le trésor »).

Ce document s'attaque à ce problème de boîte noire. Les chercheurs, travaillant au MIT et au Army Research Laboratory, voulaient apprendre aux agents les véritables « règles du jeu » — les probabilités spécifiques de passer d'une pièce cachée à une autre et les indices spécifiques que chaque pièce émet. Ils se concentrent sur un type spécial de casse-tête mathématique appelé POMDP (Processus de Décision de Markov Partiellement Observable). Considérez le POMDP comme un jeu de plateau où vous ne voyez pas le plateau, seulement les lancers de dés et les pièces sur lesquelles vous atterrissez. Le but est de comprendre la disposition du plateau en jouant simplement au jeu, encore et encore. La grande question qu'ils posent est la suivante : pouvons-nous apprendre la disposition exacte du plateau, même si certaines pièces se ressemblent exactement de l'extérieur ?

La découverte principale de l'équipe est une nouvelle façon ingénieuse d'apprendre ces cartes cachées, mais avec une condition très importante. Ils ont trouvé que si les actions du robot sont de « rang plein » (une façon sophistiquée de dire que les actions sont assez diverses pour secouer le système et éviter de rester bloqué dans des boucles), le robot peut apprendre les probabilités réelles de mouvement entre des groupes de pièces. Cependant, ils ont prouvé que si deux pièces différentes émettent exactement les mêmes indices pour chaque action possible, le robot ne pourra jamais les distinguer simplement en se déplaçant. C'est comme essayer de faire la différence entre deux jumeaux identiques qui portent les mêmes vêtements et parlent avec la même voix ; peu importe le nombre de questions que vous leur posez, vous ne pourrez pas être certain de savoir lequel est lequel.

Alors, qu'ont-ils fait concrètement ? Ils ont combiné deux astuces mathématiques existantes. La première astuce, appelée Représentations d'États Prédictifs (PSR), est excellente pour deviner le futur mais mauvaise pour expliquer le passé. La seconde astuce, impliquant la « décomposition tensorielle », est comme un détective de haute technologie capable de séparer des signaux mélangés pour trouver les sources originales. Les auteurs ont réalisé que s'ils utilisaient d'abord la méthode PSR pour obtenir un croquis grossier du monde, ils pourraient ensuite utiliser la méthode tensorielle pour « faire pivoter » ce croquis jusqu'à ce qu'il corresponde à la disposition réelle du monde.

Voici la partie magique : dans de nombreux scénarios du monde réel, comme un bras robotique essayant de saisir une tasse, le robot peut échouer parfois (glisser) ou réussir d'autres fois. Ces actions « désordonnées » sont en fait utiles car elles créent suffisamment de variété dans les données pour permettre à la mathématique de fonctionner. Les auteurs ont montré qu'en utilisant ces actions à rang plein, leur méthode peut apprendre les matrices de transition et d'observation (les règles du jeu) jusqu'à une « partition ». Cela signifie que le robot apprend que « la pièce A et la pièce B sont dans le même groupe parce qu'elles sont identiques », et il apprend les règles pour se déplacer entre ces groupes. Si chaque pièce possède une empreinte digitale unique, le robot apprend la carte entière parfaitement. Si certaines pièces sont des jumelles, il apprend la carte des groupes.

Le papier exclut également explicitement l'idée que nous puissions un jour apprendre la différence exacte entre ces pièces « jumelles » en utilisant simplement une seule ligne de données de déplacement. Ils ont construit une preuve mathématique montrant que deux configurations de maisons complètement différentes pourraient produire exactement la même séquence de craquements et de chocs. Si le robot ne peut pas faire la différence dans les indices, il ne peut pas faire la différence dans la carte. Ce n'est pas un échec de leur algorithme ; c'est une limite fondamentale de l'univers.

Dans leurs expériences, ils ont testé cela sur plusieurs mondes numériques, incluant un jeu de « Tigre » (où un tigre se trouve derrière l'une des deux portes) et un domaine « Sense-Float-Reset » (un robot se déplaçant sur une ligne). Ils ont constaté que leur méthode apprenait avec succès les probabilités de mouvement entre les « groupes » d'états. Plus important encore, parce qu'ils ont appris les véritables règles du jeu plutôt qu'un simple prédicteur de boîte noire, ils pouvaient changer l'objectif du robot après l'apprentissage. Par exemple, on pourrait dire au robot : « Maintenant, va dans la pièce bruyante du milieu », et le robot pourrait trouver comment y parvenir en utilisant la carte qu'il avait déjà construite. Les méthodes précédentes auraient dû tout recommencer pour apprendre un nouvel objectif.

Les auteurs suggèrent que cette approche est un pas significatif vers des robots plus flexibles. Elle permet d'apprendre un modèle du monde qui est interprétable et réutilisable. Cependant, ils précisent avec prudence que cela fonctionne mieux lorsque le robot dispose d'un ensemble d'actions diversifiées. Si le robot est trop maladroit ou si l'environnement est trop statique, la mathématique pourrait ne pas être capable de séparer les états cachés. Ils indiquent également que leur méthode actuelle fonctionne mieux pour des systèmes ayant un petit nombre d'états cachés, car les calculs deviennent très lourds pour des mondes vastes et complexes. Mais pour l'instant, ils ont montré que nous pouvons jeter un coup d'œil derrière le rideau des états cachés, tant que nous acceptons que certains jumeaux resteront toujours indiscernables.

Résumé Technique : Vers l'apprentissage des POMDP au-delà des actions à rang plein et de l'observabilité des états

Énoncé du problème
Le papier traite du défi consistant à permettre à des agents autonomes d'apprendre et de raisonner sur des systèmes dotés d'états cachés, en modélisant ces systèmes spécifiquement comme des processus de décision de Markov partiellement observables (POMDP) discrets. L'agent est fourni avec les espaces d'actions et d'observations, mais ne possède aucune connaissance préalable de l'espace d'états, de la dynamique de transition ou des modèles d'observation. L'objectif est d'estimer le nombre d'états cachés ainsi que les matrices explicites de transition et d'observation à partir d'une séquence d'actions et d'observations collectées via une exploration aléatoire.

Bien que les méthodes spectrales comme les représentations d'états prédictifs (PSR) puissent apprendre des statistiques suffisantes pour prédire des résultats futurs, elles fonctionnent comme des modèles de type "boîte noire". Elles ne produisent pas de vraisemblances explicites de transition et d'observation, ce qui rend difficile la manipulation du modèle pour de nouvelles tâches de planification (par exemple, changer les fonctions de récompense) sans réapprendre l'intégralité du système. Inversement, les méthodes de décomposition tensorielle existantes pour la récupération de modèles POMDP complets reposent généralement sur des hypothèses strictes : que les matrices de transition sont de rang plein et que chaque état possède une distribution d'observation unique pour chaque action. Ces hypothèses échouent dans de nombreux scénarios réels impliquant un masquage d'état (state aliasing, où des états distincts partagent des distributions d'observation identiques) ou des actions qui peuvent échouer de manière probabiliste.

Méthodologie
Les auteurs proposent une méthode qui combine la décomposition spectrale et la décomposition tensorielle pour apprendre les paramètres des POMDP sous des hypothèses plus souples. L'approche se déroule en trois étapes principales :

Construction de la matrice de Hankel et apprentissage de la PSR :
La méthode commence par la construction d'une matrice de Hankel à partir des trajectoires action-observation observées. Cette matrice encode les vraisemblances conjointes des observations passées et futures. En effectuant une factorisation de rang (via la décomposition en valeurs singulières, SVD) sur cette matrice, l'algorithme dérive une représentation d'état prédictif (PSR) linéaire. Cela produit un ensemble de matrices de mise à jour linéaires ( $M_{ao}$ ), un vecteur initial ( $m_0$ ) et un vecteur final ( $m_\infty$ ). Ces composantes représentent la dynamique du système jusqu'à une transformation de similitude inconnue $P$ .
Récupération de la transformation de similitude :
Pour récupérer les matrices explicites de transition ( $T^a$ ) et d'observation ( $O_{ao}$ ), l'algorithme doit estimer la transformation de similitude $P$ . Les auteurs reformulent les techniques de décomposition tensorielle pour estimer $P$ .

Premièrement, ils marginalisent les observations pour obtenir les matrices de transition jusqu'à la transformation : $\sum_o M_{ao} = P T^a P^{-1}$ .
Pour les actions ayant des matrices de transition à rang plein, ils calculent le produit $M_{ao} M_a^{-1} = P O_{ao} P^{-1}$ .
Puisque les $O_{ao}$ sont diagonales, les valeurs propres de ces produits correspondent aux entrées diagonales. Pour résoudre l'ambiguïté causée par les valeurs propres répétées (qui surviennent lorsque des états partagent des distributions d'observation), la méthode emploie une diagonalisation conjointe d'une somme pondérée de ces matrices. Des poids aléatoires sont échantillonnés pour garantir que les valeurs propres soient distinctes presque sûrement pour les états possédant des distributions d'observation uniques à travers toutes les actions à rang plein.

Apprentissage jusqu'aux partitions d'observabilité :
Le papier introduit le concept de Partition d'Observabilité à Rang Plein. Si plusieurs états partagent exactement la même distribution d'observation pour toutes les actions ayant des transitions à rang plein, ils ne peuvent être distingués par les seules données séquentielles. L'algorithme récupère la transformation de similitude $P$ jusqu'à cette partition. Par conséquent, le modèle appris fournit des matrices de transition et d'observation explicites entre les partitions d'états plutôt qu'entre les états individuels. Pour les états au sein d'une même partition, le modèle apprend la dynamique agrégée.

Contributions clés

Hypothèses assouplies : La méthode étend les approches de décomposition tensorielle pour apprendre des POMDP où les états peuvent être masqués (partageant des distributions d'observation) et où les matrices de transition ne sont pas nécessairement de rang plein pour chaque action, à condition que le produit des matrices de transition et d'observation soit de rang plein.
Récupération de modèle explicite : Contrairement aux PSR, la méthode récupère des matrices de transition et d'observation explicites (jusqu'à une partition), permettant la spécification de nouvelles fonctions de récompense et d'objectifs après la phase initiale d'apprentissage sans réentraînement.
Limites théoriques : Les auteurs prouvent qu'apprendre la dynamique de transition et d'observation au-delà de la partition d'observabilité est impossible à partir d'une seule trajectoire de données séquentielles. Ils construisent un contre-exemple démontrant deux POMDP distincts avec des dynamiques internes différentes qui produisent des distributions d'observation identiques pour toutes les séquences d'actions, établissant ainsi la limite théorique d'identifiabilité.

Résultats expérimentaux
Les auteurs évaluent leur méthode sur plusieurs domaines, notamment le domaine "Sense-Float-Reset" (présentant un masquage d'état), le problème du Tigre et le T-Maze.

Convergence : La méthode récupère avec succès les modèles d'observation sous-jacents et les matrices de transition au niveau de la partition, convergeant vers les valeurs de vérité terrain à mesure que le nombre d'interactions d'exploration augmente. En revanche, l'algorithme d'espérance-maximisation (EM) converge souvent vers des minima locaux qui prédisent correctement les observations mais produisent des paramètres de modèle incorrects.
Performance de planification : Lorsqu'elle est utilisée avec un planificateur standard (PO-UCT), les POMDP de niveau partition appris atteignent une performance de planification comparable aux modèles de vérité terrain et aux PSR.
Spécification de récompense : Dans de nouveaux domaines "Noisy Hallway" et "Directional Hallway", les auteurs démontrent que les vraisemblances explicites de transition et d'observation permettent de diriger un agent vers des états latents spécifiques (par exemple, un état de couloir central avec des observations ambiguës) en assignant des récompenses aux états plutôt qu'aux simples couples observation-action. Cette capacité n'est pas disponible avec les PSR standards ou les modèles basés sur l'EM qui échouent à récupérer la structure d'état correcte.

Signification et affirmations
Le papier affirme que sa méthode comble le fossé entre le pouvoir prédictif des PSR et l'interprétabilité des modèles explicites de POMDP. En apprenant jusqu'à une partition d'observabilité, la méthode capture une classe plus large de systèmes du monde réel (particulièrement en manipulation robotique où les actions peuvent échouer ou les états peuvent être masqués) que les méthodes antérieures basées sur les tenseurs.

Les auteurs affirment modestement que, bien que leur méthode ne puisse pas récupérer la structure interne exacte des états masqués à partir de données séquentielles, elle récupère la quantité maximale d'informations théoriquement possible. La capacité de manipuler le modèle appris pour de nouvelles tâches (via la spécification explicite de récompenses) est mise en avant comme un avantage primaire par rapport aux modèles prédictifs de type boîte noire. Ce travail suggère que pour de nombreuses applications pratiques, l'apprentissage de la dynamique entre les partitions d'observabilité est suffisant pour une planification et un raisonnement efficaces.

Articles similaires