Jugar Atari con aprendizaje reforzado profundo

1Valores desde los cuadros

Aparte del puntaje, el agente ve solo los cuadros del juego, y el agente de las figuras mira los dos últimos. Una red convierte ese par en un valor para cada movimiento: los puntos que cabe esperar al hacerlo y jugar bien después, contando menos los puntos que llegan más tarde.

La figura muestra la red que entrena la corrida de la sección 3. Arrastra la pelota: donde la sueltas es donde está ahora, en el último cuadro, y la dirección en que la moviste fija dónde estaba un paso antes, dibujada tenue.

• Las barras son los valores que la red da a los tres movimientos, y la flecha azul junto a la paleta apunta al movimiento que más vale.
• La línea roja corta sobre cada barra es el valor exacto de ese movimiento con el mejor juego, calculado con las reglas del juego, que la red nunca ve.
• El botón Un cuadro muestra los valores de una red cuya entrada es solo el último cuadro.

Donde un movimiento decide la devolución, el mejor movimiento de la red devuelve la pelota; los movimientos que casi no se hacen en una situación quedan con valores toscos. El resto de esta sección construye lo que muestra la figura: el estado que ve la red, los valores a los que apunta y la red misma.

El agente del paper juega a través de un emulador de la consola, ℰ. En cada paso de tiempo t elige una acción a_t de 𝒜 = {1, …, K}, aquí K = 3: subir, quedarse y bajar; ve una imagen x_t ∈ ℝ^d, los píxeles del cuadro (aquí d = 48, cada uno 0 o 1); y recibe una recompensa r_t, el cambio en el puntaje. El resto del juego de este apunte:

• Hay 12 saques, desde la pared izquierda en cualquiera de las 6 filas, subiendo o bajando, con la paleta en las filas 2 y 3; dentro de un paso, la paleta se mueve antes que la pelota.
• Un peloteo se corta a las 10 devoluciones: el corte no es un final, y el agente aprende como si el juego siguiera.

Con Un cuadro, una pelota junto a la paleta recibe los mismos valores subiendo o bajando, aunque el movimiento que la devuelve depende de cuál: un cuadro no muestra toda la situación.

Así que el paper toma como estado toda la secuencia de cuadros y acciones hasta ese momento,

La secuencia contiene todo lo que decide lo que viene después, y como en los juegos del paper todo episodio termina, hay una cantidad finita de secuencias: un problema grande pero finito, al que se aplican los métodos de los apuntes anteriores.

Una red necesita una entrada de largo fijo, así que el paper le da φ(s_t), los últimos cuatro cuadros, cada uno reducido a 84 × 84 píxeles en grises. En el juego de este apunte la pelota se mueve un píxel en diagonal por paso, en línea recta entre rebotes, así que dos cuadros muestran hacia dónde va, salvo en el saque, donde el primer cuadro cuenta dos veces:

El agente apunta al retorno, las recompensas desde t en adelante, cada una descontada por γ por cada paso que llega más tarde (el paper no da un valor; las figuras usan γ = 0.9):

y el valor de una acción es el mayor retorno esperado tras ella, entre todas las formas de seguir jugando,

Las líneas rojas de la figura son Q^*, que la página calcula exactamente para este juego, con el value iteration del apunte de model-based RL sobre las 552 situaciones verdaderas del juego, algo que el agente, que no conoce las reglas ni el estado, no puede hacer. Como el corte no es un final, estos son los valores de un peloteo que nunca termina:

Con un valor para cada secuencia, o para cada par de cuadros, el agente no aprendería nada sobre un par que no hubiera visto, y aunque este juego tiene solo 1336 pares, un juego de Atari tiene demasiados. Así que el paper estima Q^* con pesos θ, como lo hacían los apuntes de aproximación:

Una estimación lineal como las de esos apuntes fracasa sobre los píxeles. Cada píxel encendido suma su propio peso, así que la estimación no puede decir que subir es bueno cuando la pelota está sobre la paleta y malo cuando está debajo, estén donde estén las dos. Una red aprende esas combinaciones desde los píxeles.

Una red se construye en capas, cada una de las cuales multiplica lo que recibe por una tabla de pesos y pasa el resultado por una función fija (la red del apunte de word2vec). La red de las figuras tiene dos capas:

• 96 entradas, los píxeles de los dos cuadros;
• 32 unidades ocultas rectificadoras, max(0, z), que mantienen un número positivo y convierten uno negativo en 0;
• y 3 salidas, un valor para cada movimiento:

con un 1 delante de φ y de la capa oculta, de modo que las primeras columnas de W₁ y W₂ tienen los sesgos, como en el apunte de los vectores de palabras; θ es W₁ (32 × 97) y W₂ (3 × 33), 3203 pesos; el Q(s, a; θ) del paper se calcula como Q(φ(s), a; θ).

Una salida por movimiento es la elección del paper: las redes anteriores recibían la acción como entrada y necesitaban una pasada por cada acción; esta da el valor de todos los movimientos en una sola pasada. En la notación de los apuntes anteriores:

2Aprender de sus propias estimaciones

Q^* cumple la ecuación de optimalidad de Bellman del apunte de Q-learning, aquí en la notación del paper (su ecuación 1):

Value iteration, que el apunte de model-based RL aplicó a los valores de los estados, la convierte en una actualización que se repite iteración tras iteración, y converge a Q^*:

Pero necesita un valor para cada secuencia, y no aprende nada de una secuencia a partir de otra.

El paper mantiene la forma de value iteration con una red. En la iteración i ajusta los pesos θ_i a objetivos calculados con los pesos de la iteración anterior, θ_i−1, haciendo pequeña una pérdida, un número que dice cuán equivocadas están las estimaciones, como lo hacía el VE del apunte de predicción (la ecuación 2 del paper):

donde el objetivo es

• ρ(s, a) es la distribución de comportamiento del paper, cuán seguido aparecen cada secuencia y cada acción al jugar (el μ del apunte de predicción, no la razón ρ del apunte de n-step bootstrapping).
• θ_i−1 no es una segunda red: son los pesos antes de un paso, y θ_i los pesos que el paso cambia.

Así que los objetivos dependen de los pesos. En el aprendizaje supervisado, el objetivo de cada ejemplo, su etiqueta, está fijo antes de empezar a aprender. Aquí cada paso que cambia los pesos puede cambiar también los objetivos.

La figura toma el primer paso del juego desde un saque: la paleta se queda quieta, la recompensa es 0, y el siguiente par de cuadros es φ₂. La red aprende Q(φ₁, quedarse; θ) solo de esa transición, con un paso de gradiente sobre L_i por iteración, en dos corridas, el valor en azul y su objetivo en rojo:

• la de la izquierda mantiene el primer objetivo, como se mantendría una etiqueta;
• la de la derecha lo vuelve a calcular antes de cada paso, con los pesos como están.

El objetivo se movió porque una misma red calcula los dos valores:

1. El paso que subió quedarse en φ₁ cambió los pesos de salida de quedarse, que usan todos los pares de cuadros, y las unidades ocultas que reciben los píxeles que comparten los dos cuadros; así que subió también quedarse en φ₂, en cerca de cuatro quintos de esa subida.
2. Bajar había sido el mayor valor de φ₂, apenas sobre quedarse; después del paso, el mayor es quedarse, así que el objetivo toma prestado justo el valor que suben los pasos.
3. Multiplicado por γ = 0.9, el objetivo gana cerca de 0.73 de lo que gana el valor, así que la brecha se achica cerca de un quinto por paso, hasta que los dos se encuentran en 0.329, un punto fijo, como el fixed point de TD del apunte de predicción lo era para una estimación lineal.

Si un paso hubiera subido el valor del siguiente par de cuadros en más de 1/0.9 veces lo que sube el valor que actualiza, el objetivo se habría adelantado, y los dos habrían crecido sin límite: aprender de sus propias estimaciones puede diverger, como retoma la sección 4. Solo el objetivo de una transición final, la recompensa −1, no puede moverse.

Para hacer pequeña L_i, el paper sigue su gradiente. Con θ_i−1 fijo, es (la ecuación 3 del paper, con un factor agregado):

El ½ del apunte de predicción daba el mismo paso, w ← w − ½α∇[…]² = w + α[…]∇v (apunte de predicción), y mantener θ_i−1 fijo lo vuelve lo que ese apunte llamaba semi-gradient: el paso sigue cómo los pesos mueven la estimación, e ignora cómo mueven el objetivo. Para una red, ∇_θQ se calcula capa por capa, desde la salida hacia atrás, con la regla de la cadena del apunte de los modelos lineales, un cálculo que se llama retropropagación (backpropagation).

