Proceso de decisión de Márkov

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;[1]​ 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.[2]​ 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 ${\displaystyle s}$, y el responsable de la toma de decisiones puede elegir cualquier acción ${\displaystyle a}$ que esté disponible en el estado ${\displaystyle s}$. El proceso responde en el siguiente paso temporal pasando aleatoriamente a un nuevo estado ${\displaystyle s'}$, y ofreciendo al responsable de la toma de decisiones la recompensa correspondiente ${\displaystyle R_{a}(s,s')}$.

La probabilidad de que el proceso pase a su nuevo estado ${\displaystyle s'}$ está influida por la acción elegida. En concreto, viene dada por la función de transición de estado ${\displaystyle P_{a}(s,s')}$. Así, el siguiente estado ${\displaystyle s'}$ depende del estado actual ${\displaystyle s}$ y de la acción del decisor ${\displaystyle a}$. Pero dado ${\displaystyle s}$ y ${\displaystyle a}$, 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

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 ${\displaystyle (S,A,P_{a},R_{a})}$, en el que:

• ${\displaystyle S}$ es un conjunto de estados denominado espacio de estados,
• ${\displaystyle A}$ es un conjunto de acciones denominado espacio de acciones (alternativamente, ${\displaystyle A_{s}}$ es el conjunto de acciones disponibles a partir del estado ${\displaystyle s}$),
• ${\displaystyle P_{a}(s,s')=\Pr(s_{t+1}=s'\mid s_{t}=s,a_{t}=a)}$ es la probabilidad de que la acción ${\displaystyle a}$ en el estado ${\displaystyle s}$ en el momento ${\displaystyle t}$ conducirá al estado ${\displaystyle s'}$ en el momento ${\displaystyle t+1}$,
• ${\displaystyle R_{a}(s,s')}$ es la recompensa inmediata (o recompensa inmediata esperada) recibida tras pasar del estado ${\displaystyle s}$ al estado ${\displaystyle s'}$ debido a la acción ${\displaystyle a}$

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.[3]​

Una función política ${\displaystyle \pi }$ es una correspondencia (potencialmente probabilística) entre el espacio de estados (${\displaystyle S}$) al espacio de acción (${\displaystyle A}$).

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 ${\displaystyle \pi }$ que especifica la acción ${\displaystyle \pi (s)}$ que el decisor elegirá cuando se encuentre en el estado ${\displaystyle s}$. 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 ${\displaystyle s}$ está completamente determinada por ${\displaystyle \pi (s)}$ y ${\displaystyle \Pr(s_{t+1}=s'\mid s_{t}=s,a_{t}=a)}$ se reduce a ${\displaystyle \Pr(s_{t+1}=s'\mid s_{t}=s)}$, una matriz de transición de Márkov).

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

${\displaystyle E\left[\sum _{t=0}^{\infty }{\gamma ^{t}R_{a_{t}}(s_{t},s_{t+1})}\right]}$ (donde elegimos ${\displaystyle a_{t}=\pi (s_{t})}$ es decir, las acciones dadas por la política).

La expectativa se toma sobre ${\displaystyle s_{t+1}\sim P_{a_{t}}(s_{t},s_{t+1})}$, donde ${\displaystyle \gamma }$ es el factor de descuento que satisface ${\displaystyle 0\leq \ \gamma \ \leq \ 1}$, que suele ser cercano a 1 (por ejemplo, ${\displaystyle \gamma =1/(1+r)}$ 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 ${\displaystyle \pi ^{*}}$. 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, ${\displaystyle P_{a}(s,s')}$ 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.[4]​ (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, ${\displaystyle G}$ se utiliza a menudo para representar un modelo generador. Por ejemplo, la expresión ${\displaystyle s',r\gets G(s,a)}$ podría denotar la acción de muestreo del modelo generador donde ${\displaystyle s}$ y ${\displaystyle a}$ son el estado y la acción actuales, y ${\displaystyle s'}$ y ${\displaystyle r}$ 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 ${\displaystyle V}$,que contiene valores reales, y la política ${\displaystyle \pi }$, que contiene acciones. Al final del algoritmo, ${\displaystyle \pi }$ contendrá la solución y ${\displaystyle V(s)}$ contendrá la suma descontada de las recompensas que se obtendrán (en promedio) siguiendo esa solución desde el estado ${\displaystyle s}$.

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.

${\displaystyle V(s):=\sum _{s'}P_{\pi (s)}(s,s')\left(R_{\pi (s)}(s,s')+\gamma V(s')\right)}$

${\displaystyle \pi (s):=\operatorname {argmax} _{a}\left\{\sum _{s'}P_{a}(s,s')\left(R_{a}(s,s')+\gamma V(s')\right)\right\}}$

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.[5]​

Variantes notables

Iteración de valor

En la iteración del valor (Bellman et al., 1957), también llamada inducción hacia atrás, el algoritmo ${\displaystyle \pi }$ no se utiliza; en su lugar, el valor de ${\displaystyle \pi (s)}$ se calcula dentro de ${\displaystyle V(s)}$ siempre que sea necesario. Sustituyendo el cálculo de ${\displaystyle \pi (s)}$ en el cálculo de ${\displaystyle V(s)}$ da el paso combinado:

${\displaystyle V_{i+1}(s):=\max _{a}\left\{\sum _{s'}P_{a}(s,s')\left(R_{a}(s,s')+\gamma V_{i}(s')\right)\right\},}$

donde ${\displaystyle i}$ es el número de iteración. La iteración del valor comienza en ${\displaystyle i=0}$ y ${\displaystyle V_{0}}$ como conjetura de la función de valor. A continuación, itera, calculando repetidamente ${\displaystyle V_{i+1}}$ para todos los estados ${\displaystyle s}$, hasta que ${\displaystyle V}$ 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,[6]​ pero esto no se reconoció hasta más tarde.[7]​

Iteración de políticas

En la iteración de políticas (Howard et al., 1960), 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[8]​).

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 ${\displaystyle s=s'}$ 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 ${\displaystyle \pi }$ 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 (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.[9]​[10]​ 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 ${\displaystyle V}$ o ${\displaystyle \pi }$ 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 ${\displaystyle s}$ es conocido en el momento de actuar; en caso contrario ${\displaystyle \pi (s)}$ 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.[11]​

Para ello es útil definir una función adicional, que corresponde a tomar la acción ${\displaystyle a}$ y luego continuar de forma óptima (o según la política que se tenga en ese momento):

${\displaystyle \ Q(s,a)=\sum _{s'}P_{a}(s,s')(R_{a}(s,s')+\gamma V(s')).\ }$

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

El aprendizaje por refuerzo puede resolver procesos de decisión de Márkov sin especificar explícitamente las probabilidades de transición; los valores de las probabilidades de transición se necesitan en la iteración de valores y políticas. En el aprendizaje por refuerzo, en lugar de especificar explícitamente las probabilidades de transición, se accede a ellas a través de un simulador que suele reiniciarse muchas veces a partir de un estado inicial uniformemente aleatorio. El aprendizaje por refuerzo también puede combinarse con la aproximación de funciones para abordar problemas con un número muy elevado de estados.

Autómatas de aprendizaje

Otra aplicación del proceso MDP en la teoría del aprendizaje automático se denomina autómata de aprendizaje. Se trata también de un tipo de aprendizaje por refuerzo si el entorno es estocástico. El primer artículo detallado sobre los autómatas de aprendizaje es el de Narendra y Thathachar (1974), que originalmente se describieron explícitamente como autómatas de estado finito.[12]​ De forma similar al aprendizaje por refuerzo, un algoritmo de autómatas de aprendizaje también tiene la ventaja de resolver el problema cuando la probabilidad o las recompensas son desconocidas. La diferencia entre los autómatas de aprendizaje y el Q-learning es que la primera técnica omite la memoria de los valores Q, pero actualiza directamente la probabilidad de acción para hallar el resultado del aprendizaje. Los autómatas de aprendizaje son un esquema de aprendizaje con una prueba rigurosa de convergencia.[13]​

En la teoría de los autómatas de aprendizaje, un autómata estocástico consiste en:

• un conjunto x de posibles entradas,
• un conjunto Φ = { Φ₁, ..., Φ_s } de posibles estados internos,
• un conjunto α = { α₁, ..., α_r } de posibles salidas, o acciones, con r ≤ s,
• un vector inicial de probabilidad de estado p(0) = ≪ p₁(0), ..., p_s(0) ≫,
• una función computable A que después de cada paso de tiempo t genera p(t + 1) a partir de p(t), la entrada actual y el estado actual, y
• una función G: Φ → α que genera la salida en cada paso de tiempo.

Los estados de un autómata de este tipo corresponden a los estados de un "proceso de Márkov de parámetros discretos de estado discreto".[14]​ En cada paso de tiempo t = 0,1,2,3,..., el autómata lee una entrada de su entorno, actualiza P(t) a P(t + 1) mediante A, elige aleatoriamente un estado sucesor según las probabilidades P(t + 1) y emite la acción correspondiente. El entorno del autómata, a su vez, lee la acción y envía la siguiente entrada al autómata.[13]​

Interpretación teórica de las categorías

Aparte de las recompensas, un proceso de decisión de Márkov ${\displaystyle (S,A,P)}$ puede entenderse en términos de teoría de categorías. A saber, ${\displaystyle {\mathcal {A}}}$ el monoide libre con el conjunto generador A. Dist denota la categoría de Kleisli de la mónada de Giry. Entonces un functor ${\displaystyle {\mathcal {A}}\to \mathbf {Dist} }$ codifica tanto el conjunto S de estados como la función de probabilidad P.

De este modo, los procesos de decisión de Márkov podrían generalizarse de los monoides (categorías con un objeto) a categorías arbitrarias. Se puede llamar al resultado ${\displaystyle ({\mathcal {C}},F:{\mathcal {C}}\to \mathbf {Dist} )}$ un proceso de decisión de Márkov dependiente del , porque pasar de un objeto a otro en ${\displaystyle {\mathcal {C}}}$ cambia el conjunto de acciones disponibles y el conjunto de estados posibles.

Proceso de decisión de Márkov de tiempo continuo

En los procesos de decisión de Márkov de tiempo discreto, las decisiones se toman en intervalos de tiempo discretos. Sin embargo, en los procesos de decisión de Márkov de tiempo continuo, las decisiones pueden tomarse en cualquier momento que elija el decisor. En comparación con los procesos de decisión de Márkov de tiempo discreto, los procesos de decisión de Márkov de tiempo continuo pueden modelar mejor el proceso de toma de decisiones para un sistema que tiene una dinámica continua, es decir, la dinámica del sistema está definida por ecuaciones diferenciales ordinarias (EDO).

Definición

Para analizar el proceso de decisión de Márkov de tiempo continuo, introducimos dos conjuntos de notaciones:

Si el espacio de estados y el espacio de acciones son finitos,

• ${\displaystyle {\mathcal {S}}}$: Espacio de estados;
• ${\displaystyle {\mathcal {A}}}$: Espacio de acción;
• ${\displaystyle q(i\mid j,a)}$: ${\displaystyle {\mathcal {S}}\times {\mathcal {A}}\rightarrow \triangle {\mathcal {S}}}$, función de tasa de transición;
• ${\displaystyle R(i,a)}$: ${\displaystyle {\mathcal {S}}\times {\mathcal {A}}\rightarrow \mathbb {R} }$, una función de recompensa.

Si el espacio de estados y el espacio de acciones son continuos,

• ${\displaystyle {\mathcal {X}}}$: espacio de estados;
• ${\displaystyle {\mathcal {U}}}$: espacio de control posible;
• ${\displaystyle f(x,u)}$: ${\displaystyle {\mathcal {X}}\times {\mathcal {U}}\rightarrow \triangle {\mathcal {X}}}$: una función de tasa de transición;
• ${\displaystyle r(x,u)}$: ${\displaystyle {\mathcal {X}}\times {\mathcal {U}}\rightarrow \mathbb {R} }$ una función de tasa de recompensa tal que ${\displaystyle r(x(t),u(t))\,dt=dR(x(t),u(t))}$, , donde ${\displaystyle R(x,u)}$ es la función de recompensa de la que hablamos en el caso anterior.

Problema

Al igual que en los procesos de decisión de Márkov en tiempo discreto, en los procesos de decisión de Márkov en tiempo continuo queremos encontrar la política o el control óptimo que pueda darnos la recompensa integrada óptima esperada:

${\displaystyle \max \operatorname {E} _{u}\left[\left.\int _{0}^{\infty }\gamma ^{t}r(x(t),u(t))\,dt\;\right|x_{0}\right]}$

en el que ${\displaystyle 0\leq \gamma <1.}$

Formulación de la programación lineal

Si el espacio de estados y el espacio de acciones son finitos, podríamos utilizar la programación lineal para encontrar la política óptima, que fue uno de los primeros enfoques aplicados. Aquí sólo consideramos el modelo ergódico, lo que significa que nuestro MDP de tiempo continuo se convierte en una cadena de Márkov ergódica de tiempo continuo bajo una política estacionaria. Bajo este supuesto, aunque el decisor puede tomar una decisión en cualquier momento en el estado actual, no podría beneficiarse más tomando más de una acción. Es mejor que tomen una acción sólo en el momento en que el sistema pasa del estado actual a otro estado. En determinadas condiciones (para más detalles, véase el corolario 3.14 de Procesos de decisión de Márkov en tiempo continuo), si nuestra función de valor óptimo ${\displaystyle V^{*}}$ es independiente del estado ${\displaystyle i}$ tendremos la siguiente desigualdad:

${\displaystyle g\geq R(i,a)+\sum _{j\in S}q(j\mid i,a)h(j)\quad \forall i\in S{\text{ and }}a\in A(i)}$

Si existe una función ${\displaystyle h}$, entonces ${\displaystyle {\bar {V}}^{*}}$ será el ${\displaystyle g}$ más pequeño que safisface la ecuación. Para hallar ${\displaystyle {\bar {V}}^{*}}$ se podría utilizar los siguientes modelo de programación lineal:

• Programa lineal primario (P-LP)

${\displaystyle {\begin{aligned}{\text{Minimizar}}\quad &g\\{\text{s.t}}\quad &g-\sum _{j\in S}q(j\mid i,a)h(j)\geq R(i,a)\,\,\forall i\in S,\,a\in A(i)\end{aligned}}}$

• Programa lineal doble o dual (D-LP)

${\displaystyle {\begin{aligned}{\text{Maximizar}}&\sum _{i\in S}\sum _{a\in A(i)}R(i,a)y(i,a)\\{\text{s.t.}}&\sum _{i\in S}\sum _{a\in A(i)}q(j\mid i,a)y(i,a)=0\quad \forall j\in S,\\&\sum _{i\in S}\sum _{a\in A(i)}y(i,a)=1,\\&y(i,a)\geq 0\qquad \forall a\in A(i){\text{ y }}\forall i\in S\end{aligned}}}$

${\displaystyle y(i,a)}$ es una solución factible para el D-LP si ${\displaystyle y(i,a)}$ no es nativa y satisface las restricciones del problema D-LP. Una solución factible ${\displaystyle y^{*}(i,a)}$ al D-LP se dice que es una solución óptima si

${\displaystyle {\begin{aligned}\sum _{i\in S}\sum _{a\in A(i)}R(i,a)y^{*}(i,a)\geq \sum _{i\in S}\sum _{a\in A(i)}R(i,a)y(i,a)\end{aligned}}}$

para toda solución factible ${\displaystyle y(i,a)}$ al D-LP. Una vez que hemos encontrado la solución óptima ${\displaystyle y^{*}(i,a)}$, podemos utilizarlo para establecer las políticas óptimas.

Ecuación de Hamilton-Jacobi-Bellman

En un MDP de tiempo continuo, si el espacio de estado y el espacio de acción son continuos, el criterio óptimo podría encontrarse resolviendo la ecuación diferencial parcial de Hamilton-Jacobi-Bellman (HJB). Para analizar la ecuación de HJB, tenemos que reformular nuestro problema

${\displaystyle {\begin{aligned}V(x(0),0)={}&\max _{u}\int _{0}^{T}r(x(t),u(t))\,dt+D[x(T)]\\{\text{s.t.}}\quad &{\frac {dx(t)}{dt}}=f[t,x(t),u(t)]\end{aligned}}}$

${\displaystyle D(\cdot )}$ es la función de recompensa terminal, ${\displaystyle x(t)}$ es el vector de estado del sistema, ${\displaystyle u(t)}$ es el vector de control del sistema que tratamos de encontrar. ${\displaystyle f(\cdot )}$ muestra cómo el vector de estado cambia con el tiempo. La ecuación de Hamilton-Jacobi-Bellman es la siguiente:

${\displaystyle 0=\max _{u}(r(t,x,u)+{\frac {\partial V(t,x)}{\partial x}}f(t,x,u))}$

Podríamos resolver la ecuación para encontrar el control óptimo ${\displaystyle u(t)}$, lo que podría darnos la función de valor óptimo ${\displaystyle V^{*}}$.

Aplicación

Los procesos de decisión de Márkov en tiempo continuo tienen aplicaciones en sistemas de colas, procesos epidémicos y procesos poblacionales.

Notaciones alternativas

La terminología y la notación de los MDP no están del todo definidas. Hay dos corrientes principales: una se centra en los problemas de maximización de contextos como la economía, utilizando los términos acción, recompensa, valor, y llamando al factor de descuento ${\displaystyle \beta }$ o γ, mientras que la otra se centra en los problemas de minimización de la ingeniería y la navegación, utilizando los términos control, coste, coste a ir, y llamando al factor de descuento α. Además, la notación para la probabilidad de transición varía.

en este artículo	alternativa	comentario
acción a	control u
recompensa R	coste g	g es el negativo de R
valor V	coste a ir J	J es el negativo de V
política π	política μ
factor de descuento γ	factor de descuento α
probabilidad de transición ${\displaystyle P_{a}(s,s')}$	probabilidad de transición ${\displaystyle p_{ss'}(a)}$

En adición, la probabilidad de transición a veces es escrita como ${\displaystyle \Pr(s,a,s')}$, ${\displaystyle \Pr(s'\mid s,a)}$ o, raras veces, ${\displaystyle p_{s's}(a).}$

Procesos de decisión de Márkov restringidos

Los procesos de decisión de Márkov restringidos (en inglés: constrained Márkov decision processes, CMDPS) son extensiones de los procesos de decisión de Márkov (MDP). Existen tres diferencias fundamentales entre los MDP y los CMDP.[15]​

• Hay múltiples costes en los que se incurre tras aplicar una acción en lugar de uno.
• Los CMDP se resuelven sólo con programas lineales, y la programación dinámica no funciona.
• La política final depende del estado inicial.

Los CMDP tienen varias aplicaciones. Recientemente se ha utilizado en escenarios de planificación de movimiento en robótica.[16]​

Véase también

• Programación dinámica
• Ecuación de Bellman
• Ecuación de Hamilton-Jacobi-Bellman
• Control óptimo
• Juego estocástico
• Q-learning

Referencias

1. Bellman, R. (1957). «A Markovian Decision Process». Journal of Mathematics and Mechanics 6 (5): 679-684. 
2. Howard, Ronald A. (1960). Dynamic Programming and Markov Processes. The M.I.T. Press. 
3. Wrobel, A. (1984). «On Markovian Decision Models with a Finite Skeleton». Mathematical Methods of Operations Research 28 (Febrero): 17-27. doi:10.1007/bf01919083. 
4. Kearns, Michael; Mansour, Yishay; Ng, Andrew (2002). «A Sparse Sampling Algorithm for Near-Optimal Planning in Large Markov Decision Processes». Machine Learning 49 (193–208): 193-208. doi:10.1023/A:1017932429737. 
5. Reinforcement Learning: Theory and Python Implementation. Beijing: China Machine Press. 2019. p. 44. ISBN 9787111631774. 
6. Shapley, Lloyd (1953). «Stochastic Games». Proceedings of the National Academy of Sciences of the United States of America 39 (10): 1095-1100. Bibcode:1953PNAS...39.1095S. PMC 1063912. PMID 16589380. doi:10.1073/pnas.39.10.1095. 
7. Kallenberg, Lodewijk (2002). «Finite state and action MDPs». En Feinberg, Eugene A.; Shwartz, Adam, eds. Handbook of Markov decision processes: methods and applications. Springer. ISBN 978-0-7923-7459-6. 
8. Howard (2002). Comments on the Origin and Application of Markov Decision Processes. 
9. Puterman, M. L.; Shin, M. C. (1978). «Modified Policy Iteration Algorithms for Discounted Markov Decision Problems». Management Science 24 (11): 1127-1137. doi:10.1287/mnsc.24.11.1127. 
10. van Nunen, J.A. E. E (1976). «A set of successive approximation methods for discounted Markovian decision problems». Zeitschrift für Operations Research 20 (5): 203-208. doi:10.1007/bf01920264. 
11. Shoham, Y.; Powers, R.; Grenager, T. (2003). «Multi-agent reinforcement learning: a critical survey». Technical Report, Stanford University: 1-13. Consultado el 12 de diciembre de 2018. 
12. Narendra, K. S.; Thathachar, M. A. L. (1974). «Learning Automata – A Survey». IEEE Transactions on Systems, Man, and Cybernetics. SMC-4 (4): 323-334. ISSN 0018-9472. doi:10.1109/TSMC.1974.5408453. 
13. Narendra, Kumpati S.; Thathachar, Mandayam A. L. (1989). Learning automata: An introduction (en inglés). Prentice Hall. ISBN 9780134855585. 
14. Narendra y Thathachar, 1974, pp. p.325.
15. Altman, Eitan (1999). Constrained Markov decision processes 7. CRC Press. 
16. Feyzabadi, S.; Carpin, S. (2014). «Risk-aware path planning using hierarchical constrained Markov Decision Processes». IEEE International Conference (Automation Science and Engineering (CASE)): 297, 303. 

Lectura adicional

• Bellman, R. E. (2003). Dynamic Programming. Princeton, NJ: Princeton University Press. ISBN 978-0-486-42809-3. 
• Bertsekas, D. (1995). Dynamic Programming and Optimal Control 2. MA: Athena. 
• Derman, C. (1970). Finite state Markovian decision processes. Academic Press. 
• Feinberg, E.A., Shwartz, A., ed. (2002). Handbook of Markov Decision Processes. Boston, MA: Kluwer. ISBN 9781461508052. 
• Guo, X.; Hernández-Lerma, O. (2009). Continuous-Time Markov Decision Processes. Stochastic Modelling and Applied Probability. Springer. ISBN 9783642025464. 
• Meyn, S. P. (2007). Control Techniques for Complex Networks. Cambridge University Press. ISBN 978-0-521-88441-9. Archivado desde el original el 19 de junio de 2010.  El apéndice contiene un resumen de "Meyn & Tweedie". Archivado desde el original el 18 de diciembre de 2012.
• Puterman, M. L. (1994). Markov Decision Processes. Wiley. 
• Ross, S. M. (1983). Introduction to stochastic dynamic programming. Academic press. 
• Sutton, R. S.; Barto, A. G. (2017). Reinforcement Learning: An Introduction. Cambridge, MA: The MIT Press. 
• Tijms., H.C. (2003). A First Course in Stochastic Models. Wiley. ISBN 9780470864289. 

Enlaces externos

• Learning to Solve Márkovian Decision Processes (en inglés), por Satinder P. Singh.