Resumo Técnico: Gradiente de Política Natural como Iteração de Política Duplamente Suavizada

Declaração do Problema

Problemas de Aprendizado por Reforço (AR) são tipicamente modelados como Processos de Decisão de Markov (MDPs). Enquanto métodos clássicos de programação dinâmica, como Iteração de Política (PI) e Iteração de Valor (VI), dependem das propriedades de contração e monotonicidade do operador de Bellman, métodos modernos baseados em gradiente, como Gradiente de Política Natural (NPG) e Média Dual de Política (PDA), são frequentemente analisados através da lente da otimização contínua sobre o espaço de políticas.

Existe uma lacuna conceitual na literatura: análises do NPG frequentemente falham em aproveitar a contração fundamental na norma $\ell_\infty$ do operador de Bellman, que sustenta as garantias de convergência forte dos métodos clássicos. Consequentemente, os resultados teóricos existentes para o NPG frequentemente sofrem de uma ou mais limitações:

1. Falta de convergência geométrica global.
2. Dependência de distribuições de estado inicial ou coeficientes de concentrabilidade.
3. Necessidade de regularização adicional do MDP ou do algoritmo para induzir curvatura.
4. Dependência de tamanhos de passo adaptativos e dependentes da trajetória.

O artigo visa preencher essa lacuna fornecendo um quadro unificado que conecta a PI clássica com métodos modernos baseados em gradiente, permitindo uma análise de convergência geométrica livre de distribuições, sem modificar o MDP ou exigir passos adaptativos.

Metodologia: Iteração de Política Duplamente Suavizada (DSPI)

Os autores introduzem a Iteração de Política Duplamente Suavizada (DSPI), um quadro algorítmico unificado formulado como um quadro de operador de Bellman. A DSPI atualiza a política por meio de uma etapa gananciosa regularizada aplicada a uma média ponderada das funções Q passadas.

O núcleo da DSPI envolve dois níveis de suavização:

1. Suavização por Média: Em vez de usar apenas a função Q mais recente, o algoritmo mantém uma média em execução ($\bar{Q}_k$) de todas as funções Q passadas.
2. Suavização por Regularização: A atualização da política gananciosa é substituída por uma etapa regularizada (por exemplo, softmax) envolvendo uma função côncava $\nu(\cdot)$ (como entropia).

A regra de atualização é definida como:
$$\pi_{k+1}(s) \in \arg\max_{\mu \in \Delta(A)} \left\{ \mu^\top \bar{Q}_{k+1}(s) + \eta_k \nu(\mu) \right\}$$
onde $\bar{Q}_{k+1} = (1-\beta_k)\bar{Q}_k + \beta_k Q_{\pi_k}$, e o parâmetro de suavização $\eta_k$ decai geometricamente com base nos tamanhos de passo $\beta_k$.

Crucialmente, os autores demonstram que a DSPI admite uma formulação compacta usando operadores de Bellman suavizados ($H_\eta$ e $H^\pi_\eta$). Isso permite que o algoritmo seja analisado usando as propriedades de monotonicidade e contração desses operadores, em vez de depender exclusivamente de ferramentas teóricas de otimização.

Contribuições Principais

1. Unificação de Algoritmos

O artigo estabelece que a DSPI é um quadro geral que abrange vários algoritmos principais como casos especiais:

• Iteração de Política (PI): Recuperada quando o tamanho de passo $\beta_k \equiv 1$ (sem média) e a regularização desaparece.
• Gradiente de Política Natural (NPG): Recuperado definindo $\nu(\cdot)$ como a entropia de Shannon e escolhendo cronogramas de tamanho de passo específicos.
• Média Dual de Política (PDA): Recuperado escolhendo $\nu(\cdot)$ como uma função geradora de divergência negativa deslocada.
• Iteração de Política com Média Dual: Uma nova variante onde a política é atualizada gananciosamente com base nas funções Q médias ($\nu(\cdot) \equiv 0$).

