🤖 AI

Toward Learning POMDPs Beyond Full-Rank Actions and State Observability

Este artigo apresenta um método para aprender as matrizes de transição e observação explícitas de um Processo de Decisão Markoviana Parcialmente Observável (POMDP) a partir de dados sequenciais, aproveitando abordagens espectrais e decomposição de tensores sob suposições de posto suaves, permitindo que agentes planejem para diversos objetivos ao provar que aprender além de uma partição de estado específica é teoricamente impossível.

Autores originais: Seiji Shaw, Travis Manderson, Chad Kessens, Nicholas Roy

Publicado 2026-07-22

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Seiji Shaw, Travis Manderson, Chad Kessens, Nicholas Roy

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você está tentando ensinar um robô a navegar em uma mansão assustadora e totalmente escura. Você não consegue ver os cômodos, mas consegue ouvir estalos, sentir correntes de ar e esbarrar em móveis. Cada vez que o robô dá um passo, ele recebe uma pequena pista de onde ele pode estar. Este é o mundo dos sistemas "Parcialmente Observáveis": o agente (o robô) sabe quais ações pode realizar e o que pode sentir, mas não conhece o mapa real da casa ou exatamente onde está parado em qualquer momento dado. Para agir de forma inteligente, o robô precisa construir um modelo mental deste mundo oculto. Durante décadas, cientistas desenvolveram formas de adivinhar esse modelo, mas eles frequentemente batiam em um muro: os modelos que construíam eram como "caixas pretas". Eles podiam prever o que aconteceria a seguir, mas não consegravam explicar o porquê ou mudar seus planos facilmente se o objetivo mudasse (como mudar de "encontrar o gato" para "encontrar o tesouro").

Este artigo aborda esse problema da caixa preta. Os pesquisadores, trabalhando no MIT e no Laboratório de Pesquisa do Exército, queriam ensinar agentes a aprender as próprias "regras do jogo" — as probabilidades específicas de mover-se de um cômodo oculto para outro e as pistas específicas que cada cômodo emite. Eles se concentram em um tipo especial de quebra-cabeça matemático chamado POMDP (Processo de Decisão de Markov Parcialmente Observável). Pense no POMDP como um jogo de tabuleiro onde você não consegue ver o tabuleiro, apenas os lançamentos de dados e as peças onde você cai. O objetivo é descobrir o layout do tabuleiro apenas jogando o jogo repetidamente. A grande questão que eles fazem é: podemos aprender o layout exato do tabuleiro, mesmo quando alguns cômodos parecem exatamente iguais por fora?

A principal descoberta da equipe é uma nova e inteligente maneira de aprender esses mapas ocultos, mas com uma ressalva muito importante. Eles descobriram que, se as ações do robô forem de "posto completo" (uma forma elegante de dizer que as ações são diversas o suficiente para agitar o sistema e não ficar preso em loops), o robão pode aprender as probabilidades reais de mover-se entre grupos de cômodos. No entanto, eles provaram que, se dois cômodos diferentes emitirem exatamente as mesmas pistas para cada ação possível, o robô nunca poderá diferenciá-los apenas caminhando por aí. É como tentar diferenciar dois gêmeos idênticos que usam as mesmas roupas e falam com a mesma voz; não importa quantas vezes você faça perguntas, você não terá certeza de qual é qual.

Então, o que eles realmente fizeram? Eles combinaram dois truques matemáticos existentes. O primeiro truque, chamado Representações de Estado Preditivo (PSR), é ótimo para adivinhar o futuro, mas ruim para explicar o passado. O segundo truque, envolvendo "decomposição tensorial", é como um detetive de alta tecnologia que pode separar sinais misturados para encontrar as fontes originais. Os autores perceberam que, se usassem o método PSR primeiro para obter um esboço bruto do mundo, poderiam então usar o método tensorial para "rotacionar" esse esboço até que ele correspondesse ao layout real do mundo.

Aqui está a parte mágica: em muitos cenários do mundo real, como um braço robótico tentando pegar uma xícara, o robô pode falhar às vezes (escorregando) ou ter sucesso outras vezes. Essas ações "bagunçadas" são, na verdade, úteis porque criam variedade suficiente nos dados para permitir que a matemática funcione. Os autores mostraram que, ao usar essas ações de posto completo, seu método pode aprender as matrizes de transição e observação (as regras do jogo) até uma "partição". Isso significa que o robô aprende que "o Cômodo A e o Cômodo B estão no mesmo grupo porque parecem idênticos" e aprende as regras para se mover entre esses grupos. Se cada cômodo tiver uma impressão digital única, o robô aprende o mapa inteiro perfeitamente. Se alguns cômodos forem gêmeos, ele aprende o mapa dos grupos.

