Proceso de decisión de Markov parcialmente observable

Un proceso de decisión de Markov parcialmente observable ( POMDP ) ​​es una generalización de un proceso de decisión de Markov (MDP). Un POMDP modela un proceso de decisión de agente en el que se supone que la dinámica del sistema está determinada por un MDP, pero el agente no puede observar directamente el estado subyacente. En cambio, debe mantener un modelo de sensor (la distribución de probabilidad de diferentes observaciones dado el estado subyacente) y el MDP subyacente. A diferencia de la función de política en MDP que asigna los estados subyacentes a las acciones, la política de POMDP es una asignación del historial de observaciones (o estados de creencia) a las acciones.

El marco POMDP es lo suficientemente general como para modelar una variedad de procesos de decisión secuencial del mundo real. Las aplicaciones incluyen problemas de navegación de robots, mantenimiento de máquinas y planificación bajo incertidumbre en general. El marco general de los procesos de decisión de Markov con información imperfecta fue descrito por Karl Johan Åström en 1965 ^[1] en el caso de un espacio de estados discretos, y fue estudiado más a fondo en la comunidad de investigación de operaciones donde se acuñó el acrónimo POMDP. Posteriormente fue adaptado para problemas en inteligencia artificial y planificación automatizada por Leslie P. Kaelbling y Michael L. Littman . ^[2]

Una solución exacta de un POMDP produce la acción óptima para cada creencia posible en los estados del mundo. La acción óptima maximiza la recompensa esperada (o minimiza el costo) del agente en un horizonte posiblemente infinito. La secuencia de acciones óptimas se conoce como la política óptima del agente para interactuar con su entorno.

Un POMDP de tiempo discreto modela la relación entre un agente y su entorno. Formalmente, un POMDP es una tupla de 7 , donde${\displaystyle (S,A,T,R,\Omega ,O,\gamma )}$

• ${\estilo de visualización S}$es un conjunto de estados,
• ${\estilo de visualización A}$es un conjunto de acciones,
• ${\estilo de visualización T}$es un conjunto de probabilidades de transición condicionales entre estados,
• ${\displaystyle R:S\times A\to \mathbb {R} }$es la función de recompensa.
• ${\estilo de visualización\Omega}$es un conjunto de observaciones,
• ${\estilo de visualización O}$es un conjunto de probabilidades de observación condicionales, y
• ${\displaystyle \gamma \en [0,1)}$es el factor de descuento.

