Aprendizado por Diferença Temporal (Temporal-Difference, TD)

Visão geral

Aprendizado por diferença temporal (Temporal-Difference, TD) é uma família de métodos de aprendizado por reforço (reinforcement learning, RL) para aprender funções de valor a partir de experiência por meio de bootstrap (bootstrapping) — isto é, atualizando estimativas atuais usando outras estimativas aprendidas, em vez de esperar o episódio terminar para calcular um retorno completo.

Os métodos TD ficam entre:

• Programação Dinâmica (Dynamic Programming, DP): faz bootstrap, mas assume um modelo conhecido do ambiente.
• Monte Carlo (Monte Carlo, MC): aprende a partir de retornos amostrados sem bootstrap, mas tipicamente precisa esperar até o fim de um episódio.

O aprendizado TD combina as vantagens de ambos: é sem modelo (model-free) (como MC) e pode aprender online a partir de episódios incompletos (como DP).

As ideias de TD fundamentam muitos algoritmos centrais de RL, incluindo SARSA (controle TD on-policy) e Q-learning (controle TD off-policy). Veja também: Q-learning, Iteração de Política Generalizada e Métodos Ator-Crítico.

---

Contexto: funções de valor e o alvo TD

A maioria dos métodos TD assume que o ambiente pode ser modelado como um Processo de Decisão de Markov (Markov Decision Process, MDP) com:

• estados (s \in \mathcal{S})
• ações (a \in \mathcal{A})
• recompensa (r_{t+1})
• fator de desconto (\gamma \in [0,1))

O retorno a partir do tempo (t) é:

[ G_t = r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \cdots ]

Uma função de valor de estado para uma política (\pi) é:

[ V^\pi(s) = \mathbb{E}_\pi[G_t \mid s_t = s] ]

Uma identidade-chave é a equação de expectativa de Bellman (a estrutura de “olhar um passo à frente”):

[ V^\pi(s) = \mathbb{E}\pi[r{t+1} + \gamma V^\pi(s_{t+1}) \mid s_t = s] ]

O aprendizado TD explora essa estrutura formando um alvo TD de um passo:

[ \text{Alvo TD} = r_{t+1} + \gamma V(s_{t+1}) ]

Isso usa a estimativa atual (V(s_{t+1})) como substituta do valor verdadeiro desconhecido — isto é bootstrap.

---

O erro TD (o motor do aprendizado TD)

A quantidade central nos métodos TD é o erro TD:

[ \delta_t = r_{t+1} + \gamma V(s_{t+1}) - V(s_t) ]

Intuição:

• Se (\delta_t > 0), o resultado foi melhor do que o esperado → aumente (V(s_t)).
• Se (\delta_t < 0), o resultado foi pior do que o esperado → diminua (V(s_t)).
• Se (\delta_t \approx 0), a estimativa de valor está consistente com a experiência observada (e com o próprio bootstrap).

---

TD(0): aprendizado por diferença temporal de um passo

TD(0) é o método mais simples de predição TD. Ele atualiza o valor do estado atual em direção ao alvo TD de um passo:

[ V(s_t) \leftarrow V(s_t) + \alpha \bigl[r_{t+1} + \gamma V(s_{t+1}) - V(s_t)\bigr] ]

onde (\alpha \in (0,1]) é a taxa de aprendizado.

Algoritmo TD(0) (tabular, avaliação de política)

# Initialize V(s) arbitrarily (e.g., 0 for all states)
for each episode:
    s = env.reset()
    done = False
    while not done:
        a = pi(s)                      # take action from policy
        s_next, r, done = env.step(a)
        td_target = r + gamma * (0 if done else V[s_next])
        td_error  = td_target - V[s]
        V[s] += alpha * td_error
        s = s_next

Exemplo prático: uma única atualização

Suponha:

• (V(s_t) = 1.20)
• recompensa (r_{t+1} = 0.50)
• (\gamma = 0.9)
• (V(s_{t+1}) = 1.00)
• (\alpha = 0.1)

Então:

• alvo TD (= 0.50 + 0.9 \cdot 1.00 = 1.40)
• erro TD (= 1.40 - 1.20 = 0.20)
• atualização (V(s_t) \leftarrow 1.20 + 0.1 \cdot 0.20 = 1.22)

Isso ilustra a natureza incremental e online do aprendizado TD.