O artigo também descarta explicitamente a ideia de que podemos aprender a diferença exata entre esses cômodos "gêmeos" usando apenas uma única linha de dados de caminhada. Eles construíram uma prova matemática mostrando que dois layouts de casa completamente diferentes poderiam produzir exatamente a mesma sequência de estalos e esbarrões. Se o robô não consegue distinguir as pistas, ele não consegue distinguir o mapa. Isso não é uma falha do algoritmo deles; é um limite fundamental do universo.

Em seus experimentos, eles testaram isso em vários mundos digitais, incluindo um jogo do "Tigre" (onde um tigre está atrás de uma de duas portas) e um domínio "Sentir-Flutuar-Resetar" (um robô movendo-se em uma linha). Eles descobriram que seu método aprendeu com sucesso as probabilidades corretas de movimento entre os "grupos" de estados. Mais importante ainda, porque aprenderam o modelo real do jogo em vez de apenas um preditor de caixa preta, eles puderam mudar o objetivo do robô após o aprendizado ter sido concluído. Por exemplo, eles poderiam dizer ao robô: "Agora, vá para o cômodo barulhento do meio", e o robô conseguiria descobrir como chegar lá usando o mapa que já havia construído. Métodos anteriores teriam precisado começar tudo de novo para aprender um novo objetivo.

Os autores sugerem que esta abordagem é um passo significativo à frente para robôs que precisam ser flexíveis. Ela permite que aprendam um modelo do mundo que é interpretável e reutilizável. No entanto, eles observam cautelosamente que isso funciona melhor quando o robô tem um conjunto diversificado de ações para tentar. Se o robô for muito desajeitado ou o ambiente for muito estático, a matemática pode não ser capaz de separar os estados ocultos. Eles também apontam que seu método atual funciona melhor para sistemas com um número pequeno de estados ocultos, pois a matemática torna-se muito pesada para mundos vastos e complexos. Mas, por enquanto, eles mostraram que podemos espiar por trás da cortina dos estados ocultos, desde que aceitemos que alguns gêmeos sempre permanecerão indistinguíveis.

Resumo Técnico: Em Direção ao Aprendizado de POMDPs Além da Observabilidade de Estados e Ações de Posto Completo

Enunciado do Problema
O artigo aborda o desafio de capacitar agentes autônomos a aprender e raciocinar sobre sistemas com estados ocultos, modelando esses sistemas especificamente como Processos de Decisão de Markov Parcialmente Observáveis (POMDPs) discretos. O agente recebe os espaços de ação e observação, mas carece de conhecimento prévio do espaço de estados, da dinâmica de transição ou dos modelos de observação. O objetivo é estimar o número de estados ocultos e as matrizes explícitas de transição e observação a partir de uma sequência de ações e observações coletadas via exploração aleatória.

Embora métodos espectrais como as Representações de Estado Preditivo (PSRs) possam aprender estatísticas suficientes para prever resultados futuros, eles funcionam como modelos de caixa-preta. Eles não fornecem verossimilhanças explícitas de transição e observação, o que dificulta a manipulação do modelo para novas tarefas de planejamento (por exemplo, alterando funções de recompensa) sem reaprender todo o sistema. Por outro lado, os métodos de decomposição tensorial existentes para recuperar modelos POMDP completos geralmente dependem de suposições rigorosas: que as matrizes de transição sejam de posto completo (full-rank) e que cada estado possua uma distribuição de observação única para cada ação. Essas suposições falham em muitos cenários do mundo real envolvendo aliasing de estado (onde estados distintos compartilham distribuições de observação idênticas) ou ações que podem falhar probabilisticamente.

Metodologia
Os autores propõem um método que combina decomposição espectral com decomposição tensorial para aprender parâmetros de POMDP sob suposições mais brandas. A abordagem procede em três estágios principais:

Construção da Matriz de Hankel e Aprendizado de PSR:
O método começa construindo uma matriz de Hankel a partir das trajetórias observadas de ação-observação. Esta matriz codifica as verossimilhanças conjuntas de passados e futuros de observações. Ao realizar uma fatoração de posto (via Decomposição de Valores Singulares) nesta matriz, o algoritmo deriva uma Representação de Estado Preditivo (PSR) linear. Isso gera um conjunto de matrizes de atualização linear ( $M_{ao}$ ), um vetor inicial ( $m_0$ ) e um vetor final ( $m_\infty$ ). Esses componentes representam a dinâmica do sistema até uma transformação de similaridade desconhecida $P$ .
Recuperação da Transformação de Similaridade:
Para recuperar as matrizes explícitas de transição ( $T^a$ ) e observação ( $O_{ao}$ ), o algoritmo deve estimar a transformação de similaridade $P$ . Os autores reformulam técnicas de decomposição tensorial para estimar $P$ .

