Q-learning

1Los valores de la mejor conducta

Lo mejor que puede lograr una política da los valores de acción óptimos:

Conocer q_* basta para actuar bien: en cada estado, toma la acción de mayor valor. En el acantilado, con γ = 1, q_* cuenta movimientos. Desde A2, la celda sobre el inicio, moverse a la derecha deja 6 movimientos hasta la meta por el borde, así que q_*(A2, derecha) = −6, y subir cuesta dos más, q_*(A2, arriba) = −8. Desde B2, un paso hacia abajo, al acantilado, cuesta 100, y desde el inicio el mejor viaje sigue costando 7: q_*(B2, abajo) = −107.

Los valores óptimos están ligados entre sí, a un paso de distancia, por la ecuación de optimalidad de Bellman. El valor de una acción es la recompensa que trae más el valor descontado de actuar lo mejor posible desde el estado al que lleva:

Moverse a la derecha desde A2 lleva a B2, cuyos movimientos arriba, derecha, abajo e izquierda valen −7, −5, −107 y −7. Así, q_*(A2, derecha) = −1 + max(−7, −5, −107, −7) = −6.

El agente no conoce de antemano las recompensas ni los estados siguientes, así que no puede resolver esta ecuación. Como Sarsa, lleva una estimación Q(s, a) para cada par y, después de cada paso, mueve la estimación del par que acaba de probar una fracción α del camino hacia un objetivo. Los métodos de esta página solo se diferencian en su objetivo.

2La actualización de Q-learning

Compárala con la de Sarsa. El objetivo de Sarsa, R_t+1 + γQ(S_t+1, A_t+1), usa el valor de la acción que el agente toma después. El objetivo de Q-learning usa la mejor acción en el estado siguiente, haga lo que haga el agente ahí.

¿Por qué este objetivo? Es el interior de la ecuación de optimalidad de Bellman, con sus dos incógnitas reemplazadas por lo que el agente tiene:

• la esperanza sobre recompensas y estados siguientes pasa a ser la recompensa y el estado siguiente que acaba de observar;
• q_* pasa a ser la tabla actual Q.

A lo largo de muchos pasos, el azar de cada recompensa y cada estado siguiente se promedia, como un promedio muestral se acerca a una esperanza, mientras la tabla misma mejora.

Un ejemplo con números, con α = 0.5. A mitad del aprendizaje, la tabla tiene Q(A2, derecha) = −8, y en B2 arriba −7, derecha −5, abajo −60 e izquierda −7. El agente se mueve a la derecha de A2 a B2 y recibe −1. El objetivo es −1 + max(−7, −5, −60, −7) = −6, y la estimación recorre la mitad del camino hacia él:

El objetivo es el mismo haga lo que haga el agente después en B2, aunque su siguiente movimiento sea un paso al azar hacia abajo, al acantilado.

El algoritmo

El ciclo es el de Sarsa, con un cambio: el objetivo no usa la acción siguiente, así que el agente no tiene que elegirla antes de actualizar. Elige cada acción al comienzo de su paso, con la tabla tal como está. Para un tamaño de paso α en (0, 1] y un ε > 0 pequeño:

1. Parte con cualquier tabla Q(s, a), salvo Q(terminal, ·) = 0.
2. Al comienzo de cada episodio, observa el primer estado S.
3. Elige una acción A en S con una política derivada de Q, como ε-greedy.
4. Toma A, y observa la recompensa R y el estado siguiente S′.
5. Actualiza Q(S, A) ← Q(S, A) + α[R + γ max_a Q(S′, a) − Q(S, A)].
6. Haz S ← S′, y vuelve al paso 3 hasta que S sea terminal.

La figura ejecuta Q-learning en el acantilado con los parámetros de la figura de Sarsa, α = 0.5, γ = 1 y ε = 0.1. Ahora el agente elige cada movimiento después de la última actualización, y el objetivo usa los mejores movimientos de la celda siguiente, con borde rojo, haga lo que haga ahí el agente.

