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:

Actividad 3 –Q-Learning (Sarsa)/LMS

Diego García M. 1162205
Joaquín León M. 1162101
Enrique Peña A. 1162110

Instituto Tecnológico de Estudios Superiores Monterrey
Aprendizaje Automático

Actividad de programación 3 –Q-Learning (Sarsa)

a. Breve descripción del medio ambiente.
Es una pista de velocidad donde se simula una carrera de 100 metros. El agente puede controlar los movimientos del corredor de la cintura para abajo. Al coordinar de manera correcta los movimientos de los muslos y las pantorrillas se realiza un desplazamiento similar al de una persona mientras corre.
Ambiente desarrollado en C++ utilizando la librería de física Box2D.

b. Descripción detallada de la actividad o acción que va a aprender tu agente.
El agente va a aprender a correr sobre la pista. Al realizar los movimientos correctos que tiene a su disposición debe de lograr un movimiento similar a correr o al menos debe de aprender a desplazarse hacia adelante utilizando sus movimientos.

c. Solución planteada al problema utilizando el Algoritmos Q-Learning Sarsa. Describe con detalle cada elemento del planteamiento:

I. Selección de la experiencia de aprendizaje
Feedback: Indirecto, al realizar una acción, el agente recibe una recompensa con base en la distancia avanzada.
La selección de acciones la realiza el agente basándose en su tabla Q.
Todos los entrenamientos siguen la misma distribución que los ejemplos futuros.

II. Selección de las recompensas
Cada que el agente realiza una acción es recompensado inmediatamente con un número que representa la distancia que avanzó al realizar dicha acción.

III. Posibles acciones del agente en el medio
Mover sus muslos alternado con el hombro del otro lado del cuerpo.

Esperar.

IV. Estados posibles que puede sensar tu agente en el medio (descripción de los estados).
Nuestro agente no puede sensar muchas cosas de su ambiente más que la posición en la que se encuentra.
Los estados posibles se refieren más a las teclas que apretaría o no apretaría un usuario en el juego de QWOP. Esto es: Q apretada, W apretada, nada apretado.

V. Descripción de la estrategia de exploración/explotación para el aprendizaje.
La estrategia que usamos para balancear la exploración y la explotación del ambiente es una variable llamada temperatura (tomado del algoritmo “Simulated Annealing”). Ésta empieza con un valor alto lo cual hace poco probable que el algoritmo se vaya por la mejor opción. Conforme pasa el tiempo, la temperatura va bajando, obligando al algoritmo a elegir las mejores acciones.

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.
Estado 1: S (sleep) Posibles acciones: continuar en S, apretar Q, apretar W. La recompensa es igual a la cantidad avanzada por el agente al realizar la acción.
Estado 2: Q. Posibles acciones: continuar en Q, pasar a S, apretar W. La recompensa es igual a la cantidad avanzada por el agente al realizar la acción.
Estado 3: W. Posibles acciones: continuar en W, apretar Q, pasar a S. La recompensa es igual a la cantidad avanzada por el agente al realizar la acción.

VII. Explicar cuándo es que tu agente va aprendiendo y cuándo utiliza lo aprendido para tomar decisiones en el medio.
El agente empieza a aprender de una manera más eficaz en cuanto encuentra (random) una combinación de acciones que lo llevan a avanzar una distancia considerable. Esto hace que se de cuenta que esta combinación es favorable y la siga aplicando.
La diferencia entre Q-Learning y Sarsa es que en Q-Learning a la hora de actualizar la tabla se toma en cuenta el máximo valor de las posibles acciones del estado siguiente, sin tomar en cuenta la política que se está usando para escoger acciones. En Sarsa se usa la política para escoger la acción siguiente y esta misma acción es la que se toma en cuenta a la hora de actualizar el valor de la acción realizada actualmente en la tabla.

d. Conclusiones después de la programación.
En nuestro caso, la gran mayoría del tiempo lo invertimos en programar y adaptar el medio ambiente. Debido a que ninguno de nosotros estaba familiarizado con Box2D, nos costó tiempo y esfuerzo hacerlo. Una vez programado el medio ambiente procedimos a simular una elección de acciones para ver si se llevaban a cabo. La última parte fue implementar Q-Learning y Sarsa.

Nuestras conclusiones en cuanto a Q-Learning y Sarsa, además de lo ya planteado en el punto anterior es que, en el caso de QWOP, no hay tanta diferencia a la hora de comparar las corridas, al menos que se note. Es obvio que los valores de la tabla cambian de manera diferente. En Q-Learning, si tenemos algún valor grande en alguna posición, es bastante probable que los valores aledaños empiecen a crecer junto con este. En Sarsa, el crecimiento no es tan directo ya que no se escoge siempre el valor más alto, sino el que se escogió previamente de acuerdo a la estrategia. (La cual por cierto es algo similar a E-Greedy)

Actividad de programación 3 - LMS

