Phase 09 - Lesson 02

Programación Dinámica — Iteración de Políticas & Iteración de Valores

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

La programación dinámica es aprendizaje por refuerzo con trampa. Ya conoces las funciones de transición y recompensa; solo iteras la ecuación de Bellman hasta que V o π dejen de cambiar. Es el punto de referencia al que todo método basado en muestreo intenta aproximarse.

Type: Build Languages: Python Prerequisites: Phase 9 · 01 (MDPs) Time: ~75 minutos

El Problema

Tienes un MDP con un modelo conocido: puedes consultar P(s' | s, a) y R(s, a, s') para cualquier par estado-acción. Un administrador de inventario conoce la distribución de la demanda. Un juego de mesa tiene transiciones deterministas. Un gridworld son cuatro líneas de Python. Tienes un modelo.

El RL libre de modelo (Q-learning, PPO, REINFORCE) se inventó para el caso en el que no tienes un modelo: solo puedes tomar muestras del entorno. Pero cuando tienes uno, existen métodos mejores y más rápidos: la programación dinámica. Bellman los diseñó en 1957. Todavía definen la corrección: cuando la gente dice "política óptima para este MDP", se refiere a la política que devolvería la programación dinámica.

Los necesitas en 2026 por tres razones. Primero, cada entorno tabular en la investigación de RL (GridWorld, FrozenLake, CliffWalking) se resuelve con programación dinámica para producir la política estándar de oro. Segundo, los valores exactos te permiten depurar los métodos de muestreo: si la estimación de Q-learning para V*(s_0) difiere de la respuesta de programación dinámica en un 30%, tu Q-learning tiene un error. Tercero, el RL offline moderno y los métodos de planificación (MCTS, búsqueda de AlphaZero, RL basado en modelos en la Fase 9 · 10) iteran una actualización de Bellman sobre un modelo aprendido o dado.

El Concepto

Dos algoritmos, ambos de iteración de punto fijo en Bellman.

Policy iteration. Alterna dos pasos hasta que la política deja de cambiar.

