Serie sobre Aprendizaje por Refuerzo (RL), siguiendo el famoso libro de Sutton y Barto “Aprendizaje por Refuerzo” [1].
En las publicaciones anteriores terminamos de analizar la Parte I de dicho libro, que presenta técnicas de solución fundamentales que forman la base de muchos métodos de RL. Estos son: Programación Dinámica (DP), métodos Monte Carlo (MC) y Aprendizaje por Diferencia Temporal (TD). Lo que separa la Parte I de la Parte II del libro de Sutton, y justifica la distinción, es una restricción en el tamaño del problema: mientras que en la Parte I se cubrieron métodos de solución tabular, ahora nos atrevemos a profundizar en estos fascinantes temas e incluir la aproximación de funciones.
Para hacerlo específico, en la Parte I asumimos que el espacio de estados de los problemas bajo investigación era lo suficientemente pequeño como para poder representarlo y también las soluciones encontradas a través de una tabla simple (imagine una tabla que denota una cierta “bondad” – un valor – para cada estado). Ahora, en la Parte II, abandonamos este supuesto y, por lo tanto, podemos abordar problemas arbitrarios.
Y esta configuración modificada es muy necesaria, como pudimos observar de primera mano: en una publicación anterior logramos aprender a jugar Tic Tac Toe, pero ya fallamos en Connect Four, ya que el número de estados aquí es del orden de 10²⁰. O considere un problema de RL que aprende una tarea basada en imágenes de cámara: la cantidad de imágenes de cámara posibles es mayor que la cantidad de átomos en el universo conocido. [1].
Estos números deberían convencer a todos de que los métodos de solución aproximados son absolutamente necesarios. Además de permitir abordar estos problemas, también ofrecen generalización: para los métodos tabulares, dos estados cercanos, pero aún diferentes, se trataron completamente por separado, mientras que para los métodos de solución aproximada, esperaríamos que nuestra aproximación de función pueda detectar estados tan cercanos y generalizar.
Con eso, comencemos. En los próximos párrafos, haremos:
dar una introducción a la aproximación de funciones producir métodos de solución para este tipo de problemas discutir diferentes opciones para funciones de aproximación.
Introducción a la aproximación de funciones
A diferencia de los métodos de solución tabular, para los cuales usamos una tabla para representar, por ejemplo, funciones de valor, ahora usamos una función parametrizada.
con un vector de peso
v puede ser cualquier cosa, como una función lineal de los valores de entrada o una red neuronal profunda. Más adelante en esta publicación discutiremos diferentes posibilidades en detalle.
Por lo general, el número de ponderaciones es mucho menor que el número de estados, lo que produce una generalización: cuando actualizamos nuestra función ajustando algunas ponderaciones, no actualizamos solo una sola entrada en una tabla, sino que esto también tendrá un efecto en (posiblemente) todas las demás estimaciones.
Recapitulemos las reglas de actualización de algunos de los métodos que vimos en publicaciones anteriores.
Los métodos MC asignan el rendimiento observado G como valor estimado para un estado:
TD(0) arranca la estimación del valor del siguiente estado:
Mientras que DP usa:
De ahora en adelante, interpretaremos las actualizaciones de la forma s -> u como pares de entrada/salida de una función que nos gustaría aproximar, y para ello utilizaremos técnicas de aprendizaje automático, en particular: aprendizaje supervisado. Las tareas en las que es necesario estimar números (u) se conocen como aproximación de funciones o regresión.
Para solucionar este problema, en teoría podemos recurrir a cualquier método posible para dicha tarea. Discutiremos esto más adelante, pero debemos mencionar que existen ciertos requisitos para dichos métodos: por un lado, deben poder manejar cambios incrementales y conjuntos de datos, ya que en RL generalmente acumulamos experiencia con el tiempo, lo que difiere, por ejemplo, de las tareas clásicas de aprendizaje supervisado. Además, el método elegido debería poder manejar objetivos no estacionarios, lo cual discutiremos en la siguiente subsección.
El objetivo de la predicción
A lo largo de la Parte I del libro de Sutton, nunca necesitábamos un objetivo de predicción o similar; después de todo, siempre podíamos converger a la función óptima que describía perfectamente el valor de cada estado. Por las razones expuestas anteriormente, esto ya no es posible, lo que requiere que definamos un objetivo, una función de costos, que queremos optimizar.
Usamos lo siguiente:
Intentemos entender esto. Esta es una expectativa sobre la diferencia entre los valores predichos y reales, que intuitivamente tiene sentido y es común en el aprendizaje supervisado. Tenga en cuenta que esto requiere que definamos una distribución µ, que especifica cuánto nos preocupamos por ciertos estados.
A menudo, esto es simplemente una medida proporcional a la frecuencia con la que se visitan los estados: la distribución de políticas, en la que nos centraremos en esta sección.
Sin embargo, tenga en cuenta que en realidad no está claro si este es el objetivo correcto: en RL, nos preocupamos por encontrar buenas políticas. Algún método nuestro podría optimizar extremadamente bien el objetivo anterior, pero aun así no lograría resolver el problema en cuestión (por ejemplo, cuando la política pasa demasiado tiempo en estados no deseados). Aún así, como se mencionó, necesitamos uno de esos objetivos y, debido a la falta de otras posibilidades, simplemente lo optimizamos.
A continuación, introduzcamos un método para minimizar este objetivo.
Minimizar el objetivo de predicción
La herramienta que elegimos para esta tarea es el Descenso de gradiente estocástico (SGD). A diferencia de Sutton, no quiero entrar en demasiados detalles aquí y centrarme únicamente en la parte de RL, por lo que me gustaría remitir al lector interesado a [1] o cualquier otro tutorial sobre SGD/aprendizaje profundo.
Pero, en principio, SGD utiliza lotes (o mini lotes) para calcular el gradiente del objetivo y actualizar los pesos un pequeño paso en la dirección de minimizar este objetivo.
Por tanto, este gradiente es:
Ahora la parte interesante: supongamos que v_π no es el verdadero objetivo, sino alguna (ruidosa) aproximación del mismo, digamos U_t:
Podemos demostrar que si U_t es insesgado de v_π, entonces la solución obtenida mediante SGD converge a un óptimo local: conveniente. Ahora podemos simplemente usar, por ejemplo, el retorno de MC como U_t y obtener nuestro primer método RL de gradiente:
También es posible utilizar otras medidas para U_t, en particular utilizar también el bootstrapping, es decir, utilizar estimaciones previas. Al hacerlo, perdemos estas garantías de convergencia, pero, como suele ocurrir empíricamente, esto todavía funciona. Estos métodos se denominan métodos de semigradiente, ya que solo consideran el efecto de cambiar los pesos en el valor a actualizar, pero no en el objetivo.
En base a esto podemos introducir TD(0) con aproximación de función:
Una extensión natural de esto, y también una extensión del método tabular de n pasos correspondiente, es la TD de semigradiente de n pasos:
Métodos de aproximación de funciones
En el resto del Capítulo 9, Sutton describe diferentes formas de representar la función aproximada: una gran parte del capítulo cubre la aproximación de funciones lineales y el diseño de características para esto, y para la aproximación de funciones no lineales se introducen las redes neuronales artificiales. Solo cubriremos estos temas brevemente, ya que en este blog trabajamos principalmente con redes neuronales (profundas) y no con simples aproximaciones lineales, y también sospechamos que el lector astuto ya está familiarizado con los conceptos básicos del aprendizaje profundo y las redes neuronales.
Aproximación de función lineal
Aún así, analicemos brevemente la aproximación lineal. En esto, la función de valor de estado se aproxima mediante el producto interno:
Aquí, el estado es descrito por el vector.
– y, como podemos ver, esta es una combinación lineal de los pesos.
Debido a la simplicidad de la representación, existen algunas fórmulas elegantes (y representaciones de bucle cerrado) para la solución, así como algunas garantías de convergencia.
Construcción de características para métodos lineales
Una limitación de la aproximación ingenua de funciones lineales introducida anteriormente es que cada característica se usa por separado y no es posible ninguna combinación de características. Sutton enumera el problema del poste del carro como ejemplo: aquí, la alta velocidad angular puede ser buena o mala, dependiendo del contexto. Cuando el poste está bien centrado, probablemente se deben evitar movimientos rápidos y bruscos. Sin embargo, cuanto más cerca esté el polo de caerse, más rápidas podrían ser necesarias.
Por lo tanto, existe una rama separada de investigación sobre el diseño de representaciones de características eficientes (aunque se podría argumentar que, debido al aumento del aprendizaje profundo, esto se está volviendo menos importante).
Una de esas representaciones son los polinomios. Como ejemplo introductorio, imagine que el vector de estado se compone de dos partes, s_1 y s_2. Así podríamos definir el espacio de características:
Luego, usando esta representación, aún podríamos hacer una aproximación de función lineal, es decir, usar cuatro pesos para las cuatro características recién construidas y, en general, seguir teniendo una función lineal con respecto a los pesos.
De manera más general, las características de base polinómica de orden n+1 pueden representarse mediante
donde las c son números enteros en {0… n}.
Otras bases comúnmente utilizadas son la base de Fourier, la codificación gruesa y en mosaico, y las funciones de base radial, pero como se mencionó, no profundizaremos en este punto.
Conclusión
En esta publicación, dimos un paso importante más allá de las publicaciones anteriores hacia la implementación de algoritmos RL “en la naturaleza”. En las publicaciones anteriores, nos centramos en presentar los métodos RL esenciales, aunque en forma de métodos tabulares. Vimos que alcanzan rápidamente sus límites cuando se implementan en problemas más grandes y, por lo tanto, nos dimos cuenta de que se necesitan métodos de solución aproximados.
En esta publicación presentamos los fundamentos para esto. Además de permitir abordar problemas del mundo real a gran escala, estos métodos también introducen la generalización, una poderosa necesidad para cualquier algoritmo RL exitoso.
Comenzamos introduciendo un objetivo de predicción adecuado y formas de optimizarlo.
Luego, introdujimos nuestros primeros algoritmos RL de gradiente y semigradiente para el objetivo de predicción, es decir, aprender una función de valor para una política determinada.
Por último, discutimos diferentes formas de construir la función de aproximación.
Como siempre, ¡gracias por leer! Y si estás interesado, estad atentos al próximo post en el que profundizaremos en el problema de control correspondiente.
Otras publicaciones de esta serie
Referencias
[1] http://incompleteideas.net/book/RLbook2020.pdf
[2] https://pettingzoo.farama.org/