Resumo Técnico: Um Único Tamanho de Passo é Suficiente para TD(0) Linear Não Projetado

Declaração do Problema

O artigo aborda a análise de convergência em tempo finito e alta probabilidade de aprendizado de Diferença Temporal linear com viés zero (TD(0)) sob amostragem Markoviana. Neste cenário, os dados são gerados ao longo de uma única trajetória de uma cadeia de Markov, em vez de amostras independentes e identicamente distribuídas (i.i.d.).

O desafio central reside no fato de que o TD(0) não é um método de gradiente estocástico padrão; suas atualizações são enviesadas, não simétricas e o ruído é temporalmente correlacionado. Além disso, a magnitude da atualização depende da magnitude das iteradas atuais. As análises não assintóticas existentes tipicamente baseiam-se em uma de duas abordagens restritivas:

1. Projeções: Impor limitação através da projeção das iteradas sobre uma bola conhecida. Isso simplifica os argumentos de concentração, mas altera o algoritmo e requer conhecimento prévio de um raio adequado (frequentemente ligado à curvatura do problema).
2. Estabilidade Dependente da Curvatura: Explorar a natureza contrativa da dinâmica média para argumentar a estabilidade sem projeções. No entanto, isso tipicamente resulta em condições de tamanho de passo ou limites de estabilidade que dependem de um parâmetro de curvatura desconhecido ($\omega$). Quando $\omega$ é pequeno, esses limites tornam-se arbitrariamente lentos, e o tamanho do passo não pode ser escolhido independentemente de $\omega$.

Os autores visam estabelecer um cronograma de tamanho de passo único que seja independente do parâmetro de curvatura $\omega$ e que não requeira projeções, garantindo simultaneamente:

• Robustez: Uma taxa de convergência de $\tilde{O}(1/\sqrt{T})$ que se mantém independentemente de $\omega$.
• Rapidez: Uma taxa de convergência de $\tilde{O}(1/(\omega T))$ que explora a curvatura favorável quando esta existe.

Metodologia

1. Argumento de Auto-Limitação via Equações de Poisson

A principal novidade técnica é um novo argumento indutivo de "auto-limitação" (self-bounding) que controla a limitação patológica das iteradas $\theta_t$ sem depender da curvatura $\omega$ ou de projeções artificiais.

• O Ciclo: Uma análise de concentração ingênua é circular: limitar o erro requer atualizações limitadas, mas atualizações limitadas requerem iteradas limitadas.
• A Solução: Os autores decompõem o ruído Markoviano usando a Equação de Poisson associada à cadeia de Markov geometricamente misturante. Para um termo de força centrado $h$, eles resolvem $u - P_Z u = \tilde{h}$.
• Decomposição: Isso permite que a acumulação de termos de ruído Markoviano seja decomposta em um termo de martingala ($M_t$) e um termo de resto controlado ($R_t$).
• Indução: Eles estabelecem uma hipótese indutiva onde a limitação das iteradas até o tempo $t-1$ implica a limitação no tempo $t$. Ao controlar o termo de martingala via desigualdade de Pinelis e o termo de resto via propriedades de Lipschitz da solução de Poisson, eles provam que as iteradas permanecem uniformemente limitadas com alta probabilidade, independentemente de $\omega$.

2. Média de Polyak–Ruppert (PR)

O artigo analisa a iterada média de Polyak–Ruppert $\bar{\theta}_T = \frac{1}{S_T} \sum_{t=1}^T \eta_{t-1} \theta_{t-1}$, onde $S_T = \sum \eta_{t-1}$.

• Uma vez estabelecida a limitação uniforme de $\theta_t$, os autores podem controlar a variação quadrática dos termos de martingala e os termos de viés na análise de convergência.
• Eles derivam dois limites superiores distintos para o erro da função de potencial $f(\bar{\theta}_T) - f(\theta^*)$:
  • Um limite robusto derivado de uma análise clássica de gradiente estocástico com média, resultando em $\tilde{O}(1/\sqrt{T})$.
  • Um limite rápido derivado pela análise da evolução do erro $e_t = \theta_t - \theta^*$ e pelo aproveitamento da definição positiva da parte simétrica da matriz TD (curvatura $\omega$), resultando em $\tilde{O}(1/(\omega T))$.

