Resumo Técnico: Uma Taxa Robusta de $O(1/\sqrt{T})$ para Aprendizado TD Não Projetado com Aproximação de Função Linear

Declaração do Problema

O aprendizado de Diferença Temporal (TD) com aproximação de função linear é um algoritmo fundamental para a avaliação de políticas em aprendizado por reforço. Embora a convergência assintótica seja bem compreendida, estabelecer taxas de convergência em tempo finito sob condições realistas — especificamente quando os dados são gerados por uma cadeia de Markov (ruído Markoviano) em vez de amostras independentes — permanece um desafio.

Existe uma lacuna teórica crítica em relação à taxa de convergência "robusta" de $O(1/\sqrt{T})$. Trabalhos anteriores que estabeleceram essa taxa (por exemplo, Bhandari et al., 2018) basearam-se em um passo de projeção artificial, onde as iterativas são forçadas em um conjunto limitado para evitar a divergência. Essa projeção é raramente utilizada na prática e requer o conhecimento de um limite sobre a solução ótima $\theta^*$, que muitas vezes é desconhecido. Por outro lado, taxas de convergência "rápidas" de $O(1/T)$ existem para o aprendizado TD não projetado, mas dependem do inverso do quadrado da curvatura mínima ($\omega$) da função de potencial. Como $\omega$ pode ser arbitrariamente pequeno (problemas mal condicionados), a taxa rápida pode degradar significativamente em regimes não assintóticos.

O problema em aberto, proposto por Bhandari et al. (2018), é se o TD(0) não projetado pode alcançar a taxa robusta de $O(1/\sqrt{T})$ sem condições de regularidade adicionais ou projeções artificiais.

Metodologia

Os autores analisam o algoritmo padrão de TD(0) não projetado com aproximação de função linear sob amostragem Markoviana. A abordagem deles diverge fundamentalmente de análises anteriores que dependem de propriedades de contração ou projeções artificiais.

1. Seleção da Função de Potencial

Em vez de usar a distância de norma $D$ padrão $\|V_{\bar{\theta}_T} - V_{\theta^*}\|_D^2$, os autores utilizam a função de potencial proposta por Liu e Olshevsky (2021):
$$f(\theta) := (1 - \gamma) \|V_\theta - V_{\theta^*}\|_D^2 + \gamma \|V_\theta - V_{\theta^*}\|_{\text{Dir}}^2$$
Esta função de potencial é vantajosa porque:

• Ela permanece bem comportada mesmo quando o fator de desconto $\gamma \to 1$.
• O campo de atualização estacionária $\bar{g}(\theta)$ satisfaz a igualdade $\langle -\bar{g}(\theta), \theta - \theta^* \rangle = f(\theta) - f(\theta^*)$, o que simplifica a análise em comparação com as desigualdades usadas em outros trabalhos.

2. Propriedade de Auto-limitação via Indução

A principal contribuição técnica é uma nova propriedade de auto-limitação (self-bounding property) das atualizações TD. Os autores provam que, sem projetar as iterativas, a sequência $\{\theta_t\}$ permanece limitada em expectativa em torno da solução ótima $\theta^*$, desde que o tamanho do passo (stepsize) seja escolhido cuidadosamente.

• Design do Tamanho do Passo: O tamanho do passo é definido como $\eta_t = \frac{1}{c \phi_\infty^2 \log(T) \log(t+3) \sqrt{t+1}}$, onde $c$ é uma constante que satisfaz $c > 15 + 18\sqrt{2}$.
• Argumento Indutivo: A prova procede por indução. Assumindo que as iterativas são limitadas até o tempo $t-1$, os autores mostram que a atualização no tempo $t$ permanece limitada. Isso depende da decomposição da atualização em uma sequência de diferença de martingala (ruído) e um termo de viés (bias).
• Tratamento de Ruído Markoviano: Para abordar o viés introduzido por correlações Markovianas (onde $E[g(\theta, Z_t) | \mathcal{F}_{t-1}] \neq \bar{g}(\theta)$), os autores utilizam o mixing geométrico da cadeia de Markov subjacente (Teorema 3.2). Eles limitam o viés relacionando a distribuição do estado atual à distribuição estacionária sobre um atraso (lag) $k'$, utilizando a taxa de decaimento $\alpha^k$.

