Reinforcement Learning with Symbolic Reward Machines

Este artigo propõe as Máquinas de Recompensa Simbólicas (SRMs) e seus algoritmos de aprendizado associados, QSRM e LSRM, para superar as limitações de entrada manual das Máquinas de Recompensa tradicionais, permitindo o processamento direto de observações do ambiente através de fórmulas simbólicas enquanto mantém o desempenho superior e a interpretabilidade.

O essencial

Imagine que você está ensinando um robô a fazer um bolo. No mundo tradicional de Inteligência Artificial (Reinforcement Learning), o robô só recebe um "bom trabalho" ou "tente de novo" no final, ou talvez quando queima o bolo. Ele não sabe por que o bolo queimou, nem que precisou bater os ovos antes de colocar na forma. É como tentar adivinhar a receita inteira apenas pelo gosto final.

Para tarefas complexas que exigem uma ordem específica (primeiro coletar madeira, depois colocar na máquina), os cientistas criaram uma ferramenta chamada Reward Machines (Máquinas de Recompensa). Pense nelas como um "manual de instruções" que o robô segue. Mas há um problema: para usar esse manual, você precisa ter um "tradutor" humano que olhe para cada situação e diga ao robô: "Atenção, agora você está na fase de coletar madeira!". Isso é chato, trabalhoso e exige que você reescreva o manual para cada novo ambiente.

É aqui que entra o trabalho de Thomas Krug e Daniel Neider com suas Symbolic Reward Machines (SRMs) - Máquinas de Recompensa Simbólicas.

A Grande Ideia: O Detetive que Lê o Ambiente

Em vez de depender de um tradutor humano para dar etiquetas (como "coletando madeira"), as novas Máquinas Simbólicas são como detetives inteligentes que olham diretamente para o ambiente e entendem a lógica sozinhas.

• O Antigo (RM): Você precisa dizer ao robô: "Se o robô estiver no quadrado X, acenda a luz verde". Você tem que programar essa luz para cada quadrado.
• O Novo (SRM): Você diz ao robô: "Se o robô estiver em uma coordenada onde X é maior que 5 e Y é menor que 10, então acenda a luz verde". O robô olha para os números (o estado do ambiente) e aplica a fórmula mágica. Ele não precisa de um tradutor humano; ele lê a matemática do mundo diretamente.

Como eles aprendem? (QSRM e LSRM)

Os autores criaram dois métodos para ensinar esses robôs:

1. QSRM (O Aluno com o Manual):
   Imagine que você dá o manual de instruções (a Máquina Simbólica) pronto para o robô. O robô usa esse manual para aprender muito mais rápido do que tentaria sozinho. Ele sabe exatamente qual é o próximo passo lógico. O resultado é que ele aprende a tarefa perfeitamente, assim como os métodos antigos, mas sem precisar daquele "tradutor" chato. Ele se adapta a qualquer ambiente padrão que você já tenha.

2. LSRM (O Mestre que Escreve o Próprio Manual):
   Este é o truque de mágica. E se você não tiver o manual? E se não souber quais são as regras?
   O método LSRM faz o robô aprender a tarefa e descobrir as regras do jogo ao mesmo tempo.

   • O robô tenta fazer a tarefa.
   • Se ele erra (recebe uma recompensa diferente do que esperava), ele diz: "Ei, minha teoria sobre como o mundo funciona está errada!".
   • Ele então reescreve o manual (a Máquina Simbólica) para corrigir o erro.
   • Ele repete isso até que o manual esteja perfeito e ele consiga fazer a tarefa com sucesso.

É como se um aluno de culinária, ao tentar fazer um bolo, percebesse que a receita estava errada, riscasse o papel, escrevesse uma nova receita baseada no que aprendeu, e tentasse de novo até o bolo ficar perfeito. No final, ele não só sabe fazer o bolo, mas também te entrega a receita correta escrita por ele mesmo!

Por que isso é incrível?