En cada período de tiempo, el entorno está en algún estado . El agente realiza una acción , que hace que el entorno pase al estado con probabilidad . Al mismo tiempo, el agente recibe una observación que depende del nuevo estado del entorno, , y de la acción recién realizada, , con probabilidad (o a veces dependiendo del modelo del sensor). Finalmente, el agente recibe una recompensa igual a . Luego, el proceso se repite. El objetivo es que el agente elija acciones en cada paso de tiempo que maximicen su recompensa descontada futura esperada: , donde es la recompensa obtenida en el momento . El factor de descuento determina en qué medida se favorecen las recompensas inmediatas sobre las recompensas más distantes. Cuando al agente solo le importa qué acción rendirá la mayor recompensa inmediata esperada; cuando al agente le importa maximizar la suma esperada de recompensas futuras.${\displaystyle s\en S}$${\displaystyle a\en A}$${\estilo de visualización s'}$${\displaystyle T(s'\mid s,a)}$${\displaystyle o\in \Omega}$${\estilo de visualización s'}$${\estilo de visualización a}$${\displaystyle O(o\mid s',a)}$${\displaystyle O(o\mid s')}$${\estilo de visualización r}$${\displaystyle R(s,a)}$${\displaystyle E\left[\sum _{t=0}^{\infty }\gamma ^{t}r_{t}\right]}$$estilo de visualización r_{t}}$${\estilo de visualización t}$${\estilo de visualización \gamma}$${\displaystyle \gamma = 0}$${\displaystyle \gamma \rightarrow 1}$

Como el agente no observa directamente el estado del entorno, debe tomar decisiones en condiciones de incertidumbre respecto del estado real del mismo. Sin embargo, al interactuar con el entorno y recibir observaciones, el agente puede actualizar su creencia en el estado real actualizando la distribución de probabilidad del estado actual. Una consecuencia de esta propiedad es que el comportamiento óptimo puede incluir a menudo acciones (de recopilación de información) que se toman simplemente porque mejoran la estimación del agente del estado actual, lo que le permite tomar mejores decisiones en el futuro.

Resulta ilustrativo comparar la definición anterior con la definición de un proceso de decisión de Markov . Un MDP no incluye el conjunto de observaciones, porque el agente siempre conoce con certeza el estado actual del entorno. Alternativamente, un MDP puede reformularse como un POMDP estableciendo el conjunto de observaciones para que sea igual al conjunto de estados y definiendo las probabilidades condicionales de observación para seleccionar de manera determinista la observación que corresponde al estado verdadero.

Después de haber realizado la acción y observado , un agente necesita actualizar su creencia en el estado en el que puede (o no) estar el entorno. Dado que el estado es markoviano (por suposición), mantener una creencia sobre los estados solo requiere el conocimiento del estado de creencia anterior, la acción realizada y la observación actual. La operación se denota . A continuación, describimos cómo se calcula esta actualización de creencia.${\estilo de visualización a}$${\estilo de visualización o}$${\displaystyle b'=\tau(b,a,o)}$

Después de alcanzar , el agente observa con probabilidad . Sea una distribución de probabilidad sobre el espacio de estados . denota la probabilidad de que el entorno esté en el estado . Dado , entonces después de tomar la acción y observar ,${\estilo de visualización s'}$${\displaystyle o\in \Omega}$${\displaystyle O(o\mid s',a)}$${\estilo de visualización b}$${\estilo de visualización S}$${\displaystyle b(s)}$${\estilo de visualización s}$${\displaystyle b(s)}$${\estilo de visualización a}$${\estilo de visualización o}$

${\displaystyle b'(s')=\eta O(o\mid s',a)\sum _{s\in S}T(s'\mid s,a)b(s)}$

donde es una constante normalizadora con .${\displaystyle \eta = 1/\Pr(o\mid b,a)}$${\displaystyle \Pr(o\mid b,a)=\sum _{s'\in S}O(o\mid s',a)\sum _{s\in S}T(s'\mid s,a)b(s)}$

Un estado de creencia markoviano permite formular un POMDP como un proceso de decisión markoviano en el que cada creencia es un estado. El POMDP de creencia resultante se definirá así en un espacio de estados continuo (incluso si el POMDP "originario" tiene un número finito de estados: hay infinitos estados de creencia (en ) porque hay un número infinito de distribuciones de probabilidad sobre los estados (de )). ^[2]${\estilo de visualización B}$${\estilo de visualización S}$

Formalmente, la creencia MDP se define como una tupla donde${\displaystyle (B,A,\tau ,r,\gamma )}$

• ${\estilo de visualización B}$es el conjunto de estados de creencia sobre los estados POMDP,
• ${\estilo de visualización A}$es el mismo conjunto finito de acciones que para el POMDP original,
• ${\estilo de visualización \tau}$es la función de transición del estado de creencia,
• ${\displaystyle r:B\times A\to \mathbb {R} }$es la función de recompensa en los estados de creencia,
• ${\estilo de visualización \gamma}$es el factor de descuento igual al del POMDP original.${\estilo de visualización \gamma}$

De estos, y deben derivarse del POMDP original.${\estilo de visualización \tau}$${\estilo de visualización r}$${\estilo de visualización \tau}$

${\displaystyle \tau(b,a,b')=\sum _{o\in \Omega }\Pr(b'|b,a,o)\Pr(o|a,b),}$

¿Dónde está el valor derivado en la sección anterior y${\displaystyle \Pr(o|a,b)}$

${\displaystyle Pr(b'|b,a,o)={\begin{cases}1&{\text{si la actualización de creencias con argumentos }}b,a,o{\text{ devuelve }}b'\\0&{\text{en caso contrario }}\end{cases}}.}$

La función de recompensa MDP de creencia ( ) es la recompensa esperada de la función de recompensa POMDP sobre la distribución del estado de creencia:${\estilo de visualización r}$

${\displaystyle r(b,a)=\sum _{s\in S}b(s)R(s,a)}$.

La creencia MDP ya no es parcialmente observable, ya que en cualquier momento dado el agente conoce su creencia y, por extensión, el estado de la creencia MDP.

A diferencia del POMDP "de origen" (donde cada acción está disponible solo desde un estado), en el MDP de creencias correspondiente todos los estados de creencias permiten todas las acciones, ya que (casi) siempre tienes alguna probabilidad de creer que estás en cualquier estado (de origen). Como tal, especifica una acción para cualquier creencia .${\estilo de visualización \pi}$${\displaystyle a=\pi (b)}$${\estilo de visualización b}$

Aquí se supone que el objetivo es maximizar la recompensa total descontada esperada en un horizonte infinito. Cuando se define un costo, el objetivo pasa a ser la minimización del costo esperado.${\estilo de visualización R}$

La recompensa esperada por una política que parte de la creencia se define como${\estilo de visualización \pi}$$Estilo de visualización b_{0}$

${\displaystyle V^{\pi }(b_{0})=\sum _{t=0}^{\infty }\gamma ^{t}r(b_{t},a_{t})=\sum _{t=0}^{\infty }\gamma ^{t}E{\Bigl [}R(s_{t},a_{t})\mid b_{0},\pi {\Bigr ]}}$

donde es el factor de descuento. La política óptima se obtiene optimizando la recompensa a largo plazo.${\displaystyle \gamma <1}$${\displaystyle \pi ^{*}}$

${\displaystyle \pi ^{*}={\underset {\pi }{\mbox{argmax}}}\ V^{\pi }(b_{0})}$

¿Dónde está la creencia inicial?$Estilo de visualización b_{0}$

La política óptima, denotada por , produce el valor de recompensa esperado más alto para cada estado de creencia, representado de forma compacta por la función de valor óptimo . Esta función de valor es la solución de la ecuación de optimalidad de Bellman :${\displaystyle \pi ^{*}}$${\displaystyle V^{*}}$

${\displaystyle V^{*}(b)=\max _{a\in A}{\Bigl [}r(b,a)+\gamma \sum _{o\in \Omega }\Pr(o\mid b,a)V^{*}(\tau (b,a,o)){\Bigr ]}}$

En el caso de los POMDP de horizonte finito, la función de valor óptimo es lineal por partes y convexa. ^[3] Puede representarse como un conjunto finito de vectores. En la formulación de horizonte infinito, un conjunto finito de vectores puede aproximarse de forma arbitraria, cuya forma sigue siendo convexa. La iteración de valor aplica una actualización de programación dinámica para mejorar gradualmente el valor hasta la convergencia a una función de valor óptima y conserva su linealidad por partes y su convexidad. ^[4] Al mejorar el valor, la política se mejora implícitamente. Otra técnica de programación dinámica denominada iteración de política representa y mejora explícitamente la política. ^{[5] [6]}${\displaystyle V^{*}}$${\displaystyle \epsilon }$

En la práctica, los POMDP suelen ser computacionalmente intratables para resolverlos con exactitud. Esta intratabilidad se debe a menudo a la maldición de la dimensionalidad o la maldición de la historia (el hecho de que las políticas óptimas pueden depender de todo el historial de acciones y observaciones). Para abordar estas cuestiones, los científicos informáticos han desarrollado métodos que aproximan soluciones para los POMDP. Estas soluciones suelen intentar aproximarse al problema o la solución con un número limitado de parámetros, ^[7] planificar solo sobre una pequeña parte del espacio de creencias en línea o resumir el historial de acciones y observaciones de forma compacta.

Los algoritmos basados ​​en cuadrículas ^[8] comprenden una técnica de solución aproximada. En este enfoque, la función de valor se calcula para un conjunto de puntos en el espacio de creencias y se utiliza la interpolación para determinar la acción óptima a tomar para otros estados de creencias que se encuentran y que no están en el conjunto de puntos de la cuadrícula. Trabajos más recientes hacen uso de técnicas de muestreo, técnicas de generalización y explotación de la estructura del problema, y ​​han extendido la resolución de POMDP a grandes dominios con millones de estados. ^{[9] [10]} Por ejemplo, cuadrículas adaptativas y métodos basados ​​en puntos muestrean puntos de creencias alcanzables al azar para restringir la planificación a áreas relevantes en el espacio de creencias. ^{[11] [12]} También se ha explorado la reducción de dimensionalidad utilizando PCA . ^[13]

Los algoritmos de planificación en línea abordan los grandes POMDP construyendo una nueva política para la creencia actual cada vez que se recibe una nueva observación. Dicha política solo necesita considerar las creencias futuras alcanzables a partir de la creencia actual, que a menudo es solo una parte muy pequeña del espacio de creencias completo. Esta familia incluye variantes de búsqueda de árbol de Monte Carlo ^[14] y búsqueda heurística ^[15] . De manera similar a los MDP, es posible construir algoritmos en línea que encuentren políticas arbitrariamente cercanas a las óptimas y que no tengan una dependencia directa de la complejidad computacional con el tamaño de los espacios de estado y de observación ^{[16] .}

Otra línea de técnicas de solución aproximada para resolver POMDP se basa en el uso de (un subconjunto de) el historial de observaciones, acciones y recompensas anteriores hasta el paso de tiempo actual como un pseudoestado. Luego se pueden utilizar las técnicas habituales para resolver MDP basadas en estos pseudoestados (por ejemplo, Q-learning ). Idealmente, los pseudoestados deberían contener la información más importante de todo el historial (para reducir el sesgo) y al mismo tiempo estar lo más comprimidos posible (para reducir el sobreajuste). ^[17]

La planificación en POMDP es indecidible en general. Sin embargo, se han identificado algunos ajustes que son decidibles (ver la Tabla 2 en ^[18] reproducida a continuación). Se han considerado diferentes objetivos. Los objetivos Büchi se definen mediante autómatas Büchi . La alcanzabilidad es un ejemplo de una condición Büchi (por ejemplo, alcanzar un buen estado en el que todos los robots estén en casa). Los objetivos coBüchi corresponden a trazas que no satisfacen una condición Büchi dada (por ejemplo, no alcanzar un mal estado en el que algún robot murió). Los objetivos de paridad se definen mediante juegos de paridad ; permiten definir objetivos complejos de modo que se alcance un buen estado cada 10 pasos de tiempo. El objetivo se puede satisfacer:

• casi con seguridad, es decir la probabilidad de satisfacer el objetivo es 1;
• positivo, es decir la probabilidad de satisfacer el objetivo es estrictamente mayor que 0;
• cuantitativo, es decir la probabilidad de satisfacer el objetivo es mayor que un umbral dado.

También consideramos el caso de memoria finita en el que el agente es una máquina de estados finitos y el caso general en el que el agente tiene una memoria infinita.

Los POMDP se pueden utilizar para modelar muchos tipos de problemas del mundo real. Entre las aplicaciones más destacadas se incluyen el uso de un POMDP en el tratamiento de pacientes con cardiopatía isquémica, ^[19] la tecnología de asistencia para personas con demencia, ^{[9] [10]} la conservación de los tigres de Sumatra, en peligro crítico de extinción y difíciles de detectar ^[20] y la prevención de colisiones de aeronaves. ^[21]

Una aplicación es un caso de enseñanza, un problema de un bebé que llora, donde un padre necesita decidir secuencialmente si alimentar al bebé basándose en la observación de si el bebé está llorando o no, lo que es una representación imperfecta del estado real de hambre del bebé. ^{[22] [23]}

• APPL, un solucionador rápido de POMDP basado en puntos
• Controladores de estado finito que utilizan ramificación y acotación Un solucionador POMDP exacto para políticas de tamaño acotado
• pomdp: Infraestructura para procesos de decisión de Markov parcialmente observables (POMDP), un paquete R que incluye una interfaz para el programa pomdp-solve de Tony Cassandra.
• POMDPs.jl, una interfaz para definir y resolver MDP y POMDP en Julia y Python con una variedad de solucionadores.
• pyPOMDP, una caja de herramientas (PO)MDP (simulador, solucionador, aprendiz, lector de archivos) para Python por Oliver Stollmann y Bastian Migge
• zmdp, un solucionador POMDP de Trey Smith