Resumo Técnico: Preenchendo a Lacuna entre Aprendizado TD Médio e Descontado

Declaração do Problema

O aprendizado por Diferença Temporal (TD) é um pilar do aprendizado por reforço, contudo, sua análise teórica no cenário de recompensa média fica significativamente atrás do cenário descontado. No caso descontado, o operador de Bellman é uma contração, garantindo soluções únicas e uma análise de convergência direta. Por outro lado, no cenário de recompensa média, o operador de Bellman não é contrativo em relação a qualquer norma, e a solução da equação de Bellman correspondente não é única (é definida apenas até uma constante aditiva).

A literatura existente que aborda o TD de recompensa média sofre de várias limitações em comparação ao caso descontado:

1. Pressupostos Restritivos: Muitos métodos exigem pressupostos (por exemplo, $\Phi\theta \neq ce$) que excluem o cenário tabular.
2. Garantias de Convergência: Algumas abordagens garantem convergência apenas para um ponto fixo dependente do caminho amostral ou para um conjunto, em vez de uma solução única e determinística.
3. Dependência da Dimensão: Os limites de convergência frequentemente contêm fatores explícitos da dimensão do parâmetro $d$.
4. Escala do Número de Condição: As complexidades amostrais mais avançadas frequentemente exibem dependência quártica no número de condição do problema ($O(\eta^{-4})$), enquanto o cenário descontado alcança uma escala quadrática ($O(\eta^{-2})$).
5. Complexidade Algorítmica: Alcançar uma melhor escala em trabalhos anteriores frequentemente exigia técnicas complexas de redução de variância (por exemplo, loops aninhados), desviando-se da simplicidade do TD padrão.

Metodologia

Os autores propõem uma abordagem inovadora para a avaliação de políticas no cenário de recompensa média, formulando a solução da equação de Bellman como um problema de otimização com restrições. A ideia central é que a função de valor relativa $W^*$ deve satisfazer uma restrição de estado estacionário ($\mu^\top W^* = 0$).

1. Algoritmo de Dupla Cadeia

Para resolver a equação de Bellman projetada $W^* = \Pi T_\pi W^*$, onde $\Pi = I - e\mu^\top$, os autores derivam uma regra de atualização estocástica. Um desafio chave na aproximação estocástica para este cenário é o problema da "dupla amostragem": estimar o termo $\mu\mu^\top(R + W_t)$ requer a expectativa de um produto de variáveis aleatórias, o que não pode ser estimado a partir de uma única trajetória devido à correlação.

Para resolver isso, os autores introduzem um Algoritmo de Dupla Cadeia que utiliza duas cadeias de Markov independentes ($\{s_t\}$ e $\{\hat{s}_t\}$) em cada iteração.

