proceso de decisión de markov

Modelo matemático

En matemáticas, un proceso de decisión de Markov ( MDP ) es un proceso de control estocástico en tiempo discreto . Proporciona un marco matemático para modelar la toma de decisiones en situaciones donde los resultados son en parte aleatorios y en parte bajo el control de quien toma las decisiones. Los MDP son útiles para estudiar problemas de optimización resueltos mediante programación dinámica . Los MDP eran conocidos al menos ya en la década de 1950; ^[1] Un cuerpo central de investigación sobre los procesos de decisión de Markov resultó del libro de Ronald Howard de 1960, Programación dinámica y procesos de Markov . ^[2] Se utilizan en muchas disciplinas, incluida la robótica , el control automático , la economía y la fabricación . El nombre de MDP proviene del matemático ruso Andrey Markov ya que son una extensión de las cadenas de Markov .

En cada paso de tiempo, el proceso se encuentra en algún estado y quien toma las decisiones puede elegir cualquier acción que esté disponible en ese estado . El proceso responde en el siguiente paso moviéndose aleatoriamente a un nuevo estado y otorgando a quien toma la decisión la recompensa correspondiente . ${\displaystyle s}$ ${\displaystyle a}$ ${\displaystyle s}$ ${\displaystyle s'}$ ${\displaystyle R_{a}(s,s')}$