• Funciona em qualquer lugar: Você pode usar isso nos jogos e ambientes padrão que já existem (como os do Gymnasium), sem precisar reprogramar o ambiente para adicionar "etiquetas" especiais.
• É transparente: Como o robô usa fórmulas matemáticas (como "X > 5"), quando ele aprende, você pode olhar para o manual que ele criou e entender exatamente o que ele aprendeu. Você vê a lógica: "Ah, ele aprendeu que precisa ir para a esquerda antes de ir para a direita".
• Aprendizado de ponta a ponta: O robô começa do zero, sem saber as regras, e termina sabendo tanto a tarefa quanto a lógica por trás dela.

Resumo da Ópera

Os autores criaram uma forma de ensinar robôs a fazer tarefas complexas e sequenciais sem precisar de um humano para programar regras específicas para cada situação. Eles criaram robôs que olham para os números do mundo, entendem as regras lógicas por si mesmos e, se necessário, descobrem essas regras enquanto aprendem a tarefa. É como dar ao robô a capacidade de ler o manual de instruções do universo e, se o manual não existir, escrever o seu próprio enquanto joga.

Resumo técnico

Resumo Técnico: Reinforcement Learning with Symbolic Reward Machines

1. O Problema

O Aprendizado por Reforço (RL) clássico baseia-se em funções de recompensa Markovianas, onde a recompensa depende apenas do estado atual e da ação tomada. No entanto, muitos problemas do mundo real exigem recompensas não-Markovianas, que dependem de históricos de trajetórias (sequências de estados e ações) para definir o sucesso de uma tarefa (ex.: "coletar madeira" antes de "colocar na máquina").

Para lidar com isso, as Máquinas de Recompensa (Reward Machines - RMs) foram propostas. Embora eficazes, as RMs tradicionais possuem limitações críticas:

• Dependência de Funções de Rotulagem (Labeling Functions): Elas exigem que o ambiente emita "eventos de alto nível" (rótulos) derivados de um estado bruto através de uma função de rotulagem manual.
• Barreira de Usabilidade: Criar essas funções de rotulagem requer conhecimento de domínio e esforço manual para cada ambiente e tarefa, impedindo a aplicação "pronta para uso" (out-of-the-box) em frameworks de RL padrão.
• Incompatibilidade com Ambientes Padrão: A maioria dos ambientes de RL (como os do Gymnasium) fornece apenas o estado e a recompensa bruta, não os rótulos necessários para as RMs.

2. Metodologia Proposta

Os autores propõem as Máquinas de Recompensa Simbólicas (Symbolic Reward Machines - SRMs) e dois algoritmos de aprendizado associados: QSRM e LSRM.

A. Máquinas de Recompensa Simbólicas (SRMs)
As SRMs mantêm a estrutura de autômato das RMs, mas eliminam a necessidade de rótulos externos:

• Entrada Direta: Em vez de receber rótulos, as SRMs recebem o estado do ambiente diretamente.
• Guardas Simbólicos: As transições entre estados da máquina são controladas por guardas definidas como fórmulas lógicas (especificamente Aritmética Real Linear - LRA) sobre as variáveis do estado.
• Vantagem: Isso permite que a máquina processe estados brutos (ex.: coordenadas contínuas $x, y$) sem necessidade de uma função de rotulagem intermediária.

B. Algoritmo QSRM (Aprendizado com SRM Dado)

• Funcionamento: Assume que a SRM é fornecida pelo usuário (similar ao QRM, mas adaptado para SRMs).
• Mecanismo: Utiliza uma tabela Q para cada estado da SRM. Realiza atualizações múltiplas (multi-update) acelerando o aprendizado, similar ao QRM.
• Convergência: O artigo prova que o QSRM converge para uma política ótima sob as mesmas condições do Q-Learning clássico, desde que as recompensas sejam limitadas e todos os pares (estado, ação) sejam visitados infinitamente.

C. Algoritmo LSRM (Aprendizado de SRM End-to-End)
Para superar a necessidade de fornecer a SRM manualmente, os autores propõem o LSRM, que infere a estrutura da SRM durante o treinamento. Ele opera em dois modos:

