MDP (Markov Decision Process, Proceso de decisión de Markov) es una extensión de las cadenas de Markov, estas, al contrario que MDP, sólo tienen una acción para cada estado y todas las recompensas son iguales.
Uno de los primeros en recoger el término MDP fue Richard E. Bellman en 1.957 en su libro “A Markovian Decision Process”, el concepto tuvo su desarrollo en 1.960 por Ronald A. Howard en “Dynamic Programming and Markov Processes”, Alvin W. Drake plantea el primer problema en 1.962 y Karl J. Åström amplia el concepto en 1.965, después continuaron muchos más.




MDP es un modelo matemático generalmente de horizonte finito y aleatorio, al cual se le puede aplicar un control externo. Valora la incertidumbre del sistema, y su dinámica está determinada por la función de transición de probabilidad. Su objetivo es encontrar el conjunto óptimo de acciones o políticas para llevar a cabo y quien realiza estas acciones se le denomina Agente, él es quien elige cómo actuar para maximizar su recompensa en una serie de interacciones con su entorno.
Descripción del modelo.
A MDP se le suele representar por una lista compuesta de iniciales, el número y denominación es arbitrario según el autor, aquí mostramos (E, A, R, T), donde:
- E Es el conjunto discreto (finito) de posibles estados del agente.
- A Es el conjunto discreto de posibles acciones.
- R Es la función de recompensa R: E × A → R con un valor real. Para cada par estado-acción R(e, a) se proporciona un “caramelo” si ejecuta la acción a desde el estado e. γ ∈ [0, 1]: Es un factor de descuento aplicable en la Recompensa.
- T (en algunos casos P). Es una función de transición estocástica T : E × A → P(E) que especifica la probabilidad de pasar a un estado dado, desde el estado presente y la ejecución de la acción a. P(s) es una distribución de probabilidad sobre el conjunto E, es decir, transforma estados en probabilidades que describe los efectos de cada acción en cada estado. T(s, a, e’) es la probabilidad de realizar una transición desde e hasta e’ ejecutando la acción a.
Por otro lado, se debe tener en cuenta que:
- Las funciones T y R dependen únicamente del estado y de la acción actual, no de estados y acciones anteriores.
- Para que T sea una función de transición válida, la distribución sobre los estados resultantes, (E → R), deben ser una distribución de probabilidad válida, es decir, no negativa y totalizando a 1. Además, las recompensas esperadas deben ser finitas.
- La función de valor V: indica lo positivo a largo plazo. Es la recompensa acumulada total que un agente puede recibir de un estado, de alguna manera representa las predicciones de recompensas.
- γ Es un factor de descuento 0 ≤ γ < 1.
- La Política π indica cuál acción se debe ejecutar dado el estado (o probabilidad del estado). Es estática y determinista, no cambia en función del tiempo. Las políticas pueden ser:
- De horizonte finito
- De horizonte infinito
- Implícita
- Estocástica
Política de horizonte finito (π: E × T → A).
El valor esperado de una política, en cualquier estado, se puede calcular mediante una regla de decisión óptima, en nuestro caso la ecuación de Richard E. Bellman:
Estas funciones se llaman funciones de valor t-horizon o t-step y están dentro del conjunto . H es la longitud del horizonte (el número predeterminado de etapas que el proceso atraviesa).
Una política π∗ es óptima si para todas las políticas de horizonte H π´ y todos los estados e ∈ E.
El principio de optimización de Bellman permite calcular la función óptima del valor de paso t a partir de la función de valor (t – 1).
Política de horizonte infinito (π: E → A).
En esta política las decisiones óptimas se pueden calcular basándose en el estado actual del sistema, ya que en cualquier etapa, todavía hay un número infinito de pasos restantes. Estas políticas se llaman estacionarias dado que no dependen de las etapas y se pueden determinar mediante una ecuación análoga a la del caso de horizonte finito:
En esta política el agente tratará de encontrar una política π∗ que maximice la función valor para todos los estados e ∈ E:

El agente debe tomar decisiones sobre las acciones a realizar para modificar el estado del mundo (entorno) y de su misma condición, las acciones que adopte determinaran la recompensa inmediata y el siguiente estado del entorno, al menos probabilísticamente. Debe ser capaz de aprender a partir del valor de las recompensas y no dejarse llevar por pequeñas ya que puede obtener una mayor acumulándolas. Esta forma de actuar le ayuda a aprender cuál de las acciones es deseable tener en cuenta o las recompensas que pueden obtenerse en un futuro lejano. Una vez que ha aprendido a resolver una tarea, el conocimiento adquirido sólo es aplicable a esa tarea. De otra forma: El agente calcula una política -asociando estados a acciones – para maximizar un flujo de recompensas.
El principal problema de MDP es el aumento de la complejidad al incrementarse el número de estados y acciones, esto hace que el problema crezca de forma exponencial, para ello se han planteado los HDMDP (Hierarchically Determinized MDP, Procesos de Decisión de Markov Jerárquicos).
Alguno de los últimos algoritmos que se han utilizado y se utilizan dentro de MDP son buenos en tiempos de ejecución o proveen buenas soluciones, pero dificilmente ambos a la vez. Algunos de ellos se utilizan como complemento en POMDP y a su vez, parte de algunos de los de POMDP (ver) también son válidos para MDP.
Algoritmos MDP | |||
Acrónimo | Fecha | Autor | Comentarios |
A * | 1.968 | Peter E. Hart, Nils J. Nilsson y Bertram Raphael | Es un algoritmo básico utilizado en la búsqueda de grafos que combina dos funciones de evaluación g y h, f(n)=g(n) + h'(n) donde g(n) da la recompensa acumulada desde el estado de inicio hasta el estado n, y la función heurística h(n) indica la máxima recompensa estimada de los caminos de n hasta el objetivo. |
AO * | 1.980 | Nils J. Nilsson | Es una extensión del algoritmo A * que se aplica a grafos (And / Or) a cíclicos o MDP a cíclicos, por lo que no es aplicable a los MDP generales. Encuentra una solución o política que tiene una estructura condicional en forma de árbol. Al igual que otros algoritmos de búsqueda heurística, AO * puede encontrar una solución sin considerar el espacio entero de estados. |
LRTA*, δ-LRTA*, DTA* |
1.990 | Richard E. Korf | Learning RealTime A* . Aprende actualizando su función heurística en tiempo real. |
HLRTA* | 1.994 | Paul Elton Thorpe | Variante de LRTA*. |
ε-LRTA* | 1.996-7 | Toru Ishida y Masashi Shimbo |
Desarrollado para acelerar la convergencia de LRTA * , pero sacrificando la optimización del plan obtenido. Aprende actualizando su función heurística mientras avanzan en espacio de estados. |
RTDP | 1.993 | Andrew G. Barto, Steven Bradtke y Satinder Singh | Real-Time Dynamic Programmin. Está basado en el LRTA*. |
SLA* | 1.993 | Li-Yen Shue y Reza Zamani | El algoritmo es casi idéntico a LRTA *. Introduce un mecanismo de retroceso (backtracking). Cuando se hace una actualización del valor heurístico del estado actual, el agente retrocede a su estado anterior. El backtracking reduce la cantidad de memoria requerida para almacenar el valor aprendido. Tiene el inconveniente de realizar una copia cada vez que se actualiza su heurística, esto incrementa el coste de ejecución de la primera prueba. |
SLRTA* | 1.997 | Stefan Edelkamp y Jürgen Eckerle | Es similar a HLRTA* |
FALCONS | 2.000 | David Furcy y Sven Koenig | FAster Learning and CONverging Search. |
eFALCONS | 2.000 | David Furcy y Sven Koenig | Even FAster Learning and CONverging Search. Usa la búsqueda en tiempo real similar a LRTA *, la actualización de valor de regla de HLRTA * y la regla de selección de acción de FALCONS. |
SLA * T | 2.001 | Li-Yen Shue y Reza Zamani | Resuelve el problema de coste de SLA*, dando al usuario control sobre la cantidad de aprendizaje que se debe hacer por prueba antes de retroceder. |
LAO * | 2.001 | Eric A. Hansen, Shlomo Zilberstein | Es una extensión del algoritmo AO * que puede manejar MDPs con bucles |
ILAO * | 2.001 | Eric A. Hansen, Shlomo Zilberstein | Es una variante mejorada de LAO *. |
LRTDP | 2.003 | Blai Bonet y Hector Geffner | Labeled Real Time Dynamic Programming |
BLAO* | 2.003 | Kiran Bhuma y Judy Goldsmith | Es una variante bidireccional de LAO*. |
γ-Trap | 2.004 | Vadim Bulitko | Utiliza un parámetro de peso heurístico γ = 1 / (1 + ǫ) con el mismo efecto que LRTA ponderado *, además emplea una regla de actualización heurística más agresiva, indicada por “max de min” en la tabla, y utiliza valores heurísticos de todos los estados. |
BRTDP | 2.005 | McMahan, Likhachev y Gordon | Bounded RTDP. Con programación dinámica |
FRTDP | 2.006 | Smith y Simmons | Focused RTDP. |
RLAO* | 2.006 | Peng Dai y Judy Goldsmith | Reverse LAO*. Es una versión de búsqueda hacia atrás de LAO * y BLAO *. |
LRTS | 2.006 | Vadim Bulitko y Greg Lee | Learning in Real-Time Search. Toma como base a LRTA*, ε-LRTA* , SLA*, y γ-Trap, combinándolos. |
TVI | 2.007 | Peng Dai y Judy Goldsmith | Topological value iteration, Iteración de valor topológico. Divide un MDP en componentes fuertemente conectados (SCC) y luego resuelve cada componente secuencialmente en orden topológico. |
FTVI | 2.009 | Peng Dai, Mausam Mausam y Daniel S. Weld | Focused topological value iteration. |
VPI-RTDP | 2.009 | S. Sanner, R. Goetschalckx, K. Driessens y G. Shani. | Value of Perfect Information RTDP. Es una mejora de los distintos tipos de RTDP. |
HDMDP | 2.010 | Jennifer Barry, Leslie Pack Kaelbling yTomás Lozano-Pérez | Hierarchically determinized MDP. |
It’s very interesting!
Very nice post. I just stumbled upon your weblog and wished to say that I’ve truly enjoyed surfing around your blog posts. After all I will be subscribing to your feed and I hope you write again very soon!