Complementaria 9: MDP en Python

Complementaria 9: MDP en Python

#

En este tutorial nos concentramos en la implementación del modúlo de MDP de jmarkov en Python. Este modúlo permite encontrar la política óptima de un proceso de decisión markoviano (MDP) mediante dos posibles metódos de solución, iteración por valor o iteración de política.

Ejercicio MDP: héroes y villanos

Se abordará el problema 1 del archivo Complementaria 10 (Q).pdf que se encuentra en BloqueNeón. Modelaremos la situación como un proceso de decisión markoviano (MDP). Para esto, se deben definir los seis componentes principales del problema:

  1. Épocas de decisión.

  2. Variable de estado.

  3. Espacio de estados.

  4. Espacio decisiones.

  5. Probabilidades de transición,

  6. Recompensas inmediatas.

Definimos las épocas: \( E = \{1,2,..., \infty \} \rightarrow \text{cada ataque} \)

Definimos la variable de estado como: \( X_t = \text{Lugar donde atacaron los villanos en el t-1-ésimo ataque } t\\ \)

Definimos el espacio de estados: \( S_X = \{AC,AS\}\\ \) Donde AC significa que atacaron el centro y AS que atacaron los suburbios.

El espacio de decisiones: \( A(i) = \{C,S\} \) Donde C indica que los superhéroes se van al centro y S que se van a los suburbios.

Tendremos una matriz de transición para cada decisión.

\( P_{i \to j}^{(a = Suburbio)}= \begin{array}{c|cc} & \text{Centro}& \text{Suburbio} \\ \hline \text{Centro} & 0.5 & 0.5 \\ \text{Suburbio} & 0.6 & 0.4 \end{array} \\ P_{i \to j}^{(a = Centro)}= \begin{array}{c|cc} & \text{Centro}& \text{Suburbio} \\ \hline \text{Centro} & 0.3 & 0.7 \\ \text{Suburbio} & 0.8 & 0.2 \end{array} \)

Finalmente, definimos los retornos. Estos corresponden a las batallas ganadas. Notemos que se ganan las batallas cuando los villanos van al lugar que los superhéroes decidieron ir. Así, los retornos son:

\( r_{(AS,S)} = 0.4\\ r_{(AS,C)} = 0.8 \\ r_{(AC,C)} = 0.3 \\ r_{(AC,S)} = 0.5 \)

Para empezar con la implementación, llamamos las librerías necesarias.

import numpy as np
from jmarkov.mdp.dtmdp import dtmdp

Crearemos el espacio de estados en Python como un arreglo de numpy, de la siguiente manera:

estadosHeroes = np.array(['Centro','Suburbio'])
estadosHeroes

array(['Centro', 'Suburbio'], dtype='<U8')

Creamos el espacio de acciones.

accionesHeroes = np.array(['Ir al Centro','Ir al Suburbio'])
accionesHeroes

array(['Ir al Centro', 'Ir al Suburbio'], dtype='<U14')

Creamos las matrices de transición.

matricesHeroes = {}

for a in accionesHeroes:
    if a == 'Ir al Centro':
        matricesHeroes[a] = np.array([[0.5,0.5],
                                    [0.6,0.4]])
    elif a == 'Ir al Suburbio':
        matricesHeroes[a] = np.array([[0.3,0.7],
                                    [0.8,0.2]])

matricesHeroes

{'Ir al Centro': array([[0.5, 0.5],
        [0.6, 0.4]]),
 'Ir al Suburbio': array([[0.3, 0.7],
        [0.8, 0.2]])}

Creamos los retornos inmediatos.

retornosHeroes = np.array([[0.3,0.5],
                           [0.8,0.4]])
retornosHeroes

array([[0.3, 0.5],
       [0.8, 0.4]])

Creamos el problema como un MDP.

mdpHeroes = dtmdp(estadosHeroes, accionesHeroes, matricesHeroes, retornosHeroes, 0.9)

Finalmente, solucionamos.

El método solve de la librería recibe por parámetro: la tolerancia (GAP) de convergencia y el método de solución, que puede ser iteración por política o iteración por valor. Ambos métodos garantizan encontrar la solución óptima y llegar al mismo valor.

mdpHeroes.solve(0, method='policy_iteration')
value_functions, optimal_policy = mdpHeroes.solve(0, method='policy_iteration')

Notamos que el método solve nos devuelve dos resultados. El primero se refiere al valor que toma cada una de las funciones de valor; y el segundo corresponde a la política óptima. En este caso, siempre que se esté en el centro se debe decidir ir al suburbio y siempre que se esté en el suburbio se debe decidir ir al centro.

optimal_policy

