Proceso de decisión de Markov parcialmente observable

Generalización de un proceso de decisión de Markov

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.

Definición

Definición formal

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 )}$

• ${\displaystyle S}$es un conjunto de estados,
• ${\displaystyle A}$es un conjunto de acciones,
• ${\displaystyle 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.
• ${\displaystyle \Omega }$es un conjunto de observaciones,
• ${\displaystyle O}$es un conjunto de probabilidades de observación condicionales, y
• ${\displaystyle \gamma \in [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\in S}$ ${\displaystyle a\in A}$ ${\displaystyle s'}$ ${\displaystyle T(s'\mid s,a)}$ ${\displaystyle o\in \Omega }$ ${\displaystyle s'}$ ${\displaystyle a}$ ${\displaystyle O(o\mid s',a)}$ ${\displaystyle O(o\mid s')}$ ${\displaystyle r}$ ${\displaystyle R(s,a)}$ ${\displaystyle E\left[\sum _{t=0}^{\infty }\gamma ^{t}r_{t}\right]}$ ${\displaystyle r_{t}}$ ${\displaystyle t}$ ${\displaystyle \gamma }$ ${\displaystyle \gamma =0}$ ${\displaystyle \gamma \rightarrow 1}$

Discusión

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.

Actualización de creencias

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. ${\displaystyle a}$ ${\displaystyle 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 , ${\displaystyle s'}$ ${\displaystyle o\in \Omega }$ ${\displaystyle O(o\mid s',a)}$ ${\displaystyle b}$ ${\displaystyle S}$ ${\displaystyle b(s)}$ ${\displaystyle s}$ ${\displaystyle b(s)}$ ${\displaystyle a}$ ${\displaystyle 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)}$

Creencia MDP

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] ${\displaystyle B}$ ${\displaystyle S}$

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

• ${\displaystyle B}$es el conjunto de estados de creencia sobre los estados POMDP,
• ${\displaystyle A}$es el mismo conjunto finito de acciones que para el POMDP original,
• ${\displaystyle \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,
• ${\displaystyle \gamma }$es el factor de descuento igual al del POMDP original. ${\displaystyle \gamma }$

De estos, y deben derivarse del POMDP original. ${\displaystyle \tau }$ ${\displaystyle r}$ ${\displaystyle \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{if the belief update with arguments }}b,a,o{\text{ returns }}b'\\0&{\text{otherwise }}\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: ${\displaystyle 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.

Función política y de valor

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 . ${\displaystyle \pi }$ ${\displaystyle a=\pi (b)}$ ${\displaystyle 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. ${\displaystyle R}$

La recompensa esperada por una política que parte de la creencia se define como ${\displaystyle \pi }$ ${\displaystyle 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? ${\displaystyle 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 }$

Soluciones aproximadas de POMDP

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]

Teoría POMDP

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.

Aplicaciones

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]}

Referencias

