Resumo Técnico: O Reuso de Trajetórias em Gradientes de Política Permite uma Convergência Rápida

Declaração do Problema

Métodos de Gradiente de Política (PG) são eficazes para problemas de controle contínuo, mas sofrem de baixa eficiência de amostragem. Algoritmos de PG "vanilla" padrão (ex: REINFORCE, GPOMDP) dependem exclusivamente de dados on-policy frescos, exigindo $O(\epsilon^{-2})$ trajetórias para atingir um ponto estacionário $\epsilon$-aproximado. Esta ineficiência decorre da alta variância das estimativas de gradiente, que não desaparece porque os gradientes são sempre estimados a partir de novas amostras.

Embora o reuso de dados passados (trajetórias off-policy ou gradientes) seja uma estratégia comum para melhorar a eficiência, o trabalho teórico existente concentrou-se amplamente no reuso de gradientes (ex: SVRPG, SRVRPG, STORM-PG), alcançando taxas de até $O(\epsilon^{-3/2})$. O reuso de trajetórias passadas, embora intuitivo, permaneceu amplamente inexplorado de uma perspectiva teórica rigorosa. Tentativas anteriores de reuso de trajetórias careciam de garantias de convergência ou dependiam de suposições fortes e estimadores complexos (ex: exigindo o armazenamento de todas as políticas passadas ou sofrendo de alta variância devido à ponderação de importância ingênua).

A questão central abordada é: O reuso de trajetórias off-policy passadas pode levar a melhorias comprováveis na complexidade de amostragem dos métodos de PG?

Metodologia

O Algoritmo RT-PG

Os autores propõem o RT-PG (Reusing Trajectories – Policy Gradient), um novo algoritmo que estima o gradiente da política aproveitando trajetórias coletadas nas últimas $\omega$ iterações. A inovação central é o estimador de Média de Potência Múltipla (MPM), que combina dados on-policy e off-policy usando um esquema de Ponderação de Importância Múltipla (MIW) corrigido.

O Estimador MPM

Para abordar os desafios estatísticos do reuso de dados (especificamente o viés introduzido pela dependência entre os parâmetros da política atual e as trajetórias passadas), o estimador MPM emprega dois mecanismos principais:

1. Coeficientes Determinísticos: Ao contrário do Balance Heuristic (BH), que utiliza coeficientes dependentes de todas as políticas passadas (introduzindo "viés de tempo cruzado"), o RT-PG utiliza coeficientes determinísticos $\alpha_{i,k}$ que dependem apenas da contagem de iterações e do índice da janela. Isso elimina o viés de tempo cruzado.
2. Correção de Média de Potência (PM): Para garantir que os pesos de importância permaneçam limitados (uma propriedade "defensiva") e para controlar o viés introduzido pelos coeficientes determinísticos, o estimador aplica uma correção de PM aos pesos de importância vanilla. O peso corrigido para uma trajetória $\tau$ coletada sob a política $\pi_{\theta_i}$ e avaliada sob $\pi_{\theta_k}$ é:
   $$\left( (1 - \lambda_{i,k}) \frac{p_{\theta_i}(\tau)}{p_{\theta_k}(\tau)} + \lambda_{i,k} \right)^{-1}$$
   onde $\lambda_{i,k} \in [0, 1]$ é um parâmetro de correção. Este termo representa uma média harmônica entre o peso vanilla e 1, garantindo que o peso seja limitado por $1/\lambda_{i,k}$.

Análise Teórica

Os autores fornecem uma análise de tempo finito rigorosa para o estimador MPM:

• Limites de Concentração: Eles derivam limites de concentração de alta probabilidade para o estimador usando a desigualdade de Freedman para martingales e um argumento de cobertura para lidar com a natureza vetorial do gradiente.
• Controle de Viés: A análise separa e controla explicitamente duas fontes de viés:
  • Viés de Alvo (Target Bias): Decorrente do fato de o parâmetro alvo $\theta_k$ depender do histórico de trajetórias. Isso é controlado via um argumento de cobertura sobre um subconjunto do espaço de parâmetros contendo o alvo dependente do histórico.
  • Viés de PM: Decorrente do termo de correção de PM. Isso é gerenciado pela seleção cuidadosa de $\lambda_{i,k}$ baseada no tamanho do lote e no limite de divergência $\chi^2$ entre as distribuições de trajetórias.

Principais Contribuições