1. LSRM-GF (Given Formulas): O usuário fornece um conjunto de fórmulas candidatas para os guardas. O algoritmo aprende a estrutura da máquina (transições e recompensas) usando esses guardas.
2. LSRM-FT (Formula Templates): O usuário fornece apenas "modelos" de fórmulas (templates) com variáveis livres (ex.: $x \geq b_1 \land x < b_2$). O algoritmo infere tanto a estrutura da SRM quanto os valores concretos das variáveis nos templates.

Mecanismo de Inferência do LSRM:

• O algoritmo inicia com uma hipótese básica de SRM.
• Treina uma política usando QSRM.
• Se a recompensa gerada pela SRM hipotética divergir da recompensa real do ambiente, o episódio é marcado como um contraexemplo.
• O algoritmo codifica os contraexemplos em um Problema de Satisfação de Restrições (CSP) usando um solver SMT (como o Z3) para gerar uma nova SRM que seja consistente com todos os contraexemplos observados.
• O processo se repete até que a SRM aprendida seja consistente e a política ótima seja encontrada.

3. Contribuições Principais

1. Definição de SRMs: Uma nova formalização de máquinas de recompensa que opera diretamente sobre o estado do ambiente via guardas simbólicos, eliminando a necessidade de funções de rotulagem manuais.
2. Algoritmos QSRM e LSRM:
   • QSRM: Garante convergência ótima e compatibilidade com interfaces padrão de RL.
   • LSRM: Permite o aprendizado end-to-end de políticas para recompensas não-Markovianas, inferindo automaticamente a estrutura da recompensa (SRM) a partir da experiência.
3. Interpretabilidade: As SRMs aprendidas fornecem ao usuário uma representação simbólica e interpretável da estrutura da tarefa (passo a passo), revelando a lógica oculta da função de recompensa.
4. Provas de Convergência: Demonstrações teóricas de que os métodos convergem para SRMs quase certamente equivalentes e políticas ótimas (em espaços de estados finitos).

4. Resultados Experimentais

Os métodos foram avaliados em ambientes discretos (Office World) e contínuos (Mountain Car modificado), comparando-se com Q-Learning, DQN, QRM e DQRM.

• Desempenho vs. Baselines: Os métodos baseados em SRM/QSRM superaram significativamente o Q-Learning e o DQN padrão. O DQN, mesmo com pilhas de frames (frame stacks), falhou em aprender tarefas não-Markovianas complexas devido à dificuldade de capturar dependências temporais longas.
• Equivalência QRM vs. QSRM: O QSRM produziu resultados idênticos ao QRM (quando a SRM é dada), confirmando que a remoção da função de rotulagem não prejudica a eficácia, apenas a flexibilidade.
• Eficácia do LSRM:
  • Espaços Finitos: O LSRM aprendeu políticas ótimas e inferiu SRMs quase certamente equivalentes às verdadeiras.
  • Espaços Infinitos: O LSRM alcançou desempenho muito bom (embora não estritamente ótimo devido à aproximação de função), inferindo estruturas de SRM que capturam a lógica essencial da tarefa.
• Interpretabilidade: As SRMs aprendidas visualizaram corretamente as etapas da tarefa (ex.: ir para o escritório esquerdo, depois direito, depois voltar), demonstrando que o algoritmo aprendeu a estrutura sem supervisão explícita.

5. Significado e Impacto

Este trabalho representa um avanço significativo na aplicabilidade do RL para tarefas complexas e sequenciais:

• Democratização do RL Não-Markoviano: Remove a barreira técnica de criar funções de rotulagem, permitindo que agentes aprendam tarefas complexas diretamente em ambientes padrão de RL.
• Transparência: Ao aprender a SRM, o sistema não apenas encontra a política, mas também "explica" como a tarefa deve ser realizada, fornecendo insights valiosos sobre a estrutura de recompensa oculta.
• Escalabilidade: A abordagem simbólica permite lidar com espaços de estados contínuos e infinitos de forma mais eficiente do que métodos baseados puramente em memória de estado (como frames stacks), mantendo a interpretabilidade.

Em suma, as SRMs e o algoritmo LSRM oferecem uma solução robusta para o problema de recompensas não-Markovianas, combinando a eficiência do aprendizado por reforço com a interpretabilidade e a facilidade de integração com ambientes existentes.