Proceso de Decisión (MDP)

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:

 

 

Agente.

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.