Markov Decision Process (MDP)

Un proceso de decisión de Markov (MDP) es el modelo matemático de un problema de decisión secuencial: un agente observa un estado, elige una acción, recibe una recompensa y llega a un estado siguiente que depende en parte de su elección y en parte del azar. Formalmente, un MDP consta de un conjunto de estados, un conjunto de acciones, probabilidades de transición P(s′ | s, a), una función de recompensa R(s, a) y, normalmente, un factor de descuento γ entre 0 y 1. Resolverlo consiste en encontrar una política —una regla que elige una acción en cada estado— que maximice la suma descontada esperada de las recompensas futuras. Los MDP surgieron en la investigación operativa de los años cincuenta, cuando la programación dinámica de Richard Bellman aportó los métodos para resolverlos, y constituyen la formulación estándar de los problemas de aprendizaje por refuerzo (RL).

La propiedad de Markov#

El supuesto fundamental es la propiedad de Markov: el siguiente estado y la recompensa dependen únicamente del estado y la acción actuales, no del camino que ha llevado hasta allí. Así, el estado resume por completo toda la información relevante para el agente. Un único fotograma de cámara incumple este supuesto en el caso de un objeto en movimiento, porque muestra su posición, pero no su velocidad; por eso, el DQN de DeepMind para Atari proporcionaba a su red los últimos cuatro fotogramas apilados para que pudiera ver el movimiento.

Cuando el agente no puede observar el estado completo, como ocurre con un robot cuyos sensores tienen ruido u obstrucciones, el problema es un MDP parcialmente observable (POMDP). En ese caso, el agente actúa según una creencia sobre el estado, que mantiene mediante un filtro o una red recurrente, en lugar de actuar directamente sobre el estado.

Componentes de un MDP#

• Estados: Las situaciones en las que puede encontrarse el agente, como los ángulos de las articulaciones de un robot y la posición del objeto que intenta alcanzar.
• Acciones: Las opciones disponibles en cada estado. El espacio de acciones puede ser discreto (girar a la izquierda, girar a la derecha) o continuo (un ángulo de giro en grados).
• Probabilidades de transición: La probabilidad de cada estado siguiente tras una acción; refleja el deslizamiento de las ruedas, la presencia de otros conductores y cualquier otra fuente de aleatoriedad.
• Recompensas: La señal numérica inmediata que se obtiene tras una transición. La elección de recompensas del diseñador define la tarea, y una elección poco cuidadosa puede fomentar el hackeo de recompensas.
• Factor de descuento: Cuánto cuentan las recompensas futuras en comparación con las inmediatas. Con γ = 0.9, una recompensa dentro de diez pasos vale 0.9¹⁰ ≈ 0.35 veces la misma recompensa ahora.

La misma interacción se repite en cada paso temporal hasta que termina el episodio:

Resolver un MDP#

El valor de un estado es el retorno esperado desde ese estado según una política, y los valores óptimos cumplen la ecuación de Bellman: el valor de cada estado equivale a la recompensa inmediata de la mejor acción más el valor descontado y ponderado por probabilidad de los estados a los que conduce. Cuando se conocen las probabilidades de transición y las recompensas, la programación dinámica resuelve directamente esa ecuación. La iteración de valores (Bellman, 1957) la aplica repetidamente hasta que los valores dejan de cambiar, mientras que la iteración de políticas (Howard, 1960) alterna entre evaluar una política y mejorarla.

Este ejemplo de NumPy ejecuta una iteración de valores con el robot reciclador de Reinforcement Learning: An Introduction, de Sutton y Barto; el robot debe elegir entre buscar latas, esperar y recargarse cuando la batería está alta o baja:

import numpy as np

# MDP del robot reciclador: estados 0 = batería alta, 1 = batería baja; acciones 0 = buscar, 1 = esperar, 2 = recargar
gamma = 0.9  # factor de descuento
P = np.zeros((2, 3, 2))  # P[s, a, s'] = probabilidad de llegar a s' tras realizar a en s
P[0, 0] = [0.7, 0.3]  # buscar con la batería alta puede agotarla hasta un nivel bajo
P[1, 0] = [0.4, 0.6]  # buscar con la batería baja puede agotarla por completo (rescatan y recargan al robot)
P[:, 1] = np.eye(2)  # esperar mantiene el nivel de batería
P[:, 2] = [1.0, 0.0]  # recargar siempre devuelve la batería a un nivel alto
R = np.array([[2.0, 1.0, 0.0], [0.0, 1.0, 0.0]])  # R[s, a] esperado; búsqueda con batería baja: 0.6 * 2 + 0.4 * -3 = 0

# Iteración de valores: aplicar la actualización de optimalidad de Bellman hasta que los valores dejen de cambiar
V = np.zeros(2)
for _ in range(500):
    Q = R + gamma * P @ V  # valor de cada acción en cada estado
    V = Q.max(axis=1)

actions = ["search", "wait", "recharge"]
print("Optimal values:", V.round(2))
print("Optimal policy:", {s: actions[a] for s, a in zip(["high", "low"], Q.argmax(axis=1))})

Imprime valores de 15.75 para la batería alta y 14.17 para la baja, y una política que busca con la batería alta y recarga con la baja: el riesgo del 40 % de recibir una penalización de −3 por rescate hace que buscar con la batería baja resulte menos conveniente que recargar.

Cuando se desconocen las probabilidades de transición, el aprendizaje por refuerzo estima los mismos valores a partir de la experiencia. Q-learning actualiza los valores de las acciones a partir de transiciones muestreadas, los métodos de gradiente de políticas ajustan directamente una política y el aprendizaje profundo por refuerzo utiliza redes neuronales cuando el espacio de estados es demasiado grande para enumerarlo. Los algoritmos de planificación, como la búsqueda de árbol de Monte Carlo, resuelven MDP enormes sobre la marcha simulando únicamente los futuros alcanzables desde el estado actual.

MDP y modelos relacionados#

• Cadena de Markov: Secuencia de estados aleatorios sin acciones ni recompensas. Un MDP añade las opciones y el objetivo.
• Modelo oculto de Markov (HMM): Cadena de Markov cuyos estados solo se observan mediante señales ruidosas. Un POMDP guarda la misma relación con un MDP.
• Bandido multibrazo: MDP con un único estado, donde cada acción da un resultado independiente del pasado.
• Aprendizaje por refuerzo: Conjunto de métodos que aprenden a actuar bien en un MDP mediante la interacción, sin conocer sus probabilidades de transición.

Aplicaciones#

• Robótica y control: La manipulación de objetos, la locomoción y la navegación se formulan como MDP, y sus políticas suelen entrenarse mediante simulación. En el control basado en cámaras, un detector como Ultralytics YOLO26 puede proporcionar el estado, convirtiendo cada fotograma en una lista breve de clases de objetos y coordenadas de cuadros, una entrada mucho más pequeña para la política que los píxeles sin procesar.
• Entrenamiento de modelos de lenguaje: RLHF y RLVR tratan la generación de texto como un MDP cuyo estado es la instrucción más los tokens generados hasta el momento, cuya acción es el siguiente token y cuya recompensa llega cuando se completa la respuesta.
• Investigación operativa: La reposición de inventario, el mantenimiento de equipos y la fijación dinámica de precios son problemas clásicos de MDP; Ronald Howard desarrolló la iteración de políticas mientras optimizaba los envíos por correo de los catálogos de Sears.