La probabilidad de que el proceso pase a su nuevo estado está influenciada por la acción elegida. En concreto, viene dada por la función de transición de estado . Por lo tanto, el siguiente estado depende del estado actual y de la acción de quien toma las decisiones . 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 Markov . ${\displaystyle s'}$ ${\displaystyle P_{a}(s,s')}$ ${\displaystyle s'}$ ${\displaystyle s}$ ${\displaystyle a}$ ${\displaystyle s}$ ${\displaystyle a}$

Los procesos de decisión de Markov son una extensión de las cadenas de Markov ; la diferencia es la suma de acciones (que permiten elegir) y recompensas (que motivan). 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 Markov se reduce a una cadena de Markov.

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 Markov es una tupla de 4 , donde: ${\displaystyle (S,A,P_{a},R_{a})}$

• ${\displaystyle S}$es un conjunto de estados llamado espacio de estados ,
• ${\displaystyle A}$es un conjunto de acciones llamado espacio de acción (alternativamente, es el conjunto de acciones disponibles desde el estado ), ${\displaystyle A_{s}}$ ${\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 en el estado en el momento conduzca al estado en el momento , ${\displaystyle a}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle s'}$ ${\displaystyle t+1}$
• ${\displaystyle R_{a}(s,s')}$es la recompensa inmediata (o recompensa inmediata esperada) recibida después de la transición de un estado a otro , debido a la acción ${\displaystyle s}$ ${\displaystyle s'}$ ${\displaystyle a}$

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

Una función política es un mapeo (potencialmente probabilístico) desde el espacio de estados ( ) al espacio de acción ( ). ${\displaystyle \pi }$ ${\displaystyle S}$ ${\displaystyle A}$

Objetivo de optimización

El objetivo en un proceso de decisión de Markov es encontrar una buena "política" para quien toma las decisiones: una función que especifica la acción que el tomador de decisiones elegirá cuando esté en estado . Una vez que un proceso de decisión de Markov se combina con una política de esta manera, esto fija la acción para cada estado y la combinación resultante se comporta como una cadena de Markov (ya que la acción elegida en el estado está completamente determinada por una matriz de transición de Markov y se reduce a ella ). . ${\displaystyle \pi }$ ${\displaystyle \pi (s)}$ ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle \pi (s)}$ ${\displaystyle \Pr(s_{t+1}=s'\mid s_{t}=s,a_{t}=a)}$ ${\displaystyle \Pr(s_{t+1}=s'\mid s_{t}=s)}$

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

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

¿Dónde está el factor de descuento que satisface , que suele ser cercano a 1 (por ejemplo, para alguna tasa de descuento r)? Un factor de descuento más bajo motiva a quien toma las decisiones a favorecer la adopción de medidas tempranas, en lugar de posponerlas indefinidamente. ${\displaystyle \ \gamma \ }$ ${\displaystyle 0\leq \ \gamma \ \leq \ 1}$ ${\displaystyle \gamma =1/(1+r)}$

Una política que maximiza la función anterior se denomina política óptima y generalmente se denota como . Un MDP particular puede tener múltiples políticas óptimas distintas. Debido a la propiedad de Markov, se puede demostrar que la política óptima es función del estado actual, como se asumió anteriormente. ${\displaystyle \pi ^{*}}$

Modelos de simulador

En muchos casos, es difícil representar explícitamente las distribuciones de probabilidad de transición. 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 se puede iniciar desde un estado inicial y produce un estado posterior y una recompensa cada vez que recibe una entrada de acción. De esta manera se pueden producir trayectorias de estados, acciones y recompensas, a menudo llamadas episodios . ${\displaystyle P_{a}(s,s')}$

Otra forma de simulador es un modelo generativo , un simulador de un solo paso que puede generar muestras del siguiente estado y recompensar cualquier estado y acción. ^[4] (Tenga en cuenta que este es un significado diferente del término modelo generativo en el contexto de la clasificación estadística). En algoritmos que se expresan mediante pseudocódigo , a menudo se usa para representar un modelo generativo. Por ejemplo, la expresión podría denotar la acción de muestrear del modelo generativo 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 generativo tiene la ventaja de que puede generar datos de cualquier estado, no sólo de aquellos que se encuentran en una trayectoria. ${\displaystyle G}$ ${\displaystyle s',r\gets G(s,a)}$ ${\displaystyle s}$ ${\displaystyle a}$ ${\displaystyle s'}$ ${\displaystyle r}$

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

Algoritmos

Se pueden encontrar soluciones para MDP con estados finitos y espacios de acción a través de una variedad de métodos, como la programación dinámica . Los algoritmos de esta sección se aplican a MDP con estados finitos y espacios de acción y probabilidades de transición y funciones de recompensa dadas explícitamente, pero los conceptos básicos pueden ampliarse para manejar otras clases de problemas, por ejemplo, usando la aproximación de funciones .

La familia estándar de algoritmos para calcular políticas óptimas para MDP de acción y estado finito requiere almacenamiento para dos matrices indexadas por estado: valor , que contiene valores reales, y 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 . ${\displaystyle V}$ ${\displaystyle \pi }$ ${\displaystyle \pi }$ ${\displaystyle V(s)}$ ${\displaystyle s}$

El algoritmo tiene dos pasos, (1) una actualización de valor y (2) una actualización de política, que se repiten en algún orden para todos los estados hasta que no se produzcan más cambios. Ambos actualizan recursivamente una nueva estimación de la política óptima y el valor estatal utilizando una estimación anterior 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 con más frecuencia para algunos estados que para otros. Mientras ningún estado quede permanentemente excluido de cualquiera de los pasos, el algoritmo eventualmente llegará a la solución correcta. ^[5]

Variantes notables

iteración de valor

En la iteración de valores (Bellman 1957), que también se denomina inducción hacia atrás , la función no se utiliza; en cambio, el valor de se calcula dentro de cada vez que sea necesario. Sustituir el cálculo de en el cálculo de da el paso combinado ^{[ se necesita más explicación ]} : ${\displaystyle \pi }$ ${\displaystyle \pi (s)}$ ${\displaystyle V(s)}$ ${\displaystyle \pi (s)}$ ${\displaystyle V(s)}$

${\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\},}$

¿Dónde está el número de iteración? La iteración del valor comienza en y como una suposición de la función de valor . Luego itera, calculando repetidamente todos los estados , hasta que converge con el lado izquierdo igual al lado derecho (que es la " ecuación de Bellman " para este problema ^{[ aclaración necesaria ]} ). El artículo de Lloyd Shapley de 1953 sobre juegos estocásticos incluía como caso especial el método de iteración de valores para MDP, ^[6] pero esto sólo se reconoció más tarde. ^[7] ${\displaystyle i}$ ${\displaystyle i=0}$ ${\displaystyle V_{0}}$ ${\displaystyle V_{i+1}}$ ${\displaystyle s}$ ${\displaystyle V}$

Iteración de políticas

En la iteración de políticas (Howard 1960), el paso uno se realiza una vez, luego el paso dos se realiza una vez y luego ambos se repiten hasta que la política converge. Luego se vuelve a realizar el paso uno una vez y así sucesivamente. (Howard inventó la iteración de políticas para optimizar el envío por correo del catálogo de Sears , que había estado optimizando mediante la iteración de valores. ^[8] )

En lugar de repetir el paso dos para la convergencia, se puede formular y resolver como un conjunto de ecuaciones lineales. Estas ecuaciones se obtienen simplemente haciendo la ecuación del paso dos. ^{[ se necesita aclaración ]} Por lo tanto, repetir el paso dos para la convergencia puede interpretarse como resolver las ecuaciones lineales por relajación . ${\displaystyle s=s'}$

Esta variante tiene la ventaja de que existe una condición de parada definida: cuando la matriz no cambia al aplicar el paso 1 a todos los estados, el algoritmo se completa. ${\displaystyle \pi }$

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

Iteración de política modificada

En la iteración de políticas modificadas (van Nunen 1976; Puterman y Shin 1978), el paso uno se realiza una vez y luego el paso dos se repite varias veces. ^{[9] [10]} Luego, el paso uno se realiza nuevamente una vez y así sucesivamente.

Barrido priorizado

En esta variante, los pasos se aplican preferentemente a estados que son de alguna manera importantes, ya sea en función del algoritmo (hubo grandes cambios en esos estados o alrededor de ellos recientemente) o en función del uso (esos estados están cerca del estado inicial, o de otra manera). de interés para la persona o programa que utiliza el algoritmo). ${\displaystyle V}$ ${\displaystyle \pi }$

Complejidad computacional

Existen algoritmos para encontrar políticas óptimas con polinomio de complejidad temporal en el tamaño de la representación del problema para MDP finitos. Por tanto, los problemas de decisión basados ​​en MDP se encuentran en la clase de complejidad computacional P. ^[11] Sin embargo, debido a la maldición de la dimensionalidad , el tamaño de la representación del problema es a menudo exponencial en el número de variables de estado y acción, lo que limita las técnicas de solución exacta a problemas que tienen una representación compacta. En la práctica, las técnicas de planificación en línea como la búsqueda de árboles de Monte Carlo pueden encontrar soluciones útiles en problemas más grandes y, en teoría, es posible construir algoritmos de planificación en línea que puedan encontrar una política arbitrariamente cercana a la óptima sin que la complejidad computacional dependa del tamaño. del espacio de estados. ^[12]

Extensiones y generalizaciones

Un proceso de decisión de Markov es un juego estocástico con un solo jugador.

Observabilidad parcial

La solución anterior supone que se conoce el estado en el que se deben tomar medidas; de lo contrario no se puede calcular. Cuando esta suposición no es cierta, el problema se denomina proceso de decisión de Markov parcialmente observable o POMDP. ${\displaystyle s}$ ${\displaystyle \pi (s)}$

Aprendizaje reforzado

El aprendizaje por refuerzo utiliza MDP donde se desconocen las probabilidades o recompensas. ^[13]

Para ello es útil definir una función adicional, que corresponde a tomar la acción y luego continuar de manera óptima (o de acuerdo con la política que uno tenga actualmente): ${\displaystyle a}$

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

Si bien 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 sucedió"). Por lo tanto, uno tiene una matriz y usa la experiencia para actualizarla directamente. Esto se conoce como Q-learning . ${\displaystyle (s,a)}$ ${\displaystyle s'}$ ${\displaystyle s}$ ${\displaystyle a}$ ${\displaystyle s'}$ ${\displaystyle Q}$

El aprendizaje por refuerzo puede resolver procesos de decisión de Markov sin una especificación explícita de las probabilidades de transición; los valores de las probabilidades de transición son necesarios en la iteración de valores y políticas. En el aprendizaje por refuerzo, en lugar de una especificación explícita de las probabilidades de transición, se accede a las probabilidades de transición a través de un simulador que normalmente se reinicia muchas veces desde un estado inicial uniformemente aleatorio. El aprendizaje por refuerzo también se puede combinar con la aproximación de funciones para abordar problemas con una gran cantidad 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. Este también es un tipo de aprendizaje por refuerzo si el entorno es estocástico. Narendra y Thathachar (1974) analizan el primer artículo detallado sobre autómatas de aprendizaje , que originalmente se describieron explícitamente como autómatas de estados finitos . ^[14] De manera similar al aprendizaje por refuerzo, un algoritmo de autómata de aprendizaje también tiene la ventaja de resolver el problema cuando se desconocen la probabilidad o las recompensas. 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 la probabilidad de acción directamente para encontrar el resultado del aprendizaje. Los autómatas de aprendizaje son un esquema de aprendizaje con una prueba rigurosa de convergencia. ^[15]

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

• un conjunto x de posibles entradas,
• un conjunto Φ = { Φ ₁ , ..., Φ _s } de posibles estados internos,
• un conjunto α = { α ₁ , ..., α _r } de posibles resultados, o acciones, con r ≤ s ,
• un vector de probabilidad de estado inicial 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 tal autómata corresponden a los estados de un " proceso de Markov de parámetros discretos y de estado discreto ". ^[16] 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) por A , elige aleatoriamente un estado sucesor de acuerdo con las probabilidades P ( t + 1) y genera 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. ^[15]

Interpretación teórica de categorías

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

De esta manera, los procesos de decisión de Markov podrían generalizarse desde monoides (categorías con un objeto) hasta categorías arbitrarias. Se puede llamar al resultado un proceso de decisión de Markov dependiente del contexto , porque pasar de un objeto a otro cambia el conjunto de acciones disponibles y el conjunto de estados posibles. ^{[ cita necesaria ]} ${\displaystyle ({\mathcal {C}},F:{\mathcal {C}}\to \mathbf {Dist} )}$ ${\displaystyle {\mathcal {C}}}$

Proceso de decisión de Markov en tiempo continuo

En los procesos de decisión de Markov en tiempo discreto, las decisiones se toman en intervalos de tiempo discretos. Sin embargo, para los procesos de decisión de Markov de tiempo continuo , las decisiones se pueden tomar en cualquier momento que elija el tomador de decisiones. En comparación con los procesos de decisión de Markov en tiempo discreto, los procesos de decisión de Markov en tiempo continuo pueden modelar mejor el proceso de toma de decisiones para un sistema que tiene 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 Markov en tiempo continuo, introducimos dos conjuntos de notaciones:

Si el espacio de estados y el espacio de acción son finitos,

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

Si el espacio de estados y el espacio de acción son continuos,

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

Problema

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

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

dónde ${\displaystyle 0\leq \gamma <1.}$

Formulación de programación lineal.

Si el espacio de estados y el espacio de acción son finitos, podríamos usar la programación lineal para encontrar la política óptima, que fue uno de los primeros enfoques aplicados. Aquí solo consideramos el modelo ergódico, lo que significa que nuestro MDP de tiempo continuo se convierte en una cadena de Markov ergódica de tiempo continuo bajo una política estacionaria . Bajo este supuesto, aunque quien toma las decisiones puede tomar una decisión en cualquier momento en el estado actual, no podría beneficiarse más al tomar más de una acción. Es mejor para ellos realizar una acción sólo en el momento en que el sistema está pasando del estado actual a otro estado. Bajo algunas condiciones (para obtener más detalles, consulte el Corolario 3.14 de Procesos de decisión de Markov en tiempo continuo), si nuestra función de valor óptimo es independiente del estado , tendremos la siguiente desigualdad: ${\displaystyle V^{*}}$ ${\displaystyle i}$

${\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 , entonces será la más pequeña que satisfaga la ecuación anterior. Para encontrar , podríamos usar el siguiente modelo de programación lineal: ${\displaystyle h}$ ${\displaystyle {\bar {V}}^{*}}$ ${\displaystyle g}$ ${\displaystyle {\bar {V}}^{*}}$

• Programa lineal primario (P-LP)

${\displaystyle {\begin{aligned}{\text{Minimize}}\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 dual (D-LP)

${\displaystyle {\begin{aligned}{\text{Maximize}}&\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{ and }}\forall i\in S\end{aligned}}}$

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

${\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 al D-LP. Una vez que hayamos encontrado la solución óptima , podemos utilizarla para establecer las políticas óptimas. ${\displaystyle y(i,a)}$ ${\displaystyle y^{*}(i,a)}$

Ecuación de Hamilton-Jacobi-Bellman

En MDP de tiempo continuo, si el espacio de estados 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 discutir la ecuación HJB, necesitamos 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, es el vector de estado del sistema, es el vector de control del sistema que intentamos encontrar. muestra cómo el vector de estado cambia con el tiempo. La ecuación de Hamilton-Jacobi-Bellman es la siguiente: ${\displaystyle x(t)}$ ${\displaystyle u(t)}$ ${\displaystyle f(\cdot )}$

${\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 , lo que podría darnos la función de valor óptimo. ${\displaystyle u(t)}$ ${\displaystyle V^{*}}$

Solicitud

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

Notaciones alternativas

La terminología y notación de los MDP no están completamente establecidas. Hay dos corrientes principales: una se centra en problemas de maximización de contextos como la economía, utilizando los términos acción, recompensa, valor y llamando al factor de descuento β o γ , mientras que la otra se centra en problemas de minimización de la ingeniería y la navegación ^{[ cita requerida ]} , usando los términos control, costo, costo restante y llamando al factor de descuento α . Además, la notación para la probabilidad de transición varía.

Además, a veces se escribe probabilidad de transición o , rara vez, ${\displaystyle \Pr(s,a,s')}$ ${\displaystyle \Pr(s'\mid s,a)}$ ${\displaystyle p_{s's}(a).}$

Procesos de decisión de Markov restringidos

Los procesos de decisión de Markov restringidos (CMDPS) son extensiones del proceso de decisión de Markov (MDP). Hay tres diferencias fundamentales entre MDP y CMDP. ^[17]

• Se incurre en múltiples costos después de aplicar una acción en lugar de una.
• Los CMDP se resuelven únicamente con programas lineales y la programación dinámica no funciona.
• La política final depende del estado inicial.

El método de los multiplicadores de Lagrange se aplica a los CMDP. Se han desarrollado muchos algoritmos basados ​​en Lagrangiano.

• Método primal-dual del gradiente de política natural. ^[18]

Hay varias aplicaciones para CMDP. Recientemente se ha utilizado en escenarios de planificación de movimiento en robótica. ^[19]

Ver también

• Autómatas probabilísticos
• Algoritmo de probabilidades
• Autómatas cuánticos finitos
• Proceso de decisión de Markov parcialmente observable
• Programación dinámica
• Ecuación de Bellman para aplicaciones a la economía.
• Ecuación de Hamilton-Jacobi-Bellman
• Control óptimo
• Economía recursiva
• Problema de las ovejas mabinogion
• Juegos estocásticos
• Q-aprendizaje

Referencias

1. Bellman, R. (1957). "Un proceso de decisión markoviano". Revista de Matemáticas y Mecánica . 6 (5): 679–684. JSTOR  24900506.
2. Howard, Ronald A. (1960). Programación Dinámica y Procesos de Markov . La prensa del MIT.
3. Wrobel, A. (1984). "Sobre modelos de decisión markovianos con un esqueleto finito". Métodos matemáticos de investigación de operaciones . 28 (febrero): 17–27. doi :10.1007/bf01919083. S2CID  2545336.
4. Kearns, Michael; Mansur, Yishay; Ng, Andrés (2002). "Un algoritmo de muestreo disperso para una planificación casi óptima en grandes procesos de decisión de Markov". Aprendizaje automático . 49 (193–208): 193–208. doi : 10.1023/A:1017932429737 .
5. Aprendizaje por refuerzo: teoría e implementación de Python . Beijing: Prensa de máquinas de China. 2019. pág. 44.ISBN​ 9787111631774.
6. Shapley, Lloyd (1953). "Juegos estocásticos". Actas de la Academia Nacional de Ciencias de los Estados Unidos de América . 39 (10): 1095-1100. Código bibliográfico : 1953PNAS...39.1095S. doi : 10.1073/pnas.39.10.1095 . PMC 1063912 . PMID  16589380. 
7. Kallenberg, Lodewijk (2002). "MDP de acción y estado finito". En Feinberg, Eugene A .; Shwartz, Adam (eds.). Manual de procesos de decisión de Markov: métodos y aplicaciones . Saltador. ISBN 978-0-7923-7459-6.
8. Howard 2002, "Comentarios sobre el origen y la aplicación de los procesos de decisión de Markov"
9. Puterman, ML; Shin, MC (1978). "Algoritmos de iteración de políticas modificados para problemas de decisión de Markov con descuento". Ciencias de la gestión . 24 (11): 1127-1137. doi :10.1287/mnsc.24.11.1127.
10. van Nunen, JAE E (1976). "Un conjunto de métodos de aproximación sucesivos para problemas de decisión de Markov con descuento". Zeitschrift für Investigación de operaciones . 20 (5): 203–208. doi :10.1007/bf01920264. S2CID  5167748.
11. Papadimitriou, Christos ; Tsitsiklis, John (1987). "La complejidad de los procesos de decisión de Markov". Matemáticas de la Investigación de Operaciones . 12 (3). doi :10.1287/moor.12.3.441. hdl : 1721.1/2893 . Consultado el 2 de noviembre de 2023 .
12. Kearns, Michael; Mansur, Yishay; Ng, Andrew (noviembre de 2002). "Un algoritmo de muestreo disperso para una planificación casi óptima en grandes procesos de decisión de Markov". Aprendizaje automático . 49 . doi : 10.1023/A:1017932429737 . Consultado el 2 de noviembre de 2023 .
13. Shoham, Y.; Poderes, R.; Granadero, T. (2003). "Aprendizaje por refuerzo multiagente: una encuesta crítica" (PDF) . Informe técnico, Universidad de Stanford : 1–13 . Consultado el 12 de diciembre de 2018 .
14. Narendra, KS ; Thathachar, MAL (1974). "Autómatas de aprendizaje: una encuesta". Transacciones IEEE sobre sistemas, hombre y cibernética . SMC-4 (4): 323–334. CiteSeerX 10.1.1.295.2280 . doi :10.1109/TSMC.1974.5408453. ISSN  0018-9472. 
15. Narendra, Kumpati S .; Thathachar, Mandayam AL (1989). Autómatas de aprendizaje: una introducción . Prentice Hall. ISBN 9780134855585.
16. Narendra y Thathachar 1974, p.325 izquierda.
17. Altman, Eitan (1999). "Procesos de decisión de Markov restringidos" . vol. 7. Prensa CRC.
18. Ding, Dongsheng; Zhang, Kaiqing; Jovanovic, Mihailo; Basar, domador (2020). "Método primal-dual del gradiente de política natural para procesos de decisión de Markov restringidos" . Avances en los sistemas de procesamiento de información neuronal.
19. Feyzabadi, S.; Carpin, S. (18 a 22 de agosto de 2014). "Planificación de rutas conscientes de los riesgos utilizando procesos de decisión de Markov jerárquicos restringidos". Ciencia e Ingeniería de Automatización (CASE) . Conferencia Internacional IEEE. págs.297, 303.

Otras lecturas

• Bellman., RE (2003) [1957]. Programación dinámica (edición de bolsillo de Dover). Princeton, Nueva Jersey: Princeton University Press. ISBN 978-0-486-42809-3.
• Bertsekas, D. (1995). Programación Dinámica y Control Óptimo . vol. 2. MA: Atenea.
• Derman, C. (1970). "Procesos de decisión markovianos de estado finito" . Prensa académica.
• Feinberg, EA; Shwartz, A., eds. (2002). Manual de procesos de decisión de Markov. Boston, MA: Kluwer. ISBN 9781461508052.
• Guo, X.; Hernández-Lerma, O. (2009). Procesos de decisión de Markov en tiempo continuo. Modelización estocástica y probabilidad aplicada. Saltador. ISBN 9783642025464.
• Meyn, SP (2007). Técnicas de Control de Redes Complejas. Prensa de la Universidad de Cambridge. ISBN 978-0-521-88441-9. Archivado desde el original el 19 de junio de 2010.El apéndice contiene "Meyn & Tweedie" abreviado. Archivado desde el original el 18 de diciembre de 2012.
• Puterman., ML (1994). Procesos de decisión de Markov . Wiley.
• Ross, SM (1983). Introducción a la programación dinámica estocástica (PDF) . Prensa académica.
• Sutton, RS; Barto, AG (2017). Aprendizaje por refuerzo: una introducción. Cambridge, MA: The MIT Press.
• Tijms., HC (2003). Un primer curso de modelos estocásticos. Wiley. ISBN 9780470864289.

enlaces externos

• Aprender a resolver procesos de decisión markovianos por Satinder P. Singh