2. Análise de Convergência Unificada

Ao aproveitar as propriedades dos operadores de Bellman suavizados, os autores fornecem uma análise de convergência unificada para a DSPI:

• Convergência Assintótica: Provada para qualquer sequência de tamanho de passo não somável.
• Convergência Geométrica Global: Provada para tamanhos de passo constantes. O limite de erro é dado por:
  $$\|V^* - V^{\pi_k}\|_\infty \leq (1 - (1-\gamma)\beta)^{k-1} (\gamma \|V^* - V^{\pi_0}\|_\infty + \tau \nu_{\max})$$
  onde $\gamma$ é o fator de desconto e $\beta$ é o tamanho de passo constante.

3. Garantias Teóricas Aprimoradas para NPG e PDA

A aplicação do quadro DSPI ao NPG e PDA produz os seguintes resultados, que superam ou igualam o estado da arte sem exigir pressupostos restritivos:

• Livre de Distribuição: Os limites de convergência dependem apenas da norma $\ell_\infty$ da lacuna da função valor, e não da distribuição de estado inicial ou coeficientes de concentrabilidade.
• Sem Regularização Adicional: A análise vale sem modificar o MDP ou adicionar regularizadores extras além do termo de entropia inerente ao NPG padrão.
• Tamanhos de Passo Simples: Os resultados valem para um cronograma de tamanho de passo pré-especificado e geometricamente crescente simples ($\alpha_k = \beta \alpha_0 / (1-\beta)^k$), eliminando a necessidade de tamanhos de passo adaptativos que dependem da trajetória da política ou do erro de Bellman.
• Complexidade de Iteração: NPG e PDA alcançam uma política $\epsilon$-ótima em $O((1-\gamma)^{-1} \log((1-\gamma)^{-1}\epsilon^{-1}))$ iterações.

4. Término Finito da PI com Média Dual

Para o caso não regularizado (PI com Média Dual), os autores provam término finito. O algoritmo encontra uma política ótima em no máximo $O(mn(1-\gamma)^{-1} \log((1-\gamma)^{-1}))$ iterações, onde $n$ e $m$ são os tamanhos dos espaços de estado e ação. Isso é alcançado mostrando que o algoritmo elimina pelo menos uma ação subótima a cada $k^*$ iterações.

5. Extensões

O quadro é mostrado para se estender naturalmente a:

• Aproximação Linear de Função: A DSPI com aproximação linear de função alcança convergência geométrica até um termo de erro de aproximação de função.
• Problemas de Caminho Mais Curto Estocástico (SSP): A análise estende-se a problemas SSP sem desconto, estabelecendo convergência geométrica global livre de distribuições sob a suposição de que todas as políticas estacionárias são próprias.

Resultados e Significado

O artigo afirma que seu significado principal reside em fornecer uma perspectiva unificada que conecta a programação dinâmica clássica com o AR moderno baseado em gradiente. Ao interpretar NPG e PDA como variantes suavizadas e com média da Iteração de Política, os autores conseguem:

1. Recuperar Garantias Fortes: Estabelecer convergência geométrica global para NPG e PDA usando apenas as propriedades intrínsecas do operador de Bellman (monotonicidade e contração).
2. Remover Artefatos: Eliminar a necessidade de regularização "indutora de curvatura" ou tamanhos de passo adaptativos frequentemente exigidos em análises anteriores baseadas em otimização.
3. Simplificar a Análise: Fornecer uma análise mais simples e principista que evita as complexidades dos coeficientes de desajuste de distribuição.

Os autores observam que, embora sua análise atual assuma acesso a funções Q exatas (isolando a dinâmica de melhoria de política), o quadro prepara o terreno para trabalhos futuros em configurações livres de modelo, onde as funções Q devem ser estimadas. Eles identificam a combinação da DSPI com garantias de avaliação de política de tempo finito como um próximo passo não trivial para alcançar resultados agudos de complexidade de amostra para AR livre de modelo.