1. Åström, KJ (1965). "Control óptimo de procesos de Markov con información de estado incompleta". Revista de análisis matemático y aplicaciones . 10 : 174–205. doi : 10.1016/0022-247X(65)90154-X .
2. Kaelbling, LP, Littman, ML, Cassandra, AR (1998). "Planificación y actuación en dominios estocásticos parcialmente observables". Inteligencia artificial . 101 (1–2): 99–134. doi :10.1016/S0004-3702(98)00023-X.{{cite journal}}: CS1 maint: multiple names: authors list (link)
3. Sondik, EJ (1971). El control óptimo de procesos de Markov parcialmente observables (tesis doctoral). Universidad de Stanford. Archivado desde el original el 17 de octubre de 2019.
4. Smallwood, RD, Sondik, EJ (1973). "El control óptimo de procesos de decisión de Markov parcialmente observables en un horizonte finito". Investigación de operaciones . 21 (5): 1071–88. doi :10.1287/opre.21.5.1071.{{cite journal}}: CS1 maint: multiple names: authors list (link)
5. Sondik, EJ (1978). "El control óptimo de procesos de Markov parcialmente observables en el horizonte infinito: coste descontado". Investigación de operaciones . 26 (2): 282–304. doi :10.1287/opre.26.2.282.
6. Hansen, E. (1998). "Resolución de POMDP mediante búsqueda en el espacio de políticas". Actas de la Decimocuarta Conferencia Internacional sobre Incertidumbre en Inteligencia Artificial (UAI-98) . arXiv : 1301.7380 .
7. Hauskrecht, M. (2000). "Aproximaciones de funciones de valor para procesos de decisión de Markov parcialmente observables". Revista de investigación en inteligencia artificial . 13 : 33–94. arXiv : 1106.0234 . doi : 10.1613/jair.678 .
8. Lovejoy, W. (1991). "Límites computacionalmente factibles para procesos de decisión de Markov parcialmente observados". Investigación de operaciones . 39 : 162–175. doi :10.1287/opre.39.1.162.
9. Jesse Hoey; Axel von Bertoldi; Pascal Poupart; Alex Mihailidis (2007). "Asistencia a personas con demencia durante el lavado de manos mediante un proceso de decisión de Markov parcialmente observable". Actas de la Conferencia internacional sobre sistemas de visión artificial . doi :10.2390/biecoll-icvs2007-89.
10. Jesse Hoey; Pascal Poupart; Axel von Bertoldi; Tammy Craig; Craig Boutilier; Alex Mihailidis. (2010). "Asistencia automatizada para el lavado de manos para personas con demencia mediante video y un proceso de decisión de Markov parcialmente observable". Visión artificial y comprensión de imágenes . 114 (5): 503–519. CiteSeerX 10.1.1.160.8351 . doi :10.1016/j.cviu.2009.06.008. 
11. Pineau, J., Gordon, G., Thrun, S. (agosto de 2003). "Iteración de valor basada en puntos: un algoritmo en cualquier momento para POMDP" (PDF) . Conferencia conjunta internacional sobre inteligencia artificial (IJCAI). Acapulco, México . pp. 1025–32.{{cite conference}}: CS1 maint: multiple names: authors list (link)
12. Hauskrecht, M. (1997). "Métodos incrementales para calcular límites en procesos de decisión de Markov parcialmente observables". Actas de la 14.ª Conferencia Nacional sobre Inteligencia Artificial (AAAI). Providence, RI . pp. 734–739. CiteSeerX 10.1.1.85.8303 . 
13. Roy, Nicholas ; Gordon, Geoffrey (2003). "Analizador de componentes primarios de familia exponencial para compresión de creencias en POMDP" (PDF) . Avances en sistemas de procesamiento de información neuronal .
14. David Silver y Joel Veness (2010). Planificación de Montecarlo en grandes POMDP . Avances en sistemas de procesamiento de información neuronal.
15. Nan Ye, Adhiraj Somani, David Hsu y Wee Sun Lee (2017). "DESPOT: Planificación POMDP en línea con regularización". Revista de investigación en inteligencia artificial . 58 : 231–266. arXiv : 1609.03250 . doi : 10.1613/jair.5328 .{{cite journal}}: CS1 maint: multiple names: authors list (link)
16. Michael H. Lim, Tyler J. Becker, Mykel J. Kochenderfer, Claire J. Tomlin y Zachary N. Sunberg (2023). "Garantías de optimalidad para la aproximación de creencias de partículas de POMDP". Revista de investigación en inteligencia artificial . 77 : 1591–1636. arXiv : 2210.05015 . doi : 10.1613/jair.1.14525 .{{cite journal}}: CS1 maint: multiple names: authors list (link)
17. Francois-Lavet, V., Rabusseau, G., Pineau, J., Ernst, D., Fonteneau, R. (2019). Sobreajuste y sesgo asintótico en el aprendizaje por refuerzo por lotes con observabilidad parcial. Journal of Artificial Intelligence Research (JAIR) . Vol. 65. págs. 1–30. arXiv : 1709.07796 .{{cite conference}}: CS1 maint: multiple names: authors list (link)
18. Chatterjee, Krishnendu; Chmelík, Martin; Tracol, Mathieu (1 de agosto de 2016). "Qué es decidible acerca de los procesos de decisión de Markov parcialmente observables con objetivos ω-regulares". Revista de Ciencias de la Computación y de Sistemas . 82 (5): 878–911. doi : 10.1016/j.jcss.2016.02.009 . ISSN  0022-0000.
19. Hauskrecht, M., Fraser, H. (2000). "Planificación del tratamiento de la cardiopatía isquémica con procesos de decisión de Markov parcialmente observables". Inteligencia artificial en medicina . 18 (3): 221–244. doi :10.1016/S0933-3657(99)00042-1. PMID  10675716.{{cite journal}}: CS1 maint: multiple names: authors list (link)
20. Chadès, I., McDonald-Madden, E., McCarthy, MA, Wintle, B., Linkie, M., Possingham, HP (16 de septiembre de 2008). "Cuándo dejar de gestionar o estudiar especies crípticas amenazadas". Proc. Natl. Sci. USA . 105 (37): 13936–40. Bibcode :2008PNAS..10513936C. doi : 10.1073/pnas.0805265105 . PMC 2544557 . PMID  18779594. {{cite journal}}: CS1 maint: multiple names: authors list (link)
21. Kochenderfer, Mykel J. (2015). "Optimización de la prevención de colisiones aéreas". Toma de decisiones en condiciones de incertidumbre . The MIT Press.
22. Kochenderfer, Mykel J.; Wheeler, Tim A.; Wray, Kyle H. (2022). Algoritmos para la toma de decisiones. Cambridge, Massachusetts; Londres, Inglaterra: MIT Press. p. 678. ISBN 9780262047012.
23. Moss, Robert J. (24 de septiembre de 2021). "MIRA: POMDPs: Toma de decisiones en situaciones de incertidumbre POMDPs.jl. Problema del bebé que llora" (video) . youtube.com . El lenguaje de programación Julia .

Enlaces externos

• 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