{'Centro': 'Ir al Suburbio', 'Suburbio': 'Ir al Centro'}

# Valor esperado de la política óptima
mdpHeroes.expected_policy_value(value_functions,optimal_policy)

6.61538456433202

Adicionalmente, la librería nos permite conocer con un comando el valor esperado de la política óptima en el largo plazo y la matriz de probabilidades de transición de la política óptima.

# Matriz de transición de la política óptima
mdpHeroes.policy_transition_matrix(optimal_policy)

array([[0.3, 0.7],
       [0.6, 0.4]])
💡 Reto: Investiga como funciona la iteración por política y la iteración por valor. ¿En qué se parecen? ¿En qué se diferencian?

Ejercicio MDP: estudiantes de la Universidad de Los Alpes

Ahora intentemos modelar el segundo ejercicio propuesto. ¿Cuáles serían los componentes? ¿Cuántas matrices de probabilidades de transición tendríamos?

Resuelva el segundo ejercicio propuesto en el archivo Complementaria 10 (Q).pdf que se encuentra en BloqueNeón.

Clic aquí para ver la solución Podemos modelar el problema como un proceso de decisión en el tiempo con épocas infinitas. Así, el conjunto de las épocas está dado por:

\( E = \{1,2,\dots,\infty\} \rightarrow \text{cada semestre} \)

La variable de estados será \( X_{t} = \text{Clasificación de un estudiante en la época } t \) Su respectivo espacio de estados: \( S_{X} = \{ Excelente, Bueno, Promedio, Regular\} \)

Ya que un estudiante podrá decidir si asistir a clase (1), asistir a clase y realizar complementarias y tareas (2) y asistir a clase, realizar complementarias y tareas y leer el libro guía (3).

\( A(i) = \begin{cases} &\text{Asistir a Clase (1)}, \\ &\text{Asistir a Clase y Realizar Complementarias y Tareas (2)}, \\ &\text{Asistir a Clase, Realizar Complementarias y Tareas y Leer el Libro Guía} \end{cases} \)

Los retornos inmediatos están dados por la tabla 2. En este caso, agregaremos penalizaciones para los retornos infactibles.

\( r(i|a) = \begin{array}{|c|c|c|c|} \hline \text{Categoría/Acción}& \text{1} & \text{2} & \text{3} \\ \hline \text{E} & -1000 & 3 & 0 \\ \text{B} & 4 & 2 & -10 \\ \text{P} & 3 & -5 & -10 \\ \text{R} & -3 & -15 & -1000\\ \hline \end{array} \)

Las probabilidades de transición serán:

\( P_{i \to j} = \begin{array}{c|cccc} \text{a = 1} & \text{Excelente} & \text{Bueno} & \text{Regular} & \text{Promedio} \\ \hline \text{Excelente} & 0 & 0 & 0 & 0 \\ \text{Bueno} & 0.05 & 0.7 & 0.15 & 0.1 \\ \text{Promedio} & 0 & 0.2 & 0.5 & 0.3\\ \text{Regular} & 0 & 0 & 0.1 & 0.9 \\ \end{array} \)

\( P_{i \to j}= \begin{array}{c|cccc} \text{a = 2}& \text{Excelente} & \text{Bueno} & \text{Regular} & \text{Promedio} \\ \hline \text{Excelente} & 0.6 & 0.4 & 0 & 0 \\ \text{Bueno} & 0.25 & 0.6 & 0.1 & 0.05 \\ \text{Promedio} & 0.1 & 0.3 & 0.5 & 0.1\\ \text{Regular} & 0 & 0.05 & 0.25 & 0.7 \\ \end{array} \)

\( P_{i \to j}= \begin{array}{c|cccc} \text{a = 3}& \text{Excelente} & \text{Bueno} & \text{Regular} & \text{Promedio} \\ \hline \text{Excelente} & 0.9 & 0.1 & 0 & 0 \\ \text{Bueno} & 0.5 & 0.5 & 0 & 0 \\ \text{Promedio} & 0.2 & 0.3 & 0.5 & 0\\ \text{Regular} & 0 & 0 & 0 & 0 \\ \end{array} \)

Así, estamos listos para implementar.

Universidad de los Andes | Vigilada Mineducación. Reconocimiento como Universidad: Decreto 1297 del 30 de mayo de 1964. Reconocimiento personería jurídica: Resolución 28 del 23 de febrero de 1949 Minjusticia. Departamento de Ingeniería Industrial Carrera 1 Este No. 19 A 40 Bogotá, Colombia Tel. (57.1) 3324320 | (57.1) 3394949 Ext. 2880 /2881 http://industrial.uniandes.edu.co