Answer-Set-Programming-based Abstractions for Reinforcement Learning

Problema
O Aprendizado por Reforço (RL - Reinforcement Learning) permite que agentes aprendam políticas por meio da interação, mas aplicações realistas frequentemente sofrem com espaços de estados e ações enormes, tornando abordagens de aprendizado ingênuas intratáveis. Embora métodos de aproximação como o Deep Q-Learning ofereçam generalização, eles frequentemente exigem vastas quantidades de dados de treinamento e podem exibir instabilidade. O Aprendizado por Reforço Relacional (RRL) aborda essas limitações utilizando lógica de primeira ordem para raciocinar sobre objetos e suas relações, facilitando a generalização entre estados similares. Especificamente, o framework CARCASS (Compact Abstraction using Relational Conjunctions for Aggregation of State-action Spaces) por van Otterlo (2004) modela Processos de Decisão de Markov (MDPs) usando abstrações lógicas. No entanto, a implementação original do CARCASS baseia-se em Prolog e resolução SLDNF, que, embora declarativo em princípio, frequentemente necessita de recursos procedurais (como ordenação de regras ou cuts) para eficiência e carece de suporte nativo para inferência não monotônica, otimização e tratamento de preferências.

Metodologia
Os autores propõem um método geral para reimplementar o framework CARCASS usando Programação de Conjuntos de Respostas (ASP - Answer-Set Programming). O ASP é uma linguagem de representação de conhecimento baseada em lógica totalmente declarativa que suporta raciocínio não monotônico, otimização e restrições.

1. Codificação ASP do CARCASS: Os autores definem uma função de rotulagem para mapear estados abstratos e pares estado-ação para termos fundamentais (ground terms). Eles constroem uma codificação modular composta por:

   • Programas ($P_{\hat{s}_i}$) que codificam estados abstratos individuais como regras onde o corpo consiste nos literais que definem o estado abstrato.
   • Programas ($P_{\hat{s}_i, \hat{a}_{i,j}}$) que codificam a relação de cobertura para pares estado-ação abstratos, ligando ações concretas a abstratas via átomos aCov.
   • Um mecanismo de lista de decisão ($P_{\hat{C}}$) usando uma regra de escolha para selecionar exatamente um estado de cobertura por estado concreto e uma restrição para garantir que a seleção siga a lista ordenada (priorizando o menor índice).
   • Um estado abstrato "vazio" ($\hat{s}_\infty$) com o maior índice que cobre todos os estados não cobertos por regras específicas, garantindo um fallback padrão.

2. Integração de Aprendizado Online: Os autores integram esta codificação em um loop de Q-learning online (Algoritmo 2). Para um dado estado concreto, o solver ASP computa um conjunto de respostas ótimo para determinar o estado abstrato de cobertura e o conjunto de ações abstratas admissíveis. O agente então seleciona uma ação concreta do conjunto coberto pela ação abstrata escolhida e atualiza o valor Q do par estado-ação abstrato.

3. Conhecimento de Base: O framework permite a inclusão de conhecimento de base ($P_B$) para inferir propriedades complexas (ex: busca de caminho, completude de torre) diretamente dentro do processo de abstração, em vez de exigir que sejam pré-computadas ou implementadas proceduralmente.

Principais Contribuições

1. Método de Codificação Geral: O artigo introduz um método sistemático para codificar abstrações CARCASS em ASP, demonstrando como uma linguagem totalmente declarativa pode realizar abstrações relacionais de estado-ação.
2. Adaptação de Aprendizado Online: Os autores mostram como utilizar abstrações CARCASS baseadas em ASP dentro de um cenário de Q-learning online, lidando com a seleção dinâmica de estados e ações abstratas.
3. Avaliação Empírica: A implementação é avaliada em dois domínios distintos:
   • Blocks World: Uma tarefa de empilhamento de $n$-blocos onde a abstração reduz o espaço estado-ação para um tamanho constante, independentemente de $n$.
   • MiniGrid: Uma suíte de tarefas de navegação em mundo de grade (ex: Door Key, Multi Room) onde o conhecimento de base é usado para inferir layouts de salas e caminhos mais curtos, construindo estados abstratos baseados no próximo nó no caminho.

Resultados
A avaliação empírica compara o Q-learning abstrato contra o Q-learning concreto em um mundo de 20 blocos e três ambientes MiniGrid.

• Estabilidade: O Q-learning abstrato demonstrou estabilidade consistente, com retornos medianos e intervalos interquartis permanecendo altos após o aprendizado inicial, enquanto o Q-learning concreto exibiu flutuações significativas ou falha de convergência em ambientes complexos.
• Qualidade: O Q-learning abstrato alcançou altas taxas de sucesso (ex: próximo a 100% nos últimos 500 episódios para tarefas MiniGrid), superando significativamente o Q-learning concreto, que frequentemente falhou em atingir retornos positivos no mesmo período de tempo.
• Eficiência de Amostra: A abordagem abstrata exigiu significativamente menos episódios para aprender políticas de alta qualidade comparado à abordagem concreta. Por exemplo, no mundo de 20 blocos, o aprendizado abstrato alcançou retornos medianos positivos pelo episódio 376, enquanto o aprendizado concreto permaneceu no retorno negativo basal.
• Diferenças de Modelagem: No estudo de caso MiniGrid, a codificação ASP permitiu uma especificação compacta e declarativa de busca de caminho e restrições, enquanto a implementação equivalente em Prolog exigiu busca algorítmica explícita (busca em largura), destacando a vantagem do ASP em separar a especificação do problema da lógica de controle.

Significância e Alegações
O artigo conclui que o CARCASS implementado com ASP fornece uma abordagem promissora para construir abstrações em RL, particularmente quando o conhecimento do domínio está disponível. Os autores alegam que as abstrações baseadas em ASP oferecem uma alternativa flexível ao CARCASS baseado em Prolog ao suportar:

• Generalização: Através de representações relacionais.
• Restrições de Ação: Via restrições declarativas.
• Decomposição de Problemas: Ao codificar padrões de raciocínio complexos (como busca de caminho ou análise de torre) diretamente nas regras.
• Raciocínio Avançado: Incluindo inferência não monotônica, otimização e raciocínio sob conhecimento incompleto.

Os autores observam modestamente que, embora as políticas aprendidas sejam de qualidade aceitável e aprendidas com menos amostras, não há garantia de convergência para uma política ótima em geral, e a própria abstração pode não preservar a política ótima para problemas de planejamento NP-difíceis (como visto no caso Blocks World, onde a abstração troca a otimalidade pela tratabilidade). O trabalho posiciona-se como um passo em direção a frameworks orientados pelo conhecimento para RL relacional que suportam aprendizado de política tolerante à elaboração.