1. Evaluación: dada la política π, calcula V^π aplicando repetidamente V(s) ← Σ_a π(a|s) Σ_{s',r} P(s',r|s,a) [r + γ V(s')] hasta que converja.
2. Mejora: dada V^π, haz que π sea codiciosa (greedy) con respecto a V^π: π(s) ← argmax_a Σ_{s',r} P(s',r|s,a) [r + γ V(s')].

La convergencia está garantizada porque (a) cada paso de mejora mantiene π igual o aumenta estrictamente V^π para algún estado, (b) el espacio de políticas deterministas es finito. Por lo general, converge en ~5–20 iteraciones externas, incluso para espacios de estados grandes.

Value iteration. Reduce la evaluación y la mejora a un solo recorrido. Aplica la ecuación de optimalidad de Bellman:

V(s) ← max_a Σ_{s',r} P(s',r|s,a) [r + γ V(s')]

Repite hasta que max_s |V_{new}(s) - V(s)| < ε. Extrae la política al final tomando la acción codiciosa (greedy). Estrictamente más rápido por iteración — sin bucle de evaluación interno —, pero normalmente requiere más iteraciones para converger.

Generalized policy iteration (GPI). El marco unificador. La función de valor y la política están bloqueadas en un bucle de mejora mutua; cualquier método que lleve a ambos hacia la coherencia mutua (iteración de valor asíncrona, iteración de política modificada, Q-learning, actor-critic, PPO) es una instancia de GPI.

Por qué importa γ < 1. El operador de Bellman es una γ-contracción en la norma del supremo: ||T V - T V'||_∞ ≤ γ ||V - V'||_∞. La contracción implica un punto fijo único y convergencia geométrica. Si eliminas γ < 1 pierdes la garantía: necesitas un horizonte finito o un estado terminal absorbente.

Construcción

Paso 1: construir el modelo MDP de GridWorld

Usa el mismo GridWorld de 4×4 de la Lección 01. Agregamos una variante estocástica: con una probabilidad de 0.1, el agente se desliza en una dirección perpendicular aleatoria.

SLIP = 0.1

def transitions(state, action):
    if state == TERMINAL:
        return [(state, 0.0, 1.0)]
    outcomes = []
    for direction, prob in action_probs(action):
        outcomes.append((apply_move(state, direction), -1.0, prob))
    return outcomes

transitions(s, a) devuelve una lista de (s', r, p). Este es el modelo completo.

Paso 2: evaluación de políticas

Dada una política π(s) = {action: prob}, itera la ecuación de Bellman hasta que V deje de cambiar:

def policy_evaluation(policy, gamma=0.99, tol=1e-6):
    V = {s: 0.0 for s in states()}
    while True:
        delta = 0.0
        for s in states():
            v = sum(pi_a * sum(p * (r + gamma * V[s_prime])
                              for s_prime, r, p in transitions(s, a))
                   for a, pi_a in policy(s).items())
            delta = max(delta, abs(v - V[s]))
            V[s] = v
        if delta < tol:
            return V

Paso 3: mejora de políticas

Reemplaza π con la política codiciosa (greedy) con respecto a V. Si π no cambió, regresa: estamos en el óptimo.

def policy_improvement(V, gamma=0.99):
    new_policy = {}
    for s in states():
        best_a = max(
            ACTIONS,
            key=lambda a: sum(p * (r + gamma * V[s_prime])
                              for s_prime, r, p in transitions(s, a)),
        )
        new_policy[s] = best_a
    return new_policy

Paso 4: unirlos

def policy_iteration(gamma=0.99):
    policy = {s: "up" for s in states()}   # arbitrary start
    for _ in range(100):
        V = policy_evaluation(lambda s: {policy[s]: 1.0}, gamma)
        new_policy = policy_improvement(V, gamma)
        if new_policy == policy:
            return V, policy
        policy = new_policy

Convergência típica en 4×4: 4-6 iteraciones externas. Produce V*(0,0) ≈ -6 y una política que reduce estrictamente el número de pasos.

Paso 5: iteración de valores (la versión de un solo bucle)

def value_iteration(gamma=0.99, tol=1e-6):
    V = {s: 0.0 for s in states()}
    while True:
        delta = 0.0
        for s in states():
            v = max(sum(p * (r + gamma * V[s_prime])
                       for s_prime, r, p in transitions(s, a))
                   for a in ACTIONS)
            delta = max(delta, abs(v - V[s]))
            V[s] = v
        if delta < tol:
            break
    policy = policy_improvement(V, gamma)
    return V, policy

Mismo punto fijo, menos líneas de código.

Dificultades Comunes

• Olvidar manejar los estados terminales. Si aplicas Bellman a un estado absorbente, este seguirá eligiendo una "mejor acción" que no cambia nada. Protégelo con if s == terminal: V[s] = 0.
• Convergencia de la norma del supremo vs L2. Usa max |V_new - V|, no el promedio. La garantía teórica está en la norma del supremo.
• Actualizaciones in-place vs síncronas. Actualizar V[s] in-place (Gauss-Seidel) converge más rápido que un diccionario V_new separado (Jacobi). El código de producción utiliza in-place.
• Empates en la política. Si dos acciones tienen el mismo valor Q, argmax puede romper los empates de manera diferente en cada iteración, lo que hace que la verificación de "política estable" oscile. Usa un desempate estable (la primera acción en un orden fijo).
• Explosión del espacio de estados. La programación dinámica es O(|S| · |A|) por recorrido. Funciona para hasta ~10⁷ estados. Más allá de eso, necesitas aproximación de funciones (Fase 9 · 05 en adelante).

Cómo Usarlo

En 2026, la programación dinámica es la línea base de corrección y el bucle interno de los planificadores:

Cada vez que alguien dice "la función de valor óptima", se refiere al "punto fijo de la programación dinámica". Cuando veas V* o Q* en un artículo, imagina este bucle.

Envíalo

Guárdalo como outputs/skill-dp-solver.md:

---
name: dp-solver
description: Solve a small tabular MDP exactly via policy iteration or value iteration. Report convergence behavior.
version: 1.0.0
phase: 9
lesson: 2
tags: [rl, dynamic-programming, bellman]
---

Given an MDP with a known model, output:

1. Choice. Policy iteration vs value iteration. Reason tied to |S|, |A|, γ.
2. Initialization. V_0, starting policy. Convergence sensitivity.
3. Stopping. Sup-norm tolerance ε. Expected number of sweeps.
4. Verification. V*(s_0) computed exactly. Greedy policy extracted.
5. Use. How this baseline will be used to debug/evaluate sampling-based methods.

Refuse to run DP on state spaces > 10⁷. Refuse to claim convergence without a sup-norm check. Flag any γ ≥ 1 on an infinite-horizon task as a guarantee violation.

Ejercicios

1. Fácil. Ejecuta la iteración de valores en el GridWorld de 4×4 con γ ∈ {0.9, 0.99}. ¿Cuántos recorridos se necesitan hasta que max |ΔV| < 1e-6? Imprime V* como una cuadrícula de 4×4.
2. Medio. Compara la iteración de políticas frente a la iteración de valores en el GridWorld estocástico (probabilidad de deslizamiento de 0.1). Cuenta: recorridos, tiempo de ejecución real (wall-clock), V*(0,0) final. ¿Cuál converge más rápido en iteraciones? ¿Cuál en tiempo real?
3. Difícil. Construye la iteración de políticas modificada: en el paso de evaluación, ejecuta solo k recorridos en lugar de ir hasta la convergencia. Grafica el error de V*(0,0) frente a k para k ∈ {1, 2, 5, 10, 50}. ¿Qué te dice la curva sobre el equilibrio (tradeoff) entre evaluación y mejora?

Términos Clave

Lecturas Adicionales

• Sutton & Barto (2018). Ch. 4 — Dynamic Programming — la presentación canónica de la iteración de políticas y de la iteración de valores.
• Bertsekas (2019). Reinforcement Learning and Optimal Control — tratamiento riguroso de los argumentos de mapeo por contracción.
• Puterman (2005). Markov Decision Processes — iteración de políticas modificada y su análisis de convergencia.
• Howard (1960). Dynamic Programming and Markov Processes — el artículo original de la iteración de políticas.
• Bertsekas & Tsitsiklis (1996). Neuro-Dynamic Programming — el puente de DP a DP aproximada / RL profundo utilizado por cada lección subsiguiente.