Phase 09: Reinforcement Learning

Métodos de Monte Carlo Aprender com Episódios Completos

Type: Build

Languages: Python

Prerequisites: Phase 9 · 01 (MDPs), Phase 9 · 02 (Dynamic Programming)

Time: ~75 minutes

O problema

A programação dinâmica é elegante, mas assume que você pode fazer perguntas.P(s' | s, a)O sistema de preços não pode ser integrado em todas as reações dos clientes possíveis. Um LLM não pode enumerar todas as possíveis continuações após um token.

É preciso um método que só precise da capacidade de "mostrar" do ambiente.s_0, a_0, r_1, s_1, a_1, r_2, …, s_T- Usa-o para estimar valores.

A mudança de DP para MC é filosóficamente importante: passamos de modelo conhecido + backup exato para rollouts amostragados + retorno médio. A variância salta, mas a aplicabilidade explode.

O conceito

!Monte Carlo: rollout, compute returns, average; first-visit vs every-visit

The core idea, in one line: V^π(s) = E_π[G_t | s_t = s] ≈ (1/N) Σ_i G^{(i)}(s)ondeG^{(i)}(s)são observados os retornos após as visitas a sPolíticaπ- Não .

First-visit vs every-visit MC.Dado um episódio que visita o estadosMultiplicas vezes, a primeira visita MC só conta o retorno da primeira visita; cada visita MC conta todas as visitas. Ambas são imparciais no limite. A primeira visita é mais fácil de analisar (mostras de ID).

Incremental mean.Em vez de armazenar todos os resultados, atualize a média de execução:

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

Reorganizar: V_new = V_old + α · (target - V_old)comα = 1/n- Troca .1/npara um passo-dimensional constante α ∈ (0, 1)e obtém um estimador de MC não estacionário que acompanha as mudanças emπEsse movimento é o salto completo de MC para TD para todos os algoritmos RL modernos.

Exploration is now a problem.O DP tocou todos os estados por enumeração.πAs regiões inteiras do espaço do estado nunca são amostragadas e as estimativas de valor permanecem em zero para sempre.

1. Exploring starts.Comece cada episódio a partir de um par aleatório (s, a). Garante cobertura; irrealista na prática (você não pode "reset" um robô em um estado arbitrário).
2. ε-greedy.Ator ganancioso W.R.T. corrente Q, mas com probabilidade εTodos os pares de estado-ação são amostragados assintoticamente.
3. Off-policy MC.Recolher dados sob uma política de comportamento μ, aprender sobre a política de alvo πÉ uma grande variância, mas é a ponte para métodos de repetição como o DQN.

Monte Carlo Control.Avaliação → melhoria → avaliação, assim como a iteração da política, mas a avaliação é baseada em amostragem:

1. Corra .π- Não, não.
2. Atualização Q(s, a)de retornos observados.
3. FaçaπÉ-avidito W.R.T.Q- Não .
4. Repito. - Não.

Converge para QE ...πcom probabilidade 1 em condições leves (cada par visitado com infinita frequência, αsatisfaz Robbins-Monro).

Construí-lo

Passo 1: lançamento → lista de (s, a, r)

pythonCopydef 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

Não há modelo, só env.reset()E ...env.step(s, a)A mesma interface que um ambiente de ginásio, mas despojado.

Passo 2: Retorno de cálculo (varagem inversa)

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

Um passe,O(T)A recorrência retrógrada .G_t = r_{t+1} + γ G_{t+1}Evita a somação.

Passo 3: Avaliação do MC na primeira visita

pythonCopydef 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 visto na primeira visita, contar os incrementos, atualizar a média de execução.

Passo 4: controlo do MC ganancioso (na política)

pythonCopydef 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: comparação com o padrão de ouro DP

A sua estimativa do MC deV^πDevem concordar com o resultado do DP da lição 02 como episódios → ∞. Na prática: 50.000 episódios em 4×4 GridWorld o leva dentro de ~0.1da resposta DP.

Encurralagens

• Infinite episodes.MC requer episódios para acabar. Se a sua política pode circular para sempre, cap.max_stepsGridWorld com uma política aleatória rotineiramente vezes fora que é normal, só certifique-se de contar corretamente.
• Variance.MC usa retornos completos. Em longos episódios, a variação é enorme uma recompensa infeliz no final dos turnos V(s_0)O método TD (Lessão 04) reduziu isto através do bootstrapping.
• State coverage.O MC ganancioso num Q fresco com laços só vai tentar uma ação.
• Non-stationary policies.SeπA taxa de variação de dados é de uma taxa de variação de dados, mas a taxa de variação de dados é de uma taxa de variação de dados.
• Off-policy importance sampling.Os pesos .π(a|s)/μ(a|s)A variância explode com o horizonte. O limite com IS ponderado por decisão ou a transição para TD.

Usá-lo

O papel dos métodos Monte Carlo em 2026:

Os algoritmos modernos de deep-RL (PPO, SAC) interpolam entre MC puro (retorno total) e TD puro (bootstrap de um passo) através de nOs dois pontos finais são exemplos do mesmo estimador.

Envia-o

Salva comooutputs/skill-mc-evaluator.md- Não .

markdownCopy---
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. Easy.Implementar a avaliação de MC de primeira visita da política uniforme-aleatória no 4×4 GridWorld.V(0,0)como função da contagem de episódios contra a resposta DP.
2. Medium.Implementar o controlo do MC com ε ∈ {0.01, 0.1, 0.3}Comparar o retorno médio após 20.000 episódios.
3. Hard.Implementar oft-policy MC com amostragem de importância: recolher dados sob política uniforme aleatória μ, estimativa V^πpara a política determinista ideal πComparar simples IS vs. por decisão IS vs. ponderado IS. Qual tem menor variância?

Termos-chave

Mais leitura

• Sutton & Barto (2018). Ch. 5 — Monte Carlo Methods o tratamento canónico.
• Singh & Sutton (1996). Reinforcement Learning with Replacing Eligibility Traces Análise de primeira visita versus cada visita.
• Precup, Sutton, Singh (2000). Eligibility Traces for Off-Policy Policy Evaluation MC e controlo de variações fora da política.
• Mahmood et al. (2014). Weighted Importance Sampling for Off-Policy Learning estimadores modernos de IS de baixa variação.
• Tesauro (1995). TD-Gammon, A Self-Teaching Backgammon Program a primeira demonstração empírica em larga escala de auto-jogo MC/TD convergindo para o jogo sobre-humano; precursor conceitual de cada lição na segunda metade desta fase.

This free lesson is part of the AI Engineering from Scratch curriculum. Read the full explanation, run the lesson code, and verify the result in the interactive reader or from the repository source.

Browse the complete course catalog or open this lesson on GitHub.