a. Breve descripción del medio ambiente.
Es una pista de velocidad donde se simula una carrera de 100 metros. El agente puede controlar los movimientos del corredor de la cintura para abajo. Al coordinar de manera correcta los movimientos de los muslos y las pantorrillas se realiza un desplazamiento similar al de una persona mientras corre.
Ambiente desarrollado en C++ utilizando la librería de física Box2D.

b. Descripción detallada de la actividad o acción que va a aprender tu agente.
El agente va a aprender a correr sobre la pista. Al realizar los movimientos correctos que tiene a su disposición debe de lograr un movimiento similar a correr o al menos debe de aprender a desplazarse hacia adelante utilizando sus movimientos.

c. Solución planteada al problema utilizando el Algoritmo LMS. Describe con detalle cada elemento del planteamiento:

I. Selección de la experiencia de aprendizaje
Feedback: Indirecto, al realizar una acción, el agente recibe una recompensa con base en la distancia avanzada y la pendiente de su tronco. Todos los entrenamientos siguen la misma distribución que los ejemplos futuros.

II. Función objetivo
V : B -> |R

V(b) = 100000 si la distancia recorrida es 100

V(b) = 1 si se cayó

V(b) = n, donde n > 1 y <>

III. Selección de la representación de la función objetivo
Mover sus muslos alternado con el hombro del otro lado del cuerpo. Mover sus brazos y pantorrillas.

Esperar. V(b) = w0+(w1*x1)+(w2*x2)

Dónde x1 = la distancia recorrida

x2 = 10 si la pendiente es mayor que .7 y menor que 50

0 de lo contrario

IV. Selección del algoritmo de aproximación

i. Los valores iniciales de W1 y W2, pueden ser cuales quiera ya que el problema de que se llega a un estado final en el primer cálculo de estados, no causa un cambio.

d. Conclusiones después de la programación.
Nuestra implementación de LMS funciona en cuanto al logaritmo como tal, es decir, se hace la corrida, se termina el episodio, se actualizan los pesos y se repite otra vez. El problema es que esta corrida es (ridículamente) corta ya que el personaje es muy frágil y se cae muy fácilmente lo cual ocasiona un problema más o menos grave: desde la primera iteración de la corrida se llega a un estado final que es la caída. Esto ocasiona que se termine el episodio y se actualicen los pesos pero de tal manera que nunca aprende a avanzar.

En resumen, el algoritmo está bien hecho y “funciona” pero el problema en este caso es el ambiente que no lo deja evolucionar correctamente.

Actividad 3, Q-Learning y Sarsa

Medio Ambiente

Planet Wars, juego basado en Galcon. El juego tiene un mapa que contiene varios planetas, cada uno con un escuadrón de naves. Los planetas pueden pertenecer a uno de tres propietarios diferentes: al jugador 1, al enemigo o neutral. El juego tiene un cierto número máximo de vueltas y el juego puede terminar antes si uno de los jugadores pierde todas sus naves. Si ambos jugadores tiene el mismo número de naves cuando el juego termina, es un empate.

Actividad que el Agente Aprenderá: Maximizar su eficiencia de juego por medio de la creación de una estrategia de juego.

Algoritmo Q-leaning

Experiencia de Aprendizaje: Como experiencia de aprendizaje se eligió que el agente jugara contra un bot o si mismo.

Selección de Recompensas: La recompensa de una acción es dada por la siguiente función que regresa un valor evaluando el número de naves que tiene el agente, la distancia al objetivo, el número de enemigos en el objetivo, la tasa de crecimiento del objetivo y el tamaño del objetivo.

Acciones Posibles del Agente: Mover tropas a planeta pequeño, lejos y denso; mover tropas a planeta pequeño, largo y no denso; mover tropas a planeta pequeño, cerca y denso; mover tropas a planeta pequeño, cerca y no denso; mover tropas a planeta grande, lejos y denso; mover tropas a planeta grande, lejos y no denso; mover tropas a planeta grande, cerca y denso; mover tropas a planeta grande, cerca y no denso; Esperar.

Estados Posibles del Agente: El agente tiene los siguientes estados: Atacar y Expandir.

Estrategia de Exploración/explotación: Al inicio el agente se dedica únicamente a la exploración del medio, la cual consiste en recorrer todos sus estados y las acciones posibles que puede tomar en cada estado; una vez llena la tabla, se tomara la acción apropiada dependiendo de la recompensa de la misma.

Ejemplos del Estados

· Estado: Atacar

§ Acciones Posibles: Mover tropas a planeta pequeño, lejos y denso; mover tropas a planeta pequeño, largo y no denso; mover tropas a planeta pequeño, cerca y denso; mover tropas a planeta pequeño, cerca y no denso; mover tropas a planeta grande, lejos y denso; mover tropas a planeta grande, lejos y no denso; mover tropas a planeta grande, cerca y denso; mover tropas a planeta grande, cerca y no denso: Esperar

