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.

 

Modelos de marcov proceso de decisión MDP

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.

 

 

Karl J. Åström
Åström
Alvin W. Drake
Drake
Ronald A. Howard
Howard
Richard E. Bellman
Bellman

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).

 

Bellman principio de optimización

 

 

 

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:

Bellman ecuación H infinito

 

 

En esta política el agente tratará de encontrar una política π que maximice la función valor para todos los estados e ∈ E:

Bellman principio de optimizacion infinito

 

 


Agente.

 Proceso de decisión de Markov Finito
MDP – Finito

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.

 

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

8 + 12 =