Resumo Técnico: A Representação Terminal em Aprendizado por Reforço

Declaração do Problema

No Aprendizado por Reforço (RL), o aprendizado de representação é crítico para a abstração espaço-temporal. Duas abordagens estabelecidas são a Representação de Sucessor (SR) e a Representação Padrão (DR). A SR codifica estados com base em trajetórias de visitação futuras, capturando a dinâmica de transição independentemente das recompensas. A DR estende isso ao ponderar essas trajetórias com recompensas, integrando assim a estrutura de atribuição de crédito.

No entanto, ambas as representações enfrentam limitações quando aplicadas a tarefas subsequentes, como descoberta de opções, modelagem de recompensa (reward shaping) e transferência de aprendizado:

1. Sobrecarga Computacional: Utilizar a DR ou a SR para essas tarefas normalmente requer decomposição em autovalores (ou iteração de potência) para extrair autovetores. Isso impõe um custo computacional de $O((S^+)^2)$ ou superior por consulta e assume dinâmicas de transição simétricas (reversíveis), uma condição frequentemente violada em ambientes práticos de RL onde as políticas são direcionais.
2. Dimensionalidade: A SR e a DR são definidas sobre o espaço de estados completo ($S^+ \times S^+$), que pode ser grande e ineficiente para armazenar e aprender.
3. Conhecimento Indireto: Embora a DR codifique trajetórias ponderadas por recompensa, ela não isola explicitamente a alcançabilidade e a desejabilidade dos estados terminais em um formato diretamente utilizável sem análise espectral adicional.

Metodologia: A Representação Terminal (TR)

Os autores propõem a Representação Terminal (TR), uma formulação estruturalmente distinta projetada para codificar trajetórias ponderadas por recompensa especificamente em relação aos estados terminais.

Fundamentação Teórica