3. Cronograma de Tamanho de Passo

O tamanho de passo proposto é:
$$\eta_t = \frac{1}{c \tau_{\text{mix}} \phi_\infty^2} \cdot \frac{1}{\sqrt{t+1} \log(t+3)}$$
onde $c$ é uma constante numérica, $\tau_{\text{mix}}$ é o tempo de mistura e $\phi_\infty$ limita as normas das características. Crucialmente, este cronograma depende do tempo de mistura, mas não da curvatura $\omega$.

Principais Resultados

1. Limitação de Alta Probabilidade (Teorema 4.1)

Sob pressupostos padrão (MRP ergódico, características de posto total), as iteradas do TD(0) não projetadas são uniformemente limitadas com alta probabilidade ($1-\delta$):
$$\sup_{t \ge 0} \|\theta_t\|^2 \le \rho R_{\text{base}}$$
onde $R_{\text{base}}$ depende do erro inicial, da norma da solução ótima e das constantes do problema, mas é independente de $\omega$. Este é o primeiro resultado a mostrar tal limitação para TD(0) não projetado sob amostragem Markoviana sem usar $\omega$ no tamanho de passo ou no argumento de estabilidade.

2. Taxas de Convergência Simultâneas (Teorema 4.2)

Usando o mesmo tamanho de passo e a média de PR, o algoritmo alcança uma taxa de convergência de alta probabilidade para o erro da função de potencial:
$$f(\bar{\theta}_T) - f(\theta^*) \le \min \left\{ \frac{C_{\text{fast}}}{\omega S_T^2}, \frac{C_{\text{robust}}}{S_T} \right\}$$
Substituindo o cronograma de tamanho de passo, isso se traduz em:

• Taxa Robusta: $\tilde{O}\left( \frac{\tau_{\text{mix}} R_{\text{base}}^2}{\sqrt{T}} \right)$
• Taxa Rápida: $\tilde{O}\left( \frac{\tau_{\text{mix}}^2 R_{\text{base}}^2}{\omega T} \right)$

O limite se adapta automaticamente para o mínimo dessas duas taxas sem conhecimento prévio de $\omega$.

3. Variante Livre de Mistura (Apêndice E)

Os autores também propõem um tamanho de passo modificado $\eta_t \propto \frac{1}{\sqrt{t} \log^2 t}$ que não requer o conhecimento de $\tau_{\text{mix}}$. No entanto, isso acarreta uma dependência duplamente exponencial de $\tau_{\text{mix}}$ nas constantes do limite de convergência, especificamente através de $B_{m^*}$ do prefixo inicial.

Significância e Alegações

O artigo afirma ser o primeiro a estabelecer que o TD(0) linear com amostragem Markoviana pode alcançar tanto taxas de convergência robustas quanto rápidas de alta probabilidade usando um único tamanho de passo que é:

1. Independente do parâmetro de curvatura $\omega$.
2. Livre de projeção.

Os autores enfatizam que trabalhos anteriores ou exigiam projeções (alterando o algoritmo), ou dependiam de passos dependentes da curvatura (falhando quando $\omega$ é pequeno), ou forneciam apenas limites de expectativa (ex: Lee e Orabona [2025]) em vez de garantias de alta probabilidade.

A significância reside no argumento de auto-limitação via equações de Poisson, que quebra a dependência circular entre a limitação das iteradas e a magnitude da atualização sem recorrer às propriedades contrativas da dinâmica média. Isso permite que o algoritmo permaneça estável e converja rapidamente mesmo quando a curvatura é arbitrariamente pequena, um cenário onde análises anteriores sem projeção tipicamente falhavam ou exigiam estratégias de descarte de dados.

O artigo permanece modesto quanto à dependência do tempo de mistura $\tau_{\text{mix}}$. Embora a taxa rápida tenha uma dependência de $\tau_{\text{mix}}^2$ (pior do que a dependência linear de $\tau_{\text{mix}}$ em alguns trabalhos anteriores com projeção ou descarte de dados), os autores observam que a dependência ótima de $\tau_{\text{mix}}$ na ausência de projeções e descarte de dados permanece uma questão aberta. Eles também reconhecem que seu termo de erro inicial decai a uma taxa de $1/T$ em vez de exponencialmente, uma consequência de evitar argumentos baseados em contração.