En matemáticas, un proceso de decisión de Márkov (en inglés: Márkov decision process, MDP) es un proceso de control estocástico en tiempo discreto. 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. Los MDP se conocían al menos desde la década de 1950; un núcleo de investigación sobre los procesos de decisión de Márkov surgió del libro de Ronald Howard de 1960, Dynamic Programming and Márkov Processes. Se utilizan en muchas disciplinas, como la robótica, el control automático, la economía y la manufactura. El nombre de MDP procede del matemático ruso Andréi Márkov, ya que son una extensión de las cadenas de Márkov.

En cada paso temporal, el proceso se encuentra en el estado , y el responsable de la toma de decisiones puede elegir cualquier acción que esté disponible en el estado . El proceso responde en el siguiente paso temporal pasando aleatoriamente a un nuevo estado , y ofreciendo al responsable de la toma de decisiones la recompensa correspondiente .

La probabilidad de que el proceso pase a su nuevo estado está influida por la acción elegida. En concreto, viene dada por la función de transición de estado . Así, el siguiente estado depende del estado actual y de la acción del decisor . Pero dado y , es condicionalmente independiente de todos los estados y acciones anteriores; en otras palabras, las transiciones de estado de un MDP satisfacen la propiedad de Márkov.

Los procesos de decisión de Márkov son una extensión de las cadenas de Márkov; la diferencia estriba en la adición de acciones (que permiten elegir) y recompensas (que dan motivación). Por el contrario, si sólo existe una acción para cada estado (por ejemplo, "esperar") y todas las recompensas son iguales (por ejemplo, "cero"), un proceso de decisión de Márkov se reduce a una cadena de Márkov.

Definición miniaturadeimagen|400x400px|Ejemplo de un MDP simple con tres estados (círculos verdes) y dos acciones (círculos naranjas), con dos recompensas (flechas naranjas). Un proceso de decisión de Márkov es una 4-tupla , en el que:

es un conjunto de estados denominado espacio de estados, es un conjunto de acciones denominado espacio de acciones (alternativamente, es el conjunto de acciones disponibles a partir del estado ), es la probabilidad de que la acción en el estado en el momento conducirá al estado en el momento , es la recompensa inmediata (o recompensa inmediata esperada) recibida tras pasar del estado al estado debido a la acción

Los espacios de estados y acciones pueden ser finitos o infinitos, por ejemplo el conjunto de los números reales. Algunos procesos con espacios de estado y acción contablemente infinitos pueden reducirse a otros con espacios de estado y acción finitos.

Una función política es una correspondencia (potencialmente probabilística) entre el espacio de estados () al espacio de acción ().

Objetivo de optimización El objetivo en un proceso de decisión de Márkov es encontrar una buena "política" para el decisor: una función que especifica la acción que el decisor elegirá cuando se encuentre en el estado . Una vez que un proceso de decisión de Márkov se combina con una política de este modo, se fija la acción para cada estado y la combinación resultante se comporta como una cadena de Márkov (ya que la acción elegida en el estado está completamente determinada por y se reduce a , una matriz de transición de Márkov).

El objetivo es elegir una política que maximice alguna función acumulativa de las recompensas aleatorias, normalmente la suma descontada esperada en un horizonte potencialmente infinito:

(donde elegimos es decir, las acciones dadas por la política).

La expectativa se toma sobre , donde es el factor de descuento que satisface , que suele ser cercano a 1 (por ejemplo, para una tasa de descuento r). Un factor de descuento más bajo motiva al responsable de la toma de decisiones a favorecer la realización de acciones tempranas, en lugar de posponerlas indefinidamente.

Una política que maximiza la función anterior se denomina política óptima y suele denotarse como . Un MDP particular puede tener múltiples políticas óptimas distintas. Debido a la propiedad de Márkov, se puede demostrar que la política óptima es una función del estado actual, como se ha supuesto anteriormente.

Modelos de simulador En muchos casos, es difícil representar las distribuciones de probabilidad de transición, explícitamente. En tales casos, se puede utilizar un simulador para modelar el MDP implícitamente proporcionando muestras de las distribuciones de transición. Una forma común de modelo MDP implícito es un simulador de entorno episódico que puede iniciarse a partir de un estado inicial y produce un estado y una recompensa posteriores cada vez que recibe una entrada de acción. De este modo, se pueden producir trayectorias de estados, acciones y recompensas, a menudo denominadas episodios.

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. (Nótese que éste es un significado diferente del término modelo generador en el contexto de la clasificación estadística). En algoritmos que se expresan mediante pseudocódigo, se utiliza a menudo para representar un modelo generador. Por ejemplo, la expresión podría denotar la acción de muestreo del modelo generador donde y son el estado y la acción actuales, y y son el nuevo estado y la recompensa. En comparación con un simulador episódico, un modelo generador tiene la ventaja de que puede obtener datos de cualquier estado, no sólo de los encontrados en una trayectoria.

