Phase 09 - Lesson 03

Métodos de Monte Carlo — Aprendizaje a partir de Episodios Completos

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

La programación dinámica necesita un modelo. Monte Carlo no necesita nada más que episodios. Ejecuta la política, observa los retornos, calcula su promedio. La idea más simple en RL, y la que desbloquea todo lo que viene después.

Tipo: Build Idiomas: Python Prerrequisitos: Fase 9 · 01 (MDPs), Fase 9 · 02 (Programación Dinámica) Tiempo: ~75 minutos

El Problema

La programación dinámica es elegante, pero asume que puedes consultar P(s' | s, a) para cada estado y acción. Casi nada en el mundo real funciona de esa manera. Un robot no puede calcular analiticamente la distribución sobre los píxeles de la cámara después de un torque en la articulación. Un algoritmo de fijación de precios no puede integrar sobre cada reacción posible del cliente. Un LLM no puede enumerar todas las continuaciones posibles después de un token.

Necesitas un método que solo requiera la capacidad de muestrear del entorno. Ejecuta la política. Obtén una trayectoria s_0, a_0, r_1, s_1, a_1, r_2, …, s_T. Úsala para estimar valores. Eso es Monte Carlo.

El cambio de DP a MC es filosóficamente importante: pasamos de modelo conocido + actualización exacta (exact backup) a rollouts muestreados + retorno promedio. La varianza aumenta, pero la aplicabilidad explota. Cada algoritmo de RL después de esta lección — TD, Q-learning, REINFORCE, PPO, GRPO — es un estimador de Monte Carlo en el fondo, a veces con bootstrapping estructurado encima.

El Concepto

La idea central, en una línea: V^π(s) = E_π[G_t | s_t = s] ≈ (1/N) Σ_i G^{(i)}(s) donde G^{(i)}(s) son los retornos observados después de las visitas a s bajo la política π.

MC de primera visita (first-visit) vs cada visita (every-visit). Dado un episodio que visita el estado s múltiples veces, el MC de primera visita solo cuenta el retorno de la primera visita; el MC de cada visita cuenta todas las visitas. Ambos son insesgados en el límite. El de primera visita es más simple de analizar (muestras iid). El de cada visita utiliza más datos por episodio y normalmente converge más rápido en la práctica.

Media incremental. En lugar de almacenar todos los retornos, actualiza el promedio móvil:

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

Reorganiza: V_new = V_old + α · (target - V_old) con α = 1/n. Cambia 1/n por un tamaño de paso constante α ∈ (0, 1) y obtendrás un estimador MC no estacionario que rastrea los cambios en π. Ese movimiento es todo el salto de MC a TD y a cada algoritmo de RL moderno.

La exploración ahora es un problema. DP tocaba cada estado por enumeración. MC solo ve los estados que visita la política. Si π es determinista, regiones enteras del espacio de estados nunca se muestrean y sus estimaciones de valor permanecen en cero para siempre. Tres soluciones, en orden histórico:

1. Inicios exploratorios (exploring starts). Comienza cada episodio desde un par (s, a) aleatorio. Garantiza cobertura; poco práctico en la vida real (no puedes "reiniciar" un robot en un estado arbitrario).
2. ε-greedy. Actúa de forma codiciosa (greedy) con respecto al Q actual, pero con probabilidad ε elige una acción aleatoria. Todos los pares estado-acción se muestrean de forma asintótica.
3. MC fuera de la política (off-policy). Recopila datos bajo una política de comportamiento μ, aprende sobre la política objetivo π a través de muestreo por importancia. Alta varianza, pero es el puente hacia los métodos de buffer de repetición (replay buffer) como DQN.

Control de Monte Carlo. Evaluar → mejorar → evaluar, al igual que la iteración de políticas, pero la evaluación se basa en muestreo:

1. Ejecuta π, obtén un episodio.
2. Actualiza Q(s, a) a partir de los retornos observados.
3. Haz que π sea ε-greedy con respecto a Q.
4. Repita.

Converge a Q* y π* con probabilidad 1 bajo condiciones moderadas (cada par visitado infinitamente, α satisface Robbins-Monro).

Constrúyelo

Paso 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

Sin modelo, solo env.reset() y env.step(s, a). La misma interfaz que un entorno gym pero simplificada.

Paso 2: calcular retornos (barrido inverso)

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))

Una sola pasada, O(T). La recurrencia hacia atrás G_t = r_{t+1} + γ G_{t+1} evita recalcular sumas.

Paso 3: evaluación MC de primera 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

Tres líneas hacen el trabajo: marcar el estado como visto en la primera visita, incrementar la cuenta, actualizar el promedio móvil.

Paso 4: control MC ε-greedy (en la 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

Paso 5: comparar con el estándar de oro de DP

Tu estimación MC de V^π debería coincidir con el resultado de DP de la Lección 02 a medida que los episodios → ∞. En la práctica: 50,000 episodios en GridWorld de 4×4 te acercan a ~0.1 de la respuesta de DP.

Dificultades

• Episodios infinitos. MC requiere que los episodios terminen. Si tu política puede entrar en un bucle infinito, limita max_steps y trata el límite como una falla implícita. GridWorld con una política aleatoria suele agotar el tiempo de espera (timeout); eso es normal, solo asegúrate de contarlo correctamente.
• Varianza. MC utiliza retornos completos. En episodios largos, la varianza es enorme: una sola recompensa desafortunada al final altera V(s_0) en la misma cantidad. Los métodos TD (Lección 04) reducen esto mediante bootstrapping.
• Cobertura de estados. MC codicioso (greedy) en un Q inicial con empates siempre intentará una sola acción. Debes explorar (ε-greedy, inicios exploratórios, UCB).
• Políticas no estacionarias. Si π cambia (como en el control MC), los retornos antiguos provienen de una política diferente. MC con α constante maneja esto; MC con promedio de muestras no.
• Muestreo por importancia fuera de la política (off-policy). Los pesos π(a|s)/μ(a|s) se multiplican a lo largo de una trayectoria. La varianza explota con el horizonte. Limítalo con IS ponderada por decisión o cambia a TD.

Casos de Uso

El papel de los métodos de Monte Carlo en 2026:

Los algoritmos modernos de deep-RL (PPO, SAC) interpolan entre MC puro (retornos completos) y TD puro (bootstrap de un paso) mediante retornos de n pasos o GAE. Ambos extremos son instancias del mismo estimador.

Envíalo

Guárdalo 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.

Ejercicios

1. Fácil. Implementa la evaluación MC de primera visita de la política aleatoria uniforme en GridWorld de 4×4. Ejecuta 10,000 episodios. Grafica V(0,0) en función del número de episodios en comparación con la respuesta de DP.
2. Medio. Implementa el control MC ε-greedy con ε ∈ {0.01, 0.1, 0.3}. Compara el retorno promedio después de 20,000 episodios. ¿Cómo se ve la curva? ¿Dónde reside la compensación (tradeoff) entre sesgo y varianza?
3. Difícil. Implementa MC fuera de la política (off-policy) con muestreo por importancia: recopila datos bajo la política aleatoria uniforme μ, estima V^π para la política óptima determinista π. Compara IS simple vs IS por decisión vs IS ponderada. ¿Cuál tiene menor varianza?

Términos Clave

Lecturas Adicionales

• Sutton & Barto (2018). Cap. 5 — Monte Carlo Methods — el tratamiento canónico.
• Singh & Sutton (1996). Reinforcement Learning with Replacing Eligibility Traces — análisis de primera visita vs cada visita.
• Precup, Sutton, Singh (2000). Eligibility Traces for Off-Policy Policy Evaluation — MC fuera de la política (off-policy) y control de varianza.
• Mahmood et al. (2014). Weighted Importance Sampling for Off-Policy Learning — estimadores IS modernos de baja varianza.
• Tesauro (1995). TD-Gammon, A Self-Teaching Backgammon Program — la primera demanstración empírica a gran escala de self-play de MC/TD convergiendo en un juego sobrehumano; precursor conceptual de cada lección en la segunda mitad de esta fase.