En vez de calcular las esperanzas, el paper da pasos de gradiente estocástico; con una sola muestra de ρ y de ℰ después de cada paso de tiempo, la actualización es

Esto es Q-learning: con una tabla, un peso para cada secuencia y movimiento, ∇_θQ es 1 para el par que se actualiza y 0 para todos los demás, y el paso es la actualización del apunte de Q-learning; con el valor del movimiento siguiente en lugar del máximo, sería semi-gradient Sarsa.

Como los métodos del apunte de TD, es model-free: aprende de muestras de ℰ y no construye ningún modelo de él. Y es off-policy, como en el apunte de Q-learning: aprende sobre la política greedy, a = argmax_a Q(s, a; θ), mientras juega de forma ε-greedy. El paper escribe max ahí, y en su algoritmo, donde quiere decir argmax.

3Deep Q-learning

Deep Q-learning le agrega una cosa a esa actualización: una memoria. Después de cada paso, el agente guarda la transición, e_t = (s_t, a_t, r_t, s_t+1), en un conjunto de datos (el algoritmo guarda cada s como su φ, todo lo que lee la red),

la memoria de replay, que guarda las últimas N transiciones, juntando muchos episodios.

Eso queda entre el único estado por paso del apunte de predicción y la actualización por lotes del apunte de TD. Dyna-Q, en el apunte de model-based RL, también sacaba al azar pasos recordados, pero guardaba solo el último resultado de cada par. La sección 4 dice por qué se sacan al azar.

El algoritmo

Deep Q-learning con experience replay, para una red Q con pesos θ, una memoria de N transiciones, minibatches de 32, un tamaño de paso α y un ε que baja con el tiempo, como lo dejaba achicarse el apunte de Monte Carlo, durante M episodios:

1. Parte con 𝒟 vacío, con espacio para N transiciones, y θ al azar.
2. Al inicio de cada episodio, observa el primer cuadro x₁, y haz s₁ = x₁ y φ₁ = φ(s₁).
3. Con probabilidad ε elige una acción a_t al azar; si no, a_t = argmax_a Q(φ_t, a; θ).
4. Toma a_t, observa r_t y x_t+1, y haz s_t+1 = s_t, a_t, x_t+1 y φ_t+1 = φ(s_t+1).
5. Guarda (φ_t, a_t, r_t, φ_t+1) en 𝒟, y descarta la transición más antigua cuando ya tiene N.
6. Saca al azar de 𝒟 un minibatch de transiciones (φ_j, a_j, r_j, φ_j+1), y fija el objetivo y_j de cada una (abajo).
7. Da un paso de gradiente sobre sus errores cuadráticos, con los objetivos fijos,
   θ ← θ + α · 132 Σ_j[y_j − Q(φ_j, a_j; θ)] ∇_θQ(φ_j, a_j; θ)
   Si φ_t+1 es terminal, o el peloteo llegó al corte del juego, empieza el episodio siguiente en el paso 2; si no, vuelve al paso 3.

Los objetivos del paso 6 son

Aquí j cuenta las transiciones sacadas, donde el i de la sección 2 contaba iteraciones; los objetivos usan θ antes del paso, el θ_i−1 de la sección 2, y α absorbe el 2 del error cuadrático. Un peloteo cortado a las 10 devoluciones no es terminal, así que su último objetivo todavía suma γ veces el valor del siguiente par de cuadros. El paper llama a estas redes deep Q-networks, DQN.

La figura ejecuta estos pasos en el juego, desde pesos al azar, con los ajustes de la tabla, en tres partes:

• Arriba, el juego, con las barras y la flecha de la sección 1; el movimiento recién elegido llena su fila de amarillo, y las barras que usa un objetivo se marcan en rojo.
• Al medio, la memoria, como celdas y después como una franja; números o marcas verdes señalan lo que saca cada paso.
• Abajo, una transición sacada: sus dos pares de cuadros y una escala de su valor (azul) a su objetivo (rojo), con una marca verde donde el paso lo deja; un paso mueve un valor demasiado poco para verlo en las barras.

