Aprendizaje por refuerzo: algoritmo Q Learning

Última modificación: 23 de Abril de 2017, y ha tenido 1966 vistas

Etiquetas utilizadas: agentes || algoritmos || aprendizaje automático || inteligencia artificial || machine learning || netlogo

Todos los seres vivos exhiben algún tipo de comportamiento, en el sentido que realizan alguna acción como respuesta a las señales que reciben del entorno en el que viven. Algunos de ellos, además, modifican su comportamiento a lo largo del tiempo, de forma que ante señales equivalentes se comportan de forma distinta con el paso del tiempo... en algunos de estos casos decimos que estos seres vivos han aprendido de su entorno (independientemente de si esa variación en la respuesta ha generado alguna ventaja o no en el individuo). De hecho, esta variación es la que aprovechamos cuando entrenamos un perro para que se siente cuando se lo pidamos.

Como ya hemos visto en entradas anteriores, el campo del aprendizaje automático estudia la generación de algoritmos que sean capaces de aprender de su entorno (en este caso, el entorno es el conjunto de datos que el algoritmo recibe en una etapa particular que se llama entrenamiento).

En esas entradas destacábamos dos tipos principales de aprendizaje automático: por una parte, el Aprendizaje Supervisado, y por otra el Aprendizaje no Supervisado. Sin embargo, junto a estos dos grandes tipos de aprendizaje, suele considerarse un tercer tipo que es conocido como Aprendizaje por Refuerzo, en el que el algoritmo de aprondizaje recibe algún tipo de valoración acerca de la idoneidad de la respuesta dada. Cuando la respuesta es correcta, el aprendizaje por refuerzo se parece al aprendizaje supervisado: en ambos casos el aprendiz recibe información acerca de lo que es apropiado. Sin embargo, amba aproximaciones difieren significativamente ante las respuestas erróneas, cuando el aprendiz responde de forma inadecuada. En este caso, el aprendizaje supervisado le dice exactamente al aprendiz qué debería haber respondido, mientras que el aprendizaje por refuerzo solo le informa acerca de que el comportamiento ha sido inapropiado y (normalmente) cuánto error se ha cometido. Esta aproximación, la del aprendizaje por refuerzo, es mucho más habitual en la naturaleza que el aprendizaje supervisado. En el ejemplo que comentábamos, cuando al perro le damos la orden de sentarse, si lo hace recibe algún tipo de recompensa (una galleta, o una caricia), y si no lo hace puede recibir algún tipo de castigo (si no somos muy salvajes con él, quizás una palabra de tono más elevado y que le incomoda). Repetir esta tarea con el perro produce un refuerzo de los comportamientos que reciben recompensa en detrimento de aquellos comportamientos que reciben castigo.

Aprendizaje por Refuerzo

Para simular el aprendizaje de sistemas biológicos reales necesitamos hacer algunas suposiciones que simplifican el comportamiento de nuestros agentes (o aprendices). Estas simplificaciones nos permitirán tener un sistema más flexible para proyectar diversas situaciones con el mismo sistema, y a la vez nos permitirá extraer conclusiones más generales acerca de las propiedades de los algoritmos que implementen estos sistemas de aprendizaje. En general, y como primera aproximación, supondremos que los aprendices siguen en su decisión un Proceso de Decisión de Markov , es decir:

• El agente percive un conjunto finito, S$S$, de estados distintos en su entorno, y dispone de un conjunto finito, A$A$, de acciones para interactuar con él.
• El tiempo avanza de forma discreta, y en cada instante de tiempo, t$t$, el agente percive un estado concreto, st$s_t$, selecciona una acción posible, at$a_t$, y la ejecuta, obteniendo un nuevo estado, st+1=at(st)$s_{t+1}=a_t(s_t)$.
• El entorno responde a la acción del agente por medio de una recompensa, o castigo, r(st,at)$r(s_t,a_t)$. Formalizaremos esta recompensa/castigo por medio de un número, de forma que cuanto mayor es, mayor es el beneficio.
• Tanto la recompensa como el estado siguiente obtenido no tienen porqué ser conocidos a priori por el agente, y dependen únicamente del estado actual y de la acción tomada. Es decir, antes de aprender, el agente no sabe qué pasará cuando toma una acción determinada en un estado particular. Precisamente, un buen aprendizaje es aquel que permite adelantarse al agente en las consecuencias de las acciones tomadas, reconociendo las acciones que sobre estados concretos le llevan a conseguir con más eficacia y mayores recompensas, sus objetivos.

