Proceso de decisión de Markov - Markov decision process

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 en las que los resultados son en parte aleatorios y en parte están 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 PMD se conocían al menos desde la década de 1950; Un cuerpo central de investigación sobre los procesos de decisión de Markov resultó del libro de 1960 de Ronald Howard , Programación dinámica y procesos de Markov . 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 el tomador de decisiones puede elegir cualquier acción que esté disponible en el estado . El proceso responde en el siguiente paso de tiempo moviéndose aleatoriamente a un nuevo estado y dando al tomador de decisiones 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. Específicamente, viene dado por la función de transición de estado . Por lo tanto, el siguiente estado depende del estado actual y de la acción del tomador de 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 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 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 del 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 un estado en un momento lleve a un estado en un 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 números reales . Algunos procesos con espacios de acción y estado infinitos pueden reducirse a procesos con espacios de acción y estado finitos.

Una función de política es un mapeo (potencialmente probabilístico) del 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 el tomador de decisiones: una función que especifica la acción que el tomador de decisiones elegirá cuando esté en el 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 y se reduce a una matriz de transición de Markov). . ${\ 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, normalmente 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 hace cargo${\ Displaystyle a_ {t} = \ pi (s_ {t})}$${\ Displaystyle s_ {t + 1} \ sim P_ {a_ {t}} (s_ {t}, s_ {t + 1})}$

donde es satisfactorio el factor de descuento , que suele estar cerca de 1 (por ejemplo, para alguna tasa de descuento r). Un factor de descuento más bajo motiva al tomador de decisiones a favorecer la adopción de medidas anticipadas, 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 . Un MDP en particular puede tener múltiples políticas óptimas distintas. Debido a la propiedad de Markov, se puede demostrar que la política óptima es una función del estado actual, como se supuso 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 puede iniciarse 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 dado cualquier estado y acción. (Tenga en cuenta que este es un significado diferente del término modelo generativo en el contexto de la clasificación estadística). En los algoritmos que se expresan mediante pseudocódigo , a menudo se utiliza para representar un modelo generativo. Por ejemplo, la expresión podría denotar la acción de muestreo 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 producir datos de cualquier estado, no solo de los que se encuentran en una trayectoria. ${\ Displaystyle G}$${\ Displaystyle s ', r \ obtiene G (s, a)}$${\ Displaystyle s}$${\ Displaystyle a}$${\ Displaystyle s '}$${\ Displaystyle r}$

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

Algoritmos

Las soluciones para los MDP con estados finitos y espacios de acción se pueden encontrar 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 extenderse 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 de forma recursiva 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 ') \ derecha)}$

${\ Displaystyle \ pi (s): = \ operatorname {argmax} _ {a} \ left \ {\ sum _ {s '} P (s' \ mid s, a) \ left (R (s '\ mid s , a) + \ 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 para algunos estados que para otros. Siempre que no se excluya permanentemente ningún estado de ninguno de los pasos, el algoritmo finalmente llegará a la solución correcta.

Variantes notables

Iteración de valor

En la iteración de valor ( Bellman 1957 ), que también se llama inducción hacia atrás , la función no se utiliza; en su lugar, el valor de se calcula dentro siempre que sea necesario. Sustituyendo el cálculo de en el cálculo de da el paso combinado: ${\ 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 \},}$

donde es el número de iteración. La iteración de valor comienza en y como una suposición de la función de valor . Luego 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 los MDP, pero esto se reconoció solo más tarde. ${\ 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 y luego el paso dos se repite hasta que converge. Luego, el paso uno se vuelve a realizar una vez y así sucesivamente.

En lugar de repetir el paso dos hacia la convergencia, se puede formular y resolver como un conjunto de ecuaciones lineales. Estas ecuaciones se obtienen simplemente haciendo en el paso dos la ecuación. Por lo tanto, repetir el paso dos hacia la convergencia se puede interpretar como resolver las ecuaciones lineales por relajación (método iterativo)${\ Displaystyle s = s '}$

Esta variante tiene la ventaja de que existe una condición de parada definida: cuando la matriz no cambia en el curso de la aplicación del 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ítica modificada ( van Nunen 1976 ; Puterman y Shin 1978 ), el paso uno se realiza una vez y luego el paso dos se repite varias veces. 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}$

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 asume que se conoce el estado cuando se debe tomar acción; 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)}$

Burnetas y Katehakis proporcionaron un avance importante en esta área en "Políticas de adaptación óptimas para los procesos de decisión de Markov". En este trabajo, se construyó una clase de políticas adaptativas que poseen propiedades de tasa de convergencia máxima uniforme para la recompensa total esperada del horizonte finito bajo los supuestos de espacios de acción estatal finitos y la irreductibilidad de la ley de transición. Estas políticas prescriben que la elección de acciones, en cada estado y período de tiempo, debe basarse en índices que son inflaciones del lado derecho de las ecuaciones de optimización de recompensa promedio estimadas.

Aprendizaje reforzado

El aprendizaje por refuerzo utiliza MDP donde se desconocen las probabilidades o recompensas.

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 se 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 es desconocida, la experiencia durante el aprendizaje se basa en pares (junto con el resultado ; es decir, "estaba en 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 los 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 el valor y la iteración de la política. En el aprendizaje por refuerzo, en lugar de la 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 llama autómatas de aprendizaje. Este es también un tipo de aprendizaje por refuerzo si el entorno es estocástico. El primer detalle autómatas aprendizaje papel se inspeccionó por Narendra y Thathachar (1974), que fueron originalmente descrito explícitamente como autómatas de estado finito . Similar al aprendizaje por refuerzo, un algoritmo de autómatas de aprendizaje también tiene la ventaja de resolver el problema cuando se desconocen la probabilidad o las recompensas. La diferencia entre el aprendizaje de autómatas y el Q-learning es que la técnica anterior omite la memoria de los valores Q, pero actualiza la probabilidad de acción directamente para encontrar el resultado del aprendizaje. El aprendizaje de autómatas es un esquema de aprendizaje con una rigurosa prueba de convergencia.

En el aprendizaje de la teoría de los autómatas, 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 salidas 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 de estado discreto ". 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 el 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.

Interpretación de la teoría de categorías

Aparte de las recompensas, un proceso de decisión de Markov se puede entender en términos de la teoría de categorías . Es decir, dejar que denotan el monoide libre con el grupo electrógeno A . Dejemos que Dist denote la categoría Kleisli de la mónada de Giry . Entonces un funtor codifica tanto el conjunto S de los estados y la función de probabilidad P . ${\ Displaystyle (S, A, P)}$${\ Displaystyle {\ mathcal {A}}}$${\ Displaystyle {\ mathcal {A}} \ to \ mathbf {Dist}}$

De esta forma, los procesos de decisión de Markov podrían generalizarse desde monoides (categorías con un objeto) a categorías arbitrarias. Se puede llamar al resultado un proceso de decisión de Markov dependiente del contexto , porque moverse de un objeto a otro cambia el conjunto de acciones disponibles y el conjunto de estados posibles. ${\ 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 de 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 se define mediante ecuaciones diferenciales parciales (PDE).

Definición

Para discutir el proceso de decisión de Markov en tiempo continuo, presentamos 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 estado 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 el control óptimos que podrían 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]}$

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 el tomador de decisiones puede tomar una decisión en cualquier momento en el estado actual, no podría beneficiarse más si toma más de una acción. Es mejor para ellos tomar una acción solo en el momento en que el sistema está pasando del estado actual a otro estado. Bajo algunas condiciones (para 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 {y}} 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 {alineado} {\ text {Minimizar}} \ quad & g \\ {\ text {st}} \ 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 {alineado}}}$

• Programa lineal dual (D-LP)

${\ Displaystyle {\ begin {alineado} {\ text {Maximizar}} & \ sum _ {i \ in S} \ sum _ {a \ in A (i)} R (i, a) y (i, a) \\ {\ text {st}} & \ 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 {alineado}}}$

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

${\ Displaystyle {\ begin {alineado} \ 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 {alineado}}}$

para toda la 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 se puede encontrar resolviendo la ecuación diferencial parcial de Hamilton – Jacobi – Bellman (HJB) . Para discutir la ecuación HJB, necesitamos reformular nuestro problema

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

${\ 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 {\ Partical V (t, x)} {\ Partical 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 de población .

Notaciones alternativas

La terminología y la notación de los MDP no están completamente 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 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, costo , costo para llevar y llamar al factor de descuento . Además, la notación de la probabilidad de transición varía. ${\ Displaystyle \ beta}$${\ Displaystyle \ gamma}$${\ Displaystyle \ alpha}$

en este articulo	alternativa	comentario
acción ${\ Displaystyle a}$	control ${\ Displaystyle u}$
recompensa ${\ Displaystyle R}$	costo ${\ Displaystyle g}$	${\ Displaystyle g}$ es el negativo de ${\ Displaystyle R}$
valor ${\ Displaystyle V}$	costo para llevar ${\ Displaystyle J}$	${\ Displaystyle J}$ es el negativo de ${\ Displaystyle V}$
política ${\ Displaystyle \ pi}$	política ${\ Displaystyle \ mu}$
factor de descuento ${\ Displaystyle \ \ gamma \}$	factor de descuento ${\ Displaystyle \ alpha}$
probabilidad de transición ${\ Displaystyle P_ {a} (s, s ')}$	probabilidad de transición ${\ Displaystyle p_ {ss '} (a)}$

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

Procesos de decisión de Markov restringidos

Los procesos de decisión de Markov restringidos (CMDP) son extensiones del proceso de decisión de Markov (MDP). Hay tres diferencias fundamentales entre los MDP y los CMDP.

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

Hay una serie de aplicaciones para CMDP. Recientemente se ha utilizado en escenarios de planificación de movimiento en robótica.

Ver también

Referencias

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 . 2 . MA: Atenea.
• Derman, C. (1970). Procesos de decisión de estado finito de Markov . 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 . Modelado estocástico y probabilidad aplicada. Saltador. ISBN 9783642025464.
• Meyn, SP (2007). Técnicas de control para 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 en modelos estocásticos . Wiley. ISBN 9780470864289.

enlaces externos

• Aprendiendo a resolver los procesos de decisión de Markovia por Satinder P. Singh