Finite-Time Convergence of Distributionally Robust Q-Learning with Linear Function Approximation

Resumo Técnico: Convergência em Tempo Finito de Q-Learning Distribucionalmente Robusto com Aproximação de Função Linear

Enunciado do Problema
O artigo aborda o desafio de aprender políticas ótimas em Aprendizado por Reforço Distribucionalmente Robusto (DRRL) quando o ambiente de implantação difere do ambiente de treinamento (nominal). Especificamente, os autores focam no Q-learning robusto descontado e livre de modelo (model-free) sob um conjunto de incerteza qui-quadrado $(s, a)$-retangular.

O cenário envolve um aprendiz operando em uma única trajetória Markoviana gerada por um núcleo de transição nominal desconhecido $P_0$ e uma política de comportamento $\pi_b$. O aprendiz não possui acesso generativo (não pode amostrar pares estado-ação arbitrários) e não conhece $P_0$. O objetivo é aprender a função Q robusta ótima, $Q^\star_\chi$, que maximiza o valor descontado no pior caso sobre o conjunto de incerteza.

O problema apresenta duas dificuldades acopladas:

1. Dificuldade de Aproximação de Função: Embora o operador de Bellman robusto exato seja uma contração em $\ell_\infty$, o operador de Bellman robusto projetado induzido pela aproximação de função linear não é conhecido por ser uma contração para fatores de desconto gerais $\gamma \in (0, 1)$.
2. Dificuldade de Estimação Robusta: A atualização de Bellman robusta qui-quadrado envolve uma minimização interna sobre distribuições de transição. Seu gradiente dual depende de momentos condicionais (especificamente, a parte positiva do gap de Bellman e seu quadrado) que devem ser estimados a partir de uma única trajetória. Análises padrão para Q-learning robusto tabular ou Q-learning linear não se estendem diretamente a este cenário.

Metodologia
Os autores propõem o Algoritmo 1, um algoritmo de aproximação estocástica de múltiplos estágios que combina um loop externo de rede-alvo (target-network) com um esquema de aproximação de função dual. O algoritmo opera em blocos externos onde a função Q-alvo é congelada. Dentro de cada bloco, ocorrem três estágios:

1. Estágio 1: Otimização Dual com Rastreamento de Momentos.
   O algoritmo resolve a minimização interna da atualização de Bellman robusta qui-quadrado via sua forma dual escalar. Em vez de resolver um problema dual separado para cada par estado-ação, a variável dual $\eta$ é aproximada linearmente ($\eta_\nu(i) = \psi(i)^\top \nu$).

   • Esquema de Duas Escalas de Tempo (Two-Time-Scale): A variável dual $\nu$ é atualizada em uma escala de tempo lenta, enquanto dois "críticos de rastreamento de momentos" ($\omega_1, \omega_2$) estimam os momentos condicionais necessários ($Z_1$ e $Z_2$) em uma escala de tempo mais rápida.
   • Suavização (Smoothing): Para lidar com a falta de suavidade global no objetivo dual qui-quadrado (o que causa problemas com a análise de ruído Markoviano), os autores otimizam um objetivo substituto suavizado usando um parâmetro ajustável $\tau > 0$. Isso garante que o gradiente dual seja Lipschitz contínuo.
   • Média de Sufixo (Suffix Averaging): As iterações duais são submetidas a uma média de sufixo para obter uma estimativa estável $\bar{\nu}_t$.

2. Estágio 2: Avaliação Recente (Fresh Evaluation).
   Antes de atualizar a função Q, o algoritmo realiza uma "avaliação recente" do momento de variância ($Z_1$) usando o parâmetro dual médio $\bar{\nu}_t$. Este estágio isola a estimação do momento da trajetória de otimização, evitando o acúmulo de viés que ocorreria se os críticos do Estágio 1 (aprendidos enquanto $\nu$ estava se movendo) fossem reutilizados diretamente.

