Markov (MDP)

MDP (Markov decision process, Proceso de decisión de Markov) es una extensión de las cadenas de Markov, estas, al contario 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 Bellman en 1.957 en su libro “A Markovian Decision Process”.

 

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.

andrei andreyevich markov
Andrey A. Markov

 

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.

 

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 (S, A, R, T), donde:

 

  • S 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: S × A → R con un valor real. Para cada par estado-acción R(s, a) proporciona un “caramelo”  si ejecuta la acción a desde el estado s.
  • T Es una función de transición estocástica T : S × A → P(S) 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 S, es decir, transforma estados en probabilidades que describe los efectos de cada acción en cada estado. T(s, a, s’) es la probabilidad de realizar una transición desde s hasta s’ ejecutando la acción a.

 

 Proceso de decisión de Markov Finito
Proceso de decisión de Markov Finito

Por otro lado se debe tener en cuenta que:

  • La Política ππ : S → A, indica la acción que se debe ejecutar dado el estado (o probabilidad del estado). Es estática, no cambia en función del tiempo y es determinista, siempre se elige la misma acción cuando se está en el mismo estado. La política optima se identifica por π *
  • Las funciones T y R dependen únicamente del estado y la acción actuales, 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, (S → 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.

 

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.

Acronimo 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)  acíclicos o MDP ací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 valores aprendidos. 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 un comentario

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

uno × 2 =