Ignacio Cativelli, Director de Ingeniería
Introducción
Hace pocas semanas, la ACM anunció el premio Alan Turing 2024 (el equivalente al Nobel en el ámbito de las ciencias de la computación) para Andrew Barto y Richard Sutton, por sus contribuciones al campo del aprendizaje por refuerzo (RL).
Recuerdo el año 2020, cuando empecé a dar mis primeros pasos en RL, y compré mi copia del libro Reinforcement Learning de Sutton y Barto, que tengo en este momento en mi mesa de luz. Sigo pensando que es uno de los mejores libros de tecnología que he leído por su abordaje, completitud y profundidad en un tema complejo y apasionante.
En este artículo, buscaré introducir la teoría detrás de RL y cómo podemos producir agentes que interactúen con su entorno y aprendan, errando, explorando y mejorando, intento a intento, hasta dominar la tarea objetivo y maximizar su recompensa.
¿Qué es RL?
Dentro del campo de Machine Learning, se suelen dividir las tareas de aprendizaje en tres tipos:
- Aprendizaje supervisado: Contamos con un conjunto de características \(x\) y un objetivo \(y\) y buscamos encontrar \(f: y=f(x)\). Por ejemplo, encontrar una función de clasificación que identifique si una radiografía de antebrazo contiene o no una fractura.
- Aprendizaje no supervisado: No contamos con etiquetas \(y\), simplemente tenemos un conjunto de características \(x\) en nuestro set de datos y buscamos explicarlo. Por ejemplo, encontrar clusters de clientes con patrones de consumo similares.
- Aprendizaje por refuerzo: En este escenario, tenemos un agente automático que interactúa con su entorno por medio de acciones y recibe señales en base a su estado actual y la acción seleccionada. Estas señales son recompensas, que el agente busca maximizar. Por ejemplo, controlar la dirección, aceleración y freno de un vehículo autónomo en una autopista.
En este artículo nos centraremos en el último tipo de aprendizaje, que modelaremos matemáticamente para producir algoritmos que sean capaces de aprender en base a las señales de refuerzo recibidas. RL presenta muchos desafíos particulares que tendremos que abordar, como la demora de las señales de recompensa (en un partido de ajedrez recién en el último movimiento sé si gané, perdí o empaté), los ambientes continuos (un agente de trading automático no opera por episodios que empiezan y terminan, sino que está continuamente interactuando), el balance exploración/explotación (si no exploro puedo estar eligiendo acciones subóptimas por no haber descubierto las mejores, pero si exploro demasiado sacrifico mi recompensa total) y el famoso “curse of dimensionality” (a medida que crece el espacio dimensional, se necesita un crecimiento exponencial de los datos de entrenamiento para lograr cobertura).
Procesos de decisión de Markov
Comenzaremos por modelar las interacciones de nuestro agente con su
entorno por medio de un proceso de decisión de Markov (MDP). Estos son
procesos estocásticos que cumplen con la propiedad Markoviana, es decir,
\(P(s_{n} | s_{n-1}, a) = P(s_{n} |
s_{n-1}\ldots s_{0}, a)\). En palabras, la probabilidad de estar
en un estado, tomar una acción y llegar a un nuevo estado, depende
únicamente del estado actual, y no de la historia de estados anteriores
que visité.
A priori la propiedad Markoviana puede parecer muy restrictiva, pero no
lo es, es una simplificación en el modelado matemático que puede
reflejar los estados con los que trabajamos en nuestro entorno. En
algunos casos esto es evidente, por ejemplo, en el ajedrez la mejor
próxima jugada depende únicamente de la disposición actual del tablero,
no importa el conjunto de estados anteriores por los que se pasó para
llegar a la configuración actual. En otros casos esto es menos claro,
como en un agente de trading, donde sí importa la evolución de los
valores de los activos en el tiempo. Sin embargo, siempre podemos
codificar esta información en el estado, incluyendo por ejemplo
indicadores técnicos, características aprendidas en base a la historia,
¡o incluso en el caso más extremo una lista de los últimos cierres!
Definiremos un MDP finito como un conjunto de estados posibles \(S = {s_{1}\ldots S_{n}}\), acciones \(A={a_{1}\ldots a_{m}}\), recompensas \(R={r_{1}\ldots r_{k}}\) y una función de probabilidad \(P(s', r | s, a)\) que describe la probabilidad de encontrarnos en el estado \(s\), tomar la acción \(a\) y llegar al estado \(s'\) con recompensa \(r\). Por ley de probabilidad total, debemos tener, para todo \((s,a)\), \(\sum\limits_{s'}\sum\limits_{r}P(s', r|s, a) = 1\).
Al interactuar con su entorno, nuestro agente generará una secuencia de estados, acciones y recompensas de la siguiente forma: \(s_{1}, a_{1}, r_{2}, s_{2}, a_{2}, r_{3}, s_{3}, a_{3}, r_{4}, \ldots\). Pero, ¿cuál es nuestro objetivo? ¿Maximizar las recompensas inmediatas \(r_{2}, r_{3}, r_{4}\)? Claramente no, deberíamos buscar maximizar la ganancia total futura del agente, que definiremos de la siguiente forma en el tiempo \(t\): \(G_{t} = r_{t+1} + r_{t+2}+\ldots = \sum\limits_{i=t+1}^{\infty}r_{i}\).
Esta definición de ganancia, sin embargo, genera un problema: al no favorecer las ganancias obtenidas en el corto plazo sobre las de largo plazo, cuando nuestro agente trabaja en entornos continuos y no episódicos, podrá continuar obteniendo recompensas infinitamente que a tiempos infinitos generarán ganancias infinitas. Es decir, es lo mismo para nuestro trader ganar un \(0.1\%\) anual que un \(10\%\), ya que tiene tiempo infinito para explotarlo. Una solución muy astuta a este problema es introducir un factor geométrico de descuento a nuestra ganancia, para transformar una serie de suma infinita en un objetivo de explotación finito y maximizable. Recordemos la serie geométrica: \(\sum\limits_{i=0}^{\infty}\gamma^{i} = \frac{1}{1-\gamma}\) si \(0\leq\gamma<1\). Llevando este factor de descuento a nuestra definición de ganancia, tendremos \(G_{t} = r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3}+\ldots = \sum\limits_{i=t+1}^{\infty}\gamma^{i-t-1}r_{i}\).
Otra identidad importante que usaremos más adelante y se desprende de la ecuación anterior, es que \(G_{t} = r_{t+1}+\gamma(r_{t+2} + \gamma r_{t+3} + \ldots) = r_{t+1} + \gamma G_{t+1}\).
Políticas y funciones de valor
En la sección anterior definimos un modelo matemático para nuestras interacciones con el entorno, pero aún no definimos nuestro objetivo de aprendizaje (ya estamos llegando). ¿Qué es lo que necesitamos conseguir? ¿Cómo podemos distinguir un estado mejor de uno peor? ¿Qué configuración de tablero de ajedrez es mejor si presento dos configuraciones? Claramente la que me de mayor probabilidad de ganar. Esto es lo que formalizaremos ahora.
Definiremos una política como la probabilidad de tomar una acción si me encuentro en un estado. Es decir, \(\pi(a|s) = p(a|s)\). Como vemos, definimos la política de forma estocástica. Dado un estado, no siempre tengo que tomar la misma acción de forma determinista, seguramente me convenga hacerlo de forma probabilística para maximizar mi ganancia total. Esto se vuelve evidente en teoría de juegos (quizás para un artículo futuro). Por el momento es fácil pensarlo como un agente que siempre juega piedra vs uno que juega piedra, papel o tijera con un tercio de probabilidad en cada uno, ¿cuál es el mejor agente en ese caso?
Ahora que definimos nuestro objetivo de aprendizaje (una política, ya veremos cuál), podemos definir el valor de los estados y acciones que podamos tomar, dada esa política. Es evidente que el valor de un estado no es absoluto, sino que depende de la política que siga el agente, que le permitirá capturar ese valor. Es decir, definimos el valor de un estado \(s\) como la ganancia total esperada que generaré por estar en el estado \(s\) y seguir la política \(\pi\).
\(V_{\pi}(s) = E_{\pi}[G_{t}|s]=\sum\limits_{a}p(a|s)\sum\limits_{s'}\sum\limits_{r}P(s',r|s,a)(r + \gamma V_{\pi}(s'))\)
Es decir, considerar todas las acciones que puedo tomar desde \(s\) con sus probabilidades para calcular la esperanza de ganancia percibida por tomarlas. Esta ganancia considera todos los estados de destino y sus recompensas según la mecánica del MDP, combinando la recompensa inmediata con el valor descontado del estado al que llego. Esta es una definición donde, de forma similar a como hicimos anteriormente con la ganancia, calculamos el valor actual en base al valor siguiente. Este tipo de definición es de programación dinámica y nos provee un conjunto de ecuaciones lineales (uno para cada estado) que pueden resolverse para encontrar V.
De la misma manera que definimos el valor de un estado, podemos definir el valor de una acción dado un estado, comúnmente conocido como el valor Q en RL. Esta definición se desprende de la ecuación anterior, simplemente reagrupando términos.
\(Q_{\pi}(s,a) = E_{\pi}[G_{t}|s,a] = \sum\limits_{s'}\sum\limits_{r}P(s', r|s, a)(r + \gamma\sum\limits_{a'}p(a'|s')Q(s',a'))\)
Optimalidad
Las ecuaciones anteriores son conocidas como ecuaciones de Bellman, y permiten resolver un MDP. Esto puede realizarse tanto como sistema de ecuaciones lineales, como de forma numérica, aproximando los valores con buenos tiempos y garantías de convergencia.
Por último, podemos definir la política óptima como la política que maximiza \(V(s)\) o \(Q(s,a)\) para todos los estados y acciones. Esta política se representa como \(\pi^{*}\) y sus valores asociados son \(V^{*}(s)\) y \(Q^{*}(s,a)\). Es decir, \(V^{*}(s)=\max\limits_{\pi}V_{\pi}(s)\), \(Q^{*}(s,a)=\max\limits_{\pi}Q_{\pi}(s,a)\).
Con estas definiciones, podemos definir las ecuaciones de optimalidad de Bellman como los valores generados por las mejores acciones, de la siguiente manera.
\(V^{*}(s) = \max\limits_{a}\sum\limits_{s'}\sum\limits_{r}P(s', r|s,a)(r + \gamma V^{*}(s'))\)
\(Q^{*}(s,a) = \sum\limits_{s'}\sum\limits_{r}P(s',r|s,a)(r + \gamma\max\limits_{a'}Q^{*}(s', a'))\)
Las ecuaciones anteriores ya no corresponden a un sistema de ecuaciones lineales (incorporamos la función no lineal max). Sin embargo, quienes hayan trabajado en problemas de optimización saben que pueden ser resueltas con técnicas de programación lineal. Otro enfoque mucho más frecuente, es usar técnicas iterativas para resolver las ecuaciones optimales de Bellman, dado que los tiempos de los algoritmos de programación lineal se degradan con la cantidad de restricciones (estados posibles en nuestro caso). Las técnicas iterativas buscan resolver las ecuaciones de Bellman aplicándolas sucesivamente para aproximar y mejorar políticas hasta llegar al óptimo, o aproximar directamente la función de valor para luego determina la política óptima. Estas técnicas cuentan con garantías de convergencia, son muy simples de implementar (ya hicimos el trabajo duro de derivar la ecuación, ahora es solo aplicarla) y suelen converger en buenos tiempos.
Entonces, ¿ya terminamos? Para nada. Resolver las ecuaciones de Bellman asume un requisito muy exigente, que rara vez ocurre en los problemas de RL que se presentan en la práctica: conocer la dinámica del MDP, es decir, la distribución de probabilidad P. Hasta ahora todo lo que hemos visto son técnicas de planificación que conocen las dinámicas del entorno y optimizan las acciones a tomar. Pero no hemos entrado en el mundo del aprendizaje. Un agente realmente aprende cuando no conoce las dinámicas del entorno y debe explorarlo. De esta forma, a partir de la interacción, genera la experiencia necesaria para poder encontrar la política óptima.
En las siguientes secciones pasaremos de problemas de planificación a aprendizaje, y derivaremos uno de los algoritmos más importantes de RL.
Explorando un ambiente desconocido
Cuando nos enfrentamos a un problema de RL, habitualmente no conocemos las dinámicas del entorno con el que interactuamos. Por lo tanto, es necesario explorar para aprender este comportamiento al mismo tiempo que buscamos la política óptima. Pero, ¿cómo lo hacemos? ¿hasta qué punto debemos elegir acciones exploratorias y hasta dónde debemos explotar el conocimiento que ya generamos? ¿cómo afecta un exceso de exploración nuestra convergencia, y la posibilidad de capturar los verdaderos valores de cada estado?
Estas preguntas se resolverían con algoritmos GLIE (greedy in the limit with infinite exploration), es decir, técnicas de exploración que exploren todos los pares estado-acción infinitamente, pero converjan a las acciones óptimas en el límite. El algoritmo GLIE más utilizado en aprendizaje por refuerzo es \(\epsilon\)-greedy, que plantea, con probabilidad pequeña \(\epsilon\), tomar una acción aleatoria, y con probabilidad \(1-\epsilon\), elegir la acción óptima. Si hacemos decaer \(\epsilon\) a medida que avanza la cantidad de episodios, logramos los objetivos mencionados anteriormente. Es muy habitual utilizar esta técnica en algoritmos de RL, decayendo \(\epsilon\) lentamente hasta llegar a un valor mínimo de exploración y mantenerlo, dado que en la práctica no contamos con un número infinito de episodios para explorar.
Aprendizaje por diferencias temporales
Ahora que definimos cómo explorar, y qué objetivo vamos a perseguir, pasaremos a formular el aprendizaje generado a partir de nuestras interacciones con el entorno de forma iterativa (al igual que hicimos en los algoritmos de planificación con las ecuaciones de Bellman). Para ello, construiremos una tabla de valores \(Q(s,a)\) para los pares estado-acción, inicializada de forma arbitraria (a excepción de los estados terminales), y la actualizaremos en base a las observaciones que realizamos de nuestras interacciones con el entorno de la siguiente forma:
\(Q(s_{t},a_{t}) \leftarrow (1-\alpha)Q(s_{t},a_{t}) + \alpha G_{t} = Q(s_{t}, a_{t}) + \alpha[G_{t} – Q(s_{t}, a_{t})]\)
En este caso, \(\alpha\), nuestro ratio de aprendizaje, promedia las ganancias obtenidas en los pares estado-acción observados con las observaciones anteriores. Esta ecuación simplemente muestra cómo recorrer los estados e ir reflejando las ganancias obtenidas en un promedio computado paso a paso. Es importante hacerlo de esta forma porque se trata de un ambiente estocástico, la misma acción tomada en un estado puede traer resultados muy diferentes en dos momentos separados. Según la teoría de aproximación estocástica, \(\alpha\) debe proveer ciertas garantías para garantizar la convergencia que no exploraremos ahora, pero en la práctica suele bastar con definir un \(\alpha\) pequeño y una programación de caída del valor a medida que avanza su entrenamiento para obtener buenos resultados.
El término que complejiza la ecuación anterior es \(G_{t}\), porque requiere que en cada paso realice la actualización de la tabla de valores en base a la ganancia futura que voy a obtener en el episodio (¡o al infinito para problemas continuos!). Esto demoraría mucho el aprendizaje, que debe esperar a finalizar episodios completos para comenzar a realizar las acutalizaciones de valores. Para resolver este problema, Sutton propuso en un famoso paper del año 1988 los métodos de aprendizaje por diferencias temporales (TD-learning). Básicamente el aprendizaje por diferencias temporales actualiza las nuevas estimaciones en base a las aproximaciones del siguiente paso (o los \(n\) siguientes pasos), lo que se conoce en RL como bootstrapping. A nivel de la ecuación, la modificación es sencilla, y Sutton demostró que, si bien es una estimación que tiene un sesgo sobre el objetivo que se busca predecir, en el infinito converge al valor correcto.
\(Q(s_{t},a_{t}) \leftarrow Q(s_{t}, a_{t}) + \alpha[r_{t+1} + \gamma\max\limits_{a} Q(s_{t+1}, a) – Q(s_{t}, a_{t})]\)
Y ahí lo tenemos, esa es la ecuación de aprendizaje por diferencias temporales que usa la inforamción obtenida del Q siguiente para estimar el valor del Q actual. Luego de derivada, parece simple, y es la piedra fundamental de los algoritmos más complejos de RL que se han desarrollado posteriormente, como el DQN que pudo vencer a Lee Sedol en una partida de Go con AlphaGo.
Q-learning
Por último, nos falta únicamente mostrar el algoritmo Q-learning, que es quizás el más famoso de RL y será muy simple de implementar en base a todo lo que hemos definido hasta ahora. Este algoritmo de aprendizaje fue propuesto por Watkins en 1989 y permite resolver problemas de aprendizaje por refuerzo donde trabajamos con conjuntos finitos de estados y acciones. A continuación listamos el pseudocódigo de Q-learning con exploración \(\epsilon\)-greedy.
Inicializar Q(s,a) arbitrariamente excepto estados terminales, donde será 0.
Para cada episodio:
Comenzar en estado de inicio \(s = s_{0}\)
Hasta completar el episodio:
Elegir la acción a usando \(\epsilon\)-greedy sobre Q
Tomar acción a, observar r y s’
\(Q(s,a) = Q(s,a) + \alpha(r + \gamma\max\limits_{a}Q(s', a) – Q(s,a))\)
s = s’
En no más de diez líneas de código, tenemos la implementación de un algoritmo genérico y muy elegante, que nos permite aprender cualquier MDP, siempre que sea finito, sin requerir conocer las dinámicas internas del proceso de decisión.
En la práctica, los problemas de RL suelen manejar estados con valores continuos (ej: precios) o cardinalidad muy elevada por la cantidad de dimensiones. Esto suele hacer inviable aplicar Q-learning tal cual lo definimos a estos problemas, en su lugar aplicando otras técnicas como aproximadores de funciones (ej: redes neuronales que aproximan la función Q) o técnicas de optimización directamente sobre las políticas, sin usar las funciones de valor. Es interesante observar el primer caso, donde modificaciones en la implementación del algoritmo permiten generalizar a problemas de conjuntos de estados continuos, obteniendo resultados excelentes. Pero eso será material para un post futuro, donde podremos implementar DQN sobre un problema continuo. De momento, recomiendo ver el documental de Alpha Go, que está basado en todo lo que vimos en este post, y para profundizar en RL, los videos de David Silver en Youtube, pero sobre todo, el libro Reinforcement Learning de Sutton y Barto, que no tiene desperdicio y fue lo que me inspiró a escribir este artículo.