Phase 09 - Lesson 04

Diferença Temporal — Q-Learning & SARSA

This lesson includes a graded coding exercise that runs in your browser, unlocked with lifetime access.

O Monte Carlo espera até o fim do episódio. O TD atualiza a cada passo por meio de bootstrapping da próxima estimativa de valor. Q-learning é off-policy e otimista; SARSA é on-policy e cauteloso. Ambos são uma linha de código. Ambos fundamentam todos os métodos de deep RL nesta fase.

Tipo: Criar Linguagens: Python Pré-requisitos: Fase 9 · 01 (MDPs), Fase 9 · 02 (Programação Dinâmica), Fase 9 · 03 (Monte Carlo) Tempo: ~75 minutos

O Problema

O Monte Carlo funciona, mas tem duas exigências caras. Ele precisa de episódios que terminem e só atualiza depois que o retorno tempo final é obtido. Se o seu episódio tiver 1.000 passos, o MC espera 1.000 passos para atualizar qualquer coisa. Ele possui alta variância, baixo viés e é lento na prática.

A programação dinâmica tem o perfil oposto — atualizações via bootstrap com variância zero — mas exige um modelo conhecido.

O aprendizado por diferença temporal (TD) divide essa diferença. A partir de uma única transição (s, a, r, s'), forma-se um alvo de um passo r + γ V(s') e ajusta-se V(s) em direção a ele. Sem modelo. Sem episódios completos. Viés por usar um V aproximado no lado direito da equação, mas variância drasticamente menor que o MC e atualizações online desde o primeiro passo.

Este é o ponto de virada sobre o qual todo o RL moderno — DQN, A2C, PPO, SAC — gira. O restante da Fase 9 consiste em camadas de aproximação de funções e truques construídos sobre a atualização de TD de um passo que você escreverá nesta lição.

O Conceito

A atualização de TD(0) para V:

V(s) ← V(s) + α [r + γ V(s') - V(s)]

A quantidade entre colchetes é o erro de TD δ = r + γ V(s') - V(s). É o análogo online de G_t - V(s_t) no MC. A convergência exige que α satisfaça Robbins-Monro (Σ α = ∞, Σ α² < ∞) e que todos os estados sejam visitados infinitamente vezes.

Q-learning. Um método TD off-policy para controle:

Q(s, a) ← Q(s, a) + α [r + γ max_{a'} Q(s', a') - Q(s, a)]

O max assume que a política gulosa (greedy) será seguida de s' em diante, independentemente da ação que o agente realmente tome. Esse desacoplamento faz com que o Q-learning aprenda Q* enquanto o agente explora via ε-greedy. Mnih et al. (2015) converteram isso em deep Q-learning no Atari (Lição 05).

SARSA. Um método TD on-policy:

Q(s, a) ← Q(s, a) + α [r + γ Q(s', a') - Q(s, a)]

O nome vem da tupla (s, a, r, s', a'). O SARSA usa a ação a' que o agente realmente toma em seguida, e não o argmax guloso. Converge para Q^π para qualquer π ε-greedy que esteja rodando, o que no limite ε → 0 se torna Q*.

A diferença no cliff-walking. Na clássica tarefa de caminhada no penhasco (cliff-walking, onde cair do penhasco = recompensa -100), o Q-learning aprende o caminho ideal ao longo da borda do penhasco, mas ocasionalmente sofre a penalidade durante a exploração. O SARSA aprende um caminho mais seguro a um passo de distância do penhasco porque incorpora o ruído de exploração em seu valor Q. Com o treinamento, ambos alcançam o ideal quando ε → 0. Na prática isso importa: quando a exploração realmente ocorre na implantação, o comportamento do SARSA é mais conservador.

Expected SARSA. Substitui Q(s', a') por seu valor esperado sob π:

Q(s, a) ← Q(s, a) + α [r + γ Σ_{a'} π(a'|s') Q(s', a') - Q(s, a)]

Variância menor que a do SARSA (sem amostragem de a'), mesmo alvo on-policy. Frequentemente é o padrão nos livros didáticos modernos.

n-step TD e TD(λ). Interpola entre TD(0) e MC esperando n passos antes do bootstrapping. n=1 é TD, n=∞ é MC. O TD(λ) faz uma média sobre todos os n com pesos geométricos (1-λ)λ^{n-1}. A maior parte do deep RL usa n entre 3 e 20.

Construa

Passo 1: SARSA em política ε-greedy

def sarsa(env, episodes, alpha=0.1, gamma=0.99, epsilon=0.1):
    Q = defaultdict(lambda: {a: 0.0 for a in ACTIONS})

    def choose(s):
        if random() < epsilon:
            return choice(ACTIONS)
        return max(Q[s], key=Q[s].get)

    for _ in range(episodes):
        s = env.reset()
        a = choose(s)
        while True:
            s_next, r, done = env.step(s, a)
            a_next = choose(s_next) if not done else None
            target = r + (gamma * Q[s_next][a_next] if not done else 0.0)
            Q[s][a] += alpha * (target - Q[s][a])
            if done:
                break
            s, a = s_next, a_next
    return Q

Oito linhas. A única diferença para o Q-learning é a linha do alvo.

Passo 2: Q-learning

def q_learning(env, episodes, alpha=0.1, gamma=0.99, epsilon=0.1):
    Q = defaultdict(lambda: {a: 0.0 for a in ACTIONS})
    for _ in range(episodes):
        s = env.reset()
        while True:
            a = choose(s, Q, epsilon)
            s_next, r, done = env.step(s, a)
            target = r + (gamma * max(Q[s_next].values()) if not done else 0.0)
            Q[s][a] += alpha * (target - Q[s][a])
            if done:
                break
            s = s_next
    return Q

O max desacopla o alvo do comportamento. Esse único símbolo é a diferença entre on-policy e off-policy.

Passo 3: curvas de aprendizado

Monitore o retorno médio a cada 100 episódios. O Q-learning converge mais rápido em um GridWorld determinístico simples; o SARSA é mais conservador no cliff-walking. No GridWorld 4×4 em code/main.py, ambos ficam próximos do ideal após ~2.000 episódios com α=0.1, ε=0.1.

Passo 4: comparar com o gabarito de DP

Execute a iteração de valor (Lição 02) para obter Q*. Verifique max_{s,a} |Q_learned(s,a) - Q*(s,a)|. Um agente TD tabular saudável fica a menos de ~0.5 do ideal no GridWorld 4×4 após 10.000 episódios.

Armadilhas

• Os valores iniciais de Q importam. A inicialização otimista (Q = 0 para uma tarefa com recompensas negativas) incentiva a exploração. A inicialização pessimista pode prender uma política gulosa para sempre.
• Cronograma (schedule) de α. Um α constante é adequado para problemas não estacionários. O decaimento α_n = 1/n garante a convergência na teoria, mas é muito lento na prática — limite α no intervalo [0.05, 0.3] e monitore a curva de aprendizado.
• Cronograma (schedule) de ε. Comece alto (ε=1.0) e decaia até ε=0.05. "GLIE" (greedy in the limit with infinite exploration / guloso no limite com exploração infinita) é a condição de convergência.
• Viés de máximo no Q-learning. O operador max é tendencioso para cima quando Q é ruidoso. Isso leva à superestimativa — o Double Q-learning de Hasselt (usado pelo DDQN na Lição 05) corrige isso com duas tabelas Q.
• Episódios não terminativos. O TD pode aprender sem terminais, mas você precisa limitar os passos ou lidar corretamente com o bootstrap no limite. Padrão: trate o limite de passos como não terminal e continue fazendo o bootstrap.
• Hasteamento (hashing) de estados. Se os estados forem tuplas/tensores, use uma chave hashable (tupla, não lista; tupla de floats arredondados, não brutos).

Use-o

O panorama de TD em 2026:

Noventa por cento do "RL" sobre o qual você lê em artigos de 2026 é alguma elaboração de Q-learning ou SARSA. Compreenda a atualização tabular na prática antes de se aprofundar.

Envie

Salve como outputs/skill-td-agent.md:

---
name: td-agent
description: Pick between Q-learning, SARSA, Expected SARSA for a tabular or small-feature RL task.
version: 1.0.0
phase: 9
lesson: 4
tags: [rl, td-learning, q-learning, sarsa]
---

Given a tabular or small-feature environment, output:

1. Algorithm. Q-learning / SARSA / Expected SARSA / n-step variant. One-sentence reason tied to on-policy vs off-policy and variance.
2. Hyperparameters. α, γ, ε, decay schedule.
3. Initialization. Q_0 value (optimistic vs zero) and justification.
4. Convergence diagnostic. Target learning curve, `|Q - Q*|` check if DP is possible.
5. Deployment caveat. How will exploration behave at inference? Is SARSA's conservatism needed?

Refuse to apply tabular TD to state spaces > 10⁶. Refuse to ship a Q-learning agent without a max-bias caveat. Flag any agent trained with ε held at 1.0 throughout (no exploitation phase).

Exercícios

1. Fácil. Implemente o Q-learning e o SARSA no GridWorld 4×4. Plote as curvas de aprendizado (retorno médio a cada 100 episódios) para 2.000 episódios. Quem converge mais rápido?
2. Médio. Construa um ambiente de cliff-walking (4×12, onde a última linha é o penhasco com recompensa -100 e reinício no ponto inicial). Compare as políticas finais do Q-learning e do SARSA. Tire uma captura de tela dos caminhos que cada um percorre. Qual está mais próximo do penhasco?
3. Difícil. Implemente o Double Q-learning. Em um GridWorld com recompensa ruidosa (ruído gaussiano com σ=5 adicionado à recompensa por passo), mostre que o Q-learning superestima V*(0,0) por uma quantidade significativa, enquanto o Double Q-learning não.

Termos-Chave

Leitura Adicional

• Watkins & Dayan (1992). Q-learning — o artigo original e a prova de convergência.
• Sutton & Barto (2018). Ch. 6 — Temporal-Difference Learning — TD(0), SARSA, Q-learning, Expected SARSA.
• Hasselt (2010). Double Q-learning — correção para o viés de maximização.
• Seijen, Hasselt, Whiteson, Wiering (2009). A Theoretical and Empirical Analysis of Expected SARSA — motivação do expected SARSA.
• Rummery & Niranjan (1994). On-line Q-learning using connectionist systems — o artigo que cunhou o termo SARSA (então chamado de "modified connectionist Q-learning").
• Sutton & Barto (2018). Ch. 7 — n-step Bootstrapping — generaliza o TD(0) para TD(n), a transição do Q-learning para eligibility traces e, posteriormente, GAE no PPO.