Phase 09: Reinforcement Learning

Programación dinámica Iteración de políticas y iteración de valores

La programación dinámica es RL con el engaño. Ya sabes las funciones de transición y recompensa; sólo se repite la ecuación de Bellman hasta queVo πEl método de referencia es el que todos los métodos basados en muestreo intentan abordar.

Type: Build

Languages: Python

Prerequisites: Phase 9 · 01 (MDPs)

Time: ~75 minutes

El problema

Tiene un MDP con un modelo conocido: puede consultar P(s' | s, a)y R(s, a, s')Un gerente de inventario conoce la distribución de la demanda. un juego de mesa tiene transiciones deterministas. un mundo de cuadrícula es cuatro líneas de Python. tienes un modelo.

La RL libre de modelos (Q-learning, PPO, REINFORCE) fue inventada para el caso en el que no tienes un modelo solo puedes tomar muestras del entorno. Pero cuando lo tienes, hay métodos más rápidos y mejores: programación dinámica. Bellman las diseñó en 1957.

Los datos de la investigación de RL (GridWorld, FrozenLake, CliffWalking) se resuelven con DP para producir la política estándar de oro.V*(s_0)En tercer lugar, los métodos modernos de RL y planificación fuera de línea (MCTS, búsqueda de AlphaZero, RL basado en el modelo en la Fase 9 · 10) reiteran todos una copia de seguridad Bellman sobre un modelo aprendido o dado.

El concepto

!Policy iteration and value iteration, side by side

Two algorithms, both fixed-point iteration on Bellman.

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

  1. Evaluación: política dada π, computación V^πmediante la aplicación repetida V(s) ← Σ_a π(a|s) Σ_{s',r} P(s',r|s,a) [r + γ V(s')]hasta que converge.
  2. Mejora: dada V^π, hacerπcodicioso W.R.T.V^π¿ Qué es esto ?π(s) ← argmax_a Σ_{s',r} P(s',r|s,a) [r + γ V(s')]¿ Qué ?

La convergencia está garantizada porque a) cada paso de mejora mantiene oπel mismo o aumentan estrictamente V^πPara algunos estados, (b) el espacio de las políticas deterministas es finito. generalmente converge en ~ 520 iteraciones externas incluso para grandes espacios de estados.

Value iteration.Se desmorona la evaluación y la mejora en un solo barrido. Aplique la ecuación Bellman optimalidad:

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

Repita hasta quemax_s |V_{new}(s) - V(s)| < ε. Extraer la política al final tomando la acción codiciosa. Estrictamente más rápido por iteración no hay bucle de evaluación interna pero normalmente necesita más iteraciones para converger.

Generalized policy iteration (GPI).La estructura unificadora. La función de valor y la política están bloqueadas en un bucle de mejora bidireccional; cualquier método que impulse ambos hacia la consistencia mutua (iteración de valores sincronizados, iteración de políticas modificadas, Q-learning, actor-critico, PPO) es una instancia de GPI.

Why γ < 1 matters.El operador Bellman es unγ- contracción en la norma de sup: ||T V - T V'||_∞ ≤ γ ||V - V'||_∞La contracción implica un punto fijo único y una convergencia geométrica.γ < 1y pierdes la garantía necesitas un horizonte finito o un estado terminal de absorción.

Construye el mismo

Paso 1: construir el modelo de MDP de GridWorld

Usamos el mismo 4x4 GridWorld de la Lección 01. Añadimos una variante estocástica: con probabilidad 0.1El agente se desliza hacia una dirección perpendicular aleatoria.

pythonSLIP = 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 todo el modelo.

Paso 2: Evaluación de las políticas

Dado que hay una política π(s) = {action: prob}, repite la ecuación de Bellman hasta que VSe detiene:

pythondef 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 las políticas

Reemplazarπcon la política codiciosa W.R.T.VSi ...πNo cambió, regreso estamos en el óptimo.

pythondef 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: Conectadlos

pythondef 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

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

Paso 5: Iteración de valor (versión de un bucle)

pythondef 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

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

Las trampas

  • Forgetting to handle terminals.Si aplicas Bellman a un estado de absorción, sigue recogiendo una "mejor acción" que no cambia nada.if s == terminal: V[s] = 0¿ Qué ?
  • Sup-norm vs L2 convergence.Usarmax |V_new - V|La garantía teórica está en la sup-norma.
  • In-place vs synchronous updates.Actualización V[s]En el lugar (Gauss-Seidel) converge más rápido que en un lugar separado V_newEl código de producción utiliza en el lugar.
  • Policy ties.Si dos acciones tienen el mismo valor Q,argmaxEl sistema de correlación puede romper los vínculos de manera diferente en cada iteración, causando que el control de "estabilidad de política" oscile.
  • State-space explosion.DP esO(|S| · |A|)Para el análisis de la función, el valor de la función se calcula en un punto de referencia.

Usalo

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

Use caseMethod
Solve a small tabular MDP exactlyValue iteration (simpler) or policy iteration (fewer outer steps)
Verify a Q-learning / PPO implementationCompare to DP-optimal V* on a toy environment
Model-based RL (Phase 9 · 10)Bellman backup on a learned transition model
Planning in AlphaZero / MuZeroMonte Carlo Tree Search = async Bellman backup
Offline RL (CQL, IQL)Conservative Q-iteration — DP with a penalty on OOD actions

Cada vez que alguien dice "la función de valor óptimo", se refiere a "el punto fijo DP".Vo Qen un periódico, imagínate este bucle.

Envío

Salvo comooutputs/skill-dp-solver.md¿Qué es esto ?

markdown---
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.

Los ejercicios

  1. Easy.Ejecutar la iteración de valor en la 4×4 GridWorld con γ ∈ {0.9, 0.99}¿ Cuántas barradas hasta ?max |ΔV| < 1e-6¿ Impresión ?V*como una cuadrícula 4×4.
  2. Medium.Comparación de la iteración de la política vs iteración de valor en la estocástica GridWorld (probabilidad de deslizamiento 0.1Contar: barridos, tiempo del reloj de la pared, final V*(0,0)¿Cuál converge más rápido en iteraciones?
  3. Hard.Construir una iteración de política modificada: en la etapa de evaluación, ejecutar sólo kSe desliza en lugar de convergir.V*(0,0)error vs kpork ∈ {1, 2, 5, 10, 50}¿Qué le dice la curva sobre la compensación entre evaluación y mejora?

Términos clave

TermWhat people sayWhat it actually means
Policy iteration"DP algorithm"Alternating evaluation (V^π) and improvement (greedy π w.r.t. V^π) until the policy stops changing.
Value iteration"Faster DP"Bellman optimality backup applied in one sweep; converges to V* geometrically.
Bellman operator"The recursion"(T V)(s) = max_a Σ P (r + γ V(s')); a γ-contraction in sup-norm.
Contraction"Why DP converges"Any operator T with ||T x - T y|| ≤ γ ||x - y|| has a unique fixed point.
GPI"Everything is DP"Generalized Policy Iteration: any method driving V and π to mutual consistency.
Synchronous update"Jacobi-style"Use old V throughout a sweep; cleanly analyzable but slower.
In-place update"Gauss-Seidel-style"Use V as it's being updated; converges faster in practice.

Leer más

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.