---

Por que o aprendizado TD é útil (comparado ao Monte Carlo)

Avaliação Monte Carlo (MC)

Métodos MC atualizam usando o retorno completo:

[ V(s_t) \leftarrow V(s_t) + \alpha (G_t - V(s_t)) ]

Isso é não viesado em relação ao retorno amostrado, mas:

• frequentemente é necessário esperar até o fim do episódio para computar (G_t)
• a variância pode ser alta (especialmente com horizontes longos)

Avaliação TD

TD(0) atualiza imediatamente após cada passo e tipicamente tem:

• menor variância (porque faz bootstrap)
• algum viés (porque usa uma estimativa (V(s_{t+1})))

Isso introduz uma troca viés–variância fundamental, que fica explícita em métodos de (n) passos e TD((\lambda)).

---

Além de um passo: TD de \(n\) passos e a ponte para Monte Carlo

TD(0) usa um alvo de um passo. TD de (n) passos usa as primeiras (n) recompensas e então faz bootstrap:

[ G_t^{(n)} = r_{t+1} + \gamma r_{t+2} + \cdots + \gamma^{n-1} r_{t+n} + \gamma^n V(s_{t+n}) ]

• (n=1) dá TD(0)
• (n \to \infty) (em tarefas episódicas) se aproxima de Monte Carlo

Na prática, valores intermediários de (n) podem funcionar muito bem, especialmente quando as recompensas são atrasadas mas ainda se deseja atualizações antes do término do episódio.

---

TD(λ): traços de elegibilidade para misturar muitas escalas de tempo

TD((\lambda)) fornece uma forma fundamentada de combinar muitos alvos de (n) passos usando traços de elegibilidade (eligibility traces), resultando em atribuição de crédito mais rápida e, frequentemente, melhor velocidade de aprendizado.

Há duas visões complementares:

Visão forward: o retorno-λ

TD((\lambda)) pode ser visto como aprender em direção a uma média ponderada de retornos de (n) passos:

[ G_t^\lambda = (1-\lambda)\sum_{n=1}^{\infty}\lambda^{n-1}G_t^{(n)} ]

• (\lambda \in [0,1])
• (\lambda = 0) se reduz a TD(0)
• (\lambda \to 1) se aproxima de Monte Carlo (em cenários episódicos)

Visão backward: traços de elegibilidade (o que você implementa)

A visão backward mantém um traço (e(s)) para cada estado indicando quão “elegível” ele é para receber crédito a partir do erro TD atual.

Uma forma tabular comum de TD((\lambda)):

[ \delta_t = r_{t+1} + \gamma V(s_{t+1}) - V(s_t) ] [ e_t(s) = \begin{cases} \gamma \lambda e_{t-1}(s) + 1 & \text{se } s = s_t \ \gamma \lambda e_{t-1}(s) & \text{caso contrário} \end{cases} ] [ V(s) \leftarrow V(s) + \alpha \delta_t e_t(s) ]

Intuição: quando você visita um estado, seu traço de elegibilidade aumenta; então erros TD futuros se propagam para trás para atualizar estados visitados recentemente, em proporção aos seus traços.

Pseudocódigo de TD(λ) (tabular)

# Initialize V(s) and e(s)=0
for each episode:
    e = {s: 0.0 for s in S}
    s = env.reset()
    done = False
    while not done:
        a = pi(s)
        s_next, r, done = env.step(a)

        td_target = r + gamma * (0 if done else V[s_next])
        delta = td_target - V[s]

        e[s] += 1.0                          # accumulating trace
        for s2 in S:
            V[s2] += alpha * delta * e[s2]
            e[s2] *= gamma * lambda_

        s = s_next

Variantes de traços (detalhe prático)

• Traços acumulativos: (e(s) \leftarrow e(s)+1) (mostrado acima)
• Traços de substituição: (e(s) \leftarrow 1) quando visitado
  Frequentemente ajuda quando estados se repetem com frequência (reduz traços “descontrolados”).
• Com aproximação de função, os traços se estendem a vetores de características (elegibilidade para parâmetros).

---

Da predição ao controle: SARSA e Q-learning

Métodos TD se tornam algoritmos de controle quando aplicados a funções de valor-ação (action-value functions) (Q(s,a)) e combinados com melhoria de política (este é o laço central em Iteração de Política Generalizada).