Estas clases de modelos forman una jerarquía de contenido informativo: un modelo explícito da lugar trivialmente a un modelo generador mediante el muestreo de las distribuciones, y la aplicación repetida de un modelo generador da lugar a un simulador episódico. En sentido inverso, sólo es posible aprender modelos aproximados mediante regresión. El tipo de modelo disponible para un MDP concreto desempeña un papel importante a la hora de determinar qué algoritmos de solución son adecuados. Por ejemplo, los algoritmos de programación dinámica descritos en la siguiente sección requieren un modelo explícito, y el árbol de búsqueda Monte Carlo requiere un modelo generador (o un simulador episódico que pueda copiarse en cualquier estado), mientras que la mayoría de los algoritmos de aprendizaje por refuerzo sólo requieren un simulador episódico.

Algoritmos 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. Los algoritmos de esta sección se aplican a los MDP con espacios de estados y acciones finitos y con probabilidades de transición y funciones de recompensa dadas explícitamente, pero los conceptos básicos pueden ampliarse para tratar otras clases de problemas, por ejemplo utilizando la aproximación de funciones.

La familia estándar de algoritmos para calcular políticas óptimas para MDPs de estado y acción finitos requiere almacenamiento para dos matrices indexadas por el estado: valor ,que contiene valores reales, y la política , que contiene acciones. Al final del algoritmo, contendrá la solución y 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.

Su orden depende de la variante del algoritmo; también se pueden hacer para todos los estados a la vez o estado por estado, y más a menudo a unos estados que a otros. Mientras no se excluya permanentemente ningún estado de ninguno de los pasos, el algoritmo acabará llegando a la solución correcta.

Variantes notables

Iteración de valor En la iteración del valor , también llamada inducción hacia atrás, el algoritmo no se utiliza; en su lugar, el valor de se calcula dentro de siempre que sea necesario. Sustituyendo el cálculo de en el cálculo de da el paso combinado:

donde es el número de iteración. La iteración del valor comienza en y como conjetura de la función de valor. A continuación, itera, calculando repetidamente para todos los estados , hasta que converge con el lado izquierdo igual al lado derecho (que es la "ecuación de Bellman" para este problema). El artículo de Lloyd Shapley de 1953 sobre juegos estocásticos incluía como caso especial el método de iteración de valor para MDP, pero esto no se reconoció hasta más tarde.

Iteración de políticas En la iteración de políticas , el paso uno se realiza una vez, y luego el paso dos se realiza una vez, luego ambos se repiten hasta que la política converge. A continuación, se repite el primer paso y así sucesivamente. (La iteración de políticas fue inventada por Howard para optimizar el envío por catálogo de Sears, que había estado optimizando utilizando la iteración de valores).

En lugar de repetir el paso dos hasta la convergencia, puede formularse y resolverse como un conjunto de ecuaciones lineales. Estas ecuaciones se obtienen simplemente haciendo en la ecuación del paso dos. Así, la repetición del paso dos hasta la convergencia puede interpretarse como la resolución de las ecuaciones lineales por relajación.

Esta variante tiene la ventaja de que existe una condición de parada definida: cuando la matriz no cambia en el transcurso de la aplicación del paso 1 a todos los estados, el algoritmo se completa.

La iteración de políticas suele ser más lenta que la iteración de valores para un gran número de estados posibles.

Iteración de política modificada En la iteración de política modificada (), el paso uno se realiza una vez y, a continuación, el paso dos se repite varias veces. A continuación, el paso uno se vuelve a realizar una vez y así sucesivamente.

Barrido priorizado 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 o en torno a esos estados recientemente) o en función del uso (esos estados están cerca del estado inicial, o son de interés para la persona o el programa que utiliza el algoritmo).

Extensiones y generalizaciones Un proceso de decisión de Márkov es un juego estocástico con un solo jugador.

Observabilidad parcial La solución anterior supone que el estado es conocido en el momento de actuar; en caso contrario no se puede calcular. 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).

Aprendizaje por refuerzo

El aprendizaje por refuerzo utiliza MDP en los que las probabilidades o recompensas son desconocidas.

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

Aunque esta función también se desconoce, la experiencia durante el aprendizaje se basa en pares (junto con el resultado ; es decir, "Estaba en el estado e intenté hacer y ocurrió "). Así, se tiene una matriz y se utiliza la experiencia para actualizarla directamente. Es lo que se conoce como Q-learning.