Resumo Técnico: Aprendizado de Imitação Adversário Off-Policy Provavelmente Eficiente com Garantias de Convergência

Declaração do Problema

O Aprendizado de Imitação Adversário (AIL) enquadra o aprendizado de imitação como um jogo de dois jogadores onde um agente atualiza sua política para corresponder ao desempenho de um especialista, enquanto um adversário atualiza uma função de recompensa para maximizar a lacuna de desempenho entre os dois. Algoritmos padrão de AIL exigem dados on-policy (amostras geradas pela política atual do agente) para avaliar as recompensas cumulativas esperadas durante as atualizações da função de recompensa. Esse requisito leva a uma ineficiência de amostragem significativa, pois exige novas interações com o ambiente em cada etapa de atualização, tornando a abordagem impraticável em configurações onde as interações são caras ou limitadas.

Embora métodos off-policy tenham sido propostos para reutilizar dados de políticas anteriores para melhorar a eficiência de amostragem, eles introduzem um erro de desvio de distribuição porque os dados não correspondem mais perfeitamente à distribuição de visitação de estado-ação da política atual. As abordagens de AIL off-policy existentes dependem de amostragem de importância (que induz alta variância) ou de transformações de variáveis complexas que alteram a função objetivo, muitas vezes perdendo garantias teóricas de convergência. O desafio central abordado neste trabalho é: Podemos garantir a convergência do AIL off-policy e assegurar a eficiência de amostragem sem depender de técnicas explícitas de correção off-policy, como a amostragem de importância?

Metodologia

Os autores propõem um algoritmo de AIL off-policy que combina descida de espelho baseada em modelo para atualizações de política com ascensão de gradiente projetado off-policy para atualizações de recompensa. A principal inovação reside no controle do erro de desvio de distribuição através da seleção cuidadosa do número de políticas passadas ($N$) cujos dados serão reutilizados durante as atualizações de recompensa.

1. Atualizações de Política

O algoritmo emprega uma abordagem de descida de espelho baseada em modelo.

• Estimativa de Modelo: A função de transição de estado $\hat{P}_h$ é estimada empiricamente a partir de encontros de estado-ação.
• Otimização de Política: A política é atualizada usando uma etapa de descida de espelho regularizada por divergência KL (Equação 3). Esta regra de atualização, derivada dos valores Q estimados, garante que as mudanças na política sejam conservadoras o suficiente para limitar a distância de Variação Total (TV) entre políticas consecutivas. Essa estabilidade é crucial para controlar o desvio de distribuição nas atualizações de recompensa off-policy.

2. Atualizações de Recompensa

Em vez de usar apenas dados da política atual $\pi_{k-1}$, a atualização de recompensa utiliza uma mistura de dados das $N(k)$ políticas mais recentes.

• Distribuição de Mistura: O algoritmo amostra de uma distribuição de mistura $d^{k-1, mix}_h = \sum_{n=1}^{N} \beta_n d^{k-n}_h$, onde $\beta_n$ são pesos uniformes.
• Objetivo: Os parâmetros da recompensa $\mu$ são atualizados via ascensão de gradiente projetado para maximizar a perda $L(\pi^{k-1, mix}, \mu) = J(\pi_E, \mu) - \frac{1}{N}\sum_{n=1}^N J(\pi_{k-n}, \mu)$.
• Controle de Erro: A análise teórica (Lema 4.2 e Teorema 4.3) demonstra que, se as atualizações de política forem suficientemente pequenas (controladas pelo tamanho do passo $\sigma$), a divergência entre a distribuição de mistura e a distribuição da política atual permanece limitada.

3. Estrutura Teórica

O regret do algoritmo AIL é decomposto em regret de política e regret de recompensa (Lema 3.2). Os autores derivam limites para ambos:

• Regret de Política: Limitado por $\tilde{O}(\sqrt{H^4 S^2 A K})$ usando a atualização de descida de espelho.
• Regret de Recompensa: Limitado por um termo composto pelo regret padrão, um termo de erro induzido por atualizações off-policy e um termo de erro de estimativa (Teorema 4.4).
• Resultado Principal (Teorema 4.5): O regret total é sublinear em relação ao número de iterações $K$, desde que o número de políticas reutilizadas $N(k)$ escale como $o(\sqrt{K})$. Especificamente, se $N$ for fixo, o escalonamento ideal é $N^* = \tilde{O}((S/(HAB))^{1/3})$.

Principais Contribuições

1. Garantias de Convergência sem Correção: O artigo fornece as primeiras garantias teóricas de convergência para um algoritmo de AIL off-policy que não requer técnicas de correção off-policy (ex: amostragem de importância).
2. Análise de Eficiência de Amostragem: Os autores estabelecem que a reutilização de amostras das $o(\sqrt{K})$ políticas mais recentes não compromete a convergência. Eles provam que o erro de desvio de distribuição é dominado pelos benefícios do aumento da disponibilidade de dados, particularmente quando o tamanho do espaço de estados ($S$) é grande em relação ao horizonte ($H$) e ao espaço de ações ($A$).
3. Validação Prática: O algoritmo é validado tanto em tarefas MiniGrid de espaço discreto quanto em benchmarks de OpenAI Gym (MuJoCo) de espaço contínuo, demonstrando que variantes off-policy ($N > 1$) convergem mais rápido e requerem menos amostras do que seus equivalentes on-policy.

Resultados Experimentais

• MiniGrid (Discreto): Em tarefas EmptyRoom de vários tamanhos ($3\times3$, $5\times5$, $9\times9$), algoritmos off-policy com $N=32$ alcançaram desempenho de nível especialista com aproximadamente 1.000 interações, enquanto o algoritmo on-policy ($N=1$) exigiu o horizonte completo de 10.000 interações para convergir. Os resultados confirmaram que espaços de estados maiores se beneficiam de um $N$ maior.
• MuJoCo (Contínuo): Nas tarefas HalfCheetah, Hopper e Walker2d, os algoritmos off-policy superaram consistentemente a linha de base on-policy. Embora o $N$ ideal varie entre os ambientes, ganhos significativos foram observados mesmo com $N$ pequenos (ex: $N=4$ ou $N=16$).
• Observação: Os experimentos apoiam a afirmação teórica de que o AIL off-policy pode alcançar eficiência de amostragem superior, embora o número ideal de políticas reutilizadas dependa das características específicas do ambiente.

Significância e Alegações

O artigo afirma preencher a lacuna entre a compreensão teórica e a aplicação prática do AIL off-policy. Embora trabalhos anteriores tenham demonstrado o sucesso prático do AIL off-policy, eles careciam de provas rigorosas de convergência. Este trabalho demonstra que:

• Suporte Teórico: É possível garantir a convergência para o AIL off-policy simplesmente controlando o desvio de distribuição através de atualizações de política conservadoras e limitando o número de políticas reutilizadas.
• Eficiência de Amostragem: O "erro" introduzido pelos dados off-policy é teoricamente mostrado como sendo superado pelos benefícios estatísticos de ter mais dados, especialmente em espaços de estados de alta dimensão.
• Simplicidade: O método proposto evita técnicas complexas de redução de variância, como a amostragem de importância, oferecendo uma alternativa mais simples e teoricamente fundamentada que se alinha às observações empíricas de eficiência de amostragem na prática.

Os autores observam modestamente que sua análise teórica assume configurações tabulares (estendidas para MDPs lineares no apêndice) e que o $N$ ideal em ambientes de RL profundo (MuJoCo) pode não se alinhar perfeitamente com os limites teóricos de pior caso devido à parametrização de redes neurais, mas as tendências de desempenho permanecem consistentes com a teoria.