Actividad 3: Q-Learning y Sarsa

EQUIPO 7:

Martha Hernández
Alfonso Martínez
Angel Daza

Breve descripción del medio ambiente

Nuestro medio ambiente es un patio de una escuela simulada, en donde nuestro agente principal será un niño de esa escuela. En ese ambiente se transmiten mensajes o chismes entre los alumnos. El problema es que estos chismes no siempre son transmitidos de manera fiel por lo que es necesario aprender a rastrearlos para saber quién ha dicho el chisme.

Descripción detallada de la actividad o acción que va a aprender el agente

En esta actividad nuestro objetivo es que el agente, utilizando los algoritmos Q-Learning y Sarsa, aprenda a rastrear el chisme que se ha propagado entre todos los alumnos. En primer lugar aparecen los niños en posición aleatoria, nuestro agente y finalmente hay uno solo que tiene un chisme. Ese niño chismoso comienza a caminar por el paisaje y conforme se va encontrando niños les transmite el chisme. Estos niños portadores del chisme, a su vez, lo transmiten a los niños que se encuentran en su camino, el problema es que el chisme ya ha sido modificado por cada uno de los transmisores. El objetivo de la primera etapa es que todos los niños posean información, ya sea falsa o verdadera, del chisme. La siguiente etapa comienza con nuestro agente investigando sobre ese chisme que fue propagado, y es en esta etapa donde utilizamos el Q-Learning y Sarsa.

Solución planteada al problema utilizando el Algoritmo Q-Learning y el Algoritmo Sarsa

i. Selección de la experiencia de aprendizaje

Las instancias del problema se generarán de manera aleatoria por la computadora.

ii. Selección de las recompensas

Gracias a lo aprendido en la actividad anterior, decidimos que se le daría una recompensa, aun cuando ésta sea mínima, por realizar acciones que le acerquen a encontrar el origen de la siguiente manera:

· Preguntar a otros niños 10 puntos

· Explorar el mundo 1 puntos

· Encontrar el origen 100 puntos – este es un estado final.

iii. Posibles acciones del agente en el medio

· Caminar: implica moverse por el mundo hasta encontrar a quien preguntarle.

o Puede caminar hacia arriba, hacia abajo, hacia la derecha y hacia la izquierda, nunca en diagonales.

· Preguntar: implica obtener una versión del chisme y su respectiva procedencia.

iv. Estados posibles que puede sensar tu agente en el medio

Un estado se compone de tres variables, que a su vez se componen de otros elementos más pequeños:

· Chisme:

o mensaje: un arreglo de 3 enteros, con el chisme que se pasan los niños.

o xFuente: la x del niño que contó el chisme. Pueden ser falsas.

o yFuente: la y del niño que contó el chisme. Puede ser un dato falso.

o fuente: el niño que contó el chisme. Sus x y y no son visibles.

· Vision: Un arreglo de 3x3 enteros, donde -1 representa el borde del mundo, 0 un lugar a donde se puede caminar y un número mayor a 0 a un agente.

· nPersonas: el número de personas a las que se les ha preguntado.

v. Descripción de la estrategia de exploración/explotación para el aprendizaje.

· Al inicio de la corrida, el agente se enfocará en la exploración del mundo, ya que tiene que recopilar información suficiente para llegar al origen. En situaciones posteriores podría ir explotando sus conocimientos para llegar de manera más rápida al origen ya que tendría una idea general de lo que le dicen los niños.

vi. Ejemplo de tres estados distintos del medio ambiente, con las respectivas acciones que pueden ser realizadas desde dicho estado y las recompensas que se le otorgan al agente al tomar las acciones.

1. Chisme = null; visión = [0,0,0,0,99,0,0,0,0]; 0; El agente aún no se ha enterado del chisme, y no le ha preguntado a ninguna persona. Puede caminar en cualquier dirección, y su recompensa será el cambio en la distancia que tiene desde su posición hasta las x y y que cree que conoce del niño chismoso.

2. Chisme = {[0,0,0], 5, 6, Nino 7}; visión = [0,2,0,7,99,0,0,8,0]; 6; El agente y se enteró del chisme, tiene arriba y al lado izquierdo a dos personas, y le ha preguntado a 6 personas. Puede caminar a la derecha y abajo, así como preguntarle a las personas que tiene al lado si no lo ha hecho. La recompensa de preguntar es 10, y la de caminar es igual que en el número anterior.

3. Chisme = {[0,2,3], 6, 8, Nino 10}; visión = {-1,-1,-1, -1,99,0,0,0,0}, 3; El agente ya tiene una versión del chisme, tiene una visión limitada porque está en la esquina superior izquierda del mundo, y le ha preguntado a tres personas. Solo puede caminar hacia la derecha y hacia abajo, y la recompensa es el cambio en la distancia hacias las x y las y donde cree que está el niño chismoso. No puede preguntar porque no tiene a nadie cerca.

vii. Explicar cuándo es que tu agente va aprendiendo y cuándo utiliza lo aprendido para tomar decisiones en el medio.

Corremos nuestro programa durante varios episodios. La tabla Q del agente se conserva durante los episodios para que así aprenda a través de todas las iteraciones. Lo que aprende es cuál es la mejor decisión que puede tomar en su estado actual, es decir, si es preferible caminar hacia arriba/abajo/derecha/izquierda, preguntarle a un niño chismoso que este cerca. Generalmente, dadas las recompensas preferirá preguntar a un niño cercano, sin embargo, a través de las iteraciones puede aprender a caminar más directamente hacia el origen que preguntar a un niño aunque esté cerca.

Al iniciar cada episodio se utiliza todo lo que se aprendió en los anteriores con el afán de mejorar su desempeño, sin embargo el aprendizaje es algo lento debido a la diversidad de estados que tenemos.

Conclusiones Aquí debes de hacer una comparación e interpretación de las corridas utilizando Q-Learning y Sarsa:

Al comparar ambos algoritmos no logramos ver una diferencia considerable en el aprendizaje del agente. Ambos métodos son algo tardados pues la tabla de aprendizaje es muy grande y también es difícil que el agente vuelva a encontrarse en el mismo estado. Se supone que el chisme se propaga al principio y el agente arranca desde un sitio y se dedica a preguntar, al terminar el episodio actualiza su tabla Q y para el siguiente episodio vuelve a comenzar utilizando la tabla Q actualizada, pero no se nota mucho el aprendizaje a través de los episodios tanto en Q-Learning como en Sarsa por los motivos que ya dijimos.

NUESTRO VIDEO: