Achieving $\epsilon^{-2}$ Sample Complexity for Single-Loop Actor-Critic under Minimal Assumptions

Resumo Técnico: Alcançando Complexidade de Amostragem $\tilde{O}(\epsilon^{-2})$ para Actor-Critic de Loop Único sob Suposições Mínimas

Declaração do Problema
A aprendizagem por reforço (RL) visa resolver Processos de Decisão de Markov (MDPs) através de métodos orientados por dados. Enquanto métodos no espaço de valor, como Q-learning, estabeleceram complexidade de amostragem $\tilde{O}(\epsilon^{-2})$ sob suposições mínimas (especificamente, a existência de uma política de comportamento irredutível), métodos no espaço de políticas, como actor-critic, historicamente ficaram atrás em garantias teóricas. As análises existentes de actor-critic que alcançam complexidade $\tilde{O}(\epsilon^{-2})$ tipicamente dependem de duas condições restritivas:

1. Implementações de loops aninhados: Onde o crítico atualiza múltiplas vezes enquanto o ator permanece fixo, uma estrutura distinta dos algoritmos práticos de loop único.
2. Suposições fortes e dependentes do algoritmo: Como exigir que todas as políticas encontradas durante a trajetória do algoritmo (ou toda a classe de políticas) induzam cadeias de Markov irredutíveis e aperiódicas com taxas de mistura e propriedades de exploração uniformemente limitadas.

Essas suposições criam uma dependência circular: verificar as propriedades de mistura exige controlar a sequência de políticas gerada pelo algoritmo, que é precisamente o objeto da análise de convergência. Além disso, algoritmos práticos de actor-critic operam de maneira de loop único e escala de tempo única com aprendizagem off-policy, onde o crítico rastreia uma política-alvo variante no tempo. Isso introduz desafios relacionados a equações de atualização acopladas e iterações potencialmente ilimitadas devido à amostragem por importância, que estruturas teóricas existentes lutam para abordar sem suposições fortes.

Metodologia
Os autores propõem um algoritmo actor-critic off-policy de loop único e escala de tempo única, onde o ator e o crítico são atualizados simultaneamente a cada iteração. O ator emprega atualizações incrementais em direção a uma política-alvo $\tilde{\pi}_t$ derivada via iteração de política aproximada (API) ou gradiente de política natural (NPG), enquanto o crítico realiza aprendizagem de diferença temporal (TD) off-policy. Os autores consideram duas variantes do crítico:

• Amostragem por Importância (IS): Corrige o desajuste de distribuição usando uma razão de peso de importância.
• Diferença Temporal Esperada (ETD): Calcula diretamente a função Q esperada no próximo estado, evitando pesos de importância explícitos.

A inovação técnica central reside no quadro de análise. Para lidar com o acoplamento entre as atualizações do ator e do crítico e a natureza ilimitada das iterações off-policy, os autores empregam um quadro de deriva de Lyapunov acoplado.

1. Funções de Lyapunov: Eles constroem funções de Lyapunov separadas para o ator ($V_t = \|Q^* - Q_{\pi_t}\|_\infty^2$) e para o crítico ($W_t = \|Q_t - Q_{\pi_t}\|_\nu^2$).
2. Desigualdades de Deriva: Eles estabelecem desigualdades de deriva negativa para ambas as funções. Crucialmente, essas desigualdades contêm termos cruzados que representam o erro do sistema acoplado (por exemplo, o erro do crítico aparecendo na deriva do ator e vice-versa).
3. Dominação Cruzada: A análise depende de uma propriedade de "dominação cruzada". Ao selecionar cuidadosamente as razões de tamanho de passo e garantindo que os termos de erro de acoplamento sejam dominados pelos termos de deriva negativa dos respectivos sistemas, os autores combinam as duas desigualdades de deriva em uma única recursão para $V_t + W_t$. Essa abordagem é inspirada na teoria de pequeno ganho em sistemas dinâmicos, mas é adaptada aqui para lidar com ruído markoviano, alvos variantes no tempo e iterações ilimitadas de maneira unificada.

Principais Contribuições e Resultados
O artigo estabelece as primeiras taxas de convergência da última iteração para um algoritmo actor-critic de loop único que alcança complexidade de amostragem $\tilde{O}(\epsilon^{-2})$ sob suposições mínimas.

• Suposições Mínimas: A única suposição necessária é a existência de uma política que induza uma cadeia de Markov irredutível sobre o espaço de estados. Essa política não precisa ser visitada pelo algoritmo, nem o algoritmo precisa controlar as propriedades de mistura das políticas que gera. Isso contrasta com trabalhos anteriores que exigiam ergodicidade uniforme ao longo da trajetória ou de toda a classe de políticas.
• Complexidade de Amostragem: Sob essa suposição mínima, o algoritmo alcança uma complexidade de amostragem de $\tilde{O}(\epsilon^{-2})$ para encontrar uma política $\epsilon$-ótima. Essa taxa é quase minimax ótima em relação a $\epsilon$.
• Esquemas de Tamanho de Passo: Os resultados valem para sequências de tamanho de passo constantes, harmônicas e polinomiais. Especificamente, o uso de tamanhos de passo harmônicos com parâmetros apropriados produz a taxa ótima.
• Variantes do Algoritmo: A análise cobre críticos baseados tanto em IS quanto em ETD. Embora ambos alcancem a mesma ordem de complexidade, a variante ETD exibe uma dependência mais branda em parâmetros do problema (tamanho do espaço de estados $n$, tamanho do espaço de ações $m$ e fator de desconto $\gamma$) porque evita a estocasticidade adicional introduzida pelas razões de amostragem por importância.
• Iterações Ilimitadas: O quadro lida com sucesso com as iterações potencialmente ilimitadas induzidas pela aprendizagem off-policy (particularmente com IS), um desafio que frequentemente exige suposições fortes de limitação na literatura anterior.

Significado e Afirmações
Os autores afirmam que este trabalho preenche uma lacuna teórica significativa entre métodos no espaço de valor e métodos no espaço de políticas. Ao demonstrar que métodos actor-critic podem alcançar complexidade de amostragem minimax ótima sem loops aninhados ou suposições fortes de mistura dependentes do algoritmo, o artigo desafia a noção de que métodos no espaço de políticas são inerentemente menos eficientes em amostragem ou exigem condições mais fortes.

O quadro analítico baseado em deriva de Lyapunov acoplada e dominação cruzada é apresentado como uma contribuição de interesse independente, potencialmente aplicável a outros algoritmos iterativos acoplados com iterações ilimitadas. O artigo nota explicitamente que, embora a dependência de $\epsilon$ seja quase ótima, a dependência de constantes específicas do problema ($n, m, (1-\gamma)^{-1}$) pode ser subótima em comparação com métodos baseados em valor, sugerindo que técnicas de redução de variância poderiam ser uma direção para melhoria futura. O trabalho evita fazer afirmações sobre configurações de aproximação de funções (a "tríade mortal") ou aplicações empíricas específicas, focando estritamente no cenário tabular e em garantias teóricas.