SARSA: controle TD on-policy

SARSA atualiza (Q(s,a)) em direção ao valor da próxima ação efetivamente executada sob a política de comportamento atual (tipicamente (\epsilon)-greedy):

[ \delta_t = r_{t+1} + \gamma Q(s_{t+1}, a_{t+1}) - Q(s_t, a_t) ] [ Q(s_t,a_t) \leftarrow Q(s_t,a_t) + \alpha \delta_t ]

Ele é chamado SARSA porque usa a tupla ((s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1})).

Implicação prática: SARSA aprende o valor da política que está de fato seguindo, incluindo seu comportamento de exploração. Isso frequentemente produz políticas “mais seguras” em ambientes estocásticos (por exemplo, pode evitar atalhos arriscados se a exploração puder causar falha).

Q-learning: controle TD off-policy

Q-learning atualiza em direção à estimativa gulosa do próximo estado, independentemente de qual ação foi realmente tomada:

[ \delta_t = r_{t+1} + \gamma \max_{a'} Q(s_{t+1}, a') - Q(s_t, a_t) ] [ Q(s_t,a_t) \leftarrow Q(s_t,a_t) + \alpha \delta_t ]

Isso é off-policy: o comportamento pode ser exploratório, mas o alvo corresponde à política gulosa. Veja Q-learning para mais profundidade.

SARSA vs Q-learning em um cenário simples

Considere um gridworld com um “penhasco” ao lado do caminho mais curto:

• Q-learning tende a aprender o caminho guloso ótimo (passando rente ao penhasco), porque avalia o alvo guloso.
• SARSA frequentemente aprende um caminho um pouco mais longo, mas mais seguro, porque a exploração pode empurrá-lo para o penhasco e ele incorpora esse risco nas estimativas de valor.

---

Aprendizado TD com aproximação de função (e por que pode ficar complicado)

Métodos TD tabulares armazenam um valor por estado (ou estado-ação). Problemas reais frequentemente exigem aproximação de função (function approximation), por exemplo:

• modelos lineares (V_\mathbf{w}(s) = \mathbf{w}^\top \phi(s))
• redes neurais (V_\theta(s)) ou (Q_\theta(s,a)) (ver Aprendizado Profundo por Reforço)

Atualização TD por semigradiente

Com vetor de parâmetros (\mathbf{w}), uma atualização comum de TD(0) é:

[ \mathbf{w} \leftarrow \mathbf{w} + \alpha , \delta_t , \nabla_{\mathbf{w}} V_\mathbf{w}(s_t) ]

Isso é chamado de método de semigradiente (semi-gradient) porque o alvo contém (V_\mathbf{w}(s_{t+1})), mas o gradiente tipicamente trata o alvo como fixo (não faz backprop através do alvo de bootstrap).

A “tríade mortal” (aviso prático importante)

Métodos TD podem se tornar instáveis ou até divergir ao combinar:

1. aproximação de função
2. bootstrap
3. aprendizado off-policy

Isso às vezes é chamado de tríade mortal (deadly triad). É um motivo-chave para que sistemas práticos de RL profundo incorporem técnicas de estabilização.

---

Como ideias de TD aparecem em RL profundo (por exemplo, DQN)

Muitos algoritmos de RL profundo estão, fundamentalmente, minimizando erros TD. Por exemplo, Redes Q Profundas (Deep Q-Networks, DQN) (um exemplo clássico em Aprendizado Profundo por Reforço) usam uma perda de erro TD ao quadrado:

[ L(\theta) = \mathbb{E}\left[\left(r + \gamma \max_{a'} Q_{\theta^-}(s',a') - Q_\theta(s,a)\right)^2\right] ]

Principais estabilizadores (todos motivados pelas propriedades do aprendizado TD):

• Redes-alvo (target networks) (Q_{\theta^-}): parâmetros que mudam lentamente para o alvo de bootstrap reduzem laços de realimentação.
• Replay de experiência (experience replay): quebra a correlação no fluxo de dados e melhora a eficiência amostral.
• Variantes do algoritmo (Double DQN, Dueling Networks) refinam como o alvo TD é computado para reduzir o viés de superestimação.

---

Traços de elegibilidade em controle (breve orientação)

Traços de elegibilidade também podem ser usados para controle:

• SARSA((\lambda)): controle on-policy com traços.
• Q((\lambda)) de Watkins (Watkins’s Q((\lambda))): um método de traços off-policy que trunca traços quando ações não gulosas são tomadas (para preservar a correção off-policy).
• Abordagens mais modernas podem usar retornos de (n) passos (por exemplo, em RL profundo distribuído) em vez de traços explícitos, mas a ideia subjacente — misturar alvos multi-passos — é intimamente relacionada.

---

Convergência e considerações práticas

Convergência tabular (visão de alto nível)

No cenário tabular, a avaliação de política com TD(0) converge sob suposições padrão como:

• exploração suficiente (cada estado visitado infinitas vezes no limite)
• tamanhos de passo satisfazem condições de Robbins–Monro (por exemplo, (\alpha_t) decrescente com (\sum \alpha_t = \infty), (\sum \alpha_t^2 < \infty))

Métodos de controle têm suas próprias condições; por exemplo, Q-learning converge para (Q^*) no caso tabular com exploração e cronogramas de taxa de aprendizado apropriados.

Escolhendo \(\gamma\), \(\alpha\) e \(\lambda\)

• Desconto (\gamma):
  Valores mais altos fazem o agente valorizar recompensas de longo prazo, mas podem desacelerar o aprendizado e aumentar a variância. Muitas tarefas episódicas usam (0.95)–(0.99); tarefas contínuas podem exigir um escalonamento cuidadoso de recompensas.
• Taxa de aprendizado (\alpha):
  Muito alta pode causar instabilidade; muito baixa desacelera o aprendizado. Com redes neurais, (\alpha) frequentemente é controlada por um otimizador (Adam, RMSProp), mas as mesmas preocupações de estabilidade permanecem.
• Decaimento do traço (\lambda):
  (\lambda=0) é míope, mas estável/baixa variância; (\lambda\approx 1) propaga crédito por longas distâncias, mas se aproxima da variância de MC. Valores como 0.8–0.97 são pontos de partida comuns na prática, mas dependem da tarefa.

Estados terminais

Para transições terminais, o termo de bootstrap deve desaparecer:

• trate (V(\text{terminal}) = 0) e (Q(\text{terminal},\cdot)=0)
• ou pule explicitamente o termo (\gamma V(s_{t+1})) quando done=True

---

Aplicações práticas do aprendizado TD

O aprendizado TD é amplamente usado sempre que é necessário estimar resultados de longo prazo a partir de interação em fluxo contínuo:

• Robótica: aprender funções de valor para navegação/manipulação; frequentemente como o crítico em Métodos Ator-Crítico.
• Jogos: muitos agentes que jogam dependem de atualizações TD (do clássico TD-Gammon ao RL profundo moderno).
• Operações e escalonamento: aprender custos e benefícios de longo prazo (por exemplo, filas, estoque).
• Sistemas de recomendação / cenários tipo bandit com recompensas atrasadas: métodos TD ajudam a atribuir crédito ao longo de sequências de interações do usuário.
• Finanças e controle: aprender estimativas de valor sob incerteza (com tratamento cuidadoso de não estacionariedade e risco).

---

Resumo

• Aprendizado TD atualiza estimativas de valor usando alvos com bootstrap, não retornos completos.
• O erro TD (\delta_t = r_{t+1} + \gamma V(s_{t+1}) - V(s_t)) é o sinal central que impulsiona o aprendizado.
• TD(0) realiza atualizações com bootstrap de um passo; TD de (n) passos e TD((\lambda)) estendem isso para atribuição de crédito em múltiplos passos.
• Traços de elegibilidade (TD((\lambda))) propagam eficientemente erros TD para trás através de estados visitados recentemente.
• SARSA e Q-learning são algoritmos de controle TD; SARSA é on-policy, Q-learning é off-policy.
• Na prática moderna, o aprendizado TD é fundamental para métodos de RL profundo e arquiteturas ator-crítico, mas deve ser tratado com cuidado com aproximação de função e aprendizado off-policy devido a preocupações de estabilidade.

Se você quiser, posso adicionar um mini-exemplo resolvido (por exemplo, predição em caminhada aleatória com TD(0) vs TD((\lambda))) ou uma implementação de referência compacta mostrando SARSA e Q-learning lado a lado.

---