Control on-policy con aproximación

1Valores de los empujones

Para elegir un empujón, el agente compara los valores de sus dos empujones en el estado en que está. Con demasiados estados para una tabla, los estima a partir de pesos, q(s, a, w) ≈ q_π(s, a), el valor de tomar la acción a en el estado s y seguir π después. Las features ahora describen un estado y una acción juntos, x(s, a), y la estimación lineal las pondera como antes:

¿Qué features? Los seis rangos del ángulo del péndulo que usaba el apunte de predicción no bastan para elegir, por una razón que está en la física del carro:

1. Un empujón cambia de inmediato qué tan rápido se mueve el carro, y con eso qué tan rápido gira el péndulo.
2. El ángulo del péndulo cambia recién en los pasos siguientes.
3. Un agente que solo ve el ángulo vería el mismo estado siguiente empujara hacia donde empujara, y una actualización que mira un paso adelante nunca podría distinguir sus dos empujones.

Por eso el agente de este apunte también ve hacia dónde gira el péndulo:

Para cada situación hay una feature por empujón, d = 24: x_i(s, a) vale 1 para la situación de s y el empujón a, y 0 para las otras 23, así que q(s, a, w) es el peso de ese par. Es otra vez agregación de estados, ahora sobre pares de un estado y una acción.

Los pesos aprenden como en el apunte de predicción, de ejemplos que ahora juntan un estado y una acción con un objetivo, S_t, A_t ↦ U_t:

El objetivo puede ser el retorno G_t, o uno de los retornos de n pasos del apunte de n-step bootstrapping. El objetivo de Sarsa, la recompensa más el valor del estado siguiente y de la acción elegida en él, da semi-gradient Sarsa de un paso para tareas episódicas:

Es un método semi-gradient por la misma razón que semi-gradient TD(0): su objetivo depende de los pesos, y la actualización lo ignora. Para una política fija converge como semi-gradient TD(0), a un punto fijo propio, con el mismo tipo de cota para su error.

La figura muestra los 24 pesos para la política al azar del apunte de predicción, en el retorno promedio tras cada empujón cuando los empujones siguientes son al azar, que es donde termina gradient Monte Carlo:

• cada par de barras está sobre su situación, dibujada como un pequeño carro con su péndulo y una flecha curva para su sentido de giro;
• la barra de la izquierda es un empujón a la izquierda, la de la derecha un empujón a la derecha;
• una pequeña flecha azul junto al carro apunta al empujón que vale más.

Arrastra el péndulo de arriba: su inclinación elige el rango, y el sentido en que lo mueves, el giro.

2Aprender a mantener el péndulo arriba

Los valores de la sección anterior son los de la política al azar. Para hacerlo mejor, el agente actúa con sus propias estimaciones, como los métodos de control de los apuntes anteriores: en el estado siguiente calcula el valor de cada acción y toma la greedy,

o, algunas veces, una al azar: ε-greedy. Con dos empujones eso toma dos consultas. Con muchas acciones, o con un rango continuo de ellas, encontrar la mejor es un problema en sí mismo, sin una respuesta establecida. La política que actúa es la que se aprende, on-policy, así que cada actualización cambia un poco la política.

El algoritmo

Semi-gradient Sarsa para tareas episódicas, para una estimación q diferenciable en sus pesos, un tamaño de paso α > 0 y un ε > 0 pequeño:

1. Parte con pesos w cualesquiera, por ejemplo todos 0.
2. Al inicio de cada episodio, observa el primer estado S, y elige A a partir de q(S, ·, w), ε-greedy.
3. Toma A, y observa la recompensa R y el estado siguiente S′.
4. Si S′ es terminal, actualiza w ← w + α[R − q(S, A, w)] ∇q(S, A, w), y vuelve al paso 2 para el episodio siguiente.
5. Si no, elige A′ a partir de q(S′, ·, w), ε-greedy, y actualiza w ← w + α[R + γq(S′, A′, w) − q(S, A, w)] ∇q(S, A, w).
6. Haz S ← S′ y A ← A′, y vuelve al paso 3.

El agente de la figura explora sin empujones al azar, con ε = 0. En cambio, parte con todos sus pesos en 300 pasos, más de lo que durará cualquiera de sus episodios. Todo empujón que prueba se queda corto de 300 tarde o temprano, así que el empujón que no ha probado parece mejor, y prueba ese: optimismo, el inicio optimista del apunte de bandits.

α se queda en 0.1 todo el tiempo. El apunte de predicción achicaba α de un episodio al siguiente para que sus pesos se asentaran; aquí primero tienen que bajar desde 300, y sus objetivos siguen cambiando a medida que la política mejora. En 100 corridas de 500 episodios:

La figura dibuja el carro y el péndulo arriba, con el empujón recién elegido como una flecha amarilla, y debajo las barras de la sección anterior, con un punto en el eje del ángulo de la fila del giro del péndulo. Cada vez que avanzas es una línea de los pasos de arriba, como en la figura de Sarsa del apunte de TD: elegir A, tomarla, elegir A′, el objetivo, con borde rojo, y la actualización, con borde verde.

3Mirar n pasos adelante

El retorno de n pasos con pesos, de los apuntes de eligibility traces y de predicción, funciona también con valores de acciones, tomando la estimación del final de los pesos tal como están:

con G_t:t+n = G_t cuando t + n ≥ T. Toma el lugar del objetivo de Sarsa en la actualización general, que, como en el apunte de n-step bootstrapping, actualiza el par de n pasos atrás:

El algoritmo

Semi-gradient n-step Sarsa para tareas episódicas, con α > 0, un ε > 0 pequeño y n ≥ 1. Guarda los últimos n + 1 estados, acciones y recompensas:

1. Parte con pesos w cualesquiera, por ejemplo todos 0.
2. Al inicio de cada episodio, observa S₀, elige A₀ a partir de q(S₀, ·, w), ε-greedy, y haz T ← ∞.
3. Para t = 0, 1, 2, …: si t < T, toma A_t y observa R_t+1 y S_t+1; si S_t+1 es terminal, haz T ← t + 1, y si no, elige A_t+1 a partir de q(S_t+1, ·, w), ε-greedy.
4. Haz τ ← t − n + 1, el tiempo cuya estimación se actualiza. Si τ ≥ 0: G ← Σmin(τ+n, T)i=τ+1γ^i−τ−1R_i; si τ + n < T, G ← G + γⁿq(S_τ+n, A_τ+n, w); y w ← w + α[G − q(S_τ, A_τ, w)] ∇q(S_τ, A_τ, w).
5. Repite los pasos 3 y 4 hasta que τ = T − 1, y luego empieza el episodio siguiente.

En el cart-pole, importa cuántas recompensas reales tiene el objetivo:

• un objetivo que mira un paso adelante aprende poco de la mayoría de los pasos: el péndulo suele quedarse en la misma situación, así que el objetivo toma prestado justo el peso que se actualiza, y el TD error es 1 valga lo que valga ese peso, como en el apunte de predicción;
• un objetivo con n recompensas reales ve más de lo que hizo un empujón;
• con demasiadas, en cambio, el objetivo es un retorno completo, que varía más de un episodio a otro.

La figura corre el agente de la sección anterior con cuatro valores de n, 200 veces cada uno, y muestra cuánto dura arriba el péndulo, episodio a episodio.

Aquí el n que anda mejor es uno grande, 16 pasos, cerca de un tercio de segundo del movimiento del carro: las doce situaciones son demasiado gruesas para que la estimación de la siguiente reemplace bien lo que viene después.

4Una tarea que no termina

El cart-pole también se puede plantear sin episodios. Tras cada falla, el péndulo que cae o el carro que sale del riel, el carro y el péndulo parten de nuevo y la tarea sigue, con una recompensa de −1 en cada falla y 0 en todos los demás pasos. Un retorno que suma recompensas para siempre sería entonces −∞ para toda política que alguna vez falle. En vez de un total, una política se juzga por su recompensa promedio por paso:

Aquí es menos la tasa de fallas: una política que pierde el carro cada 183 pasos en promedio tiene r(π) = −1/183 ≈ −0.0055.

La definición supone que este promedio de largo plazo no depende de dónde parte el agente. Los valores miden entonces cada paso frente a él:

En el cart-pole, el valor diferencial de un empujón es cuántas fallas menos que el promedio le siguen, a la larga.

La figura muestra por qué hay que sacar primero el promedio. Suma R_t − R a lo largo de 1100 pasos de un agente que aprendió a mantener el péndulo arriba, el de la sección siguiente, para una estimación R de r(π) que fijas arrastrando el final de la suma.

Aprender no necesita maquinaria nueva. El TD error mide la recompensa frente a la estimación R_t, y suma los valores del par siguiente y de este, sin descuento:

Los pesos siguen w_t+1 ≐ w_t + αδ_t∇q(S_t, A_t, w_t), y R aprende del mismo error con un tamaño de paso propio, R ← R + βδ_t: cuando las recompensas le ganan una y otra vez a R, los TD errors son casi siempre positivos y R sube, y al revés.

5Differential semi-gradient n-step Sarsa

Con n pasos, el retorno diferencial le resta la estimación del promedio a cada una de sus n recompensas, y después toma prestada la estimación del final:

y el TD error de n pasos, δ_t ≐ G_t:t+n − q(S_t, A_t, w), actualiza los pesos y R como en la sección anterior.

El algoritmo

Differential semi-gradient n-step Sarsa, con tamaños de paso α, β > 0, un ε > 0 pequeño y n ≥ 1. Guarda los últimos n + 1 estados, acciones y recompensas:

1. Parte con pesos w cualesquiera y cualquier R, por ejemplo todos 0.
2. Observa S₀ y elige A₀ a partir de q(S₀, ·, w), ε-greedy.
3. Para t = 0, 1, 2, …: toma A_t, observa R_t+1 y S_t+1, y elige A_t+1 a partir de q(S_t+1, ·, w), ε-greedy.
4. Haz τ ← t − n + 1. Si τ ≥ 0: δ ← Στ+ni=τ+1(R_i − R) + q(S_τ+n, A_τ+n, w) − q(S_τ, A_τ, w), después R ← R + βδ y w ← w + αδ∇q(S_τ, A_τ, w).

No hay episodio que termine: el ciclo sigue mientras el agente siga. β tiene que ser pequeño, para que R siga el promedio de largo plazo y no las últimas recompensas.

El agente de la figura usa n = 4, α = 0.1, β = 0.0001 y ε = 0, y parte con todos los pesos y R en 0, lo que también es optimista: R = 0 no espera ninguna falla. A medida que corre:

• una falla pone un −1 en las ventanas de cuatro actualizaciones;
• entre fallas, las recompensas de 0 le ganan a un R negativo, lo que suma un poco a cada TD error.

La figura se dibuja como la de la sección 2, pero sus barras son valores diferenciales, que pueden ser negativos, y los bordes azules punteados marcan los cuatro empujones de la ventana de la actualización.

6Resumen

Las ideas clave junto a sus equivalentes en NumPy, para una estimación lineal:

• x es el vector de features de S_t y A_t, y x_next el de S_t+1 y A_t+1;
• xs_next tiene los vectores de features de S_t+1 con cada acción, como filas;
• en las filas de n pasos, rs tiene las n recompensas que siguen a A_t, y x_n el vector de features de S_t+n y A_t+n;
• rewards tiene las recompensas de una corrida larga.