Phase 09 - Lesson 03

Métodos de Monte Carlo — Aprendizado a partir de Episódios Completos

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

A programação dinâmica precisa de um modelo. Monte Carlo precisa de nada além de episódios. Execute a política, observe os retornos, faça a média deles. A ideia mais simples em RL — e aquela que desbloqueia tudo o que vem a seguir.

Tipo: Build Idiomas: Python Pré-requisitos: Fase 9 · 01 (MDPs), Fase 9 · 02 (Programação Dinâmica) Tempo: ~75 minutos

O Problema

A programação dinâmica é elegante, mas assume que você pode consultar P(s' | s, a) para cada estado e ação. Quase nada no mundo real funciona dessa forma. Um robô não pode calcular analiticamente a distribuição sobre os pixels da câmera após um torque na junta. Um algoritmo de precificação não pode integrar sobre cada reação possível do cliente. Um LLM não pode enumerar todas as continuações possíveis após um token.

Você precisa de um método que precise apenas da capacidade de amostrar do ambiente. Execute a política. Obtenha uma trajetória s_0, a_0, r_1, s_1, a_1, r_2, …, s_T. Use-a para estimar valores. Isso é Monte Carlo.

A mudança de DP para MC é filosoficamente importante: passamos de modelo conhecido + backup exato para rollouts amostrados + retorno médio. A variância aumenta, mas a aplicabilidade explode. Cada algoritmo de RL após esta lição — TD, Q-learning, REINFORCE, PPO, GRPO — é um estimador de Monte Carlo no fundo, às vezes com bootstrapping adicionado por cima.

O Conceito

A ideia central, em uma linha: V^π(s) = E_π[G_t | s_t = s] ≈ (1/N) Σ_i G^{(i)}(s) onde G^{(i)}(s) são os retornos observados após as visitas a s sob a política π.

MC de primeira visita (first-visit) vs cada visita (every-visit). Dado um episódio que visita o estado s múltiplas vezes, o MC de primeira visita conta apenas o retorno da primeira visita; o MC de cada visita conta todas as visitas. Ambos são não viesados no limite. O de primeira visita é mais simples de analisar (amostras iid). O de cada visita usa mais dados por episódio e normalmente converge mais rápido na prática.

Média incremental. Em vez de armazenar todos os retornos, atualize a média móvel:

V_n(s) = V_{n-1}(s) + (1/n) [G_n - V_{n-1}(s)]

Reorganize: V_new = V_old + α · (target - V_old) com α = 1/n. Troque 1/n por um tamanho de passo constante α ∈ (0, 1) e você obterá um estimador MC não estacionário que rastreia mudanças em π. Esse movimento é todo o salto de MC para TD e para cada algoritmo de RL moderno.

A exploração agora é um problema. A DP tocava todos os estados por enumeração. O MC só vê os estados que a política visita. Se π for determinística, regiões inteiras do espaço de estados nunca serão amostradas, e suas estimativas de valor permanecerão em zero para sempre. Três soluções, em ordem histórica:

1. Inícios exploratórios (exploring starts). Inicie cada episódio a partir de um par (s, a) aleatório. Garante cobertura; irrealista na prática (você não pode "resetar" um robô em um estado arbitrário).
2. ε-greedy. Agir de forma gulosa (greedy) em relação ao Q atual, mas com probabilidade ε escolher uma ação aleatória. Todos os pares estado-ação são amostrados de forma assintótica.
3. MC fora da política (off-policy). Colete dados sob uma política de comportamento μ, aprenda sobre a política alvo π via amostragem por importância. Variância alta, mas é a ponte para métodos de buffer de replay como DQN.

Controle de Monte Carlo. Avaliar → melhorar → avaliar, assim como na iteração de política, mas a avaliação é baseada em amostragem:

1. Execute π, obtenha um episódio.
2. Atualize Q(s, a) a partir dos retornos observados.
3. Torne π ε-greedy em relação a Q.
4. Repita.

Converge para Q* e π* com probabilidade 1 sob condições brandas (cada par visitado infinitamente, α satisfaz Robbins-Monro).

Construa

Passo 1: rollout → lista de (s, a, r)

def rollout(env, policy, max_steps=200):
    trajectory = []
    s = env.reset()
    for _ in range(max_steps):
        a = policy(s)
        s_next, r, done = env.step(s, a)
        trajectory.append((s, a, r))
        s = s_next
        if done:
            break
    return trajectory

Sem modelo, apenas env.reset() and env.step(s, a). Mesma interface de um ambiente gym, mas simplificada.

Passo 2: calcular retornos (varredura reversa)

def returns_from(trajectory, gamma):
    returns = []
    G = 0.0
    for _, _, r in reversed(trajectory):
        G = r + gamma * G
        returns.append(G)
    return list(reversed(returns))

Uma única passagem, O(T). A recorrência para trás G_t = r_{t+1} + γ G_{t+1} evita recalcular somas.

Passo 3: avaliação MC de primeira visita

def mc_policy_evaluation(env, policy, episodes, gamma=0.99):
    V = defaultdict(float)
    counts = defaultdict(int)
    for _ in range(episodes):
        trajectory = rollout(env, policy)
        returns = returns_from(trajectory, gamma)
        seen = set()
        for t, ((s, _, _), G) in enumerate(zip(trajectory, returns)):
            if s in seen:
                continue
            seen.add(s)
            counts[s] += 1
            V[s] += (G - V[s]) / counts[s]
    return V

Três linhas fazem o trabalho: marcar o estado como visto na primeira visita, incrementar a contagem, atualizar a média móvel.

Passo 4: controle MC ε-greedy (na política / on-policy)

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

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

    for _ in range(episodes):
        trajectory = rollout(env, policy)
        returns = returns_from(trajectory, gamma)
        seen = set()
        for (s, a, _), G in zip(trajectory, returns):
            if (s, a) in seen:
                continue
            seen.add((s, a))
            counts[s][a] += 1
            Q[s][a] += (G - Q[s][a]) / counts[s][a]
    return Q, policy

Passo 5: comparar com o padrão-ouro de DP

Sua estimativa MC de V^π deve concordar com o resultado de DP da Lição 02 à medida que os episódios → ∞. Na prática: 50.000 episódios no GridWorld 4×4 aproximam você de ~0.1 da resposta de DP.

Armadilhas

• Episódios infinitos. O MC exige que os episódios terminem. Se a sua política puder entrar em loop infinito, limite max_steps e trate o limite como uma falha implícita. O GridWorld com uma política aleatória costuma estourar o tempo (timeout) — isso é normal, apenas certifique-se de contar isso corretamente.
• Variância. O MC usa retornos completos. Em episódios longos, a variância é enorme — uma única recompensa azarada no final altera V(s_0) pela mesma quantidade. Os métodos TD (Lição 04) reduzem isso usando bootstrapping.
• Cobertura de estados. O MC guloso (greedy) em um Q inicial com empates sempre tentará apenas uma ação. Você deve explorar (ε-greedy, inícios exploratórios, UCB).
• Políticas não estacionárias. Se π mudar (como no controle MC), os retornos antigos serão de uma política diferente. O MC com α constante lida com isso; o MC com média amostral não.
• Amostragem por importância fora da política (off-policy). Os pesos π(a|s)/μ(a|s) se multiplicam ao longo de uma trajetória. A variância explode com o horizonte. Limite com IS ponderada por decisão ou mude para TD.

Casos de Uso

O papel dos métodos de Monte Carlo em 2026:

Algoritmos modernos de deep-RL (PPO, SAC) interpolam entre MC puro (retornos completos) e TD puro (bootstrap de um passo) via retornos de n passos ou GAE. Ambos os extremos são instâncias do mesmo estimador.

Envie

Salve como outputs/skill-mc-evaluator.md:

---
name: mc-evaluator
description: Evaluate a policy via Monte Carlo rollouts and produce a convergence report with DP-comparison if available.
version: 1.0.0
phase: 9
lesson: 3
tags: [rl, monte-carlo, evaluation]
---

Given an environment (episodic, with reset+step API) and a policy, output:

1. Method. First-visit vs every-visit MC. Reason.
2. Episode budget. Target number, variance diagnostic, expected standard error.
3. Exploration plan. ε schedule (if needed) or exploring starts.
4. Gold-standard comparison. DP-optimal V* if tabular; otherwise a bound from a Q-learning / PPO baseline.
5. Termination check. Max-step cap, timeouts, handling of non-terminating trajectories.

Refuse to run MC on non-episodic tasks without a finite horizon cap. Refuse to report V^π estimates from fewer than 100 episodes per state for tabular tasks. Flag any policy with zero-variance actions as an exploration risk.

Exercícios

1. Fácil. Implemente a avaliação MC de primeira visita da política uniforme-aleatória no GridWorld 4×4. Execute 10.000 episódios. Plote V(0,0) como uma função da contagem de episódios em comparação com a resposta de DP.
2. Médio. Implemente o controle MC ε-greedy com ε ∈ {0.01, 0.1, 0.3}. Compare o retorno médio após 20.000 episódios. Como é a aparência da curva? Onde reside o tradeoff de viés-variância?
3. Difícil. Implemente o MC fora da política (off-policy) com amostragem por importância: colete dados sob a política uniforme-aleatória μ, estime V^π para a política ótima determinística π. Compare IS simples vs IS por decisão vs IS ponderada. Qual delas tem a menor variância?

Termos-Chave

Leituras Adicionais

• Sutton & Barto (2018). Cap. 5 — Monte Carlo Methods — o tratamento canônico.
• Singh & Sutton (1996). Reinforcement Learning with Replacing Eligibility Traces — análise de primeira visita vs cada visita.
• Precup, Sutton, Singh (2000). Eligibility Traces for Off-Policy Policy Evaluation — MC fora da política (off-policy) e controle de variância.
• Mahmood et al. (2014). Weighted Importance Sampling for Off-Policy Learning — estimadores IS modernos de baixa variância.
• Tesauro (1995). TD-Gammon, A Self-Teaching Backgammon Program — a primeira demonstração empírica em grande escala do self-play de MC/TD convergindo para um jogo sobre-humano; precursor conceitual de cada lição na segunda metade desta fase.