El objetivo del aprendizaje por refuerzo es extraer qué acciones deben ser elegidas en los diferentes estados para maximizar la recompensa. En cierta forma, buscamos que el agente aprenda lo que se llama una política, que formalmente podemos verla como una aplicación que dice en cada estado qué acción tomar. Dividiremos la política del agente en dos componentes: por una parte, cómo de buena cree el agente que es una acción sobre un estado determinado y, por otra, cómo usa el agente lo que sabe para elegir una de las acciones posibles.

Hay varias formas de implementar estos procesos de aprendizaje. En esta entrada nos centraremos en lo que se conoce como Q learning, una forma de aprendizaje por refuerzo en la que el agente aprende a asignar valores de bondad a los pares (estado, acción).

Para diseñar un algoritmo que use estas ideas hemos de hacer una distinción entre lo que es verdad en el mundo, y lo que el agente cree que es verdad en el mundo:

Comencemos por lo que es verdad en el mundo. Si un agente está en un determinado estado y toma una acción concreta, estamos interesados en la recompensa inmediata que recibe, pero también en las recompensas futuras que se obtendrán por pasar a otros estados donde se pueden tomar otras acciones, que seguirán un política particular. En el algoritmo Q Learning, el valor Q de un par (estado, acción) contiene la suma de todas estas posibles recompensas. El problema es que esta suma podría ser infinita en caso de que no haya un estado terminal que alcanzar, además, es posible que no queramos dar el mismo peso a las recompensas inmediatas que a las recompensas futuras, en cuyo caso se hace uso de lo que se llama un refuerzo acumulado con descuento: las recompensas futuras quedan multiplicadas por un factor, γ∈[0,1]$\gamma \in [0,1]$, de forma que cuanto mayor sea este factor, más influencia tienen las recompensas futuras en el valor Q del par analizado.

Si el agente supiera a priori los valores Q de todos los posibles pares (estado, acción) podría usar esta información para seleccionar la acción adecuada para cada estado. El problema es que al principio el agente no tiene esta información, por lo que su primer objetivo es aproximar lo mejor posible esta asignación de valores Q. Como los valores de Q dependen tanto de recompensas futuras como de recompensas actuales, hemos de proporcionar un método que sea capaz de calcular el valor final a partir de los valores inmediatos y locales. Para ello:

• Si una acción en un estado determinado causa un resultado no deseado, hay que aprender a no aplicar esa acción en ese estado. Si una acción en un estado determinado causa un resultado sí deseado, hay que aprender a aplicar esa acción en ese estado.
• Si todas las acciones que se pueden tomar desde un estado determinado dan resultado negativo, es conveniente aprender a evitar ese estado. Es decir, no tomar acciones desde otros estados que nos lleven a él. Por contra, si cualquier acción en un determinado estado da un resultado positivo, se debe aprender que es conveniente llegar a él. Este hecho es lo que permite propagar la recompensa de un par (estado, acción) a los pares de los estados adyacentes.

Matemáticamente, podemos formalizar el cálculo de los valores Q por medio de la aiguiente ecuación:

\(Q(s_t,a_t)= r(s_t,a_t) + \gamma \max_{a_{t+1

http://www.cs.us.es/~fsancho/?e=109
https://advancedtech.wordpress.com/2008/08/08/aprendizaje-por-refuerzo/