Proceso de decisión de Márkov
Proporciona un marco matemático para modelar la toma de decisiones en situaciones en las que los resultados son en parte aleatorios y en parte están bajo el control de quien toma la decisión.
Los MDP son útiles para estudiar problemas de optimización resueltos mediante programación dinámica.
[2] Se utilizan en muchas disciplinas, como la robótica, el control automático, la economía y la manufactura.
La probabilidad de que el proceso pase a su nuevo estado
Algunos procesos con espacios de estado y acción contablemente infinitos pueden reducirse a otros con espacios de estado y acción finitos.
que maximice alguna función acumulativa de las recompensas aleatorias, normalmente la suma descontada esperada en un horizonte potencialmente infinito:
Otra forma de simulador es un modelo generativo, un simulador de un solo paso que puede generar muestras del siguiente estado y recompensa dados cualquier estado y acción.
[4] (Nótese que éste es un significado diferente del término modelo generador en el contexto de la clasificación estadística).
se utiliza a menudo para representar un modelo generador.
podría denotar la acción de muestreo del modelo generador donde
En sentido inverso, sólo es posible aprender modelos aproximados mediante regresión.
Las soluciones para los MDP con espacios de estado y acción finitos se pueden encontrar mediante diversos métodos, como la programación dinámica.
contendrá la suma descontada de las recompensas que se obtendrán (en promedio) siguiendo esa solución desde el estado
El algoritmo consta de dos pasos, (1) una actualización del valor y (2) una actualización de la política, que se repiten en cierto orden para todos los estados hasta que no se producen más cambios.
Ambos actualizan recursivamente una nueva estimación de la política óptima y del valor del estado utilizando una estimación más antigua de esos valores.
[5] En la iteración del valor (Bellman et al., 1957), también llamada inducción hacia atrás, el algoritmo
A continuación, se repite el primer paso y así sucesivamente.
Así, la repetición del paso dos hasta la convergencia puede interpretarse como la resolución de las ecuaciones lineales por relajación.
no cambia en el transcurso de la aplicación del paso 1 a todos los estados, el algoritmo se completa.
En la iteración de política modificada (van Nunen, 1976 y Puterman & Shin, 1978), el paso uno se realiza una vez y, a continuación, el paso dos se repite varias veces.
En esta variante, los pasos se aplican preferentemente a los estados que son de alguna manera importantes – ya sea basándose en el algoritmo (hubo grandes cambios en
Cuando esta suposición no es cierta, el problema se denomina proceso de decisión de Márkov parcialmente observable o (en inglés: partially observable Márkov decision process, POMDP).
El aprendizaje por refuerzo utiliza MDP en los que las probabilidades o recompensas son desconocidas.
[11] Para ello es útil definir una función adicional, que corresponde a tomar la acción
y luego continuar de forma óptima (o según la política que se tenga en ese momento):
se podría utilizar los siguientes modelo de programación lineal:
no es nativa y satisface las restricciones del problema D-LP.
Para analizar la ecuación de HJB, tenemos que reformular nuestro problema
La terminología y la notación de los MDP no están del todo definidas.
En adición, la probabilidad de transición a veces es escrita como