A TR é derivada dentro do framework de Processos de Decisão de Markov Linearmente Solúveis (LMDPs). Em um LMDP, a função de valor ótima $v(s)$ pode ser transformada em um valor exponencial $z(s) = e^{v(s)/\lambda}$, satisfazendo a equação linear:
$$z(s) = e^{R(s)/\lambda} \sum_{s'} P_\mu(s'|s)z(s')$$
onde $P_\mu$ é uma política padrão e $\lambda$ é um parâmetro de temperatura.

Ao decompor o espaço de estados em estados não-terminais ($S$) e estados terminais ($T$), os autores derivam a matriz TR $M$ como:
$$M = (I_S - D_S)^{-1} D_T$$
onde $D_S = R_S P_S$ representa a dinâmica não-terminal e $D_T = R_S P_T$ representa as transições de não-terminais para terminais. Aqui, $R_S$ e $R_T$ são matrizes diagonais de recompensas exponencializadas.

A TR permite a recuperação zero-shot dos valores exponencializados ótimos $z$ para qualquer configuração de recompensas terminais $y$ (onde $y(\tau) = e^{R(\tau)/\lambda}$) via a relação linear:
$$z = M y$$

Algoritmos de Aprendizado

O artigo estabelece a convergência de dois algoritmos de aprendizado para $M$:

1. Programação Dinâmica (Baseada em Modelo): Uma regra de atualização iterativa $M_{k+1} = D_T + D_S M_k$ é provada para convergir para a verdadeira TR.
2. Baseado em Amostras (Sem Modelo): Uma regra de atualização do tipo diferença temporal (TD) é derivada para aprendizado online:
   $$\hat{M}(s_t) \leftarrow (1 - \alpha_t)\hat{M}(s_t) + \alpha_t e^{r_t/\lambda} \hat{M}^+(s_{t+1})$$
   onde $\hat{M}^+$ é um mapeamento estendido que lida com transições para estados terminais. O Teorema 4.2 prova que isso converge para $M$ sob condições padrão de aproximação estocástica.

Principais Propriedades Teóricas

• Dimensionalidade: A TR é uma matriz $S \times T$. Como o número de estados terminais $T$ é frequentemente muito menor que o espaço de estados total $S^+$, a TR é significativamente mais compacta que a DR $S^+ \times S^+$.
• Usabilidade Direta (Sem Decomposição em Autovalores): As colunas da TR correspondem diretamente à informação tipicamente extraída via autovetores da DR. O Teorema 7.1 demonstra que o autovetor principal da DR é estruturalmente composto por uma coluna da TR (especificamente a coluna correspondente ao estado terminal mais desejável) e uma série geométrica. Assim, a TR captura o mesmo conhecimento estrutural subjacente sem exigir decomposição em autovalores.
• Tratamento de Assimetria: Ao contrário das abordagens baseadas em autovetores que dependem da reversibilidade das dinâmicas de transição (simetria) para garantir autovalores reais, a TR é inerentemente assimétrica e bem definida sob dinâmicas arbitrárias e não reversíveis.
• Composicionalidade: A TR suporta composicionalidade zero-shot. Se uma nova tarefa é uma combinação linear de tarefas base com diferentes recompensas terminais, a função de valor ótima pode ser recuperada combinando linearmente as colunas correspondentes da TR, evitando a necessidade de reaprender as funções de valor base.
• Equivalência de Recompensa: Os autores provam que LMDPs com recompensas dependentes de transição ou de estado-ação podem ser mapeados para LMDPs equivalentes com recompensas dependentes de estado, garantindo que a teoria da TR se aplique amplamente a diferentes formulações de recompensa.

Resultados Experimentais

Os autores avaliam a TR contra a SR e a DR através de quatro aplicações subsequentes em ambientes de grid-world (Four Rooms, RiverSwim, SixArms):

1. Descoberta de Opções: Na tarefa de "cobertura de eigenopções", a TR é usada para gerar opções (evitando o cálculo de autovetores). Variantes usando a coluna do estado terminal de maior recompensa ou todas as colunas alcançaram desempenho competitivo com os métodos RACE (baseado em DR) e CEO (baseado em SR), muitas vezes atingindo recompensas médias mais altas ao empurrar os agentes diretamente para os objetivos desejáveis.
2. Modelagem de Recompensa (Reward Shaping): Usar a TR para construir recompensas de potencial baseadas em forma ($\hat{r}_t = 1 - M(s_{t+1}, \tau)$) resultou em desempenho idêntico ao da DR e superior ao da SR. Isso confirma a capacidade da TR de capturar a informação estrutural necessária para navegação eficiente sem decomposição em autovalores.
3. Exploração Baseada em Contagem: Usar a norma da TR como um bônus de exploração nos ambientes RiverSwim e SixArms resultou em desempenho quase idêntico ao da DR e significativamente melhor que o da SR.
4. Transferência de Aprendizado: Quando as recompensas terminais mudaram entre as tarefas, a TR foi usada para transferir conhecimento. Ela teve desempenho semelhante ao de Default Features (DF) (a variante da DR independente de política) e superou as Successor Features (SF) em várias configurações de política base, alcançando isso sem um passo explícito de aprendizado de características.

Significância e Alegações

O artigo afirma que a Representação Terminal oferece uma alternativa viável e computacionalmente eficiente para a SR e a DR. Sua principal significância reside em:

• Eficiência: Reduz a dimensionalidade da representação e elimina a necessidade de decomposição em autovalores dispendiosa, reduzindo a complexidade de consulta de $O((S^+)^2)$ para $O(1)$ para extração de coluna.
• Robustez: Funciona corretamente sob dinâmicas de transição não simétricas (não reversíveis), um cenário comum em RL onde métodos de autovetores podem falhar ou gerar autovalores complexos.
• Aplicabilidade Direta: Codifica o conhecimento do estado terminal explicitamente, permitindo o uso direto em modelagem de recompensa, descoberta de opções e transferência de aprendizado sem análise espectral intermediária.

Os autores mantêm uma postura modesta, observando que, embora a TR seja competitiva com a DR, ela não é fundamentalmente superior em todos os aspectos semânticos; em vez disso, fornece um mecanismo mais compacto e computacionalmente tratável para acessar o mesmo conhecimento estrutural subjacente em relação aos estados terminais. Sugere-se que trabalhos futuros estendam a TR para ambientes de alta dimensão via aproximação de função e lidem com configurações sem estados terminais explicitamente definidos.