Toma de Decisiones Secuencial (MDPs)

La toma de decisiones secuencial formaliza cómo un agente debe actuar a lo largo del tiempo en un entorno estocástico, utilizando procesos de decisión de Markov en los que las acciones producen recompensas y cambian probabilísticamente el estado, para calcular una política que maximice la recompensa esperada a largo plazo.

Definition

Un proceso de decisión de Markov se define por estados, acciones, una función de probabilidad de transición y una función de recompensa; la toma de decisiones secuencial busca una política que mapee estados a acciones que maximice la recompensa acumulativa esperada (típicamente descontada), dado el modelo.

Scope

Este tema abarca la planificación de decisiones a lo largo del tiempo: el modelo de proceso de decisión de Markov (MDP) de estados, acciones, probabilidades de transición, recompensas y descuento; políticas y funciones de valor; las ecuaciones de Bellman que caracterizan el comportamiento óptimo; y los algoritmos de programación dinámica de iteración de valor e iteración de políticas para resolver un modelo conocido. También introduce los MDP parcialmente observables (POMDPs) y la planificación de estados de creencia. El enfoque se centra en la planificación cuando el modelo es dado; el aprendizaje de una política a partir de la experiencia sin un modelo conocido es el aprendizaje por refuerzo, que pertenece al subcampo del aprendizaje automático.

Core questions

• ¿Cómo se modela la actuación a lo largo del tiempo bajo transiciones estocásticas como estados, acciones, transiciones y recompensas?
• ¿Qué dice la ecuación de optimalidad de Bellman sobre el valor de una política óptima?
• ¿Cómo calculan la iteración de valor y la iteración de políticas una política óptima cuando el modelo es conocido?
• ¿Cómo conduce la observabilidad parcial a los POMDPs y la planificación sobre estados de creencia?

Key concepts

• estados, acciones, transiciones, recompensas
• política
• función de valor
• factor de descuento
• ecuaciones de Bellman
• iteración de valor
• iteración de políticas
• POMDP y estado de creencia

Key theories

Ecuación de optimalidad de Bellman

El valor óptimo de un estado es igual a la mejor recompensa inmediata más el valor óptimo esperado descontado del siguiente estado; esta relación recursiva caracteriza el comportamiento secuencial óptimo y es la base de las soluciones de programación dinámica.

Iteración de valor y de políticas

Para un MDP conocido, la iteración de valor aplica repetidamente la actualización de Bellman hasta la convergencia, y la iteración de políticas alterna la evaluación y mejora de políticas; ambas garantizan encontrar una política óptima.

MDPs parcialmente observables

Cuando el estado no es directamente observable, la planificación se realiza sobre un estado de creencia (una distribución sobre estados) actualizado a partir de observaciones; resolver tales POMDPs es mucho más difícil que el caso totalmente observable, pero captura limitaciones de detección realistas.

Clinical relevance

La toma de decisiones basada en MDP y POMDP subyace a la navegación y el control de robots, la gestión automatizada de diálogos, las decisiones de mantenimiento e inventario, y la asignación de recursos, y proporciona la base de planificación teórica de decisiones sobre la cual se construye el aprendizaje por refuerzo cuando el modelo del entorno debe aprenderse en su lugar.

History

La toma de decisiones secuencial surgió de la programación dinámica de Bellman (1957) y la iteración de políticas de Howard (1960). La monografía de Puterman de 1994 consolidó la teoría de los procesos de decisión de Markov, y Kaelbling, Littman y Cassandra (1998) introdujeron los MDP parcialmente observables en la IA convencional como un modelo para actuar bajo percepción incierta.

Key figures

• Richard Bellman
• Ronald A. Howard
• Martin L. Puterman
• Leslie P. Kaelbling
• Michael L. Littman

Seminal works

• bellman1957
• puterman1994
• kaelbling1998

Frequently asked questions

¿En qué se diferencia esto del aprendizaje por refuerzo?

La toma de decisiones secuencial con MDPs asume que el modelo de transición y recompensa es conocido, por lo que una política óptima puede calcularse directamente mediante programación dinámica. El aprendizaje por refuerzo aborda el caso en que el modelo es desconocido y el agente debe aprender una buena política a partir de la experiencia; utiliza el MDP como su formalismo subyacente.

¿Qué es un estado de creencia en un POMDP?

En un MDP parcialmente observable, el agente no puede ver el estado verdadero, por lo que mantiene un estado de creencia, una distribución de probabilidad sobre los estados posibles, actualizada a medida que realiza acciones y recibe observaciones. La planificación se lleva a cabo entonces sobre estos estados de creencia en lugar de directamente sobre los estados ocultos.