Proceso de decisión de Markov

Modelo matemático para la toma de decisiones secuencial en condiciones de incertidumbre

El proceso de decisión de Markov ( MDP ), también llamado programa dinámico estocástico o problema de control estocástico, es un modelo para la toma de decisiones secuencial cuando los resultados son inciertos. ^[1]

Los MDP, que se originaron a partir de la investigación de operaciones en la década de 1950, ^{[2] [3]} desde entonces han ganado reconocimiento en una variedad de campos, incluidos la ecología , la economía , la atención médica , las telecomunicaciones y el aprendizaje de refuerzo . ^[4] El aprendizaje de 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 los elementos clave de los desafíos de la inteligencia artificial . Estos elementos abarcan la comprensión de la causa y el efecto , la gestión de la incertidumbre y el no determinismo, y la búsqueda de objetivos explícitos. ^[4]

El nombre proviene de su conexión con las cadenas de Markov , un concepto desarrollado por el matemático ruso Andrey Markov . El "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 llama "proceso de decisión" porque implica tomar decisiones que influyen en estas transiciones de estado, extendiendo el concepto de una cadena de Markov al ámbito de la toma de decisiones en condiciones de incertidumbre.

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 . El espacio de estados puede ser discreto o continuo, como el conjunto de números reales .
• ${\displaystyle A}$es un conjunto de acciones llamado espacio de acciones (alternativamente, es el conjunto de acciones disponibles desde el estado ). En cuanto al estado, este conjunto puede ser discreto o continuo. ${\displaystyle A_{s}}$ ${\displaystyle s}$
• ${\displaystyle P_{a}(s,s')}$es, en un nivel intuitivo, la probabilidad de que la acción en el estado en el momento conduzca al estado en el momento . En general, esta transición de probabilidad se define para satisfacer para cada medida medible. En caso de que el espacio de estados sea discreto, la integral se entiende con respecto a la medida de conteo, de modo que esta última se simplifica como ; En caso de , la integral suele estar pensada con respecto a la medida de Lebesgue . ${\displaystyle a}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle s'}$ ${\displaystyle t+1}$ ${\displaystyle \Pr(s_{t+1}\in S'\mid s_{t}=s,a_{t}=a)=\int _{S'}P_{a}(s,s')ds',}$ ${\displaystyle S'\subseteq S}$ ${\displaystyle P_{a}(s,s')=\Pr(s_{t+1}=s'\mid s_{t}=s,a_{t}=a)}$ ${\displaystyle S\subseteq \mathbb {R} ^{d}}$
• ${\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}$

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

Objetivo de optimización

El objetivo de un proceso de decisión de Markov es encontrar una "política" adecuada para el decisor: una función que especifique la acción que elegirá el decisor cuando se encuentre en el estado . Una vez que un proceso de decisión de Markov se combina con una política de esta manera, se 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 ). ${\displaystyle \pi }$ ${\displaystyle \pi (s)}$ ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle \pi (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 asume ${\displaystyle a_{t}=\pi (s_{t})}$ ${\displaystyle s_{t+1}\sim P_{a_{t}}(s_{t},s_{t+1})}$

donde es el factor de descuento que satisface , que suele estar cerca de (por ejemplo, para una tasa de descuento determinada). Un factor de descuento más bajo motiva al que toma las decisiones a favorecer la adopción de medidas de forma temprana, en lugar de posponerlas indefinidamente. ${\displaystyle \ \gamma \ }$ ${\displaystyle 0\leq \ \gamma \ \leq \ 1}$ ${\displaystyle 1}$ ${\displaystyle \gamma =1/(1+r)}$ ${\displaystyle r}$

Otro objetivo posible, pero estrictamente relacionado, que se utiliza habitualmente es el retorno por pasos. En este caso, en lugar de utilizar un factor de descuento , el agente se interesa únicamente por los primeros pasos del proceso, teniendo cada recompensa el mismo peso. ${\displaystyle H-}$ ${\displaystyle \ \gamma \ }$ ${\displaystyle H}$

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

¿Dónde está el horizonte temporal? En comparación con el objetivo anterior, este último es más utilizado en la teoría del aprendizaje. ${\displaystyle \ H\ }$

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

Modelos de simuladores

En muchos casos, es difícil representar las distribuciones de probabilidad de transición, , explícitamente. En tales casos, se puede utilizar un simulador para modelar la MDP implícitamente proporcionando muestras de las distribuciones de transición. Una forma común de modelo de MDP implícito es un simulador de entorno episódico que puede iniciarse desde un estado inicial y produce un estado y una recompensa posteriores cada vez que recibe una entrada de acción. De esta manera, se pueden producir trayectorias de estados, acciones y recompensas, a menudo denominadas 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 recompensa dado cualquier estado y acción. ^[5] (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 utilizando 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 los encontrados 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 a través del 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 a través de la 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 descritos en la siguiente sección requieren un modelo explícito, y la búsqueda de árboles 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 de refuerzo solo requieren un simulador episódico.

Ejemplo

Ejemplo de equilibrio en barra (representación del entorno del banco de pruebas Open AI Gym)

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

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

Algoritmos

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

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: value , que contiene valores reales, y policy , 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) al seguir esa solución desde state . ${\displaystyle V}$ ${\displaystyle \pi }$ ${\displaystyle \pi }$ ${\displaystyle V(s)}$ ${\displaystyle s}$

El algoritmo consta de dos pasos: (1) una actualización de valores y (2) una actualización de políticas, que se repiten en un orden determinado para todos los estados hasta que no se produzcan más cambios. Ambos pasos actualizan de forma recursiva una nueva estimación del valor óptimo de la política y del estado 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 realizar 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 excluido permanentemente de ninguno de los pasos, el algoritmo llegará finalmente a la solución correcta. ^[6]

Variantes notables

Iteración de valor

En la iteración de valores (Bellman 1957) , que también se denomina inducción hacia atrás , no se utiliza la función; en su lugar, se calcula el valor de cada vez que se necesita. Sustituir el cálculo de en el cálculo de da como resultado el paso combinado ^{[ se necesita más explicación ]} : harv error: no target: CITEREFBellman1957 (help) ${\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 estimació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 ^{[ aclaración necesaria ]} ). El artículo de Lloyd Shapley de 1953 sobre juegos estocásticos incluía como un caso especial el método de iteración de valor para MDP, ^[7] pero esto fue reconocido solo más tarde. ^[8] ${\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 realiza una vez, luego ambos se repiten hasta que la política converge. Luego el paso uno se realiza nuevamente una vez y así sucesivamente. (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 iteración de valores. ^[9] ) harv error: no target: CITEREFHoward1960 (help)

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. ^{[ Aclaración necesaria ]} Por lo tanto, repetir el paso dos para la convergencia se puede interpretar como resolver las ecuaciones lineales por relajación . ${\displaystyle s=s'}$

Esta variante tiene la ventaja de que existe una condición de detención definida: cuando la matriz no cambia durante 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. ^{[10] [11]} Luego, el paso uno se realiza nuevamente una vez y así sucesivamente.

Barrido prioritario

En esta variante, los pasos se aplican preferentemente a estados que son importantes de algún modo, ya sea en función del algoritmo (hubo grandes cambios en o alrededor de 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 usa el algoritmo). ${\displaystyle V}$ ${\displaystyle \pi }$

Complejidad computacional

Existen algoritmos para encontrar políticas óptimas con una complejidad temporal polinómica en el tamaño de la representación del problema para MDP finitos. Por lo tanto, los problemas de decisión basados ​​en MDP están en la clase de complejidad computacional P. ^[12] 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 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. ^[13]

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 debe actuar; 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)}$

Procesos de decisión de Markov restringidos

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

• Se incurren en múltiples costos después de aplicar una acción en lugar de uno.
• 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 multiplicadores de Lagrange se aplica a los CMDP. Se han desarrollado muchos algoritmos basados ​​en el método de Lagrange.

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

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

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, en los procesos de decisión de Markov en tiempo continuo , las decisiones se pueden tomar en cualquier momento que elija el decisor. 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 una dinámica continua , es decir, la dinámica del sistema se define mediante ecuaciones diferenciales ordinarias (EDO). Este tipo de aplicaciones surgen en sistemas de colas , procesos epidémicos y procesos poblacionales .

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

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

dónde ${\displaystyle 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 este supuesto, aunque el tomador de decisiones puede tomar una decisión en cualquier momento en el estado actual, no hay ningún beneficio en tomar múltiples acciones. Es mejor tomar una acción solo en el momento en que el sistema está haciendo la transición del estado actual a otro estado. Bajo algunas condiciones, ^[17] 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 hallar , podemos utilizar 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 para el D-LP si no es nativa y satisface las restricciones en el 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{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 del D-LP. Una vez que hayamos encontrado la solución óptima , podemos usarla para establecer las políticas óptimas. ${\displaystyle y(i,a)}$ ${\displaystyle y^{*}(i,a)}$

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.

${\displaystyle {\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 {dx(t)}{dt}}=f[t,s(t),a(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 cambia el vector de estado con el tiempo. La ecuación de Hamilton-Jacobi-Bellman es la siguiente: ${\displaystyle s(t)}$ ${\displaystyle a(t)}$ ${\displaystyle f(\cdot )}$

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

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

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. ^[18]

El aprendizaje por refuerzo puede resolver procesos de decisión de Markov sin una especificación explícita de las probabilidades de transición que, en cambio, son necesarias para ejecutar la iteración de la política. En este contexto, las probabilidades de transición y las recompensas deben aprenderse de la experiencia, es decir, dejando 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 se acerque al óptimo (debido a la naturaleza estocástica del proceso, aprender la política óptima con un número finito de muestras es, en general, imposible). ${\displaystyle \varepsilon -}$

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 y luego continuar de manera óptima (o de acuerdo con cualquier 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 es desconocida, la experiencia durante el aprendizaje se basa en pares (junto con el resultado ; es decir, "estaba en estado y traté de 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}$

Otros ámbitos

Autómatas de aprendizaje

Otra aplicación del proceso MDP en la teoría del aprendizaje automático se denomina autómatas de aprendizaje. Este también es un tipo de aprendizaje de refuerzo si el entorno es estocástico. El primer artículo detallado sobre autómatas de aprendizaje es el de Narendra y Thathachar (1974), que originalmente se describieron explícitamente como autómatas de estados finitos . ^[19] De manera similar al aprendizaje de 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 los autómatas de aprendizaje y el aprendizaje Q es que la primera técnica omite la memoria de los valores Q, pero actualiza la probabilidad de la 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. ^[20]

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 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 un autómata de este tipo corresponden a los estados de un " proceso de Markov de parámetros discretos y estados discretos ". ^[21] 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. ^[20]

Interpretación teórica de categorías

Además 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. Denotemos con Dist la categoría de Kleisli de la mónada de Giry. Entonces, un funtor 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) a categorías arbitrarias. Se puede decir que el resultado es un proceso de decisión de Markov dependiente del contexto , porque al pasar de un objeto a otro se modifica el conjunto de acciones disponibles y el conjunto de estados posibles. ^{[ cita requerida ]} ${\displaystyle ({\mathcal {C}},F:{\mathcal {C}}\to \mathbf {Dist} )}$ ${\displaystyle {\mathcal {C}}}$

Notaciones alternativas

La terminología y la notación de los MDP no están del todo definidas. Hay dos corrientes principales: una se centra en los problemas de maximización de contextos como la economía, utilizando los términos acción, recompensa, valor y llamando al factor de descuento β o γ , mientras que la otra se centra en los problemas de minimización de la ingeniería y la navegación ^{[ cita requerida ]} , utilizando los términos control, costo, costo de uso y llamando 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 , o, raramente, ${\displaystyle \Pr(s,a,s')}$ ${\displaystyle \Pr(s'\mid s,a)}$ ${\displaystyle p_{s's}(a).}$

Véase también

• Autómatas probabilísticos
• Algoritmo de probabilidades
• Autómatas finitos cuánticos
• 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
• El problema de las ovejas Mabinogion
• Juegos estocásticos
• Aprendizaje Q
• Cadena de Markov

Referencias

1. Puterman, Martin L. (1994). Procesos de decisión de Markov: programación dinámica estocástica discreta . Series de 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. Schneider, S.; Wagner, DH (26 de febrero de 1957). "Detección de errores en sistemas redundantes". Documentos 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 (Occidental) . Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 115–121. doi :10.1145/1455567.1455587. ISBN 978-1-4503-7861-1.
3. Bellman, Richard (1958-09-01). "Programación dinámica y procesos de control estocástico". Información y Control . 1 (3): 228–239. doi :10.1016/S0019-9958(58)80003-0. ISSN  0019-9958.
4. 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.
5. Kearns, Michael; Mansour, Yishay; Ng, Andrew (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 .
6. Aprendizaje por refuerzo: teoría e implementación de Python . Pekín: China Machine Press. 2019. pág. 44. ISBN 9787111631774.
7. 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. 
8. Kallenberg, Lodewijk (2002). "MDP de estado finito y acción". 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.
9. Howard 2002, "Comentarios sobre el origen y la aplicación de los procesos de decisión de Markov"
10. Puterman, ML; Shin, MC (1978). "Algoritmos de iteración de políticas modificados para problemas de decisión de Markov descontados". Management Science . 24 (11): 1127–1137. doi :10.1287/mnsc.24.11.1127.
11. 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.
12. 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): 441–450. doi :10.1287/moor.12.3.441. hdl : 1721.1/2893 . Consultado el 2 de noviembre de 2023 .
13. Kearns, Michael; Mansour, 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 (2/3): 193–208. doi : 10.1023/A:1017932429737 .
14. Altman, Eitan (1999). Procesos de decisión de Markov restringidos . Vol. 7. CRC Press.
15. 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.
16. Feyzabadi, S.; Carpin, S. (18–22 de agosto de 2014). "Planificación de rutas consciente del riesgo mediante procesos de decisión de Markov con restricciones jerárquicas". Ciencia e ingeniería de la automatización (CASE) . Conferencia internacional IEEE. págs. 297, 303.
17. 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.
18. Shoham, Y.; Powers, R.; Grenager, T. (2003). "Aprendizaje por refuerzo de múltiples agentes: una revisión crítica" (PDF) . Informe técnico, Universidad de Stanford : 1–13 . Consultado el 12 de diciembre de 2018 .
19. Narendra, KS ; Thathachar, MAL (1974). "Autómatas que aprenden: una revisión". IEEE Transactions on Systems, Man, and Cybernetics . SMC-4 (4): 323–334. CiteSeerX 10.1.1.295.2280 . doi :10.1109/TSMC.1974.5408453. ISSN  0018-9472. 
20. Narendra, Kumpati S .; Thathachar, Mandayam AL (1989). Autómatas de aprendizaje: una introducción . Prentice Hall. ISBN 9780134855585.
21. Narendra y Thathachar 1974, p.325 izquierda.

Lectura adicional

• 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 estados finitos . 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 markovianos 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 desde el original el 19 de junio de 2010.El apéndice contiene una versión abreviada de "Meyn & Tweedie". 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 sobre modelos estocásticos. Wiley. ISBN 9780470864289.