• Regra de Atualização: O vetor de parâmetros $\theta_t$ é atualizado usando dois componentes:
  • $g(s_t, s'_t, \theta_t)$: Estima o termo padrão de erro TD $D(R + P\Phi\theta_t - \Phi\theta_t)$.
  • $f(s_t, \hat{s}_t, \theta_t)$: Estima o termo de restrição $-\mu\mu^\top(R + \Phi\theta_t)$ usando a amostra independente $\hat{s}_t$ para quebrar a correlação.
• Aproximação Linear: O método generaliza para aproximação linear de função ($W \approx \Phi\theta$) projetando as atualizações no espaço de características.

2. Algoritmo de Cadeia Única

Para evitar a sobrecarga computacional de manter duas cadeias, os autores propõem um Algoritmo de Cadeia Única inspirado no Gradient TD (GTD).

• Mecanismo: Em vez de amostrar um segundo estado independente $\hat{s}_t$, o algoritmo mantém uma variável auxiliar $w_t$ que rastreia a expectativa $E[\phi(s)] = \Phi^\top\mu$.
• Atualização: O termo $\phi(\hat{s}_t)$ na atualização de dupla cadeia é substituído por $w_t$. A variável $w_t$ é atualizada por meio de uma etapa separada de aproximação estocástica para convergir a $\Phi^\top\mu$.
• Compromisso: Embora isso simplifique o requisito de amostragem para uma única trajetória, a análise mostra uma dependência ligeiramente pior no número de condição em comparação com a variante de dupla cadeia.

3. Estrutura Teórica: Divisão de Gradiente

A análise de convergência baseia-se na técnica de divisão de gradiente [19]. Os autores demonstram que a direção de atualização esperada de seu algoritmo atua como uma "divisão de gradiente" de uma função quadrática composta específica:
$$f(\theta) = \|\Phi(\theta - \theta^*)\|_{\text{Dir}}^2 + (\mu^\top\Phi(\theta - \theta^*))^2$$
Isso permite que os autores analisem o algoritmo usando técnicas padrão de recursão de Descida de Gradiente Estocástica (SGD), apesar da natureza não contrativa do operador de Bellman subjacente.

Principais Contribuições

O artigo afirma preencher a lacuna teórica entre o aprendizado TD de recompensa média e descontado ao alcançar as seguintes características simultaneamente:

1. Ponto Fixo Único e Independente da Amostra: Os algoritmos propostos convergem quase certamente para uma solução única e determinística $\theta^*$ que é independente da trajetória aleatória e da inicialização.
2. Aplicabilidade a Cenários Tabulares e Lineares: A análise vale tanto para casos tabulares (onde $\Phi = I$) quanto para aproximação linear de função, sem exigir o pressuposto restritivo $e \notin \text{span}(\Phi)$.
3. Limites Livres de Dimensão: Os limites de convergência não contêm fatores explícitos da dimensão $d$ (além daqueles inerentes a $\|\theta^*\|$ ou $\|\theta_0\|$).
4. Convergência da Última Iteração: Os resultados são garantidos para a última iteração, alinhando-se ao padrão no TD descontado, em vez de depender da média das iterações.
5. Escala Melhorada do Número de Condição:
   • O algoritmo de Dupla Cadeia alcança uma complexidade amostral de $\tilde{O}(\epsilon^{-1}\eta_1^{-2})$, onde $\eta_1$ é um número de condição definido como $\min_{\|x\|=1} (\|\Phi x\|_{\text{Dir}}^2 + (\mu^\top\Phi x)^2)$. Isso corresponde à escala quadrática observada no cenário descontado.
   • O algoritmo de Cadeia Única alcança $\tilde{O}(\epsilon^{-1}\eta^{-4})$ (quártico), o que é uma melhoria em relação a alguns trabalhos anteriores, mas ligeiramente pior que a variante de dupla cadeia.
6. Simplicidade Algorítmica: A escala quadrática é alcançada sem técnicas de redução de variância (por exemplo, loops aninhados ou lotes completos periódicos), mantendo a simplicidade das atualizações TD puras.

Resultados

Os autores fornecem uma análise de amostra finita para ambos os algoritmos sob amostragem i.i.d. e de Markov, com tamanhos de passo constantes e decrescentes.

• Limites Teóricos: Os Teoremas 4.1–4.3 estabelecem taxas de convergência e complexidades amostrais. O método de dupla cadeia corresponde ao estado da arte para TD descontado em termos de escala de parâmetros.
• Experimentos Numéricos: Os algoritmos foram testados em 15 MDPs tabulares do OpenAI Gym e MO-Gymnasium.
  • Os resultados mostram que os métodos propostos geralmente superam as bases anteriores (incluindo [10], [11], [12], [17], [18] e [21]) em termos de erro de aproximação em relação à solução verdadeira.
  • Os experimentos confirmam que os métodos convergem para a solução única, enquanto algumas bases (que convergem para conjuntos ou pontos dependentes da amostra) apresentam maior variância ou erro no cenário tabular.

Significância

O artigo afirma resolver ressalvas teóricas persistentes associadas à análise do TD de recompensa média. Ao utilizar divisão de gradiente e uma estratégia de amostragem de duas cadeias (ou cadeia única com variável auxiliar), os autores demonstram que o TD de recompensa média pode alcançar as mesmas propriedades favoráveis de convergência do TD descontado:

• Unicidade: Convergência para uma solução bem definida e única.
• Generalidade: Aplicabilidade a cenários tabulares e lineares sem pressupostos restritivos.
• Eficiência: Dependência quadrática no número de condição sem a necessidade de maquinaria complexa de redução de variância.

Este trabalho sugere que as dificuldades teóricas do cenário de recompensa média podem ser superadas reformulando o problema como uma tarefa de otimização com restrições e aproveitando estratégias de amostragem específicas para lidar com a natureza não contrativa do operador de Bellman.