Markov Decision Process (MDP)

También llamado: MDP
Categoría: Learning & autonomy › RL & simulation
Etiquetas: reinforcement-learning, decision-making, dynamic-programming, probability, robot-learning

El modelo matemático estándar de la toma de decisiones secuencial: estados, acciones, probabilidades de transición, recompensas y un factor de descuento, en el que el estado siguiente depende solo del estado y la acción actuales.

Definición

Un proceso de decisión de Markov (Markov decision process, MDP) describe un agente que observa repetidamente un estado, elige una acción, recibe una recompensa y pasa a un nuevo estado. Suele escribirse como una tupla (S, A, P, R, γ), a menudo con una distribución de estado inicial ρ₀: el espacio de estados, el espacio de acciones, las probabilidades de transición P(s′ | s, a), la función de recompensa R(s, a) y un factor de descuento γ entre 0 y 1 que pondera las recompensas futuras frente a las inmediatas. El supuesto que lo define es la propiedad de Markov: la distribución del estado siguiente depende solo del estado y la acción actuales, no de la historia que llevó hasta allí. El trabajo de Richard Bellman sobre programación dinámica en la década de 1950 estableció el marco.

El objetivo en un MDP es una política, una correspondencia de estados a acciones (o a distribuciones sobre acciones), que maximice la suma descontada esperada de recompensas. La función de valor V(s) y la función de valor de acción Q(s, a) dan ese retorno esperado desde un estado, o desde un estado y una acción, bajo una política. Ambas satisfacen las ecuaciones de Bellman, que expresan el valor de un estado como la recompensa inmediata más el valor descontado de los estados que siguen. Cuando P y R son conocidas y el espacio de estados es pequeño, la iteración de valor y la iteración de política resuelven el MDP de forma exacta. Cuando son desconocidas, o los espacios son grandes y continuos, el aprendizaje por refuerzo estima valores y políticas a partir de experiencia muestreada.

Los MDP son la base formal de casi todo el aprendizaje por refuerzo y de una gran parte de la planificación bajo incertidumbre. Muchas variantes relajan uno de los supuestos: un MDP parcialmente observable (POMDP) abandona el supuesto de que el agente ve el estado verdadero; los MDP con restricciones añaden límites de coste; los semi-MDP permiten acciones de duración variable; y extensiones multiagente como los juegos de Markov modelan varios decisores. Elegir qué entra en el estado es una decisión de ingeniería: si se deja fuera información importante, como velocidades, el estado de contacto o la intención de otros agentes, el proceso deja de ser markoviano desde el punto de vista del agente.

Por qué importa

Todos los artículos de aprendizaje por refuerzo y la mayoría de los métodos de toma de decisiones en robótica plantean su problema como un MDP o una variante de uno. Conocer las partes de la tupla, y en qué supuesto se apoya cada método, permite leer esos artículos, diseñar estados y recompensas para un robot real y reconocer cuándo un problema es en realidad parcialmente observable.

Aplicaciones clave

Formulación de problemas de aprendizaje por refuerzo para manipulación y locomoción
Planificación bajo incertidumbre con iteración de valor e iteración de política
Diseño de recompensas y aprendizaje por refuerzo inverso, que infieren o dan forma a R
Aprendizaje por refuerzo basado en modelos, que aprende la función de transición P
Modelado de la interacción con otros agentes mediante juegos de Markov y variables latentes de intención

En la práctica

Un equipo que entrena un brazo robótico para empujar un bloque hasta un objetivo plantea la tarea como un MDP. El estado contiene los ángulos y velocidades de las articulaciones, la pose del bloque y la posición del objetivo; la acción es un cambio en la posición del efector final en cada paso de control; la recompensa es la distancia negativa del bloque al objetivo con una bonificación en caso de éxito; y γ se fija cerca de 1 porque la tarea abarca muchos pasos. En las primeras pruebas la política se comporta de forma errática cuando el bloque está en movimiento, porque el estado incluye la pose del bloque pero no su velocidad. Añadir la velocidad del bloque, o apilar las últimas observaciones, restablece la propiedad de Markov lo bastante bien como para que un algoritmo estándar como SAC o PPO aprenda de forma fiable.

Ideas erróneas comunes

Un MDP requiere estados y acciones discretos — los espacios de estados y de acciones continuos son habituales en robótica, con las sumas sustituidas por integrales y los métodos tabulares por aproximación de funciones
La propiedad de Markov es un hecho del mundo — es una propiedad del estado elegido; dejar fuera velocidades o variables ocultas puede hacer que un sistema físico no sea markoviano desde el punto de vista del agente
El factor de descuento solo refleja impaciencia — también acota el retorno en problemas de horizonte infinito y afecta a la varianza y la estabilidad del aprendizaje, por lo que a menudo se ajusta como un hiperparámetro
Resolver un MDP requiere un modelo de P — los métodos de aprendizaje por refuerzo encuentran buenas políticas a partir de transiciones muestreadas sin escribir nunca P

Quién debería saberlo

Profesionales e investigadores del aprendizaje por refuerzo
Ingenieros de aprendizaje robótico que diseñan estados, acciones y recompensas
Investigadores en planificación y toma de decisiones
Estudiantes de robótica que empiezan con el aprendizaje robótico

Tecnologías relacionadas

Ecuación de Bellman (Bellman Equation)
Iteración de valor (Value Iteration)
Iteración de política (Policy Iteration)
Q-Learning
Gymnasium
Programación dinámica (Dynamic Programming)

Términos relacionados

Proyectos relacionados

LeRobot: HuggingFace ML library for real-world robotics in PyTorch
MuJoCo: DeepMind physics engine for robotics and ML research
PyBullet: Python physics simulator for robotics and RL research with fast CPU-based simulation
OpenPI: Physical Intelligence VLA foundation models for general robot control
Microduck: Pollen Robotics' $399 walking duck robot: open-source software, closed hardware
Isaac Lab: NVIDIA robot learning framework: one task API across Newton, PhysX and Isaac Sim

Vídeos

Markov Decision Processes - Computerphile: Computerphile