proceso de decisión de Markov

Un proceso de decisión de Markov ( MDP ) es un modelo matemático para la toma de decisiones secuenciales cuando los resultados son inciertos. ^{[ 1 ]} Es un tipo de proceso de decisión estocástico ^{[ 2 ]} y a menudo se resuelve utilizando los métodos de programación dinámica estocástica .

Originarios de la investigación operativa en la década de 1950, ^{[ 3 ]}^{[ 4 ]} los MDP han ganado reconocimiento en diversos campos, como la ecología , la economía , la atención médica , las telecomunicaciones y el aprendizaje por refuerzo . ^{[ 5 ]} El aprendizaje por refuerzo utiliza el marco MDP para modelar la interacción entre un agente de aprendizaje y su entorno. En este marco, la interacción se caracteriza por estados, acciones y recompensas. El marco MDP está diseñado para proporcionar una representación simplificada de elementos clave de los desafíos de la inteligencia artificial . Este marco de modelado incorpora la comprensión de causa y efecto , la gestión de la incertidumbre y el no determinismo, y la búsqueda de objetivos explícitos. ^{[ 5 ]}

El nombre proviene de su conexión con las cadenas de Markov , un concepto desarrollado por el matemático ruso Andrey Markov . El término "Markov" en "proceso de decisión de Markov" se refiere a la estructura subyacente de las transiciones de estado que aún siguen la propiedad de Markov . El proceso se denomina "proceso de decisión" porque implica tomar decisiones que influyen en estas transiciones de estado, extendiendo el concepto de cadena de Markov al ámbito de la toma de decisiones en condiciones de incertidumbre.

Definición

Un proceso de decisión de Markov es una 4- tupla $(S,A,P_{a},R_{a})$ , dónde:

$S$ es un conjunto de estados llamado espacio de estados . El espacio de estados puede ser discreto o continuo, como el conjunto de los números reales .
$A$ es un conjunto de acciones llamado espacio de acción (alternativamente, $A_{s}$ es el conjunto de acciones disponibles del estado $s$ En cuanto al estado, este conjunto puede ser discreto o continuo.
$P_{a}(s,s')$ es, a nivel intuitivo, la probabilidad de que la acción $a$ en el estado $s$ en ese momento $t$ conducirá al estado $s'$ en ese momento $t+1$ En general, esta transición de probabilidad se define para satisfacer $\Pr(s_{t+1}\in S'\mid s_{t}=s,a_{t}=a)=\int _{S'}P_{a}(s,s')ds',$ por cada $S'\subseteq S$ mensurable. En caso de que el espacio de estados sea discreto, la integral se refiere a la medida de conteo , de modo que esta última se simplifica como $P_{a}(s,s')=\Pr(s_{t+1}=s'\mid s_{t}=s,a_{t}=a)$ ; En caso $S\subseteq \mathbb {R} ^{d}$ , la integral se suele entender con respecto a la medida de Lebesgue .
$R_{a}(s,s')$ es la recompensa inmediata (o recompensa inmediata esperada) recibida después de la acción $a$ se toma para hacer la transición del estado $s$ para declarar $s'$ La recompensa es, en general, una variable aleatoria .

Una función de política $\pi$ es una aplicación (potencialmente probabilística) del espacio de estados ( $S$ ) al espacio de acción ( $A$ ).

Objetivo de optimización

El objetivo en un proceso de decisión de Markov es encontrar una buena "política" para el responsable de la toma de decisiones: una función $\pi$ que especifica la acción $\pi (s)$ que el responsable de la toma de decisiones elegirá cuando esté en el estado $s$ 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 $s$ está completamente determinado por $\pi (s)$ ).

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

E\left[\sum _{t=0}^{\infty }{\gamma ^{t}R_{a_{t}}(s_{t},s_{t+1})}\right]

(donde elegimos

a_{t}=\pi (s_{t})

, es decir, acciones dadas por la política). Y la expectativa se asume

s_{t+1}\sim P_{a_{t}}(s_{t},s_{t+1})

dónde $\ \gamma \$ ¿El factor de descuento es satisfactorio? $0\leq \ \gamma \ \leq \ 1$ , que suele estar cerca de $1$ (Por ejemplo, $\gamma =1/(1+r)$ para alguna tasa de descuento $r$ Un factor de descuento menor hace que quien toma las decisiones sea más miope, ya que ignora comparativamente el efecto que, en ocasiones, tendrá seguir su política actual en el futuro.

Otro objetivo posible, pero estrictamente relacionado, que se usa comúnmente es el $H-$ retorno escalonado. Esta vez, en lugar de utilizar un factor de descuento $\ \gamma \$ , el agente está interesado únicamente en el primero $H$ pasos del proceso, donde cada recompensa tiene el mismo peso.

E\left[\sum _{t=0}^{H-1}{R_{a_{t}}(s_{t},s_{t+1})}\right]

(donde elegimos

a_{t}=\pi (s_{t})

, es decir, acciones dadas por la política). Y la expectativa se asume

s_{t+1}\sim P_{a_{t}}(s_{t},s_{t+1})

dónde $\ H\$ es el horizonte temporal. En comparación con el objetivo anterior, este último se utiliza más en la Teoría del Aprendizaje .

Una política que maximiza la función anterior se denomina política óptima y se suele denotar $\pi ^{*}$ 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 una función del estado actual, como se supuso anteriormente. Cuando $R_{a}(s,s')$ es determinista, siempre existirá una política óptima. $\pi ^{*}$ lo cual también es determinista.

[Prueba]

Supongamos que $R$ es determinista, lo que significa para constantes $a,s,s'$ el valor $R_{a}(s,s')$ también es constante. Para $\gamma <1$ Se sabe que existe un único punto fijo. $V^{*}$ que satisface la iteración de valor (ecuación de Bellman) recursiva

$V^{*}(s)=\max _{a}E\left[R_{a}(s,s')+\gamma V^{*}(s')\right]$

Tras la inspección, observe que este punto fijo es la función de valor asociada a la siguiente política.

$\pi ^{*}(s):=\arg \max _{a}E\left[R_{a}(s,s')+\gamma V^{*}(s')\right]$

Al desarrollar la recursión de Bellman, se puede demostrar que $V^{*}$ es efectivamente óptimo (simultáneamente para todos los estados) sobre el conjunto de políticas deterministas.

${\begin{aligned}V^{*}(s_{0})&=\max _{a_{0}}E\left[R_{a_{0}}(s_{0},s_{1})+\gamma V^{*}(s_{1})\right]\\&=\max _{a_{0}}E\left[R_{a_{0}}(s_{0},s_{1})+\gamma \max _{a_{1}}E\left[R_{a_{1}}(s_{1},s_{2})+\gamma V^{*}(s_{2})\right]\right]\\&=\max _{a_{0},a_{1}}E\left[R_{a_{0}}(s_{0},s_{1})+\gamma \left(R_{a_{1}}(s_{1},s_{2})+\gamma V^{*}(s_{2})\right)\right]\\&=\sup _{\{a_{t}\}_{t=0}^{\infty }}E\left[\sum _{t=0}^{\infty }\gamma ^{t}R_{a_{t}}(s_{t},s_{t+1})\right]\end{aligned}}$

Consideremos el caso donde $\pi$ es probabilístico, lo que significa que la acción tomada $a:=\pi (s)$ es una variable aleatoria. Se puede demostrar que cualquier política no determinista de este tipo está dominada por una política determinista. $\pi ^{*}$ como sigue.

${\begin{aligned}V^{*}(s_{0})&=\max _{a_{0}}E\left[R_{a_{0}}(s_{0},s_{1})+\gamma V^{*}(s_{1})\right]\\&\geq E\left[R_{\pi (s_{0})}(s_{0},s_{1})+\gamma V^{*}(s_{1})\right]\\&=E\left[R_{\pi (s_{0})}(s_{0},s_{1})+\gamma \max _{a_{1}}E\left[R_{a_{1}}(s_{1},s_{2})+\gamma V^{*}(s_{2})\right]\right]\\&\geq E\left[R_{\pi (s_{0})}(s_{0},s_{1})+\gamma \left(R_{\pi (s_{1})}(s_{1},s_{2})+\gamma V^{*}(s_{2})\right)\right]\\&\geq E\left[\sum _{t=0}^{\infty }\gamma ^{t}R_{\pi (s_{t})}(s_{t},s_{t+1})\right]\end{aligned}}$

Modelos de simulador

En muchos casos, es difícil representar las distribuciones de probabilidad de transición, $P_{a}(s,s')$ 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 generar un estado y una recompensa subsiguientes cada vez que recibe una acción de entrada. De esta manera, 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 dado cualquier estado y acción. ^{[ 6 ]} (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 usando pseudocódigo , $G$ se utiliza a menudo para representar un modelo generativo. Por ejemplo, la expresión $s',r\gets G(s,a)$ podría denotar la acción de muestreo del modelo generativo donde $s$ y $a$ son el estado y la acción actuales, y $s'$ y $r$ 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 solo de aquellos encontrados en una trayectoria.

Estas clases de modelos forman una jerarquía de contenido informativo: un modelo explícito genera fácilmente un modelo generativo mediante el muestreo de las distribuciones, y la aplicación repetida de un modelo generativo genera un simulador episódico. En sentido contrario, solo es posible aprender modelos aproximados mediante regresión . El tipo de modelo disponible para un MDP particular influye significativamente en la elección de los algoritmos de solución adecuados. Por ejemplo, los algoritmos de programación dinámica descritos en la siguiente sección requieren un modelo explícito, y la búsqueda en árbol de Monte Carlo requiere un modelo generativo (o un simulador episódico que se pueda copiar en cualquier estado), mientras que la mayoría de los algoritmos de aprendizaje por refuerzo solo requieren un simulador episódico.

Ejemplo

Un ejemplo de MDP es el modelo de equilibrio de polos, que proviene de la teoría de control clásica.

En este ejemplo, tenemos

$S$ es el conjunto de tuplas ordenadas $(\theta ,{\dot {\theta }},x,{\dot {x}})$ dada por el ángulo del polo, la velocidad angular, la posición del carro y su velocidad.
$A$ es $\{-1,1\}$ , correspondiente a aplicar una fuerza en la izquierda (derecha) del carro.
$P_{a}(s,s')$ es la transición del sistema, que en este caso va a ser determinista y estar regida por las leyes de la mecánica.
$R_{a}(s,s')$ es $1$ si el polo está arriba después de la transición, cero en caso contrario. Por lo tanto, esta función solo depende de $s'$ en este caso específico.

Algoritmos

Se pueden encontrar soluciones para MDP con espacios de estado y acción finitos mediante diversos métodos, como la programación dinámica . Los algoritmos de esta sección se aplican a MDP con espacios de estado y acción finitos y probabilidades de transición y funciones de recompensa explícitamente dadas, pero los conceptos básicos pueden extenderse para abordar otras clases de problemas, por ejemplo, mediante la aproximación de funciones . Además, algunos procesos con espacios de estado y acción infinitos numerables pueden reducirse exactamente a procesos con espacios de estado y acción finitos. ^{[ 7 ]}

La familia estándar de algoritmos para calcular políticas óptimas para MDP de estado y acción finitos requiere almacenamiento para dos matrices indexadas por estado: valor $V$ , que contiene valores reales y política $\pi$ , que contiene acciones. Al final del algoritmo, $\pi$ contendrá la solución y $V(s)$ contendrá la suma descontada de las recompensas que se obtendrán (en promedio) siguiendo esa solución desde el estado $s$ .

El algoritmo consta de dos pasos: (1) una actualización de valor y (2) una actualización de política, que se repiten en un orden determinado 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 del valor del estado utilizando una estimación anterior de dichos valores.

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

\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 realizar para todos los estados a la vez o estado por estado, y con mayor frecuencia para algunos estados que para otros. Siempre que ningún estado quede excluido permanentemente de ninguno de los pasos, el algoritmo llegará finalmente a la solución correcta. ^{[ 8 ]}

Variantes destacadas

Iteración de valor

En la iteración de valor ( Bellman 1957 ) , que también se denomina inducción hacia atrás , el $\pi$ La función no se utiliza; en su lugar, el valor de $\pi (s)$ se calcula dentro $V(s)$ siempre que sea necesario. Sustituyendo el cálculo de $\pi (s)$ en el cálculo de $V(s)$ da el paso combinado;

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 $i$ es el número de iteración. La iteración de valor comienza en $i=0$ y $V_{0}$ como una suposición de la función de valor . Luego itera, calculando repetidamente $V_{i+1}$ para todos los estados $s$ , hasta $V$ converge cuando el lado izquierdo es 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 incluyó como caso especial el método de iteración de valor para MDP, ^{[ 9 ]} pero esto se reconoció solo más tarde. ^{[ 10 ]}

Se garantiza que la iteración de valor convergerá para $\gamma <1$ por el teorema del punto fijo de Banach .

[Prueba]

El teorema del punto fijo de Banach establece que una aplicación de contracción dada tiene un único punto fijo; además, se puede aproximar asintóticamente a este punto fijo mediante la aplicación iterativa de la aplicación de contracción. Basta entonces con demostrar que la iteración de valor es una aplicación de contracción, lo cual se muestra a continuación para $\gamma <1$ .

Denotar $X_{a}^{V}(s):=\sum _{s'}P_{a}(s,s')\left(R_{a}(s,s')+\gamma V_{i}(s')\right)$ y $({\mathcal {B}}V)(s):=\max _{a}X_{a}^{V}(s)$ para mayor comodidad.

${\begin{aligned}\|{\mathcal {B}}V-{\mathcal {B}}W\|_{\infty }&=\max _{s}\left|({\mathcal {B}}V)(s)-({\mathcal {B}}W)(s)\right|\\&=\max _{s}\left|\max _{a}X_{a}^{V}(s)-\max _{a}X_{a}^{W}(s)\right|\\&\leq \max _{s}\max _{a}\left|X_{a}^{V}(s)-X_{a}^{W}(s)\right|\\&=\max _{s}\max _{a}\gamma \left|\sum _{s'}P_{a}(s,s')\left(V_{i}(s')-W_{i}(s')\right)\right|\\&\leq \max _{s}\max _{a}\gamma \max _{s'}\left|V_{i}(s')-W_{i}(s')\right|\\&=\gamma \max _{s'}\left|V_{i}(s')-W_{i}(s')\right|\\&=\gamma \|V_{i}-W_{i}\|_{\infty }\end{aligned}}$

Iteración de políticas

En la iteración de políticas ^{[ 11 ]} , primero se realiza la determinación de valores resolviendo para $V$ a partir del sistema lineal descrito en el paso uno, luego realiza una mejora de la política calculando $\pi$ Como en el paso dos, luego repite ambos pasos hasta que la política converja. (La iteración de políticas fue inventada por Howard para optimizar el envío de catálogos de Sears , que había estado optimizando mediante la iteración de valor. ^{[ 12 ]} )

Dado que la iteración de políticas intercala efectivamente un problema inverso lineal con una operación no lineal, puede interpretarse como un tipo de método de relajación .

Esta variante tiene la ventaja de que existe una condición de parada definida. Dado que existe una solución única $V$ para cada política $\pi$ El algoritmo se completa una vez que la mejora de la política produce la misma política dos veces consecutivas.

Si bien existen situaciones en las que la iteración de políticas puede ser más rápida que la iteración de valores (por ejemplo, cuando el espacio de acciones es significativamente mayor que el espacio de estados), 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 ; Puterman y Shin 1978 ), el paso uno se repite varias veces y luego el paso dos se realiza una vez. ^{[ 13 ]}^{[ 14 ]} Luego el paso uno se repite nuevamente varias veces y así sucesivamente.

Barrido prioritario

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 $V$ o $\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).

Complejidad computacional

Existen algoritmos para encontrar políticas óptimas con una complejidad temporal polinómica respecto al tamaño de la representación del problema para MDP finitos. Por lo tanto, ^los problemas de decisión basados en MDP pertenecen a la clase de complejidad computacional P. ^{[ 15} ] Sin embargo, debido a la maldición de la dimensionalidad , el tamaño de la representación del problema suele ser exponencial en el número de variables de estado y acción, lo que limita las técnicas de solución exacta a problemas con una representación compacta. En la práctica, las técnicas de planificación en línea, como la búsqueda en árbol de Monte Carlo, pueden encontrar soluciones útiles en problemas de mayor tamaño 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 dependencia de la complejidad computacional respecto al tamaño del espacio de estados. ^{[ 16 ]}

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 el estado $s$ Se sabe cuándo se debe actuar; de lo contrario $\pi (s)$ 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.

procesos de decisión de Markov restringidos

Los procesos de decisión de Markov restringidos (CMDP) son extensiones de los procesos de decisión de Markov (MDP). Existen tres diferencias fundamentales entre los MDP y los CMDP. ^{[ 17 ]}

Existen múltiples costos que se generan al aplicar una acción en lugar de una sola.
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 el lagrangiano.

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

Existen diversas aplicaciones para los CMDP. Recientemente se han utilizado en escenarios de planificación de movimiento en robótica. ^{[ 19 ]}

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, en los procesos de decisión de Markov de tiempo continuo , las decisiones pueden tomarse en cualquier momento que el decisor elija. En comparación con los procesos de decisión de Markov de tiempo discreto, los procesos de decisión de Markov de tiempo continuo pueden modelar mejor el proceso de toma de decisiones para un sistema con dinámica continua , es decir, cuya dinámica se define mediante ecuaciones diferenciales ordinarias (EDO). Este marco de modelado puede aplicarse a áreas como sistemas de colas , procesos epidémicos y procesos poblacionales .

Al igual que en los procesos de decisión de Markov de tiempo discreto, en los procesos de decisión de Markov de tiempo continuo el agente busca encontrar la política óptima que maximice la recompensa acumulada esperada. La diferencia clave con el caso estándar es que, debido a la naturaleza continua de la variable tiempo, la suma se reemplaza por una integral:

\max \operatorname {E} _{\pi }\left[\left.\int _{0}^{\infty }\gamma ^{t}r(s(t),\pi (s(t)))\,dt\;\right|s_{0}\right]

dónde $0\leq \gamma <1.$

Espacio discreto: Formulación de programación lineal

Si el espacio de estados y el espacio de acciones son finitos, podríamos usar 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 esta suposición, aunque el decisor puede tomar una decisión en cualquier momento en el estado actual, no hay beneficio en tomar múltiples acciones. Es mejor tomar una acción solo en el momento en que el sistema está en transición del estado actual a otro estado. Bajo ciertas condiciones, ^{[ 20 ]} si nuestra función de valor óptimo $V^{*}$ es independiente del estado $i$ Tendremos la siguiente desigualdad:

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

Programa lineal primal (P-LP)

{\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)

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

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

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

Espacio continuo: ecuación de Hamilton-Jacobi-Bellman

En MDP de tiempo continuo, si el espacio de estados y el espacio de acciones son continuos, el criterio óptimo se puede encontrar resolviendo la ecuación diferencial parcial de Hamilton-Jacobi-Bellman (HJB) . Para analizar la ecuación HJB, necesitamos reformular nuestro problema.

{\begin{aligned}V(s(0),0)={}&\max _{a(t)=\pi (s(t))}\int _{0}^{T}r(s(t),a(t))\,dt+D[s(T)]\\{\text{s.t.}}\quad &{\frac {ds(t)}{dt}}=f[t,s(t),a(t)]\end{aligned}}

$D(\cdot )$ es la función de recompensa terminal, $s(t)$ es el vector de estado del sistema, $a(t)$ es el vector de control del sistema que intentamos encontrar. $f(\cdot )$ muestra cómo cambia el vector de estado a lo largo del tiempo. La ecuación de Hamilton-Jacobi-Bellman es la siguiente:

0=\max _{a}(r(t,s,a)+{\frac {\partial V(t,s)}{\partial s}}f(t,s,a))

Podríamos resolver la ecuación para encontrar la función de valor óptimo. $V^{*}$ lo que a su vez produce el control óptimo en cualquier momento $t$ , $a(t)$ a través de $a(t)={\underset {a}{\text{argmax}}}(r(t,s,a)+{\frac {\partial V^{*}(t,s)}{\partial s}}f(t,s,a)).$

Aprendizaje por refuerzo

El aprendizaje por refuerzo es un área interdisciplinaria del aprendizaje automático y el control óptimo que tiene como objetivo principal encontrar una política aproximadamente óptima para MDP donde las probabilidades de transición y las recompensas son desconocidas. ^{[ 21 ]}

El aprendizaje por refuerzo puede resolver procesos de decisión de Markov sin la especificación explícita de las probabilidades de transición, que son necesarias para realizar la iteración de la política. En este contexto, las probabilidades de transición y las recompensas deben aprenderse a partir de la experiencia, es decir, permitiendo que un agente interactúe con el MDP durante un número determinado de pasos. Tanto a nivel teórico como práctico, se hace un esfuerzo por maximizar la eficiencia de la muestra, es decir, minimizar el número de muestras necesarias para aprender una política cuyo rendimiento sea $\varepsilon -$ cerca de la óptima (debido a la naturaleza estocástica del proceso, aprender la política óptima con un número finito de muestras es, en general, imposible).

Aprendizaje por refuerzo para MDP discretos

Para los fines de esta sección, es útil definir una función adicional, que corresponde a tomar la acción. $a$ y luego continuar de forma óptima (o de acuerdo con la política que se tenga vigente en ese momento):

\ 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 $(s,a)$ pares (junto con el resultado) $s'$ ; es decir, "yo estaba en estado $s$ y lo intenté hacer $a$ y $s'$ sucedió"). Por lo tanto, se tiene una matriz $Q$ y utiliza la experiencia para actualizarlo directamente. Esto se conoce como Q-learning .

Otros alcances

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. El primer artículo detallado sobre autómatas de aprendizaje fue revisado por Narendra y Thathachar (1974), quienes originalmente los describieron explícitamente como autómatas de estados finitos . ^{[ 22 ]} 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 aprendizaje Q es que la primera técnica omite la memoria de los valores Q, pero actualiza directamente la probabilidad de la acción para encontrar el resultado del aprendizaje. Los autómatas de aprendizaje son un esquema de aprendizaje con una prueba rigurosa de convergencia. ^{[ 23 ]}

En la teoría de 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 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 dicho autómata corresponden a los estados de un " proceso de Markov de estado discreto y parámetro discreto ". ^{[ 24 ]} 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. ^{[ 23 ]}

interpretación desde la perspectiva de la teoría de categorías

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

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 $({\mathcal {C}},F:{\mathcal {C}}\to \mathbf {Dist} )$ un proceso de decisión de Markov dependiente del contexto , porque pasar de un objeto a otro en ${\mathcal {C}}$ cambia el conjunto de acciones disponibles y el conjunto de estados posibles.

Notaciones alternativas

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

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

Véase también

Referencias

↑ Puterman, Martin L. (1994). Procesos de decisión de Markov: programación dinámica estocástica discreta . Serie Wiley en probabilidad y estadística matemática. Sección de probabilidad y estadística aplicada. Nueva York: Wiley. ISBN 978-0-471-61977-2.
↑ Yin, Bo (2021). Gestión del tiempo de transmisión para redes inalámbricas densamente desplegadas de baja latencia (tesis doctoral). Japón: Universidad de Kioto.
↑ Schneider, S.; Wagner, DH (1957-02-26). "Detección de errores en sistemas redundantes" . Artículos presentados en la conferencia conjunta de informática occidental del 26 al 28 de febrero de 1957: Técnicas para la fiabilidad en - IRE-AIEE-ACM '57 (Western) . Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 115–121 . doi : 10.1145/1455567.1455587 . ISBN 978-1-4503-7861-1.{{cite book}}: Incompatibilidad de ISBN/Fecha ( ayuda )
↑ Bellman, Richard (1958-09-01). "Programación dinámica y procesos de control estocástico" . Information and Control . 1 (3): 228– 239. Bibcode : 1958InfCo...1..228B . doi : 10.1016/S0019-9958(58)80003-0 . ISSN 0019-9958 .
1 2 Sutton, Richard S.; Barto, Andrew G. (2018). Aprendizaje por refuerzo: una introducción . Serie de computación adaptativa y aprendizaje automático (2.ª ed.). Cambridge, Massachusetts: The MIT Press. ISBN 978-0-262-03924-6.
↑ Kearns, Michael; Mansour, Yishay; Ng, Andrew (2002). "Un algoritmo de muestreo disperso para la planificación casi óptima en grandes procesos de decisión de Markov" . Machine Learning . 49 ( 193–208 ): 193–208 . doi : 10.1023/A:1017932429737 .
^ Wrobel, A. (1984). "Sobre modelos de decisión markovianos con esqueleto finito". Zeitschrift für Investigación de operaciones . 28 (1): 17– 27. doi : 10.1007/bf01919083 . S2CID 2545336 .
↑ Aprendizaje por refuerzo: teoría e implementación en Python . Pekín: China Machine Press. 2019. pág. 44. ISBN 9787111631774.
↑ Shapley, Lloyd (1953). "Juegos estocásticos" . Actas de la Academia Nacional de Ciencias de los Estados Unidos de América . 39 ( 10): 1095– 1100. Bibcode : 1953PNAS...39.1095S . doi : 10.1073/pnas.39.10.1095 . PMC 1063912. PMID 16589380 .
↑ Kallenberg, Lodewijk (2002). "MDP de estado y acción finitos". En Feinberg, Eugene A .; Shwartz, Adam (eds.). Manual de procesos de decisión de Markov: métodos y aplicaciones . Springer. ISBN 978-0-7923-7459-6.
↑ Howard, Ronald A. (1960). Programación dinámica y procesos de Markov . The MIT Press.
↑ Howard 2002, "Comentarios sobre el origen y la aplicación de los procesos de decisión de Markov"
↑ Puterman, ML; Shin, MC (1978). "Algoritmos de iteración de políticas modificadas para problemas de decisión de Markov con descuento". Management Science . 24 (11): 1127– 1137. doi : 10.1287/mnsc.24.11.1127 .
^ 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 .
↑ Papadimitriou, Christos ; Tsitsiklis, John (1987). "La complejidad de los procesos de decisión de Markov" . Matemáticas de la investigación operativa . 12 (3): 441–450 . doi : 10.1287/moor.12.3.441 . hdl : 1721.1/2893 . Recuperado el 2 de noviembre de 2023 .
↑ Kearns, Michael; Mansour, Yishay; Ng, Andrew (noviembre de 2002). "Un algoritmo de muestreo disperso para la planificación casi óptima en grandes procesos de decisión de Markov" . Machine Learning . 49 (2/3): 193–208 . doi : 10.1023/A:1017932429737 .
↑ Altman, Eitan (1999). Procesos de decisión de Markov restringidos . Vol. 7. CRC Press.
↑ Ding, Dongsheng; Zhang, Kaiqing; Jovanovic, Mihailo; Basar, Tamer (2020). Método primal-dual de gradiente de política natural para procesos de decisión de Markov restringidos . Avances en sistemas de procesamiento de información neuronal.
↑ Feyzabadi, S.; Carpin, S. (18–22 de agosto de 2014). "Planificación de rutas con conciencia del riesgo mediante procesos de decisión de Markov jerárquicos con restricciones" . Automation Science and Engineering (CASE) . Conferencia Internacional IEEE. págs. 297, 303.
↑ Procesos de decisión de Markov en tiempo continuo . Modelado estocástico y probabilidad aplicada. Vol. 62. 2009. doi : 10.1007/978-3-642-02547-1 . ISBN 978-3-642-02546-4.
↑ Shoham, Y.; Powers, R.; Grenager, T. (2003). "Aprendizaje por refuerzo multiagente: una revisión crítica" (PDF) . Informe técnico, Universidad de Stanford : 1–13 . Recuperado el 12 de diciembre de 2018 .
↑ Narendra, KS ; Thathachar, MAL (1974). "Autómatas de aprendizaje: una revisión". IEEE Transactions on Systems, Man, and Cybernetics . SMC-4 (4): 323–334 . Bibcode : 1974ITSMC...4..323N . CiteSeerX 10.1.1.295.2280 . doi : 10.1109/TSMC.1974.5408453 . ISSN 0018-9472 .
^ Narendra , Kumpati S .; Thathachar, Mandayam AL (1989). Autómatas de aprendizaje: una introducción . Prentice Hall. ISBN 9780134855585.
^ Narendra y Thathachar 1974 , p.325 izquierda.

Fuentes

Bellman, R. (1957), Programación dinámica , Princeton University Press, ISBN 978-0-486-42809-3{{citation}}: Incompatibilidad de ISBN/Fecha ( ayuda ) . Edición de bolsillo de Dover (2003)

Lecturas adicionales

Bellman, RE (2003) [1957]. Programación dinámica ( edición de bolsillo de Dover). Princeton, NJ: Princeton University Press. ISBN 978-0-486-42809-3.
Bertsekas, D. (1995). Programación dinámica y control óptimo . Vol. 2. MA: Athena.
Derman, C. (1970). Procesos de decisión markovianos de estado finito . Academic Press.
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. Springer. ISBN 9783642025464.
Meyn, SP (2007). Técnicas de control para redes complejas . Cambridge University Press. ISBN 978-0-521-88441-9Archivado del original el 19 de junio de 2010.El apéndice contiene una versión abreviada de "Meyn & Tweedie" . Archivado del 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) . Academic Press. Archivado del original (PDF) el 4 de marzo de 2022. Consultado el 19 de enero de 2019 .
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.

[1] Puterman, Martin L. (1994). Procesos de decisión de Markov: programación dinámica estocástica discreta . Serie Wiley en probabilidad y estadística matemática. Sección de probabilidad y estadística aplicada. Nueva York: Wiley. ISBN 978-0-471-61977-2.

[2] Yin, Bo (2021). Gestión del tiempo de transmisión para redes inalámbricas densamente desplegadas de baja latencia (tesis doctoral). Japón: Universidad de Kioto.

[3] Schneider, S.; Wagner, DH (1957-02-26). "Detección de errores en sistemas redundantes" . Artículos presentados en la conferencia conjunta de informática occidental del 26 al 28 de febrero de 1957: Técnicas para la fiabilidad en - IRE-AIEE-ACM '57 (Western) . Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 115–121 . doi : 10.1145/1455567.1455587 . ISBN 978-1-4503-7861-1.{{cite book}}: Incompatibilidad de ISBN/Fecha ( ayuda )

[4] Bellman, Richard (1958-09-01). "Programación dinámica y procesos de control estocástico" . Information and Control . 1 (3): 228– 239. Bibcode : 1958InfCo...1..228B . doi : 10.1016/S0019-9958(58)80003-0 . ISSN 0019-9958 .

[:0-5] 1 2 Sutton, Richard S.; Barto, Andrew G. (2018). Aprendizaje por refuerzo: una introducción . Serie de computación adaptativa y aprendizaje automático (2.ª ed.). Cambridge, Massachusetts: The MIT Press. ISBN 978-0-262-03924-6.

[Kearns_Sparse-6] Kearns, Michael; Mansour, Yishay; Ng, Andrew (2002). "Un algoritmo de muestreo disperso para la planificación casi óptima en grandes procesos de decisión de Markov" . Machine Learning . 49 ( 193–208 ): 193–208 . doi : 10.1023/A:1017932429737 .

[Wrobel_1984-7] Wrobel, A. (1984). "Sobre modelos de decisión markovianos con esqueleto finito". Zeitschrift für Investigación de operaciones . 28 (1): 17– 27. doi : 10.1007/bf01919083 . S2CID 2545336 .

[8] Aprendizaje por refuerzo: teoría e implementación en Python . Pekín: China Machine Press. 2019. pág. 44. ISBN 9787111631774.

[9] Shapley, Lloyd (1953). "Juegos estocásticos" . Actas de la Academia Nacional de Ciencias de los Estados Unidos de América . 39 ( 10): 1095– 1100. Bibcode : 1953PNAS...39.1095S . doi : 10.1073/pnas.39.10.1095 . PMC 1063912. PMID 16589380 .

[10] Kallenberg, Lodewijk (2002). "MDP de estado y acción finitos". En Feinberg, Eugene A .; Shwartz, Adam (eds.). Manual de procesos de decisión de Markov: métodos y aplicaciones . Springer. ISBN 978-0-7923-7459-6.

[11] Howard, Ronald A. (1960). Programación dinámica y procesos de Markov . The MIT Press.

[12] Howard 2002, "Comentarios sobre el origen y la aplicación de los procesos de decisión de Markov"

[13] Puterman, ML; Shin, MC (1978). "Algoritmos de iteración de políticas modificadas para problemas de decisión de Markov con descuento". Management Science . 24 (11): 1127– 1137. doi : 10.1287/mnsc.24.11.1127 .

[14] 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 .

[15] Papadimitriou, Christos ; Tsitsiklis, John (1987). "La complejidad de los procesos de decisión de Markov" . Matemáticas de la investigación operativa . 12 (3): 441–450 . doi : 10.1287/moor.12.3.441 . hdl : 1721.1/2893 . Recuperado el 2 de noviembre de 2023 .

[16] Kearns, Michael; Mansour, Yishay; Ng, Andrew (noviembre de 2002). "Un algoritmo de muestreo disperso para la planificación casi óptima en grandes procesos de decisión de Markov" . Machine Learning . 49 (2/3): 193–208 . doi : 10.1023/A:1017932429737 .

[17] Altman, Eitan (1999). Procesos de decisión de Markov restringidos . Vol. 7. CRC Press.

[18] Ding, Dongsheng; Zhang, Kaiqing; Jovanovic, Mihailo; Basar, Tamer (2020). Método primal-dual de gradiente de política natural para procesos de decisión de Markov restringidos . Avances en sistemas de procesamiento de información neuronal.

[19] Feyzabadi, S.; Carpin, S. (18–22 de agosto de 2014). "Planificación de rutas con conciencia del riesgo mediante procesos de decisión de Markov jerárquicos con restricciones" . Automation Science and Engineering (CASE) . Conferencia Internacional IEEE. págs. 297, 303.

[20] Procesos de decisión de Markov en tiempo continuo . Modelado estocástico y probabilidad aplicada. Vol. 62. 2009. doi : 10.1007/978-3-642-02547-1 . ISBN 978-3-642-02546-4.

[21] Shoham, Y.; Powers, R.; Grenager, T. (2003). "Aprendizaje por refuerzo multiagente: una revisión crítica" (PDF) . Informe técnico, Universidad de Stanford : 1–13 . Recuperado el 12 de diciembre de 2018 .

[22] Narendra, KS ; Thathachar, MAL (1974). "Autómatas de aprendizaje: una revisión". IEEE Transactions on Systems, Man, and Cybernetics . SMC-4 (4): 323–334 . Bibcode : 1974ITSMC...4..323N . CiteSeerX 10.1.1.295.2280 . doi : 10.1109/TSMC.1974.5408453 . ISSN 0018-9472 .

[NarendraEtAl1989-23] Narendra , Kumpati S .; Thathachar, Mandayam AL (1989). Autómatas de aprendizaje: una introducción . Prentice Hall. ISBN 9780134855585.

[FOOTNOTENarendraThathachar1974p.325_left-24] Narendra y Thathachar 1974 , p.325 izquierda.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

los

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]