3. Análise de Limitação (Boundedness)

Os autores demonstram que as iterativas satisfazem:
$$E[\|\theta_t\|^2] \leq \rho_c^2 \max\left(\frac{r_\infty^2}{\phi_\infty^2}, \|\theta^*\|^2\right)$$
onde $\rho_c$ é uma constante que depende do parâmetro do tamanho do passo $c$. Esta limitação é alcançada sem projetar as iterativas, fechando efetivamente o loop de indução.

Principais Resultados

Garantias Teóricas

Teorema 4.2: Para a iterativa de média ponderada $\bar{\theta}_T$ gerada pelo TD(0) não projetado com o tamanho de passo especificado, a norma quadrada esperada das iterativas é limitada por uma constante independente do tempo de mistura (mixing time) e da curvatura $\omega$.

Corolário 4.3: O algoritmo alcança uma taxa de convergência de:
$$f(\bar{\theta}_T) - f(\theta^*) = \tilde{O}\left( \frac{c \rho_c^2 \max\{r_\infty^2, \phi_\infty^2 \|\theta^*\|^2\}}{\sqrt{T}} \right)$$
Crucialmente, as constantes ocultas na notação $\tilde{O}$ dependem de $\|\theta^*\|$ e dos limites das características (features), mas não dependem da curvatura mínima $\omega$ ou do tempo de mistura $\alpha$ (exceto por uma correção polilogarítmica menor na condição do tamanho do passo).

Comparação com Trabalhos Anteriores

• Vs. Taxas Robustas Projetadas: Ao contrário de Bhandari et al. (2018), este resultado remove o passo de projeção e o requisito de conhecer a priori os limites de $\theta^*$. A taxa é comparável ($\tilde{O}(1/\sqrt{T})$), mas alcançada sem restrições artificiais.
• Vs. Taxas Rápidas Não Projetadas: Ao contrário de Srikant e Ying (2019) e trabalhos subsequentes que alcançam $O(1/T)$, este resultado não depende do parâmetro de curvatura desconhecido $\omega$. Os autores mostram, via um contra-exemplo, que $\omega$ pode ser arbitrariamente pequeno, tornando as taxas rápidas potencialmente lentas ao extremo na prática, enquanto a taxa robusta permanece estável.

Significância e Alegações

O artigo afirma resolver um problema específico identificado por Bhandari et al. (2018): fornecer uma análise de tempo finito para o TD(0) não projetado com aproximação de função linear que alcance uma taxa de convergência robusta.

• Remoção de Suposições Artificiais: O trabalho demonstra que o passo de projeção, anteriormente considerado necessário para uma análise robusta, não é necessário. A limitação das iterativas emerge naturalmente da dinâmica do algoritmo quando o tamanho do passo é adequadamente escalonado com fatores logarítmicos.
• Sem Regularidade Adicional: O resultado mantém-se sem assumir condições de regularidade adicionais na estrutura do problema além das suposições padrão (irreducibilidade, aperiodicidade, posto de coluna total das características).
• Relevância Prática: Os autores enfatizam que, embora as projeções sejam usadas na teoria para simplificar provas, elas não são usadas na prática. Esta análise preenche a lacuna entre garantias teóricas e design de algoritmos práticos.
• Limiar de Estabilidade: O artigo identifica um limiar para a constante do tamanho do passo (especificamente $c > 15 + 18\sqrt{2}$) como uma condição suficiente para estabilidade. Resultados experimentais em dados sintéticos sugerem que este limiar captura um efeito genuíno de estabilidade em tempo finito; se $c$ for muito pequeno, as iterativas podem divergir.

Os autores observam que o limiar sobre $c$ é uma condição suficiente conservadora derivada das constantes da prova (desigualdade triangular, Cauchy-Schwarz, testes integrais) e não é necessariamente uma regra de ajuste prático apertada. Além disso, o requisito de que $T$ seja suficientemente grande em relação ao tempo de mistura $\alpha$ é reconhecido como uma limitação compartilhada pela literatura mais ampla sobre limites robustos, embora os autores prefiram uma apresentação executável das suposições em vez de uma formulação "anytime" que exigiria o conhecimento de parâmetros de mistura desconhecidos.