1. Primeira Evidência Rigorosa: O artigo fornece a primeira prova teórica de que o reuso de trajetórias off-policy passadas pode acelerar significativamente a convergência de PG.
2. Novo Estimador (MPM): Introdução do estimador MPM, que mistura efetivamente dados on-policy frescos com trajetórias off-policy das últimas $\omega$ iterações, mantendo pesos de importância limitados e eliminando o viés de tempo cruzado.
3. Complexidade de Amostragem Melhorada:
   • Reuso Parcial: Quando se reusam trajetórias das últimas $\omega$ iterações (onde $\omega < K$), o RT-PG atinge uma complexidade de amostragem de $\tilde{O}(\epsilon^{-2}\omega^{-1})$.
   • Reuso Total: Quando se reusam todas as trajetórias passadas disponíveis (onde $\omega \ge K$), o algoritmo atinge uma complexidade de amostragem de $\tilde{O}(\epsilon^{-1})$. Isso iguala as melhores taxas conhecidas na literatura para métodos de PG e representa uma melhoria significativa em relação à taxa padrão de $O(\epsilon^{-2})$.
4. Implementação Prática: Uma variante prática do RT-PG é proposta que pondera adaptativamente os dados off-policy com base em estimativas empíricas de dissimilaridade de política (divergência), removendo a necessidade do limite global teórico $D$ na prática.

Resultados

Resultados Teóricos

Sob suposições padrão (divergência $\chi^2$ limitada entre distribuições de trajetórias e regularidade da classe de política), os autores provam que o RT-PG encontra um ponto estacionário $\epsilon$-aproximado com:

• Complexidade de amostragem de $\tilde{O}(\epsilon^{-1})$ no regime de reuso total.
• Complexidade de amostragem de $\tilde{O}(\epsilon^{-2}\omega^{-1})$ no regime de reuso parcial.

Estes resultados sustentam-se sem exigir o armazenamento de políticas passadas (ao contrário dos métodos baseados em BH), exigindo apenas o armazenamento de trajetórias passadas.

Resultados Empíricos

Experimentos foram conduzidos em tarefas de controle contínuo (Cart Pole, Half Cheetah, Swimmer) usando políticas Gaussianas lineares e profundas.

• Eficiência de Amostragem: O RT-PG supera consistentemente os baselines on-policy padrão (GPOMDP) e os métodos de redução de variância de estado da arte (SVRPG, SRVRPG, STORM-PG, DEF-PG) em termos de eficiência de amostragem. No ambiente Half Cheetah, o RT-PG alcançou quase o dobro do desempenho final da maioria dos baselines.
• Impacto do Reuso de Trajetórias: Experimentos variando o tamanho da janela $\omega$ demonstraram que aumentar a janela de reuso acelera a convergência. O RT-PG mostrou retornos decrescentes para janelas muito grandes, mas superou significativamente os baselines mesmo com reuso moderado.
• Comparação com Reuso Ingênuo: O RT-PG superou significativamente o MIW-PG (que usa ponderação uniforme), validando a eficácia da correção de PM e do esquema de ponderação adaptativa no controle da variância.
• Eficiência de Memória: Diferente dos métodos baseados em BH que exigem o armazenamento de todos os parâmetros de política passados para calcular os pesos, o RT-PG requer apenas o armazenamento de trajetórias passadas, tornando-o mais escalável para espaços de política de alta dimensão.

Significância e Alegações

O artigo afirma fornecer a primeira evidência teórica rigorosa de que o reuso de trajetórias é um mecanismo viável e poderoso para acelerar a convergência de Gradiente de Política. Ao introduzir o algoritmo RT-PG e o estimador MPM, os autores preenchem a lacuna entre a ideia intuitiva de reuso de dados passados e garantias de convergência comprováveis.

A significância reside em:

1. Avanço Teórico: Estabelecer que o reuso de trajetórias pode atingir a taxa $\tilde{O}(\epsilon^{-1})$, anteriormente considerada difícil para métodos de PG sem suposições fortes ou reuso de gradiente.
2. Utilidade Prática: Demonstrar que o reuso de trajetórias reduz o custo de amostragem sem comprometer a estabilidade do aprendizado, oferecendo uma alternativa prática aos métodos de reuso de gradiente que podem exigir lotes maiores ou técnicas complexas de redução de variância.
3. Eficiência de Memória: Alcançar taxas melhoradas sem o overhead de memória de armazenar as parametrizações de política passadas, uma limitação de outras abordagens de reuso de trajetória como o Balance Heuristic.

Os autores permanecem modestos quanto às limitações, observando que seus resultados dependem da suposição de divergência $\chi^2$ limitada e que a complexidade de amostragem depende da dimensionalidade $d_\Theta$ do parâmetro. Eles identificam a remoção desta suposição e a eliminação da dependência de dimensão como trabalhos futuros.