¿Cuándo funciona? Q converge a q_* con probabilidad 1 siempre que:

1. todos los pares se sigan actualizando, así que la política nunca debe dejar de probar todas las acciones;
2. los tamaños de paso se achiquen de la forma habitual: su suma crece sin límite mientras la suma de sus cuadrados se mantiene finita.

La primera condición es lo mínimo que puede pedir cualquier método, porque el valor de una acción que nunca se prueba no se puede aprender.

3Aprender sobre una política mientras se sigue otra

El agente se comporta de forma ε-greedy, pero su objetivo usa max_a Q(S_t+1, a), el valor de la acción greedy en el estado siguiente, sin importar qué acción tome realmente ahí. Así, Q-learning aprende los valores de la política greedy, mientras su experiencia viene de la ε-greedy.

La política de comportamiento igual importa en algo: decide qué pares se visitan, y así cuáles se actualizan.

Sarsa es on-policy: su objetivo usa la acción que toma después, así que cuando esa acción es un movimiento de exploración, el objetivo incluye lo que cuesta explorar. Sarsa aprende q_π de la política ε-greedy que sigue, y Q-learning aprende q_*. Un diagrama de backup muestra la diferencia, en lo que mira cada actualización.

En el acantilado, la diferencia decide la ruta. Deja que ambos métodos aprendan el tiempo suficiente, con ε = 0.1 y tamaños de paso que se achican. Sarsa se asienta una fila más arriba, como en el apunte anterior. Los valores de Q-learning suponen el movimiento greedy desde el paso siguiente en adelante, así que se queda en el borde, y mientras sigue explorando, a veces se cae.

La tabla de Q-learning describe la mejor política, que vale −7 por viaje una vez que deja de explorar, pero a Sarsa le va mejor mientras aprende. La brecha depende de ε:

• bajo ε ≈ 0.02, un movimiento al azar hacia abajo es lo bastante raro como para que Sarsa también se quede en el borde;
• sobre ε ≈ 0.26, Sarsa sube a la fila de arriba;
• si ε se achica hacia 0 con el tiempo, ambos terminan con la política óptima.

Con una conducta puramente greedy, ε = 0, los dos métodos casi coinciden: ambos actúan de forma greedy, y sus objetivos son iguales, porque la acción que Sarsa toma después es la greedy. La única diferencia es el momento. Sarsa elige su acción siguiente antes de actualizar la tabla, y Q-learning después, así que cuando el estado siguiente es el mismo estado, la actualización puede cambiar qué acción toma luego Q-learning. En la figura de Sarsa, elegir primero le costó al agente una segunda caída desde el inicio.

Muchos métodos off-policy tienen que corregir la diferencia entre las dos políticas. Q-learning de un paso no necesita esa corrección: dado el par que actualiza, la recompensa y el estado siguiente no dependen de ninguna de las dos políticas, y el objetivo usa un máximo en vez de la acción que la política de comportamiento toma después.

4Expected Sarsa

Donde el objetivo de Sarsa usa la acción siguiente que la política elige y el de Q-learning la mejor, el objetivo de Expected Sarsa promedia los valores de todas las acciones siguientes, cada uno ponderado por la probabilidad de que π la tome. Este promedio, V(S_t+1), es el valor del estado siguiente que la tabla implica bajo π. Es también lo que vale en promedio el objetivo de Sarsa, así que Expected Sarsa se mueve cada vez como Sarsa se mueve en promedio, sin el azar que agrega la elección de A_t+1. El precio es una suma sobre las acciones en cada paso.

La tabla toma el paso de A2 a B2 de la sección 2, ahora con los valores de B2 en q_* y ε = 0.1; las filas de Sarsa dan la probabilidad de cada caso. La última columna parte de Q(A2, derecha) = −6, con α = 0.5:

Los objetivos posibles de Sarsa promedian 0.925(−6) + 0.05(−8) + 0.025(−108) = −8.65, el objetivo de Expected Sarsa. Pero el valor nuevo de Sarsa depende del movimiento que toque a continuación, mientras que el de Expected Sarsa es siempre el mismo. Con menos ruido en sus actualizaciones, Expected Sarsa tolera un tamaño de paso mayor. En el acantilado los movimientos mismos son seguros y todo el azar viene de la política, así que Expected Sarsa puede usar incluso α = 1 y reemplazar cada estimación por su objetivo, mientras que Sarsa necesita un α pequeño para promediar sus objetivos aleatorios.

Expected Sarsa también puede aprender off-policy, e incluye a Q-learning como caso particular:

1. los pesos π pueden venir de una política objetivo distinta de la de comportamiento;
2. si π es greedy, el promedio pone todo su peso en la mejor acción, y el objetivo es el de Q-learning.

5Sesgo de maximización y aprendizaje doble

El objetivo de Q-learning toma la mayor de varias estimaciones.

Toma un estado con seis acciones que valen exactamente 0: cada una paga +1 o −1 con igual probabilidad. Estima cada acción con el promedio de tres pagos, de modo que una estimación es 1, 1/3, −1/3 o −1. Cada estimación acierta en promedio, pero la mayor de las seis es 1 con probabilidad 0.55, 1/3 con probabilidad 0.43, y queda bajo 0 menos del 2% de las veces. En promedio es +0.69.

Un objetivo de Q-learning que termina en un estado así recibe este optimismo, y los estados que llevan ahí parecen mejores de lo que son. El agente se ve atraído hacia estados cuyas acciones son inciertas, sin ninguna buena razón.

El sesgo viene de usar las mismas muestras dos veces: para elegir la acción que parece mejor, y para decir cuán buena es. El aprendizaje doble separa las dos tareas. Lleva dos estimaciones independientes, Q₁ y Q₂, cada una aprendida con su propia mitad de la experiencia:

• una elige la acción, A^* = argmax_a Q₁(a);
• la otra dice cuánto vale, Q₂(A^*).

Las muestras detrás de Q₂ no participaron en la elección, así que E[Q₂(A^*)] = q(A^*), sin sesgo. En el ejemplo, A^* es la acción que por azar pareció mejor, pero su valor viene de tres pagos nuevos, que promedian 0.

Double Q-learning aplica esto a Q-learning. En cada paso, una moneda decide qué tabla aprende. Si sale cara,

y si sale sello, la misma actualización con Q₁ y Q₂ intercambiadas, de modo que aprende Q₂. Las dos tablas cumplen papeles simétricos. La conducta puede usar ambas, por ejemplo ε-greedy con respecto a Q₁ + Q₂. El aprendizaje doble duplica la memoria, pero no el trabajo por paso, porque cada paso actualiza una sola tabla. La misma idea da versiones dobles de Sarsa y de Expected Sarsa.

6Afterstates

A veces el efecto inmediato de una acción se conoce, y solo lo que sigue es incierto. En un juego de tablero sabes qué posición deja tu jugada, pero no la respuesta de tu rival. Entonces conviene aprender los valores de los afterstates en vez de los valores de los pares estado–acción.

En el Nim, dos jugadores se turnan para sacar cualquier cantidad de palitos de una pila, y gana quien saca el último. Desde pilas de 3 y 2, sacar un palito de la primera pila deja pilas de 2 y 2. Desde pilas de 2 y 3, sacar uno de la segunda deja la misma posición.

Dejar pilas de 2 y 2 resulta ser ganador: saque lo que saque tu rival de una pila, tú sacas lo mismo de la otra, y te llevas el último palito.

Los métodos de aprendizaje no cambian; solo cambia de qué trata la tabla. Los afterstates también aparecen fuera de los juegos, cada vez que una acción se define por su efecto inmediato, como cargar un paquete en un camión determinado: el camión cargado se conoce, el tráfico de su ruta no.

7Resumen

Las ideas clave junto a sus equivalentes en NumPy. La tabla q se indexa por estado y acción, y g guarda un retorno o un objetivo, que es una estimación del retorno.