**SVRAI** Decisiones Secuenciales En ese tema entramos en el núcleo del objetivo del curso: la **toma de decisiones secuenciales**, donde resolver un problema consiste en realizar acciones (tomar decisiones) de forma consecutiva que conllevan el cambio dinámico del propio entorno del problema (es decir, las acciones que se tomen en un momento afectarán a las posibles acciones que se puedan tomar en el futuro). En este sentido, ya comentamos que los procedimientos voraces de buscar la optimalidad de las acciones individuales (es decir, repitiendo mecanismos de toma de decisiones de un paso) no aseguran la optimalidad de la solución del problema secuencial, por lo que hay que buscar otros marcos de representación y resolución que nos permitan mejorar esos primeros resultados ingenuos que podríamos obtener. Con este fin, este tema presenta un modelo conocido como **Procesos de Decisión de Markov** (MDP) para representar problemas de decisión secuenciales en los que los efectos de nuestras acciones son inciertos. Fueron presentados originalmente por [R.E. Bellman](https://es.wikipedia.org/wiki/Richard_Bellman) en la década de los 50 (publicados en [_Dynamic Programming_](https://press.princeton.edu/books/paperback/9780691146683/dynamic-programming)). Comenzaremos con una descripción del modelo, que especifica tanto la dinámica estocástica del sistema como la utilidad asociada a su evolución. Bajo este marco podemos utilizar diferentes algoritmos que nos permiten calcular la utilidad asociada a una estrategia de decisión y buscar una estrategia óptima. Bajo ciertos supuestos podemos encontrar soluciones exactas a los MDP, aunque lo normal es que estos métodos solo sean prácticos en modelos de tamaño muy reducido, y no proporcionan una solución efectiva. Más delante en el curso discutiremos algunos métodos de aproximación, que escalan mejor en problemas más grandes. # Elementos de la Toma de Decisiones Secuencial ![](./img/ApR.jpeg align="right")Además del agente y el entorno, se pueden identificar cuatro subelementos principales de un sistema de toma de decisiones secuencial (se debe tener en cuenta que esta organización es solo un modelo de representación, y no pretende reflejar una verdad universal del mundo real): 1. **Política**: define la forma de actuar del agente en un momento dado. A grandes rasgos, una política es un mapeo desde los estados percibidos del entorno hasta las acciones que se deben tomar cuando se encuentran en esos estados. Corresponde a lo que en psicología se llamaría un _conjunto de reglas o asociaciones estímulo-respuesta_. La política es el núcleo de un agente inteligente que debe tomar decisiones en el sentido de que por sí sola es suficiente para determinar el comportamiento. En algunos casos, una política puede darse por medio de una simple función o una tabla asociativa, mientras que en otros puede implicar un cálculo extenso, como podría ser un proceso de búsqueda y simulación. En general, las políticas no tienen porqué ser deterministas, sino que podrían ser estocásticas, especificando las probabilidades de cada acción. 1. **Señal de recompensa**: define el objetivo de la toma de decisiones. En cada paso de tiempo, el entorno envía al agente un único valor real llamado **recompensa**. Obsérvese la simplificación impuesta al considerar que un solo valor numérico es suficiente para evaluar la bondad de un estado, que reduce el objetivo del agente a maximizar la recompensa total que recibe a largo plazo. La señal de recompensa define, pues, cuáles son los eventos buenos y malos para el agente, son las características inmediatas y definitorias del problema al que se enfrenta el agente (en un sistema biológico, podríamos pensar que las recompensas son análogas a las experiencias de placer o dolor). La señal de recompensa es la base principal para modificar la política: si una acción seleccionada por la política va seguida de una baja recompensa, entonces la política puede intentar cambiarse para seleccionar en el futuro alguna otra acción más prometedora (que proporcione una mayor recompensa) en esa misma situación (aunque esta visión es tan cortoplacista como un algoritmo voraz). En general, las señales de recompensa pueden ser funciones estocásticas del estado del entorno y de las acciones realizadas. 1. **Función de Valor**: Mientras que la señal de recompensa indica lo que es bueno en un sentido inmediato, una **función de valor** especifica lo que es bueno a largo plazo. A grandes rasgos, el valor de un estado es la cantidad total de recompensa que un agente puede esperar acumular en el futuro partiendo de ese estado. Mientras que las recompensas determinan la conveniencia inmediata e intrínseca de los estados del entorno, los valores indican la conveniencia a largo plazo de los estados después de tener en cuenta los otros estados que probablemente se seguirán y las recompensas disponibles en esos otros estados. Por ejemplo, un estado puede producir siempre una recompensa inmediata baja, pero seguir teniendo un valor alto porque le siguen regularmente otros estados que producen recompensas altas... o puede ocurrir lo contrario. Para hacer una analogía animal, las recompensas son algo así como el placer (si es alto) y el dolor (si es bajo), mientras que los valores corresponden a un juicio más refinado y previsor sobre el grado de satisfacción o insatisfacción futuras que produce (en el agente) que el entorno se encuentre en un estado concreto. Las recompensas son, en cierto modo, primarias, mientras que los valores son, como predicciones de las recompensas, secundarios. Sin recompensas no podría haber valores, y el único propósito de estimar valores es conseguir más recompensas. Sin embargo, son los valores los que más nos preocupan a la hora de tomar y evaluar decisiones. Las elecciones de acción se hacen en base a juicios de valor. Buscamos acciones que provoquen estados de mayor valor, no de mayor recompensa, porque estas acciones obtienen la mayor cantidad de recompensa para nosotros a largo plazo. Por desgracia, es mucho más difícil determinar los valores que las recompensas. Básicamente, las recompensas vienen dadas directamente por el entorno, pero los valores deben ser estimados y reestimados a partir de las secuencias de observaciones que realiza un agente a lo largo de su vida. De hecho, el componente más importante de casi todos los algoritmos de toma de decisiones que vamos a considerar es un método para estimar eficazmente los valores. El papel central de la estimación de valores es, posiblemente, lo más importante que se ha aprendido sobre la toma de decisiones en las últimas décadas. 1. **Modelo del Entorno**: Se trata de algo que imita el comportamiento del entorno o, más generalmente, que permite hacer inferencias sobre cómo se comportará el entorno. Por ejemplo, dado un estado y una acción, el modelo puede predecir el siguiente estado y la siguiente recompensa resultantes. Los modelos se utilizan para permitir una planificación por medio de simulación, es decir, cualquier forma de decidir un curso de acción teniendo en cuenta las posibles situaciones futuras antes de que se produzcan. Si disponemos de un modelo, podemos adelantarnos a la evolución del sistema e inferir más sencillamente en qué situación nos encontraríamos si realizáramos ciertas acciones sin necesidad de ejecutarlas (permite la previsión). Los métodos para resolver problemas de toma de decisiones que utilizan modelos y planificación se denominan **métodos basados en modelos**, en contraposición a los métodos más sencillos **sin modelos**, o **libres de modelos**, que son explícitamente aprendices de prueba y error, considerados casi lo contrario de la planificación. Más adelante exploraremos sistemas que por ensayo y error aprenden un modelo del entorno y utilizan el modelo para planificar. Las metodologías de toma de decisiones modernas abarcan todo el espectro, desde el aprendizaje por ensayo y error de bajo nivel hasta la planificación deliberativa de alto nivel. # Procesos de Decisión de Markov ![](img/Andrei_Markov.jpg align="right" width="13%") En la mayoría de los casos los agentes habitan en un entorno cambiante, ya sea por la acción del propio agente o por acontecimientos externos (otros agentes, por ejemplo). Como hemos comentado, podemos pensar que el agente percibe el estado del mundo y luego realiza una acción que le lleva a un nuevo estado. Podemos hacer una suposición simplificadora adicional, y es que la elección del nuevo estado sólo depende del estado actual que percibe el agente y de su acción. Esta idea se recoge formalmente mediante lo que se conoce como **Proceso de Decisión de Markov** (**MDP**). !!!def:Proceso de Decisión de Markov En un **Proceso de Decisión de Markov** (**MDP**), elegimos una acción en el momento $t$ basándonos en la observación del estado $s_t$, y entonces recibimos una recompensa $r_t$. El espacio de acciones $\mathscr{A}$ es el conjunto de acciones posibles, y el espacio de estados $S$ es el conjunto de estados posibles. Algunos algoritmos asumen que estos conjuntos son finitos, pero esto no es necesario en general. El estado evoluciona de forma probabilística en función del estado actual y de la acción que realicemos. La suposición de que el siguiente estado depende sólo del estado y la acción actuales y no de ningún estado o acción anteriores se conoce como **suposición de Markov**. La función de transición $T(s'|s,a)$ da la probabilidad de que un agente en el estado $s$ que realiza la acción $a$ acabe en el estado $s'$. Para un mundo puramente **determinista**, fijado el par $(s,a)$, esta función será $0$ para todos los $s'$ excepto uno, para el que será $1$. Es decir, en un mundo determinista la acción de un agente tiene un efecto completamente predecible. En un entorno **no determinista** la acción de un agente podría conducir a un conjunto de estados diferentes, dependiendo del valor de esta función de probabilidad fija. ![Figura [MDP]: Ejemplo sencillo de MDP](img\sma1-1.png width="75%") !!!Tip La figura [MDP] muestra una representación de un **MDP**, en este caso, con $4$ estados, donde las acciones del agente están limitadas en función del estado. Por ejemplo, en el estado $s_1$ el agente sólo puede realizar las acciones $a_1$ y $a_2$. En este estado, si realiza la acción $a_1$ hay una probabilidad de $0.2$ de que se quede en el mismo estado, y de $0.8$ de que acabe en el estado $s_2$. Además, recibe una recompensa de $1$ sólo cuando llega a $s_3$, momento en el que su única opción es abandonar $s_3$ (por medio de las acciones $a_3$ o $a_4$). La función de recompensa es una función determinista de $s$ y $a$ porque representa una expectativa, pero las recompensas pueden generarse estocásticamente en el entorno o incluso depender del siguiente estado resultante. El ejemplo siguiente muestra cómo enmarcar un problema de evitación de colisiones como un MDP: !!!Tip: Problema de evitación de colisiones entre aviones como un MDP. Los estados representan las posiciones y velocidades de nuestra aeronave y de la aeronave intrusa, y las acciones representan si ascendemos, descendemos o nos mantenemos nivelados. Recibimos una gran recompensa negativa por colisionar con el otro avión y una pequeña recompensa negativa por subir o bajar. Una vez conocido el estado actual, debemos decidir si es necesario realizar una maniobra de evasión. El problema es difícil porque las posiciones de las aeronaves evolucionan de forma probabilística, y queremos asegurarnos de que empezamos nuestra maniobra lo suficientemente pronto para evitar la colisión, pero lo suficientemente tarde para evitar maniobras innecesarias. Las recompensas en un MDP se tratan como componentes de una función de utilidad descompuesta aditivamente. En un problema de **horizonte finito** con $n$ decisiones, la **utilidad** asociada a una secuencia de recompensas $r_{1:n}$ es, simplemente: \begin{equation} \label{eq1} \sum_{t=1}^n r_t \end{equation} La suma de recompensas se denomina a veces **rendimiento** o **rentabilidad**. En un problema de **horizonte infinito** en el que el número de decisiones es ilimitado, la suma de recompensas puede llegar a ser infinita. Hay varias formas de definir la utilidad en términos de recompensas individuales en problemas de horizonte infinito, las más habitual es imponer un **factor de descuento**, $\gamma \in [0,1)$, y entonces la **utilidad** viene entonces dada por: \begin{equation} \label{eq2} \sum_{t=1}^\infty \gamma^{t-1}r_t \end{equation} Este valor se denomina a veces **rentabilidad descontada**. Cuando $\gamma \in [0,1)$ y las recompensas están acotadas, la utilidad es finita. El factor de descuento hace que las recompensas en el presente valgan más que las recompensas en el futuro, un concepto que también aparece en economía. Otra forma de definir la utilidad en problemas de horizonte infinito es utilizar la **recompensa media**, también llamada **rendimiento medio**, dada por \begin{equation} \label{eq3} \lim_{n\to \infty} \frac{1}{n}\sum_{t=1}^n r_t \end{equation} Esta formulación puede ser atractiva porque no tenemos que elegir un factor de descuento, pero a menudo no hay ninguna diferencia práctica entre esta formulación y un rendimiento descontado con un factor de descuento cercano a $1$. Como el rendimiento descontado es a menudo computacionalmente más sencillo de trabajar, nos centraremos en la formulación descontada. Podemos representar un MDP en Julia usando la siguiente estructura de datos. Más adelante utilizaremos el campo `TR` para muestrear el siguiente estado y la recompensa a partir del estado y la acción actuales: `s', r = TR(s, a)`. En la escritura matemática, los MDP se definen a veces en términos de una tupla formada por los distintos componentes del MDP, es decir: `(𝒮, 𝒜, T, R, γ)`. ~~~~ struct MDP 𝒮 # state space 𝒜 # action space T # transition function R # reward function TR # sample transition and reward γ # discount factor end ~~~~