3. Estágio 3: Atualização de Q.
   O algoritmo realiza uma atualização de diferença temporal (TD) lenta para o parâmetro da função Q robusta contra o alvo avaliado e fixo derivado dos Estágios 1 e 2.

Principais Contribuições

1. Garantia de Convergência em Tempo Finito: O artigo fornece o primeiro limite de convergência de tempo finito para Q-learning robusto com aproximação de função linear e descontado, a partir de dados de trajetória única, sem impor restrições de pequenos fatores de desconto.
2. Análise de Rede-Alvo para RL Robusto: Os autores adaptam a técnica de rede-alvo (comum em RL profundo não robusto) para o cenário robusto. Ao congelar a função Q-alvo dentro de blocos externos, eles contornam a não-contratividade do operador de Bellman robusto projetado, permitindo que a análise dependa da contração do operador não projetado entre os blocos.
3. Estimação Dual Escalável: Eles introduzem um método para aproximar a própria variável dual usando uma classe de função linear, acoplada a críticos de rastreamento de momentos. Isso evita os problemas de escalabilidade de resolver problemas duais independentes para grandes espaços de estados.
4. Suavização e Controle de Viés: O artigo introduz um substituto suavizado para o objetivo dual qui-quadrado. Isso resolve o problema do gradiente não-Lipschitz inerente à formulação exata de qui-quadrado, permitindo limites rigorosos de aproximação estocástica de tempo finito sob ruído Markoviano. Os autores explicitamente observam que provas anteriores para Q-learning robusto tabular com incerteza qui-quadrado dependiam de suposições de suavidade global que não se sustentam; sua prova corrige essa lacuna.

Resultados
O principal resultado teórico (Teorema 1) estabelece um limite de convergência de ponta a ponta da forma:
$$\mathbb{E}[\| \hat{Q}_T - Q^\star_\chi \|_\infty] \leq \gamma^T \| \hat{Q}_0 - Q^\star_\chi \|_\infty + \frac{E_{stat}(N, M, K, \tau) + E_{app}(\tau)}{1 - \gamma}$$
onde:

• O primeiro termo representa o erro de contração da rede-alvo.
• $E_{stat}$ captura erros de amostra finita da atualização de Q, otimização dual, viés de suavização e avaliação recente.
• $E_{app}$ captura erros de aproximação devido à aproximação de função e suavização.

O Corolário 2 deriva a complexidade de amostragem, mostrando que, para atingir um erro $\epsilon$, o comprimento total da trajetória escala como $\tilde{O}(\epsilon^{-5/(1-a)})$ (onde $a$ é um parâmetro de tamanho de passo), até fatores logarítmicos.

Experimentos no FrozenLake MDP validam a teoria, demonstrando a convergência para o valor de referência robusto e ilustrando o compromisso (trade-off) introduzido pelo parâmetro de suavização $\tau$ (um $\tau$ menor reduz o viés, mas aumenta a variância/erro de otimização).

Significância e Alegações
O artigo afirma fechar uma lacuna significativa entre o sucesso empírico de algoritmos de RL robusto e as garantias teóricas disponíveis para seus equivalentes não robustos. Trabalhos anteriores de RL robusto livre de modelo foram limitados a configurações tabulares, exigiram acesso generativo, assumiram exploração ativa ou impuseram condições restritivas sobre o fator de desconto.

Os autores afirmam que seu trabalho fornece a primeira garantia de convergência em tempo finito para Q-learning robusto descontado com aproximação de função linear a partir de dados de trajetória única, sem suposições de pequenos fatores de desconto. Além disso, afirmam que sua prova para o caso qui-quadrado (mesmo no limite tabular) parece ser a primeira prova de convergência correta, pois aborda a falta de suavidade global no objetivo dual que análises anteriores haviam negligenciado ou assumido como dada. O framework é apresentado como um modelo analisável que pode ser estendido para implementações de redes neurais de larga escala.