Hoy trataremos de los procesos de adhesión de Márkov, un formalismo matemático para la toma de decisiones en entornos con incertidumbre. [MÚSICA] [MÚSICA] Los procesos de adhesión de Markov son una extensión de las cadenas de Markov donde vamos a incorporar las acciones del agente. El agente, a través de las acciones, va a poder cambiar las probabilidades de transición de estado. Las acciones se toman de acuerdo a una política. La política es una función que le dice a la gente, dado un estado, qué acción le conviene tomar. Si el agente trata de maximizar una función de utilidad, se dice que este agente es un agente racional. En los problemas de adhesión secuenciales, existen varias formas de definir la política óptima. Una de ellas es considerar que el agente solo trata de maximizar la utilidad del estado siguiente. Esta se le conoce como política miope. Una segunda forma de definirlo es considerar una ventana de tiempo. Por ejemplo, consideremos no solo la utilidad de mañana, sino de pasada mañana, y así durante toda la semana. Una tercera forma es considerar todos los tiempos futuros. A esta política se le conoce como de horizonte infinito, y es la más fácil de tratar matemáticamente. Anteriormente, you utilizamos cadenas de Márkov para modelar procesos estocásticos. Ahora vamos a aumentar las cadenas de Márkov con una función que asigna a cada estado una utilidad. Observamos que la probabilidad de llegar a un estado al tiempo siguiente solo depende del estado en el que nos encontramos en el tiempo actual. Representamos la cadena de Markov con un grafo de transición de estados. Definimos una utilidad para cada estado posible. En nuestro ejemplo podría ser el consumo promedio por unidad de tiempo en cada uno de los vagones. Para el vagón comedor, 27. Para el bar, 10. En el dormitorio no hay consumo. En adelante usaremos la letra R en lugar de la letra U. La R significará recompensa. A la recompensa de un estado la denotamos como recompensa instantánea. Considerando que nos interese encontrar una política horizonte infinito, plantearemos una utilidad que integre el valor esperado de utilidad para todos los estados futuros. El valor de la recompensa en tiempos futuros se verá afectado por un factor de depreciación o descuento. Una recompensa vale más hoy que mañana, y vale más mañana que pasado mañana. Aún no tomamos en cuenta las acciones del agente, pero eso lo haremos más adelante. Recordemos que para una lotería podemos calcular su utilidad sumando los productos de las utilidades de las salidas con su probabilidad respectiva. Aquí podemos plantear la utilidad de un estado de la misma manera. Para obtener la utilidad de un estado S, sumamos los productos de la utilidad de cada estado S prima al que podemos llegar desde S con su respectiva probabilidad. Aquí el valor de utilidad V de S no será la recompensa instantánea, sino la utilidad horizonte infinito. La expresión para el valor horizonte infinito de utilidad nos lleva a una ecuación donde incorporamos tanto la recompensa instantánea como el valor esperado de utilidad para tiempos futuros. Aplicamos el factor de descuento gamma para las recompensas esperadas en tiempos futuros. Observamos que la expresión del término que corresponde con la utilidad de estados futuros puede expresarse como un producto matricial. El producto de la transpuesta en la matriz de probabilidades de transición T con el vector de utilidades horizonte infinito V de S. Aquí la matriz T es la matriz de probabilidades de transición de una cadena de Markov. Esta ecuación lineal puede resolverse invirtiendo una matriz. Ahora vamos a incorporar las acciones del agente en la ecuación. Tenemos un proceso estocástico donde el agente no puede anticipar el efecto de sus acciones. Sin embargo, el estado siguiente sí va a depender de la acción que tome el agente, y también del estado en el que se encuentra. De otra forma, cualquier política sería igualmente buena. Vamos a considerar que nuestro agente es racional, esto es que trata de maximizar el valor esperado de utilidad horizonte infinito. Dada esta consideración, el proceso de edición de Markov queda descrito por la ecuación de Bellman. Observemos que aparece un término no lineal máx, el cual modela el efecto de la acción racional del agente, aquí representada con la letra A. Adicionalmente, se observa que la probabilidad de transición no solo está condicionada al estado actual, sino también a la acción del agente. En la teoría de decisiones, si encadenamos nodos de decisión con loterías formando árboles de decisión, los procesos de edición de Markov pueden interpretarse de manera similar, pero dado que resultarían árboles infinitos con probabilidades de transición estacionarias, es mejor tratarlos como grafos de decisión. Aquí comenzamos con los estados, los que representamos con nodos de decisión. Por ejemplo, un pasajero se encuentra en el vagón comedor. Nuestro agente, es decir el tren inteligente, puede decidir entre un conjunto de acciones para tratar de cambiar la probabilidad de que el pasajero continúe o transite a otro vagón. Una acción posible es hacer un anuncio publicitario en el vagón. Esto no definirá la acción del pasajero, pero sí tendrá un efecto en la probabilidad de transición de estado. La transición la representamos con un nodo de lotería. La lotería definirá el estado siguiente. En este caso, podemos transitar a cualquiera de los vagones, quedarnos en el comedor, ir al dormitorio o al bar. Cada arista de la lotería tiene anotada la probabilidad de transición. Para no saturar la figura, solo ilustraremos la probabilidad de transitar al dormitorio. Observamos que esta probabilidad está condicionada a encontrarnos en el vagón comedor y que el tren haga el anuncio uno. También es posible que el tren no haga anuncio alguno. En este caso, tenemos otra lotería para transitar de estado. Así, para el estado B, tenemos acciones similares y las loterías respectivas, y para el estado D. La pregunta relevante que hacer es ¿cuál es la política óptima? Es decir, qué acción debe tomar el tren en cada vagón tal que maximice la utilidad horizonte infinito. De la ecuación de Bellman, podemos ver que la política óptima pi estrella de S se obtiene con la acción que maximiza el valor esperado de utilidad para cada estado. El problema de diseño del agente consiste en encontrar la política óptima. Para encontrar la política óptima tenemos que resolver la ecuación de Bellman. La ecuación de Bellman es una ecuación no lineal donde aparece un término no lineal el máximo o el término máx. Para resolver la ecuación de Bellman no podemos invertir una matriz. Tenemos que utilizar métodos numéricos. Existen varios métodos numéricos para resolverla. Uno de ellos es el algoritmo de iteración de valores. En el algoritmo de iteración de valores comenzamos con una asignación arbitraria para V de S e iteramos estos valores sobre la ecuación de Bellman hasta que estos convergen a los valores óptimos. Una vez que tenemos esta función V de S, encontramos la política óptima muy fácilmente. En el segundo algoritmo, en el algoritmo de iteración de políticas, no nos interesa encontrar el valor de la función V de S, sino que directamente tratamos de encontrar la política óptima. En el algoritmo de iteración de políticas se itera la política. Comenzamos con una política arbitraria. Dada esta política arbitraria, se encuentra el valor de la función V de S, y con este valor de V de S, se selecciona la siguiente política. Esto se repite hasta que la política no cambia. A continuación, presentamos un ejemplo del algoritmo de iteración de políticas. El algoritmo de iteración de políticas está basado en el hecho de que, dado una política conocida pi, el proceso de decisión de Márkov puede tratarse como una cadena de Márkov. Regresamos al ejemplo del tren. Ahora hemos anotado las aristas con duplas de probabilidades. Cada elemento de la tupla corresponde con una acción distinta. En el ejemplo, el primer elemento de la tupla corresponde con no anunciar. El segundo elemento corresponde con la opción anuncio. La política es una función. Para cada estado nos dice qué acción tomar. Esta función puede representarse como una lista de acciones. La posición de la acción es la misma que la del estado correspondiente. Podemos pensar en un arreglo T que tiene como entrada las tuplas. La política selecciona en cada tupla un elemento particular. En este caso, si la política para todo estado es no anunciar, entonces nuestra matriz de probabilidades de transición es la misma que en el ejemplo usado en el tema de cadenas de Markov. Encontraremos la utilidad horizonte infinito para cada estado. Obsérvese que en la ecuación de Bellman matricial, la matriz de transición de la cadena de Markov aparece de forma transpuesta. Sustituimos, obtenemos los valores horizonte infinito. En este paso, vamos a recalcular la política pi 1 de S. Para el estado D, encontraremos el estado que maximiza la utilidad. Así quedan las sumatorias. Sustituimos valores. Tomaremos la acción que da el valor máximo. En este caso, hacer el anuncio resulta en una mayor utilidad. Una utilidad de 103,81. Pi 1 queda definida como hacer el anuncio si se está en el dormitorio o el comedor, pero no hacerlo si se está en el bar. Observamos que pi 0 es diferente que pi 1, por lo que el algoritmo continuará iterando. Calculamos las probabilidades de transición para pi 1, y resolvemos el sistema de ecuaciones obteniendo los nuevos valores de utilidad horizonte infinito V 1 de S. Recalculamos la política óptima pi 2 observando que el algoritmo convergió. Y el algoritmo termina aquí. [MÚSICA]. [MÚSICA]. [MÚSICA].