Cada vez que avanzas es una línea de los pasos de arriba, como en la figura de Sarsa del apunte de control; el episodio 1 se juega completo y el episodio 2 hasta su primera devolución, y desde ahí la figura salta a los momentos en que aprende algo nuevo.

Cada paso bajó el error cuadrático de sus 32 sorteos tomados juntos, pero no el de cada sorteo: cerca de un tercio de las transiciones sacadas se alejó de su objetivo en un paso, arrastrada por las demás.

4Por qué experience replay

Sarsa, Q-learning y TD-Gammon, un programa anterior que aprendió backgammon con una red, usaban cada paso una vez, en el orden en que llegaba. Una memoria cambia tres cosas, las ventajas del paper:

1. Cada paso se usa en muchas actualizaciones: la transición 12 de la figura de la sección 3 salió 243 veces mientras estuvo en la memoria.
2. Los pasos seguidos están muy correlacionados, el segundo obstáculo de la introducción, así que aprender de ellos en orden persigue el peloteo actual; sacarlos de los últimos 10 000 pasos rompe la correlación y baja la varianza de las actualizaciones.
3. Cuando un agente aprende de los datos que producen sus pesos actuales, los pesos eligen los próximos datos, el tercer obstáculo de la introducción: una red que prefiere subir entrena sobre todo con cuadros con la paleta arriba. Esos ciclos pueden atrapar los pesos o hacerlos diverger; replay promedia ρ, la distribución de comportamiento, sobre muchas conductas pasadas.

Replay vuelve off-policy el aprendizaje, en el sentido de la sección 2, se quiera o no: una transición sacada tiene un movimiento que eligieron pesos más antiguos, muchas veces al azar. Eso decide el método:

El objetivo de un paso de Q-learning no necesita ninguna corrección por la otra política, como mostró el apunte de Q-learning: dado el par que actualiza, la recompensa y el cuadro siguiente no dependen de quién eligió el movimiento. El paper también nombra los límites de su memoria: guarda solo las últimas N transiciones, y descarta las más antiguas tengan lo que tengan, y saca todas las transiciones por igual, aunque en esta corrida solo 3 o 4 de cada 32 sorteos traen una recompensa distinta de 0; sugiere favorecer las transiciones de las que hay más que aprender.

La figura corre el agente de la sección 3 con 16 semillas durante 30 000 pasos, con tres maneras de elegir el minibatch de cada paso:

Cada 250 pasos una prueba juega los 12 saques sin movimientos al azar, y cada curva cuenta los agentes que devuelven la pelota diez veces desde cada saque. Replay es azul, las otras tenues, Solo la última en línea discontinua.

Lo que gana replay es que se mantiene estable con un tamaño de paso lo bastante grande para aprender rápido: con tres veces el α de la corrida, todos los agentes con replay siguen aprendiendo, mientras que ningún agente sin replay lo logra, y en más de la mitad de ellos los valores se disparan. El ciclo de la tercera ventaja no es la causa: cuando todo movimiento es al azar, la mitad de los agentes de Últimas 32 se disparan igual. Sin replay, cada paso aprende de las últimas transiciones, casi los mismos cuadros, y empuja los mismos pesos una y otra vez, hacia objetivos que esos mismos pesos fijan. Con transiciones sacadas al azar de 10 000 pasos, esos empujes se compensan.

El paper cita resultados que muestran que Q-learning puede diverger:

• cuando su estimación no es lineal, como una red (Tsitsiklis y Van Roy, 1997);
• o cuando aprende off-policy (Baird, 1995).

No ofrece ninguna garantía de que su propio método converja, e informa que ninguna de sus corridas divergió.

5Resumen

Las ideas clave junto a sus equivalentes en NumPy, para la red y los ajustes de las figuras. En el código:

• x_prev y x son los dos últimos cuadros, w1 y w2 los pesos (los sesgos en la primera columna), theta los dos como un solo vector, y q los tres valores.
• rs tiene las recompensas de un episodio desde t, y g es el retorno R_t.
• En las filas del minibatch, r, done y q_a tienen las 32 recompensas, si cada par siguiente es terminal (1 o 0) y los valores de los movimientos hechos; q_next tiene los valores de cada par siguiente y grad_q el gradiente de cada Q(φ_j, a_j; θ), por filas, que calcula la retropropagación.

El paso es el paso de gradiente simple de las figuras, con α absorbiendo el 2 del error cuadrático.