Resumo Técnico: Métodos de Gradiente de Política para Aprendizado por Reforço Não-Markoviano

Declaração do Problema

O Aprendizado por Reforço (AR) tradicionalmente depende do framework do Processo de Decisão de Markov (MDP), assumindo que as dinâmicas e as recompensas dependem exclusivamente do estado e da ação atuais. No entanto, muitos ambientes do mundo real — como sistemas parcialmente observáveis, agentes de diálogo, sistemas de recomendação e mercados financeiros — são inerentemente Processos de Decisão Não-Markovianos (NMDPs). Nesses cenários, observações e recompensas dependem de todo o histórico de interação.

Condicionar diretamente as políticas ao histórico completo é computacionalmente intratável, pois o espaço do histórico cresce exponencialmente. Embora abordagens existentes tentem comprimir o histórico, elas frequentemente enfrentam limitações:

• Dinâmicas Fixas: Alguns métodos assumem que as dinâmicas do estado interno do agente são fixas e otimizam apenas a política de controle (por exemplo, Dong et al., 2022).
• Objetivos Preditivos: Outros métodos aprendem representações de estado otimizando objetivos preditivos auxiliares (por exemplo, prever futuras observações), o que pode exigir representações de alta dimensão e não se alinha diretamente com o objetivo final de maximizar a recompensa cumulativa (por exemplo, Subramanian et al., 2022).

Este artigo aborda o desafio de aprender conjuntamente uma representação de estado compacta e uma política de controle em NMDPs, sem depender de dinâmicas fixas ou objetivos preditivos intermediários.

Metodologia

Políticas Agent State-Markov (ASM)

Os autores introduzem uma classe de políticas Agent State-Markov (ASM). Neste framework, o agente mantém um estado interno $S_t$ que é atualizado recursivamente com base no estado anterior, na ação anterior e na observação atual:
$$S_t \sim \nu_t(\cdot \mid S_{t-1}, A_{t-1}, O_t)$$
A política de controle $\phi$ mapeia então o estado atual do agente para uma ação:
$$A_t \sim \phi_t(\cdot \mid S_t)$$
O par $(\nu, \phi)$ constitui a política ASM. Crucialmente, os autores propõem otimizar os parâmetros tanto das dinâmicas de estado $\nu$ quanto da política de controle $\phi$ conjuntamente para maximizar a recompensa cumulativa esperada, em vez de fixar $\nu$ ou aprendê-lo via previsão.

Contribuições Teóricas

O artigo estabelece um Teorema do Gradiente de Política para políticas ASM, estendendo resultados clássicos tanto para NMDPs episódicos quanto para horizonte infinito com desconto.

1. Expressão do Gradiente: Para uma política ASM parametrizada $\pi_\theta$, o gradiente do retorno esperado $J(\theta)$ é derivado como:
   $$\nabla_\theta J(\theta) = \mathbb{E}_{\pi_\theta} \left[ \sum_{t} R_{t:\infty} \nabla_\theta \log \pi_\theta(S_t, A_t \mid S_{t-1}, A_{t-1}, O_t) \right]$$
   onde $R_{t:\infty}$ representa o retorno futuro (recompensa a partir de agora).
2. Fatorização: Devido à estrutura das políticas ASM, o termo de log-probabilidade fatoriza-se nas dinâmicas de estado e na política de controle:
   $$\nabla_\theta \log \pi_\theta = \nabla_\theta \log \nu_\theta + \nabla_\theta \log \phi_\theta$$
   Isso permite a atualização separada, mas simultânea, da representação de estado e da política.
3. Garantias de Convergência: Sob suposições padrão de suavidade e limitação, os autores provam:
   • Convergência em tempo finito: A norma quadrada média do gradiente ao longo do tempo converge a uma taxa de $\tilde{O}(H^{3.5}/\sqrt{K})$ para tarefas episódicas (onde $H$ é o horizonte e $K$ é o número de iterações).
   • Convergência quase certa: Com taxas de aprendizado decrescentes, a norma do gradiente converge para zero quase certamente.
   • Garantias semelhantes são estabelecidas para o cenário de horizonte infinito com desconto, onde o horizonte efetivo é determinado pelo fator de desconto $\gamma$.

Algoritmo: ASMPG

Com base no teorema do gradiente, os autores propõem o algoritmo Agent State-Markov Policy Gradient (ASMPG). É um algoritmo online, no estilo REINFORCE, que:

• Amostra trajetórias usando a política ASM atual.
• Calcula a estimativa do gradiente usando a estrutura recursiva do estado do agente.
• Atualiza os parâmetros tanto da rede de dinâmicas de estado quanto da rede de política usando ascensão de gradiente estocástica.

Resultados Experimentais

Os autores avaliaram o ASMPG em cinco ambientes não-Markovianos:

1. CheeseMaze: Uma tarefa de navegação parcialmente observável com observações ambíguas.
2. HallwayNavigation: Uma tarefa de labirinto determinística onde configurações locais de paredes são ambíguas.
3. HealthcareTreatment: Uma tarefa de planejamento de tratamento com variáveis ocultas de toxicidade e resistência.
4. MachineRepair: Uma tarefa de manutenção com níveis de desgaste ocultos que afetam a degradação da máquina.
5. VelocityOnlyCartPole: Uma tarefa de controle onde apenas a velocidade (não a posição) é observada.

Comparação: O ASMPG foi comparado contra AIS-KL e AIS-MMD (Subramanian et al., 2022), que aprendem representações de estado via objetivos preditivos (Estados de Informação Aproximada).

Descobertas:

• Em todos os cinco ambientes, o ASMPG alcançou recompensas médias mais altas por passo ou por episódio em comparação com as linhas de base preditivas.
• A diferença de desempenho foi particularmente notável em tarefas que exigem memória de longo prazo, como CheeseMaze, MachineRepair e VelocityOnlyCartPole.
• Os resultados sugerem que otimizar diretamente as dinâmicas de estado para o objetivo de recompensa é mais eficaz do que otimizar para suficiência preditiva.

Significado e Alegações

O artigo alega que sua contribuição principal é uma formulação centrada na recompensa para AR não-Markoviano. Ao tratar as dinâmicas do estado do agente como um componente aprendível otimizado conjuntamente com a política de controle, o método contorna a necessidade de objetivos preditivos auxiliares ou representações de estado fixas.

As principais alegações incluem:

• Validade Teórica: A derivação de um teorema do gradiente de política para NMDPs gerais fornece uma base rigorosa para otimização conjunta, estendendo resultados clássicos de MDP.
• Eficácia Prática: Resultados empíricos demonstram que a otimização conjunta centrada na recompensa supera métodos que dependem de representações de estado preditivas, mesmo quando os tamanhos das representações são comparáveis.
• Condições de Optimalidade: O artigo observa que, se existirem dinâmicas de estado de agente "ideais" (aquelas que são estatísticas suficientes para recompensas e futuras observações), restringir a busca a políticas ASM não acarreta perda de optimalidade.

Os autores reconhecem que o método proposto depende de estimadores do tipo REINFORCE, que podem sofrer com alta variância. Eles identificam o desenvolvimento de variantes ator-crítico para políticas ASM como uma direção natural para trabalhos futuros, a fim de reduzir a variância enquanto preserva o objetivo centrado na recompensa.