Active Reward Machine Inference From Raw State Trajectories

Título: Inference Ativa de Máquinas de Recompensa a partir de Trajetórias de Estado Brutas

1. Problema e Motivação

O artigo aborda o desafio de aprender Máquinas de Recompensa (Reward Machines - RMs) diretamente a partir de trajetórias de estados brutos, sem acesso a recompensas, rótulos (labels) ou nós da máquina.

• Contexto: Tarefas multi-etapa em robótica frequentemente exigem memória para sequenciar sub-tarefas. RMs são autômatos que capturam essa estrutura lógica, mapeando eventos de alto nível para transições de estado.
• Limitação Atual: A maioria dos métodos existentes assume que uma função de rotulagem (que mapeia estados de baixo nível para proposições atômicas) é conhecida ou que rótulos/recompensas são observáveis.
• O Desafio: O problema proposto é mal-posto (ill-posed) e com escassez de informação: aprender tanto a estrutura da RM (transições) quanto a função de rotulagem apenas observando a política de um agente (comportamento) e os estados visitados, sem saber quais estados correspondem a quais eventos lógicos ou quais recompensas foram atribuídas.

2. Metodologia

Os autores propõem uma abordagem baseada em Satisfaibilidade Booleana (SAT) combinada com Aprendizado Ativo.

A. Formulação do Problema:

• Definição de Equivalência de Política: Duas RMs rotuladas são consideradas equivalentes se induzirem a mesma política de histórico ($\pi_h$). O objetivo é encontrar uma RM mínima (com o menor número de nós) que seja politicamente equivalente à verdadeira.
• Profundidade Suficiente ($l^*$): O artigo prova teoricamente que existe uma profundidade de trajetória $l^* = |S| \cdot u_{max}^2$ (onde $|S|$ é o número de estados do MDP e $u_{max}$ é o limite superior de nós da RM) tal que, conhecendo a política de histórico restrita a essa profundidade, é possível recuperar uma RM equivalente.

B. Algoritmo de Aprendizado (Passo 1 - Formulação SAT):

• O problema é codificado como um problema de SAT para inferir a função de transição da RM ($\delta_u$) e a função de rotulagem ($L$).
• Exemplos Negativos: A chave da formulação são "exemplos negativos": pares de trajetórias de estados ($\tau, \tau'$) que levam a ações diferentes na mesma estado final ($\pi_h(a|s, \tau) \neq \pi_h(a|s, \tau')$). Isso implica que as trajetórias devem ter levado a nós diferentes na RM.
• O solver SAT busca funções $\delta_u$ e $L$ que satisfaçam todas as restrições impostas pelos exemplos negativos observados.

C. Extensão Ativa (Passo 2 - Otimização):

• Gargalo: Enumerar todas as trajetórias possíveis até a profundidade $l^*$ é computacionalmente proibitivo (crescimento exponencial).
• Estratégia Ativa: Em vez de usar todas as trajetórias, o algoritmo seleciona ativamente quais pares de trajetórias estender para consultar a política de histórico.
• Métrica de Qualidade: O algoritmo busca pares de trajetórias que "bissectem" o conjunto de soluções candidatas (ou seja, onde metade das RMs candidatas prevêem a mesma transição e a outra metade prevê transições diferentes).
• Algoritmo:
  1. Inicia com uma profundidade de "burn-in" (ex: $l=3$ ou $6$).
  2. Gera candidatos de pares de trajetórias que dividem o espaço de hipóteses.
  3. Consulta a política de histórico para verificar se são exemplos negativos reais.
  4. Adiciona novos exemplos negativos ao problema SAT e resolve incrementalmente.
  5. Repete até convergir para uma única solução (considerando renomeação).

3. Contribuições Principais

1. Inferência sem Rótulos: É a primeira estrutura capaz de aprender tanto a função de rotulagem quanto a máquina de recompensa a partir de trajetórias de estado brutas, eliminando a necessidade de conhecimento simbólico prévio ou detectores de eventos.
2. Condição de Profundidade Suficiente: Estabelecimento teórico de que uma profundidade finita de trajetória é suficiente para garantir a recuperabilidade da RM.
3. Algoritmo de Extensão Ativa: Desenvolvimento de um método que reduz drasticamente a complexidade de memória e computação ao evitar a enumeração exaustiva de trajetórias, focando apenas nas informações que reduzem o espaço de hipóteses.
4. Validação Empírica: Demonstração em ambientes de grade (Grid World) com tarefas complexas (coleta e entrega, patrulha sequencial).

4. Resultados Experimentais

Os experimentos foram realizados em dois cenários: pick_n_drop (coleta e entrega) e patrolABCD (patrulha em ordem).

• Recuperação da Solução: O algoritmo recuperou com sucesso a RM de verdade (até renomeação de nós e rótulos) em 100% das tentativas para o primeiro tarefa e 96,6% para a segunda, usando profundidades menores que a exaustiva.
• Eficiência de Memória:
  • A abordagem exaustiva (full depth) atingiu um gargalo de memória de 24,76 GB para armazenar 414 milhões de exemplos negativos na profundidade 9.
  • A abordagem ativa, na profundidade 13, utilizou apenas 0,147 GB, reduzindo a necessidade de memória em duas ordens de magnitude.
• Eficiência Computacional:
  • O tempo total de execução da abordagem ativa foi de 3544 segundos, quase 2x mais rápido que a abordagem exaustiva (7185 segundos), que ficou presa resolvendo problemas SAT massivos.
  • A abordagem ativa conseguiu escalar para profundidades maiores (até 13) onde a abordagem exaustiva falhou ou se tornou inviável.

5. Significado e Conclusão

O trabalho estabelece um marco fundamental para a Inversão de Aprendizado por Reforço (IRL) em tarefas multi-etapa.

• Viabilidade: Demonstra que é possível inferir a estrutura lógica de tarefas complexas e a semântica dos estados apenas observando o comportamento de um agente, sem supervisão humana sobre o que é "importante" (rótulos).
• Escalabilidade: A estratégia de aprendizado ativo resolve o problema da explosão combinatória de trajetórias, tornando a inferência de RMs viável para domínios mais complexos.
• Futuro: Os autores sugerem que o próximo passo é lidar com espaços contínuos, estimar a política de histórico a partir de dados finitos e ruídos, e integrar testes de equivalência de política para encerrar o aprendizado antes da profundidade teórica máxima.

Em resumo, o paper oferece uma solução robusta e eficiente para "descobrir" a lógica oculta de tarefas robóticas complexas a partir de dados brutos, superando as limitações de métodos anteriores que dependiam de conhecimento prévio sobre o ambiente.