Phase 09 - Lesson 01

MDPs, Estados, Acciones & Recompensas

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

Un Proceso de Decisión de Markov consta de cinco elementos: estados, acciones, transiciones, recompensas y un factor de descuento. Todo en RL — Q-learning, PPO, DPO, GRPO — se optimiza sobre esta estructura. Apréndelo una vez y comprenderás el resto del aprendizaje por refuerzo fácilmente.

Tipo: Aprender Idiomas: Python Prerrequisitos: Fase 1 · 06 (Probabilidad & Distribuciones), Fase 2 · 01 (Taxonomía de ML) Tiempo: ~45 minutos

El Problema

Estás escribiendo un bot de ajedrez. O un planificador de inventario. O un agente de trading. O el bucle PPO que entrena un modelo de razonamiento. Cuatro dominios diferentes, un dato sorprendente: los cuatro se reducen al mismo objeto matemático.

El aprendizaje supervisado te da pares (x, y) y te pide ajustar una función. El aprendizaje por refuerzo no te da etiquetas, solo un flujo de estados, las acciones que tomaste y una recompensa escalar. ¿El movimiento ganó la partida? ¿La decisión de reabastecimiento ahorró dinero? ¿La transacción generó ganancias? ¿El token que el LLM acaba de producir condujo a una mayor recompensa del juez?

No puedes aprender de este flujo hasta que lo formalices. "Lo que vi", "lo que hice", "lo que pasó después", "qué tan bueno fue eso" — cada uno debe convertirse en un objeto sobre el cual puedas razonar. Esa formalización es un Proceso de Decisión de Markov. Cada algoritmo de RL en esta fase, incluyendo los bucles de RLHF y GRPO al final, se optimiza sobre esta estructura.

El Concepto

Los cinco objetos.

