Aprendizaje por Refuerzo: Aproximación de Función de Valor
En este capitulo aprenderemos como escalar RL hacia problemas en el mundo real y como resolverlos, es decir daremos un vistazo mas realista a como se aplican estos algoritmos en la época actual, e incluso veremos un algoritmo que hace poco fue el estado del arte.
Introducción
El aprendizaje por refuerzo puede ser usado para resolver problemas que suelen tener MDPs de gran cantidad de estados que resolver de otra manera sería virtualmente imposible, a continuación unos ejemplos:
- Backgammon posee una cantidad de 10²⁰ estados.
- Go posee una cantidad de 10¹⁷⁰ estados.
- Pilotear un helicóptero funciona en un espacio continuo de estados.
La primera pregunta con la cual nos podemos encontrar es ¿Cómo podemos escalar los métodos de predicción y control de modelo libre que hemos visto?
Bueno al intentar lograrlo nos trae ciertos problemas cómo:
- MDPs que tienen muchos estados y no pueden representarse en una tabla o en una base como lo hemos estado haciendo hasta el momento, debido a que la cantidad que ocuparían en memoria no sería eficiente.
- Cuando existen tantos estados resulta muy lento aprender cada uno de estos individualmente.
Hasta ahora hemos representado la función de valor en una tabla donde podíamos elegir que acción tomar, eso no nos permitiría crecer si es que estuviéramos lidiando con un ambiente que tenga incontables estados y acciones, por otro lado esto también representaría que necesitaríamos una cantidad muy grande de episodios para tener el valor de cada acción para cada estado, lo cual termina siendo inviable en tiempo y en almacenamiento.
Debido a eso buscamos que nuestra función de valor sea capaz de generalizar a través de todos los estados que pudiera encontrar en el ambiente en el que se encuentra, lo cual no nos asegura que el valor que se le asigne a una acción en un estado sea necesariamente el valor optimo, pero lo que si representa es una aproximación muy cercana. Para lograrlo nos basamos en una función de valor que se aproxime al valor real, la cual permita que los valores que se estimen para cada acción o estado sea lo mas parecido posible a la función de valor real e incluso pueda tener el cuenta el valor de estados que todavía no se han visitado.
Utilizando este principio podemos obtener diferentes tipos de aproximación de función de valor:
- En el primer ejemplo nos muestra como se puede obtener el valor de un estado, al introducirlo dentro de nuestro aproximador de función.
- En el segundo ejemplo se puede observar que al introducir un estado y que acción estaríamos dispuestos a tomar, la función nos retornaría que tanto valor nos daría tomar dicha acción.
- En el último caso, dado el estado donde nos encontramos podríamos determinar el valor para cada una de las acciones que podemos tomar desde dicho estado.
Dado que estamos buscando como aproximar nuestra función puede existir muchas alternativas, entre ellas las mas usadas son:
- Combinación lineal de Features.
- Red Neuronal.
- Arboles de decisión, etc.
¿Si hay tantas opciones entonces cual deberíamos elegir? En este caso debemos centrarnos en aproximadores de función que sean diferenciables ya que conocemos hacia donde se va a dirigir la gradiente de nuestra función debido a que tenemos la recompensa real de cada acción para cada estado (que es lo que se experimenta en cada episodio).
Métodos incrementales
Revisaremos algunos métodos para actualizar incrementalmente nuestra función de valor, antes de esto, por motivos de practicidad vamos a considerar que tenemos el valor real de la función de valor y queremos llegar a aprenderla con alguno de los métodos presentados a continuación.
Aproximación de Función de Valor con Stochastic Gradient Descent
Gradient Descent busca minimizar el MSE sobre el valor que se aproxima en la función y el valor verdadero.
La gradiente de J(w) se define como:
Para encontrar el mínimo local de J(w) se debe ajustar en dirección de la gradiente:
Donde α representa con que magnitud nos moveremos en dicha dirección. Para esto tomaremos una muestra aleatoria sobre una acción dado que nos encontramos en un estado, y la compararemos con el valor verdadero, utilizaremos gradient descent para decidir en que dirección y con que magnitud vamos a corregir nuestro error, entonces con esto logramos acercarnos cada ves mas a la función verdadera basado en los resultados que tenemos al interactuar directamente con el ambiente.
Aproximación de Función de Valor Lineal
Un método para aproximar la función de valor es el lineal, está basado en una representación del estado donde nos encontramos, esto se puede realizar por medio de un Vector de Características (Feature Vector) el cual podría estar representado por la configuración actual de un tablero de ajedrez, las tendencias en el mercado de valores, etc. Esta representación termina siendo fundamental debido a que si captura correctamente el ambiente en el que se encuentra hará el problema mucho mas fácil de resolver.
¿Cómo podemos utilizar ese vector de características? La forma mas práctica es formando una combinación lineal de cada uno de sus valores, esto nos permitirá estimar el valor para cada caso utilizando la suma ponderada de cada una de las características que recibirá nuestra función.
Para actualizar nuestros pesos se seguiría la siguiente regla, básicamente veremos que tanto se asemeja nuestra resultado a la realidad y nos moveremos ligeramente con magnitud de α hacia esa dirección:
Algoritmos de predicción incremental
Hasta ahora se ha asumido que tenemos la capacidad de ver la verdadera función de valor, como una especie de “oráculo”, pero esto no ocurre en la realidad. En la practica podemos encontrar valores que nos permiten estimar la función directamente desde la experiencia que obtenemos en el ambiente y veremos que las técnicas que hemos venido leyendo también pueden funcionar para este caso.
MonteCarlo
Como podemos observar se va a remplazar el valor “correcto” que poseíamos antes por el retorno total de un episodio, esto funcionará como un objetivo un poco ruidoso, que lentamente, dado que cada actualización se dará al fin de un episodio, nos llevará a la verdadera función de valor.
En pocas palabras utilizaremos la información de cada episodio como datos de entrenamiento, como si fuera entrenamiento supervisado
TD(0):
TD(λ):
Para el caso de TD estimará un valor sesgado, esto se da por que se le pide a la propia función que estime cual será la recompensa total que recibiremos hasta el final de la trayectoria, eso nos puede generar un error de lo que nuestra función creía era correcto y lo que realmente pasa en el ambiente, esto puede traer consecuencias negativas, como que no necesariamente converja en la función de valor real.
Control con Aproximación de Valor
Esta vez como control utilizaremos una evaluación de política se basará en utilizar el aproximador de función de valor que diseñamos y la cual nos ayudará a encontrar, luego de algunas iteraciones la función de valor más indicada dado los parámetros que ingresamos. En pocas palabras utilizaremos el mismo concepto que hemos revisado en este post, con al excepción que en ves de centrarnos en V(s) nos centraremos en Q(s,a), pero utilizaremos exactamente los mismos conceptos que revisamos con MonteCarlo y TD.
Metodos de Batch
Hasta ahora hemos visto métodos para actualizar nuestra función de valor luego de cada experiencia, pero esto no termina siendo eficiente debido a que al actualizar nuestra función con la experiencia que acaba de desarrollar nuestro agente la solemos desechar y continuar con una siguiente interacción con el ambiente, esto genera que el uso de los datos no sea eficiente, ya que cada experiencia solo se termina usando una vez y no permite que el agente encuentre realmente la mejor función de valor para todos los episodios, en este caso un Batch representaría a un conjunto de experiencias del agente.
Predicción basada en mínimos cuadrados
Podemos definir nuestros datos de entrenamiento de la misma manera que lo hemos hecho, es decir un par entre estado y valor y mejoraremos los valores de nuestra función al reducir la suma del error cuadrático[poner link] entre lo que predice nuestra función y (para ejemplos prácticos) la función de valor verdadera, dicha función puede ser remplazada por el valor que obtenemos siguiendo monte carlo o td. La función de mínimos cuadrados se define con la siguiente formula.
Experience Replay
Para hacer un uso correcto de las muestras que obtendremos en la interacción con el ambiente utilizaremos la técnica llamada experience replay, la cual consiste en cada cada interacción que se de con el ambiente y recompensa que nos otorgue quedará registrada dentro de una estructura de datos, luego se elegirá aleatoriamente un número de “experiencias” las cuales utilizaremos para entrenar nuestro algoritmo, de esta manera se puede romper la correlación entre los datos y generar una función mucho mas estable. Se entrenará el algoritmo una y otra vez hasta que se llegue al mínimo global, reduciendo el error mínimo cuadrático.
Implementación
A continuación comparto una implementación de aproximación de valor utilizando una red neuronal, el código tambien se puede encontrar aquí.
Gracias por haberme seguido hasta aquí, si tienes alguna duda (o algo en lo que crees que podría mejorar) no dudes en hablarme.