§ Nota: Las acciones del estado “Atacar” aplican solo para planetas ocupados por el enemigo

· Estado: Expandir

§ Acciones Posibles: Mover tropas a planeta pequeño, lejos y denso; mover tropas a planeta pequeño, largo y no denso; mover tropas a planeta pequeño, cerca y denso; mover tropas a planeta pequeño, cerca y no denso; mover tropas a planeta grande, lejos y denso; mover tropas a planeta grande, lejos y no denso; mover tropas a planeta grande, cerca y denso; mover tropas a planeta grande, cerca y no denso; Esperar

§ Nota: Las acciones del estado “Expandir” aplican solo para planetas neutrales.

Aprendizaje del Agente: Se aprende después de cada turno, utiliza los valores generados por la función para generar nuevas recompensas y por ende nuevas estrategias.

Algoritmo SARSA

La información relacionada con el algoritmo SARSA es la misma, lo único que cambia es la forma en la que el agente va aprendiendo.

Aprendizaje del Agente: A diferencia de Q.Learning normal, la implementación de SARSA aprende al final de cada partida, una vez que se cumple el ciclo de exploración y de explotación.

Conclusiones

Después de trabajar en la implementación de Q-Learning y Sarsa hemos llegado a la conclusión de que ninguno de los dos es adecuado a nuestro medio debido a que el medio cambia muy rápidamente, ya que cada partida será distinta por lo que el algoritmo no podría adaptarse de forma adecuada; los dos algoritmos serian adecuados si el medio fuera constante en todas las partidas, y los oponentes siguieran siempre el mismo patrón de ataque expansión.

Actividad Programación 3 Algoritmo Q-Learning Sarsa

Breve descripción del medio ambiente.

El medio ambiente es un campo de batalla limitado y de forma hexagonal con dos jugadores que pueden disparar y cuyo objetivo es matar al contrincante.

Descripción detallada de la actividad o acción que va a aprender tu agente.
Aprende a matar al contrincante

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

Describe con detalle cada elemento del planteamiento:

Selección de la experiencia de aprendizaje

Se iba a premiar al agente por cada vez que este dañara o matara al enemigo, cuando lo detectaba y castigar cuando moría.

Selección de las recompensas.

Cuando la acción es quedarse en el ángulo en el que se encuentran la recompensa es 1.

Cuando cambian de ángulo la recompensa es -0.5 y cuando disparan la recompensa depende de si matan al contrincante, lo hieren, son heridos o mueren, obteniendo respectivamente 2,0.5,-0.5,-2.

Posibles acciones de tu agente en el medio.

Girar, disparar, moverse.

Estados posibles que puede sensar tu agente en el medio (descripción de los estados).

Cada uno de los 8 cuadrantes que puede ver más un estado sin actividad.

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

Lo ideal sería que se seleccionara de forma aleatoria algún estado del agente para poder poblar la tabla q y luego se pasara a explotación. Aquí fue donde surgió uno de los problemas, en lo que se le iba a enseñar era muy difícil definir un estado de terminación. Podría estar explorando varios caminos pero realmente no iba a funcionar uno del todo ya que el contrincante no se iba a mover de la misma forma siempre. Por lo cual la exploración realmente no acababa y tenía que darse siempre en cada iteración.

Al principio hay bastante exploración pero conforme aumenta el tiempo la explotación aumenta.

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.

Moviéndose a la derecha:

Puede: detenerse, disparar, moverse en ocho direcciones (8 acciones)

La recompensa depende del estado al que llega y algunas dependen de que hizo. Si dispara, se le debe de premiar solo si hiere, si gasta una bala y no le da a nadie se le castiga.

Quieto

Puede: disparar en 8 direcciones, disparar y moverse. La recompensa depende de si hiere o no a alguien, si se mueve se le premia con una pequeña cantidad

Moverse arriba del mismo

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

No llega a aprender ya que el ambiente siempre está cambiando.

Conclusiones después de la programación. Aquí debes de hacer una comparación e
interpretación de las corridas utilizando Q-Learning y Sarsa.

Q-learning es una técnica muy útil cuando se trata de ambientes no tan cambiantes, ya que las decisiones que tomas son repetir algo. Si el ambiente cambia hay que correr el q-learning de nuevo para cuando hay cosas nuevas y que las detecte. En nuestro caso q-learning no sirvió ya que ambos agentes lo trataron de usar y a aprender algo. El problema de que los estados "finales" dependían de otros agentes y no de ellos no permitió que se estableciera una buena representación en fsm y que cada cosa aprendida en la tala tenga que borrarse ya que solo serviría si el enemigo hacia lo mismo siempre. Por ejemplo si mataba a alguien mientras iba por la derecha quería siempre disparar a la derecha pro el enemigo podría aparecer ahora por la izquierda y cuando eso pasara luego diría que ala izquierda. El problema es que convergiría ej algo probablemente no serviría más.