• Estados S. Todo lo que el agente necesita para decidir. En GridWorld, la celda. En ajedrez, el tablero. En un LLM, la ventana de contexto más cualquier memoria.
• Acciones A. Las elecciones. Mover hacia arriba/abajo/izquierda/derecha. Realizar una jugada. Emitir un token.
• Transiciones P(s' | s, a). Dado el estado s y la acción a, la distribución sobre el siguiente estado. Determinista en ajedrez, estocástica en inventario, casi determinista en la decodificación de LLM.
• Recompensas R(s, a, s'). La señal escalar. Victoria = +1, derrota = -1. Ingresos menos costos. El término de la razón de log-verosimilitud en GRPO.
• Descuento γ ∈ [0, 1). Cuánto cuenta la recompensa futura frente a la presente. γ = 0.99 define un horizonte de ~100 pasos; γ = 0.9 define ~10.

La propiedad de Markov P(s_{t+1} | s_t, a_t) = P(s_{t+1} | s_0, a_0, …, s_t, a_t). El futuro depende solo del estado presente. Si no es así, la representación del estado está incompleta; no es una falla del método, sino una falla del estado.

Políticas y retornos. Una política π(a | s) mapeia estados a distribuciones de acciones. El retorno G_t = r_t + γ r_{t+1} + γ² r_{t+2} + … es la suma descontada de las recompensas futuras. El valor V^π(s) = E[G_t | s_t = s] es el retorno esperado comenzando desde s bajo la política π. El valor Q Q^π(s, a) = E[G_t | s_t = s, a_t = a] es el retorno esperado comenzando con una acción específica. Cada algoritmo de RL estima uno de estos dos y luego mejora π en consecuencia.

Las ecuaciones de Bellman. Las ecuaciones de punto fijo que todo en esta fase utiliza:

V^π(s) = Σ_a π(a|s) Σ_{s', r} P(s', r | s, a) [r + γ V^π(s')] Q^π(s, a) = Σ_{s', r} P(s', r | s, a) [r + γ Σ_{a'} π(a'|s') Q^π(s', a')]

Estas dividen el retorno esperado en "la recompensa de este paso" más el "valor descontado de donde aterrizas". Recursivo. Cada algoritmo de la Fase 9 itera esta ecuación hasta la convergencia (programación dinámica), toma muestras de ella (Monte Carlo) o realiza un bootstrap de un paso (diferencia temporal).

Constrúyelo

Paso 1: un pequeño MDP determinista

Un GridWorld de 4×4. El agente comienza arriba a la izquierda, el estado terminal está abajo a la derecha, la recompensa es de -1 por paso y las acciones son {up, down, left, right}. Consulta code/main.py.

GRID = 4
TERMINAL = (3, 3)
ACTIONS = {"up": (-1, 0), "down": (1, 0), "left": (0, -1), "right": (0, 1)}

def step(state, action):
    if state == TERMINAL:
        return state, 0.0, True
    dr, dc = ACTIONS[action]
    r, c = state
    nr = min(max(r + dr, 0), GRID - 1)
    nc = min(max(c + dc, 0), GRID - 1)
    return (nr, nc), -1.0, (nr, nc) == TERMINAL

Cinco líneas. Ese es el entorno completo. Transiciones deterministas, penalización constante por paso, estado terminal absorbente.

Paso 2: ejecutar (rollout) una política

Una política es una función de un estado a una distribución de acciones. La más simple: aleatoria uniforme.

def uniform_policy(state):
    return {a: 0.25 for a in ACTIONS}

def rollout(policy, max_steps=200):
    s, total, steps = (0, 0), 0.0, 0
    for _ in range(max_steps):
        a = sample(policy(s))
        s, r, done = step(s, a)
        total += r
        steps += 1
        if done:
            break
    return total, steps

Ejecuta la política aleatoria 1000 veces. El retorno promedio está alrededor de -60 a -80 para este tablero de 4×4. El retorno óptimo es -6 (camino en línea recta hacia abajo y a la derecha). Cerrar esa brecha lo es todo en la Fase 9.

Paso 3: calcular V^π exactamente a través de la ecuación de Bellman

Para MDPs pequeños, la ecuación de Bellman es un sistema lineal. Enumera los estados, aplica la expectativa y realiza iteraciones hasta que los valores dejen de cambiar.

def policy_evaluation(policy, gamma=0.99, tol=1e-6):
    V = {s: 0.0 for s in all_states()}
    while True:
        delta = 0.0
        for s in all_states():
            if s == TERMINAL:
                continue
            v = 0.0
            for a, pi_a in policy(s).items():
                s_next, r, _ = step(s, a)
                v += pi_a * (r + gamma * V[s_next])
            delta = max(delta, abs(v - V[s]))
            V[s] = v
        if delta < tol:
            return V

Esta es la evaluación de política iterativa. Es el primer algoritmo en Sutton & Barto y la base teórica de cada método de RL que le sigue.

Paso 4: γ es un hiperparámetro con significado físico

El horizonte efectivo es aproximadamente 1 / (1 - γ). γ = 0.9 → 10 pasos. γ = 0.99 → 100 pasos. γ = 0.999 → 1000 pasos.

Demasiado bajo y el agente actúa de manera miope. Demasiado alto y la asignación de crédito se vuelve ruidosa, porque muchos pasos tempranos comparten la responsabilidad de la recompensa en el futuro lejano. El RLHF para LLMs típicamente usa γ = 1 porque los episodios son cortos y acotados. Las tareas de control usan 0.95–0.99. Los juegos de estrategia de horizonte largo usan 0.999.

Errores Comunes

• Estado no Markoviano. Si necesitas las últimas tres observaciones para decidir, el "estado" no es solo la observación actual. Solución: apilar fotogramas (DQN en Atari apila 4) o usar un estado recurrente (LSTM/GRU sobre las observaciones).
• Recompensas dispersas. Las recompensas que solo se otorgan al ganar hacen que el aprendizaje sea casi imposible en espacios de estados grandes. Diseña recompensas (señal intermedia) o inicia con imitación (Fase 9 · 09).
• Hackeo de recompensa (Reward hacking). Optimizar una recompensa proxy a menudo produce un comportamiento patológico. El agente de carreras de botes de OpenAI daba vueltas en círculos recolectando potenciadores (power-ups) indefinidamente en lugar de terminar la carrera. Siempre define la recompensa en función del resultado objetivo, no de la proxy.
• Especificación incorrecta del descuento. γ = 1 en una tarea de horizonte infinito hace que todos los valores sean infinitos. Limita siempre mediante un horizonte finito o γ < 1.
• Escala de recompensa. Las recompensas de {+100, -100} frente a {+1, -1} dan políticas óptimas idénticas pero magnitudes de gradiente muy diferentes. Normaliza a un rango cercano a [-1, 1] antes de introducirlas en PPO/DQN.

Úsalo

La tecnología de 2026 reduce cada flujo de RL a un MDP antes de tocar el código:

Escribe las cinco tuplas antes de programar cualquier bucle de entrenamiento. La mayoría de los informes de errores del tipo "RL no funciona" se deben a una formulación de MDP que ya estaba incorrecta en papel.

Entregar

Salve como outputs/skill-mdp-modeler.md:

---
name: mdp-modeler
description: Given a task description, produce a Markov Decision Process spec and flag formulation risks before training.
version: 1.0.0
phase: 9
lesson: 1
tags: [rl, mdp, modeling]
---

Given a task (control / game / recommendation / LLM fine-tuning), output:

1. State. Exact feature vector or tensor spec. Justify Markov property.
2. Action. Discrete set or continuous range. Dimensionality.
3. Transition. Deterministic, stochastic-with-known-model, or sample-only.
4. Reward. Function and source. Sparse vs shaped. Terminal vs per-step.
5. Discount. Value and horizon justification.

Refuse to ship any MDP where the state is non-Markovian without explicit mention of frame-stacking or recurrent state. Refuse any reward that was not defined in terms of the target outcome. Flag any `γ ≥ 1.0` on an infinite-horizon task. Flag any reward range >100x the typical step reward as a likely gradient-explosion source.

Ejercicios

1. Fácil. Implementa el GridWorld de 4×4 y el rollout de la política aleatoria en code/main.py. Ejecuta 10,000 episodios. Informa la media y la desviación estándar del retorno. Compáralo con el retorno óptimo (-6).
2. Medio. Ejecuta policy_evaluation con γ ∈ {0.5, 0.9, 0.99} para la política aleatoria uniforme. Imprime V como una cuadrícula de 4×4 para cada uno. Explica por que los valores de estado cerca del terminal crecen más rápido con un γ mayor.
3. Difícil. Haz que el GridWorld sea estocástico: cada acción se desvía a una dirección adyacente con una probabilidad de p = 0.1. Reevalúa la política uniforme. ¿V[start] mejora o empeora? ¿Por qué?

Términos Clave

Lecturas Recomendadas

• Sutton & Barto (2018). Reinforcement Learning: An Introduction, 2nd ed. — el libro de texto. El Cap. 3 cubre los MDPs y las ecuaciones de Bellman; el Cap. 1 fundamenta la hipótesis de recompensa que subyace en cada lección subsiguiente.
• Bellman (1957). Dynamic Programming — el origen de la ecuación de Bellman.
• OpenAI Spinning Up — Part 1: Key Concepts — introducción concisa a los MDP desde la perspectiva del aprendizaje por refuerzo profundo (deep-RL).
• Puterman (2005). Markov Decision Processes — la referencia de investigación de operaciones sobre MDPs y métodos de solución exacta.
• Littman (1996). Algorithms for Sequential Decision Making (PhD thesis) — la derivación más clara de los MDPs como una especialización de la programación dinámica.