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