Procesos de decisión de Markov

Problemas de decisión secuenciales

Son los problemas que involucran decisiones cuyo resultado se conoce hasta el final, se considera

que se tiene una serie de estados y decisiones asociadas en el tiempo. En estos problemas se tiene

incertidumbre asociada con los resultados y posiblemente en los estados.

La incertidumbre de una decisión se modela como una probabilidad de llegar al estado “j” dado

que se encuentra en el estado “i” y realiza la acción “a”.

Modelo de sensores: Normalmente el agente puede censar el ambiente para observar en qué

estado se encuentra. Existen dos casos principales:

1. Observa directamente el estado donde se encuentra: proceso de decisión de Markov

2. Se tiene incertidumbre sobre el estado en el que se encuentra: proceso de decisión de

Markov parcialmente observable

Política óptima: dado el modelo de transición y el modelo de sensores se encuentra una política

óptima para maximizar la utilidad, esta política debe de indicar la acción que se debe ejecutar

dado el estado. Las probabilidades de transición solo dependen del estado actual por lo que son

procesos markovianos.

Procesos de decisión de Markov

Controlador basado en MDP

Solución MDP

Controlador

Sistema

Modelo

Eventos

Estado Acción

Política

El modelo clásico para resolver un MDP se conoce como “iteración de valor” y consiste en calcular

el la utilidad de cada estado y usar estas para seleccionar la optima. Otros métodos que existen

son “iteración de política” y “programación lineal”

Un MDP se define por:

Un conjunto finito de estados (S)

Un conjunto finito de posibles acciones (A)

Un modelo de transición que especifica la probabilidad de pasar a un estado dado el

estado presente P(s | s’, a)

Una función de recompensas, que especifica el valor, de ejecutar cierta acción en el

estado s, r(s, a)

La utilidad del estado depende de la secuencia de acciones tomadas a partir de dicho estado i de

acuerdo a la política p. Si l utilidad es separable se puede estimar como la utilidad de los siguientes

estados y la forma más sencilla es que sea de forma aditiva.

Programación dinámica: dada la condición de separabilidad, la utilidad de un estado se puede

obtener en forma iterativa maximizando la utilidad del siguiente estado:

U (i) = R (i) + maxa ∑j P(sj | si, a)U(j)

Los problemas con número finito de pasos se conocen como MDP de horizonte finito, y los que

pueden tener número infinito de pasos son MDP de horizonte infinito. Los métodos para resolver

un MDP son:

1. Iteración de valor (Bellman, 57)

2. Iteración de política (Howards, 60)

3. Programación lineal (Puterman, 94)

Procesos de decisión de Markov parcialmente observables

Los elementos con los que cuenta un MDP parcialmente observable son los mismos con los que se

cuenta en en MDP pero se le añaden 2 cosas nuevas:

Una función de observación que especifica la probabilidad de observaciones dado el

estado P (O | S)

Una distribución inicial para los estados P (S)

Para resolver un POMDP (procesos de decisión de Markov parcialmente observables) se requiere

considerar toda la historia de observaciones y acciones, esto equivale a considerar la distribución

de probabilidad sobre los estados y en base a estas determinar las opciones óptimas.