**Agentes Basados en Utilidades:** Procesos de Decisión de Markov SVRAI
Fernando Sancho Caparrini --- **Objetivo SMA**: encontrar métodos para modelar sistemas complejos con agentes autónomos con conocimiento local y habilidades limitadas. Usa herramientas de: * **Teoría de Juegos** / **Economía** / **Sociología** / **Biología** y las complementa con ideas/algoritmos de **Inteligencia Artificial**: * **Planificación** * **Razonamiento Automático** * **Búsqueda** * **Aprendizaje Automático** --- # Funciones de Utilidad --- * Simplificación: las preferencias de un agente pueden ser capturadas por una **función de utilidad** * Tomado de la **Teoría de Juegos** (von Neumann, Morgenstern) !!!def:Función de Utilidad Si $S$ es el conjunto de *estados del mundo que el agente puede percibir*: $$ u : S \rightarrow \mathbb{R} $$ * Para que sea abordable: reducción del espacio de estados reconocibles por el agente * Funciones de utilidad: forma compacta y matemática de representar el comportamiento de un agente (probabilísticas, aprendibles mientras el agente actúa, incompletas, resultado de inferencia o inducción,...) --- ## Utilidad Esperada * Los agentes tienen **sensores** para determinar el estado del mundo, y **actuadores** para realizar acciones sobre el mundo. * Ejecutar acciones conduce al agente a nuevos estados del mundo. * **Función de Transición Estocástica**: sensores y efectores pueden no funcionar bien, el agente conoce la probabilidad de alcanzar el estado $s'$ suponiendo que está en el estado $s$ y realiza la acción $a$, $T(s,a,s')$: $$ \forall a\in A,\; \forall s\in S\; (\sum_{s'\in S}T(s,a,s')=1) $$ --- ## Utilidad Esperada !!! Tip En un Espacio de Estados, la función de transición devuelve, para cada estado, $s$, y acción, $a$, un estado futuro, $s'=T(s,a)=T_{s,a}$, por lo que se comporta como una función completamente determinista. Sin embargo, cuando hay incertidumbre acerca de la ejecución de la acción, lo que obtenemos es una probabilidad de acabar en cualquiera de los posibles estados del mundo: $F_{s,a}(s')=T(s,a,s')$, y por ello expresamos la función de transición como una gran función que depende de los tres factores. --- ## Utilidad Esperada !!!def:Utilidad Esperada Bajo la existencia de una función de utilidad, y por medio de esta función de transición, el agente puede calcular la **utilidad esperada** por tomar la acción $a$ en el estado $s$ como: $$ E[u,s,a] = \sum_{s' \in S} T(s,a,s')u(s') $$ !!! Tip Probabilidad básica: esta definición no es distinta de la cualquier esperanza de una variable aleatoria. --- ## Asignar valor a la información recibida Si una nueva información lleva al agente a determinar que no está realmente en el estado $s$ que creía, sino un estado distinto, $t$, el agente puede comparar la utilidad esperada entre ambos estados, de forma que **valor de la información** recibida podría ser: $$ E[u,t,\pi(t)] - E[u,t,\pi(s)] $$ donde $\pi$ representa la estrategia de toma de acciones que el agente usa para determinar qué hacer (evaluando su creencia del estado del mundo). !!!Tip Proporciona una forma sencilla y robusta para que los agentes tomen decisiones a un nivel superior sobre qué conocimiento buscar. Un agente puede utilizar esta información para evaluar *qué pasaría si* y determinar su mejor acción. --- ## Procesos de Decisión de Markov ![](../SVRAI/img/Andrei_Markov.jpg align="right" width="15%") Podemos pensar que el agente percibe el estado del mundo y luego realiza una acción que le lleva a un nuevo estado. **Suposición simplificadora adicional**: la elección del nuevo estado sólo depende del estado actual que percibe el agente y de su acción. !!!def:Proceso de Decisión de Markov Un **MDP** consta de un estado inicial $s_1\in S$, una función de transición $T(s,a,s')$ y una función de recompensa $r: S \rightarrow \mathbb{R}$. --- ## Procesos de Decisión de Markov ![](..\SVRAI\img\sma1-1.png height="70%") --- ## Procesos de Decisión de Markov !!!:Políticas El comportamiento del agente es capturado por un **política**, que es un mapeo de los estados a las acciones. Usaremos $\pi$ para denotar la política del agente. !!!Tip: Ejemplos 1. Elegir en $s$ cualquiera de las acciones disponibles (para $s$) con la misma probabilidad: $\pi(s, a) = \frac{1}{|A(s)|},\ \forall s\in S,\ a\in A(s)$. 2. Si hay orden entre las acciones, elegir siempre la primera acción disponible en cada estado. --- ## Políticas de Maximización de Utilidad Un agente *egoísta* tiene como objetivo encontrar su política óptima: la que maximiza su utilidad esperada. !!! **Máxima Utilidad Esperada**: $\pi^*(s) = \arg \max_{a \in A} E[u,s,a]$ Pero hay que determinar qué hacer con las recompensas futuras. !!! **Recompensas con Descuento**: Reducen el impacto de las recompensas que están más lejos en el futuro. Si se usa un factor de descuento, $\gamma\in (0,1)$ ($\gamma=0$, agente voraz, recompensas inmediatas), entonces la recompensa total será: $$ \gamma^0 r(s_1) + \gamma^1 r(s_2) + \gamma^2 r(s_3) + \cdots $$ --- ## Políticas de Maximización de Utilidad ![](..\SVRAI\img\Richard_Ernest_Bellman.jpg align="left")Sólo sabemos $s_1$, los estados, $s_2, s_3,\ldots$ dependen de $T$. Si el agente intenta maximizar la utilidad entonces debe seguir la política: $$ \pi^*(s) = \arg\max_a \sum_{s'} T(s,a,s') u(s') $$ !!! **Ecuación de Bellman**: $u(s) = r(s) + \gamma \cdot \max_a \sum_{s'} T(s,a,s')u(s')$ La utilidad de un agente no sólo depende de sus recompensas inmediatas, sino también de sus recompensas futuras con descuento. --- ## Políticas de Maximización de Utilidad Una vez que tenemos esta función definida para todos los estados, $s$, también tenemos la verdadera política óptima del agente $\pi^*(s)$. **Problema**: cómo calcular $\pi^*(s)$ a partir de la definición del **MDP**. ¿Intentar resolver exactamente el conjunto de ecuaciones construidas? Con $n$ estados hay $n$ ecuaciones de Bellman, cada una con una variable diferente. ... si el sistema fuera lineal, sería resoluble, pero el operador $\max$ hace que las ecuaciones no sean lineales. --- ## Funciones de Valor Óptimas !!!Tip Una función de valor indica cómo de bueno es para el agente estar en un estado dado o realizar una acción particular en un estado dado. !!!def: Función de valor-estado para $\pi$ El valor de un estado $s$ bajo una política $\pi$, $V^\pi(s)$, es la utilidad esperada a partir del estado $s$ si se sigue la política $\pi$. Formalmente: $$V^\pi(s)= E_\pi[r_t:\ s_t = s] = E_\pi[\sum_{k=0}^\infty \gamma^k r_{t+k+1}:\ s_t=s]$$ --- ## Funciones de Valor Óptimas !!!Tip Como el resultado de las acciones es no determinista, la ejecución de una misma $\pi$ desde un mismo $s$ puede resultar en una distinta trayectoria y utilidad en cada ejecución, por lo que $V^\pi(s)$ es en sí mismo una variable aleatoria. !!! **Una forma muy primitiva de calcularlo**: Ejecutar $n$ veces $\pi$ desde $s$, registrar cada una de las utilidades obtenidas, y luego promediarlas para obtener una estimación de la utilidad esperada. Entonces, cuando $n\to \infty$, esta estimación se acerca al verdadero valor de $V^\pi(s)$. --- ## Funciones de Valor Óptimas !!!def:Función de valor-acción para $\pi$ El valor de la acción $a$ en el estado $s$, $Q^\pi(s, a)$, es la utilidad esperada cuando se comienza en el estado $s$, se toma la acción $a$ y después se sigue la política $\pi$: $$Q^\pi(s, a) = E_\pi[r_t:\ s_t = s,\ a_t = a] = E_\pi[\sum_{k=0}^\infty \gamma^k r_{t+k+1}:\ s_t=s,\ a_t=a]$$ **Objetivo**: Encontrar la política óptima, $\pi^*$ ($\Pi$ es el espacio de políticas posibles): $$V^{\pi^*}(s)\geq V^\pi(s),\ \forall s\in S,\ \forall \pi\in \Pi\\ Q^{\pi^*}(s,a)\geq Q^\pi(s,a),\ \forall s\in S,\ \forall a \in A,\ \forall \pi\in \Pi$$ --- ## Métodos de Resolución de MDP Si tenemos $V^*$ o $Q^*$, $\pi^*(s)$ puede ser derivada fácilmente. Aunque hay multitud de técnicas para resolver MDPs, veremos: **value-iteration** y **Q-learning**.  --- ### Value-Iteration Un mecanismo habitual es el de **iteración de valores** (mecanismos *recursivos*): comenzamos estableciendo los valores de $u(s)$ a valores arbitrarios (por ejemplo, todos a $0$) y luego mejoramos iterativamente estos valores utilizando la **ecuación de actualización de Bellman**: $u^{t+1}(s) \leftarrow r(s) + \gamma \max_a \sum_{s'}T(s,a,s')u^t(s')$ ~~~~none VALUE-ITERATION(T,r,γ,ε) u = 0 (la función nula) Hacer: u = u' δ = 0 Para cada s ∈ S hacer: u'(s) = r(s) + γ max_a Σ_{s'}T(s,a,s')u(s') Si |u'(s)-u(s)| > δ entonces δ = |u'(s)-u(s)| hasta que δ < ε(1-γ)/γ Devolver u ~~~~ --- ### Value-Iteration ![Ejecución del Algoritmo Value-Iteration](..\SVRAI\img\sma1-3.png width="100%") --- ### Q-Learning Diferencia con *Value-Iteration*: la política no se deriva del modelo, sino que se aproxima $\pi^*$ a partir de la experiencia del agente en su interacción con el entorno. Q-Learning es uno de los métodos de aprendizaje por refuerzo más conocidos y se basa en el aprendizaje de la función $Q^*$: $$Q^*(s_t, a_t) = r_{t+1} + \gamma\cdot \max_a Q^*(s_{t+1}, a)$$ Podemos aprovecharla para la regla de actualización: $$Q(s_t, a_t) \leftarrow \alpha \left( r_{t+1} + \gamma \cdot\max_a Q(s_{t+1}, a)\right) + (1 − \alpha)Q(s_t, a_t) $$ --- ### Q-Learning ~~~~none Q-LEARNING Inicializar Tabla Q(s, a) para cada s ∈ S y cada a ∈ A(s) (con 0’s o valores arbitrarios). Hacer: Inicializar s. Hacer: Elegir a desde s usando una política derivada de Q. Ejecutar a, observar estado resultante s′ y recompensa r. Q(s, a) ← Q(s, a) + α[r + γ max_a′Q(s′, a′) − Q(s, a)] s ← s′ Hasta que s sea terminal ~~~~ $\alpha$ (**índice de aprendizaje**) determina hasta qué punto la nueva información sobrescribe la vieja: $\alpha=0$ hace que el agente no aprenda, $\alpha=1$ hace que el agente considere solo la información más reciente. --- ### Otras Opciones MDPs como marco teórico del **Aprendizaje por Refuerzo**. Destaca Q-Learning. **Limitaciones prácticas**: representar $Q$ con una tabla de dimensiones $|S|\times |A|$. **Solución**: aproximar $Q$ por medio de funciones. Recientemente, redes neuronales, que dan lugar **Deep Q-Learning**, donde destaca el famoso algoritmo **Deep Q-network** (**DQN**). Otras: **REINFORCE** (ascenso del gradiente); **métodos basados en modelo** (aprenden dinámicas)... combinaciones de los 3 enfoques. --- ## MDP multiagente Formas de transformar un MDP en un MDP multiagente: 1. Colocar todos los efectos de los otros agentes en la función de transición: los otros agentes como parte del entorno. Solo para casos sencillos donde los agentes no cambian su comportamiento (la transición en un MDP debe ser fija). 2. Definir $T(s,\vec{a},s')$, donde $\vec{a}$ donde cada componente es la acción de un agente. Determinar cómo se va a repartir la recompensa: - dividirla por igual entre los agentes (¿recompensarles por sus malas acciones porque hay otros que lo están haciendo bien?); - proporcional a su contribución a la recompensa global del sistema. --- ## MDPs Parcialmente Observables Cuando no es posible percibir el estado completo del mundo o son inciertas. !!!def:Proceso de Decisión de Markov Parcialmente Observable - **Estado de creencia**, $\vec{b}$ (de *believe*): una distribución de probabilidad sobre el conjunto de estados posibles e indica la creencia del agente de que está en ese estado. - **Modelo de observación**, $O(s,o)$, la probabilidad de que perciba la observación $o$ cuando esté en el estado $s$. $$\forall s'\in S \;(\vec{b}'(s') = \alpha \cdot O(s', o) \sum_{s\in S} T(s,a,s')\, \vec{b}(s))$$ --- ## Planificación en SMA !!! **Planificación**: el agente recibe un conjunto de operadores. Encontrar una secuencia de operadores que lleven al agente desde el estado inicial hasta el estado objetivo (caso especial de MDP, donde sólo los estados finales proporcionan recompensa). - Proporcionan una definición mucho más compacta y expresiva del problema. - La mayoría de los algoritmos de planificación modernos utilizan una representación en forma de grafo del problema (muchas veces con elementos de alguna lógica), y cada nodo del grafo puede ser interpretado como un estado. Es decir, acaban convirtiendo el problema en un problema tipo MDP y lo resuelven. - Planificación Jerárquica. --- ## Resumen !!! Tip Agente autónomo como agente maximizador de utilidad es muy flexible, aplicable a dominios dispares, analizable formalmente con herramientas matemáticas o computacionales. Por ello, base para formular problemas de modelado de sistemas complejos. Pero lo más habitual es encontrar algoritmos que utilizan métodos más compactos y prácticos... específicas del dominio y difícil trasladarlas de un dominio a otro. Considerar: las soluciones genéricas no son eficientes en muchos de problemas concretos.