Un proceso de decisión de Markov (MDP, por sus siglas en inglés) es un modelo matemático para la toma de decisiones secuenciales cuando los resultados son inciertos. Es un tipo de proceso estocástico de decisión, que a menudo se resuelve mediante métodos de programación dinámica estocástica. Originado en la investigación de operaciones en la década de 1950, los MDP han ganado reconocimiento en campos como la ecología, la economía, la atención médica, las telecomunicaciones y el aprendizaje automático. En el aprendizaje por refuerzo, el marco de los MDP modela la interacción entre un agente de aprendizaje y su entorno, caracterizado por estados, acciones y recompensas, proporcionando una representación simplificada de elementos clave de los desafíos de la inteligencia artificial, incluyendo causa y efecto, incertidumbre y objetivos explícitos.
El nombre deriva de su conexión con las cadenas de Markov, desarrolladas por el matemático ruso Andréi Márkov. La propiedad de Markov se refiere a la estructura subyacente donde las transiciones de estado dependen únicamente del estado y la acción actuales, no de la historia previa. El proceso se denomina "de decisión" porque implica tomar decisiones que influyen en estas transiciones, extendiendo las cadenas de Markov a la toma de decisiones bajo incertidumbre.
Definición formal
Un MDP se define típicamente como una 4-tupla \((S, A, P_a, R_a)\), donde:
- \(S\) es el espacio de estados, que puede ser discreto o continuo (por ejemplo, el conjunto de números reales).
- \(A\) es el espacio de acciones, con \(A_s\) denotando el conjunto de acciones disponibles desde el estado \(s\). Este conjunto también puede ser discreto o continuo.
- \(P_a(s, s')\) es la probabilidad de transición de que la acción \(a\) en el estado \(s\) en el tiempo \(t\) conduzca al estado \(s'\) en el tiempo \(t+1\). Para estados discretos, \(P_a(s, s') = \Pr(s_{t+1} = s' \mid s_t = s, a_t = a)\). Para espacios de estados continuos, la probabilidad se define mediante una integral, a menudo con respecto a la medida de Lebesgue.
- \(R_a(s, s')\) es la recompensa inmediata (o recompensa esperada) recibida después de tomar la acción \(a\) para transitar del estado \(s\) al estado \(s'\). La recompensa generalmente es una variable aleatoria.
Una política \(\pi\) es una función (potencialmente probabilística) que mapea el espacio de estados al espacio de acciones, especificando qué acción tomar en cada estado.
Objetivo de optimización
El objetivo en un MDP es encontrar una política \(\pi\) que maximice una función acumulativa de las recompensas aleatorias, típicamente la suma descontada esperada sobre un horizonte infinito: \(\mathbb{E}[\sum_{t=0}^{\infty} \gamma^t R_{a_t}(s_t, s_{t+1})]\), donde \(\gamma \in [0, 1)\) es un factor de descuento. Una vez que se fija una política, el MDP se comporta como una cadena de Markov, ya que la acción en cada estado está determinada por \(\pi(s)\).
Los métodos de solución comunes incluyen técnicas de programación dinámica como la iteración de valores y la iteración de políticas, que calculan funciones de valor óptimas o políticas óptimas. Estos métodos son fundamentales en algoritmos de aprendizaje por refuerzo como Q-learning y SARSA.
Aplicaciones
Los MDP se aplican ampliamente en diversos dominios. En economía, modelan decisiones óptimas de consumo e inversión. En atención médica, guían la planificación de tratamientos bajo incertidumbre, como en el manejo de enfermedades crónicas. En telecomunicaciones, optimizan la asignación de recursos y el enrutamiento de redes. En ecología, informan estrategias de conservación para la gestión de especies. En el aprendizaje automático, los MDP son centrales para el aprendizaje por refuerzo, permitiendo que los agentes aprendan de la interacción con sus entornos, como se observa en robótica, juegos y conducción autónoma.
Relación con el aprendizaje por refuerzo
El aprendizaje por refuerzo (RL, por sus siglas en inglés) utiliza el marco de los MDP para formalizar la interacción agente-entorno. En RL, el agente no conoce de antemano las probabilidades de transición ni las funciones de recompensa; en cambio, aprende una política óptima mediante prueba y error, utilizando muestras del entorno. Esto distingue al RL de la resolución clásica de MDP, que asume parámetros del modelo conocidos. El RL moderno, incluido el aprendizaje por refuerzo profundo, combina los MDP con aproximadores de funciones basados en redes neuronales para manejar espacios de estados grandes, como se demuestra en aplicaciones como juegos y conducción autónoma.
Extensiones y variaciones
Varias extensiones abordan las limitaciones del MDP básico. Los procesos de decisión de Markov parcialmente observables (POMDP, por sus siglas en inglés) manejan situaciones donde el agente no puede observar directamente el estado completo. Los MDP factorizados explotan la estructura en el espacio de estados para mejorar la escalabilidad. Los MDP multi-agente extienden el marco a múltiples agentes con objetivos que interactúan. Estas variaciones conservan la propiedad de Markov central mientras se adaptan a problemas del mundo real más complejos.
Contexto histórico
La formalización de los MDP se atribuye a Richard Bellman en la década de 1950, quien también desarrolló la programación dinámica. El trabajo anterior de Andréi Márkov sobre procesos estocásticos proporcionó la base teórica. Desde entonces, los MDP se han convertido en una piedra angular de la investigación de operaciones y la inteligencia artificial, influyendo tanto en el trabajo teórico como en el aplicado en la toma de decisiones secuenciales.