Introducción al aprendizaje por refuerzo con Python

El aprendizaje por refuerzo es definitivamente una de las áreas de investigación más activas y estimulantes en IA. El interés en este campo creció exponencialmente en los últimos...

Introducción

El aprendizaje por refuerzo es definitivamente una de las áreas de investigación más activas y estimulantes en IA.

El interés en este campo creció exponencialmente en los últimos años, tras grandes (y muy publicitados) avances, como AlphaGo de DeepMind venciendo al campeón mundial de GO, y modelos OpenAI AI [vencer a jugadores profesionales de DOTA](https://venturebeat.com/2019/04/22/openais-dota-2-bot-defeated-99-4-of- jugadores-en-partidas-públicas/).

Gracias a todos estos avances, el aprendizaje por refuerzo ahora se aplica en una variedad de campos diferentes, desde la atención médica hasta las finanzas, desde la química hasta la gestión de recursos.

En este artículo, presentaremos los conceptos fundamentales y la terminología del aprendizaje por refuerzo, y los aplicaremos en un ejemplo práctico.

¿Qué es el aprendizaje por refuerzo? {#qué es el aprendizaje por refuerzo}

Aprendizaje reforzado (RL) es una rama del aprendizaje automático que se ocupa de los actores, o agentes, tomar acciones es una especie de entorno para maximizar algún tipo de recompensa que recogen en el camino.

Esta es deliberadamente una definición muy vaga, por lo que las técnicas de aprendizaje por refuerzo se pueden aplicar a una amplia gama de problemas del mundo real.

Imagina a alguien jugando un videojuego. El jugador es el agente y el juego es el entorno. Las recompensas que obtiene el jugador (es decir, vencer a un enemigo, completar un nivel) o no (es decir, caer en una trampa, perder una pelea) le enseñarán cómo ser un mejor jugador.

Como probablemente haya notado, el aprendizaje por refuerzo no encaja realmente en las categorías de aprendizaje supervisado/no supervisado/semisupervisado.

En el aprendizaje supervisado, por ejemplo, cada decisión que toma el modelo es independiente y no afecta lo que vemos en el futuro.

En el aprendizaje por refuerzo, en cambio, estamos interesados ​​en una estrategia a largo plazo para nuestro agente, que podría incluir decisiones subóptimas en pasos intermedios, y una compensación entre exploración (de caminos desconocidos) y explotación de lo que ya sabemos sobre el medio ambiente.

Breve historia del aprendizaje por refuerzo

Durante varias décadas (¡desde la década de 1950!), el aprendizaje por refuerzo siguió dos hilos de investigación separados, uno centrado en los enfoques de ensayo y error y otro basado en el control óptimo.

Los métodos de control óptimo tienen como objetivo diseñar un controlador para minimizar una medida del comportamiento de un sistema dinámico a lo largo del tiempo. Para lograrlo, utilizaron principalmente algoritmos de programación dinámica, que como veremos son la base de las modernas técnicas de aprendizaje por refuerzo.

Los enfoques de prueba y error, en cambio, tienen profundas raíces en la psicología del aprendizaje animal y la neurociencia, y de ahí proviene el término reforzamiento: las acciones seguidas (reforzadas) por buenos o malos resultados tienden a ser reseleccionadas en consecuencia .

Del estudio interdisciplinario de estos dos campos surgió un campo llamado [Aprendizaje de diferencia temporal (TD)] (http://www.scholarpedia.org/article/TD-learning).

Los enfoques modernos de aprendizaje automático para RL se basan principalmente en TD-Learning, que se ocupa de las señales de recompensa y una función de valor (veremos más en detalle cuáles son en los siguientes párrafos).

Terminología

Ahora vamos a echar un vistazo a los principales conceptos y la terminología del Aprendizaje por Refuerzo.

Agente

Un sistema que está incrustado en un entorno y realiza acciones para cambiar el estado del entorno. Los ejemplos incluyen robots móviles, agentes de software o controladores industriales.

Ambiente

El sistema externo que el agente puede "percibir" y sobre el que actuar.

Los entornos en RL se definen como procesos de decisión de Markov (MDP). Un MDP es una tupla:

$$
(S, A, P, R, \gamma)
$$

dónde:

  • S es un conjunto finito de estados
  • A es un conjunto finito de acciones
  • P es una matriz de probabilidad de transición de estado

$$ P_{ss'}^{a} = \mathbb{P}[S_{t+1} = s'| S_t = s, A_t = a] $$

  • R es una función de recompensa

$$ R_s^a = \mathbb{E}[R_{t+1}|S_t=s, A_t = a] $$

  • γ es un factor de descuento, γ ∈ [0,1]

Markov decision process{.img-responsive}

Muchos escenarios del mundo real se pueden representar como Procesos de decisión de Markov, desde un simple tablero de ajedrez hasta un videojuego mucho más complejo.

En un entorno de ajedrez, los estados son todas las configuraciones posibles del tablero (hay muchas). Las acciones se refieren a mover las piezas, rendirse, etc.

Las recompensas se basan en si ganamos o perdemos la partida, por lo que las acciones ganadoras tienen mayor rentabilidad que las perdedoras.

Las probabilidades de transición de estado hacen cumplir las reglas del juego. Por ejemplo, una acción ilegal (mover una torre en diagonal) tendrá probabilidad cero.

Función de recompensa

La función de recompensa asigna estados a sus recompensas. Esta es la información que los agentes utilizan para aprender a navegar por el entorno.

Se investiga mucho para diseñar una buena función de recompensa y superar el problema de las recompensas escasas, cuando la naturaleza a menudo escasa de las recompensas en el entorno no permite que el agente aprenda adecuadamente de ellas.

El retorno G~t~ se define como la suma descontada de las recompensas del intervalo de tiempo t.

$$ G_t=\sum_{k=0}^{\infty} \gamma^k R_{t+k+1} $$

γ se denomina factor de descuento y funciona al reducir la cantidad de las recompensas a medida que avanzamos hacia el futuro.

Descontar recompensas nos permite representar la incertidumbre sobre el futuro, pero también nos ayuda a modelar mejor el comportamiento humano, ya que se ha demostrado que los humanos/animales tienen preferencia por las recompensas inmediatas.

Función de valor {#función de valor}

La función de valor es probablemente la información más importante que podemos tener sobre un problema de RL.

Formalmente, la función de valor es el retorno esperado a partir del estado s. En la práctica, la función de valor nos dice qué tan bueno es para el agente estar en un estado determinado. Cuanto mayor sea el valor de un estado, mayor será la cantidad de recompensa que podemos esperar:

$$ v_\pi (s) = \mathbb{E}_\pi [G_t|S_t = s] $$

El nombre real de esta función es función estado-valor, para distinguirla de otro elemento importante en RL: la función acción-valor.

La función acción-valor nos da el valor, es decir, el rendimiento esperado, para usar la acción a en un cierto estado s:

$$ q_\pi (s, a) = \mathbb{E}_\pi [G_t|S_t = s, A_t = a] $$

Política

La política define el comportamiento de nuestro agente en el MDP.

Formalmente, las políticas son distribuciones sobre acciones dadas a estados. Una política asigna estados a la probabilidad de realizar cada acción desde ese estado:

$$ \pi (a|s) = \mathbb{P}[A_t = a|S_t=s] $$

El objetivo final de RL es encontrar una póliza óptima (o suficientemente buena) para nuestro agente. En el ejemplo del videojuego, puede pensar en la política como la estrategia que sigue el jugador, es decir, las acciones que realiza el jugador cuando se le presentan ciertos escenarios.

Enfoques principales

Se están aplicando muchos modelos y algoritmos diferentes a los problemas de RL.

De verdad, mucho.

Sin embargo, todos ellos caen más o menos en las mismas dos categorías: basados ​​en políticas y basados ​​en valores.

Enfoque basado en políticas

En los enfoques de RL basados ​​en políticas, nuestro objetivo es aprender la mejor política posible. Los modelos de políticas generarán directamente el mejor movimiento posible desde el estado actual, o una distribución sobre las posibles acciones.

Enfoque basado en valores

En los enfoques basados ​​en el valor, queremos encontrar la función de valor óptimo, que es la función de valor máximo sobre todas las políticas.

Luego podemos elegir qué acciones tomar (es decir, qué política usar) en función de los valores que obtenemos del modelo.

Exploración frente a explotación {#exploración frente a explotación}

La compensación entre exploración y explotación ha sido ampliamente estudiada en la literatura de RL.

La exploración se refiere al acto de visitar y recopilar información sobre estados del entorno que aún no hemos visitado, o sobre los que todavía no tenemos mucha información. La idea es que explorar nuestro MDP podría llevarnos a tomar mejores decisiones en el futuro.

Por otro lado, la explotación consiste en tomar la mejor decisión dado el conocimiento actual, cómodo en la burbuja de lo ya conocido.

Veremos en el siguiente ejemplo cómo se aplican estos conceptos a un problema real.

Un bandido con múltiples brazos

Ahora veremos un ejemplo práctico de un problema de aprendizaje por refuerzo: el problema del bandido armado.

El bandido de múltiples brazos es uno de los problemas más populares en RL:

Te enfrentas repetidamente a una elección entre k opciones o acciones diferentes. Después de cada elección, recibe una recompensa numérica elegida de una distribución de probabilidad estacionaria que depende de la acción que haya seleccionado. Su objetivo es maximizar la recompensa total esperada durante un período de tiempo, por ejemplo, más de 1000 selecciones de acción o pasos de tiempo.

Puedes pensar en ello como una analogía con una máquina tragamonedas (un bandido con un solo brazo). Cada selección de acción es como un juego de una de las palancas de la máquina tragamonedas, y las recompensas son los pagos por ganar el premio mayor.

Bandit machine{.img-responsive}

Resolver este problema significa que podemos idear una política óptima: una estrategia que nos permita seleccionar la mejor acción posible (la que tiene el mayor retorno esperado) en cada paso de tiempo.

Métodos de valor de acción {#métodos de valor de acción}

Una solución muy simple se basa en la función de valor de acción. Recuerde que el valor de una acción es la recompensa media cuando se selecciona esa acción:

$$ q(a) = E[R_t \mid A=a] $$

Podemos estimar fácilmente q usando el promedio de la muestra:

$$ Q_t(a) = \frac{\text{suma de recompensas cuando se toma "a" antes de "t"}}{\text{número de veces que se toma "a" antes de "t"}} $$

Si recopilamos suficientes observaciones, nuestra estimación se acerca lo suficiente a la función real. Luego, podemos actuar con avidez en cada paso de tiempo, es decir, seleccionar la acción con el valor más alto para recolectar las recompensas más altas posibles.

No seas demasiado codicioso

¿Recuerdas cuando hablamos de la compensación entre exploración y explotación? Este es un ejemplo de por qué deberíamos preocuparnos por ello.

De hecho, si siempre actuamos con avidez como se propone en el párrafo anterior, nunca intentaremos acciones subóptimas que podrían conducir a mejores resultados.

Para introducir cierto grado de exploración en nuestra solución, podemos usar una estrategia ε-voraz: seleccionamos acciones con avidez la mayor parte del tiempo, pero de vez en cuando, con probabilidad ε, seleccionamos una acción aleatoria, independientemente de los valores de acción.

Resulta que este método de exploración simple funciona muy bien y puede aumentar significativamente las recompensas que obtenemos.

Una advertencia final: para evitar que nuestra solución sea demasiado costosa desde el punto de vista computacional, calculamos el promedio de forma incremental de acuerdo con esta fórmula:

$$ Q_{n+1} = Q_n + \frac{1}{n}[R_n - Q_n] $$

Tutorial de la solución de Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import numpy as np

# Number of bandits
k = 3

# Our action values
Q = [0 for _ in range(k)]

# This is to keep track of the number of times we take each action
N = [0 for _ in range(k)]

# Epsilon value for exploration
eps = 0.1

# True probability of winning for each bandit
p_bandits = [0.45, 0.40, 0.80]

def pull(a):
    """Pull arm of bandit with index `i` and return 1 if win, 
    else return 0."""
    if np.random.rand() < p_bandits[a]:
        return 1
    else:
        return 0

while True:
    if np.random.rand() > eps:
        # Take greedy action most of the time
        a = np.argmax(Q)
    else:
        # Take random action with probability eps
        a = np.random.randint(0, k)
    
    # Collect reward
    reward = pull(a)
    
    # Incremental average
    N[a] += 1
    Q[a] += 1/N[a] * (reward - Q[a])

Et voilà! Si ejecutamos este script durante un par de segundos, ya vemos que nuestros valores de acción son proporcionales a la probabilidad de ganar el premio mayor para nuestros bandidos:

1
2
3
0.4406301434281669, 
0.39131455399060977, 
0.8008844354479673

Esto significa que nuestra política codiciosa favorecerá correctamente las acciones de las que podemos esperar mayores recompensas.

Conclusión

El aprendizaje por refuerzo es un campo en crecimiento y hay mucho más por cubrir. De hecho, todavía no hemos analizado algoritmos y modelos de propósito general (por ejemplo, programación dinámica, Monte Carlo, diferencia temporal).

Lo más importante en este momento es familiarizarse con conceptos como funciones de valor, políticas y MDP. En la sección Recursos de este artículo, encontrará algunos recursos increíbles para obtener una comprensión más profunda de este tipo de material.

Recursos