Primeiro, eles marginalizam as observações para obter matrizes de transição até a transformação: $\sum_o M_{ao} = P T^a P^{-1}$ .
Para ações com matrizes de transição de posto completo, eles computam o produto $M_{ao} M_a^{-1} = P O_{ao} P^{-1}$ .
Como as $O_{ao}$ são diagonais, os autovalores desses produtos correspondem às entradas diagonais. Para resolver a ambiguidade causada por autovalores repetidos (que ocorrem quando estados compartilham distribuições de observação), o método emprega uma diagonalização conjunta de uma soma ponderada dessas matrizes. Pesos aleatórios são amostrados para garantir que os autovalores sejam distintamente diferentes quase certamente para estados com distribuições de observação únicas através de todas as ações de posto completo.

Aprendizado até as Partições de Observabilidade:
O artigo introduz o conceito de uma Partição de Observabilidade de Posto Completo. Se múltiplos estados compartilham exatamente a mesma distribuição de observação para todas as ações com transições de posto completo, eles não podem ser distinguidos apenas por dados sequenciais. O algoritmo recupera a transformação de similaridade $P$ até essa partição. Consequentemente, o modelo aprendido fornece matrizes de transição e observação explícitas entre partições de estados, em vez de estados individuais. Para estados dentro de uma única partição, o modelo aprende a dinâmica agregada.

Principais Contribuições

Suposições Relaxadas: O método estende abordagens de decomposição tensorial para aprender POMDPs onde os estados podem sofrer aliasing (compartilhando distribuições de observação) e onde as matrizes de transição não são necessariamente de posto completo para cada ação, desde que o produto das matrizes de avanço e retrocesso seja de posto completo.
Recuperação de Modelo Explícito: Diferente das PSRs, o método recupera matrizes explícitas de transição e observação (até uma partição), permitendo a especificação de novas funções de recompensa e objetivos após a fase inicial de aprendizado sem necessidade de retreinamento.
Limites Teóricos: Os autores provam que aprender a dinâmica de transição e observação além da partição de observabilidade é impossível a partir de uma única trajetória de dados sequenciais. Eles constroem um contraexemplo demonstrando dois POMDPs distintos com dinâmicas internas diferentes que produzem distribuições de observação idênticas para todas as sequências de ações, estabelecendo o limite teórico de identificabilidade.

Resultados Experimentais
Os autores avaliam seu método em diversos domínios, incluindo o domínio "Sense-Float-Reset" (apresentando aliasing de estado), o problema do Tigre e o T-Maze.

Convergência: O método recupera com sucesso os modelos de observação subjacentes e as matrizes de transição ao nível de partição, convergindo para os valores da verdade fundamental (ground truth) conforme o número de interações de exploração aumenta. Em contraste, a Expectativa-Maximização (EM) frequentemente converge para mínimos locais que predizem as observações corretamente, mas resultam em parâmetros de modelo incorretos.
Desempenho de Planejamento: Quando utilizado com um planejador padrão (PO-UCT), os POMDPs aprendidos ao nível de partição alcançam desempenho de planejamento comparável aos modelos de verdade fundamental e às PSRs.
Especificação de Recompensa: Em domínios inéditos de "Noisy Hallway" e "Directional Hallway", os autores demonstram que as verossimilhanças explícitas de transição e observação permitem que um agente seja direcionado para estados latentes específicos (por exemplo, um estado de corredor central com observações ambíguas) ao atribuir recompensas a estados em vez de apenas pares observação-ação. Esta capacidade não está disponível em PSRs padrão ou modelos baseados em EM que falham em recuperar a estrutura de estado correta.

Significância e Alegações
O artigo afirma que seu método preenche a lacuna entre o poder preditivo das PSRs e a interpretabilidade dos modelos explícitos de POMDP. Ao aprender até uma partição de observabilidade, o método captura uma classe mais ampla de sistemas do mundo real (particularmente em manipulação robótica, onde ações podem falhar ou estados podem sofrer aliasing) do que os métodos anteriores baseados em tensores.

Os autores afirmam modestamente que, embora seu método não possa recuperar a estrutura interna exata de estados com aliasing a partir de dados sequenciais, ele recupera a quantidade máxima de informação teoricamente possível. A capacidade de manipular o modelo aprendido para novas tarefas (via especificação explícita de recompensa) é destacada como uma vantagem primária sobre modelos preditivos de caixa-preta. O trabalho sugere que, para muitas aplicações práticas, aprender a dinâmica entre partições de observabilidade é suficiente para um planejamento e raciocínio eficazes.

Mais como este