n-step bootstrapping

1El retorno de n pasos

Parte con la predicción: estimar v_π(s), el retorno esperado desde cada estado s al seguir una política fija π, a partir de episodios que siguen π. V es la tabla de estimaciones. El objetivo de una actualización Monte Carlo es el retorno completo, todas las recompensas hasta que el episodio termina en el tiempo T:

El objetivo de una actualización TD de un paso se queda con la primera recompensa y reemplaza el resto por la estimación descontada del estado siguiente. Es el retorno de un paso, G_t:t+1 = R_t+1 + γV_t(S_t+1). Quedarse con n recompensas en vez de una da el retorno de n pasos:

En este retorno:

• el subíndice t:t+n dice que parte en el tiempo t y usa recompensas hasta el tiempo t + n;
• el último término es la estimación del estado al que se llega después de n pasos, que reemplaza a todas las recompensas posteriores, y V_t+n−1 es la tabla tal como está cuando ese retorno se puede calcular por primera vez;
• si el episodio termina antes de n pasos, cuando t + n ≥ T, no queda nada que estimar, y el retorno de n pasos es el retorno completo G_t.

Un ejemplo. Un robot vuelve a su cargador desde la cocina, pasando por el pasillo y el estudio. Llegar al cargador da +10, cada otro paso 0, y γ = 0.9, así que los valores reales son 8.1 para la cocina, 9 para el pasillo y 10 para el estudio. La tabla del robot todavía es mala: V(cocina) = 2, V(pasillo) = 4 y V(estudio) = 6. Los retornos desde la cocina, en t = 0:

Cada paso extra reemplaza parte de una estimación por una recompensa real. Con tres pasos el robot llega al cargador, así que no queda ninguna estimación, y el retorno es el retorno completo, 8.1.

Por qué un retorno más largo es un mejor objetivo

En el retorno de n pasos, las recompensas son reales, y la única estimación va multiplicada por γⁿ. Por eso su esperanza está más cerca de la verdad que la tabla, en el peor caso por un factor γⁿ. Esta es la propiedad de reducción del error:

En el ejemplo, el peor error de la tabla es 6.1, en la cocina:

Esta propiedad es la razón por la que todo método n-step TD converge a los valores correctos bajo las condiciones técnicas apropiadas: los métodos de un paso y Monte Carlo son los dos extremos de una misma familia.

2n-step TD

La actualización mueve la estimación de S_t hacia su retorno de n pasos, y deja todos los demás estados como estaban. Los índices registran el momento:

1. G_t:t+n necesita R_t+n y S_t+n, que llegan en el tiempo t + n, así que el estado visitado en el tiempo t se actualiza n pasos después.
2. Durante los primeros n − 1 pasos de un episodio no se actualiza nada.
3. Para compensarlo, los últimos n − 1 estados se actualizan después de que termina el episodio, con retornos que el final deja más cortos.

Este es el episodio del pasillo con n = 2 y α = 0.5. En cada tiempo t, el estado que se actualiza es el del tiempo τ = t − n + 1:

TD de un paso, en el mismo episodio, mueve la cocina solo de 2 a 2.8 y el pasillo de 4 a 4.7, porque sus objetivos, 3.6 y 5.4, se apoyan en las malas estimaciones del estado siguiente. Con dos pasos, la recompensa de +10 llega dos estados atrás en vez de uno, así que un solo episodio la lleva el doble de lejos.

El algoritmo

Para una política π que se quiere evaluar, un tamaño de paso α en (0, 1] y un entero positivo n, y en cada episodio:

1. Observa el primer estado S₀, y haz T ← ∞, porque todavía no se sabe cuándo termina.
2. En cada tiempo t = 0, 1, 2, …, mientras t < T: toma una acción según π, y guarda la recompensa R_t+1 y el estado siguiente S_t+1. Si S_t+1 es terminal, haz T ← t + 1.
3. Haz τ ← t − n + 1, el tiempo cuyo estado se actualiza ahora. Si τ ≥ 0, haz G ← Σmin(τ+n, T)i=τ+1γ^i−τ−1R_i, las recompensas descontadas; si τ + n < T, suma γⁿV(S_τ+n); luego actualiza V(S_τ) ← V(S_τ) + α[G − V(S_τ)].
4. Detente cuando τ = T − 1, una vez actualizado el último estado del episodio.

Solo se necesitan los últimos n + 1 estados y recompensas, así que se pueden guardar en un buffer indexado módulo n + 1.

El error de n pasos como suma de TD errors

El TD error de un paso mide cuánto cambia una estimación en un paso:

Si la tabla no cambia en el camino, el error de la actualización de n pasos es la suma descontada de los TD errors de sus n pasos, porque las estimaciones intermedias se cancelan:

En el ejemplo, δ₀ = 0 + 0.9 · 4 − 2 = 1.6 y δ₁ = 0 + 0.9 · 6 − 4 = 1.4, y 1.6 + 0.9 · 1.4 = 2.86, que es 4.86 − 2. Con el episodio completo, esto se vuelve el error de Monte Carlo, y las eligibility traces se construyen sobre la misma suma.

Cómo elegir n

Qué n aprende más rápido depende de la tarea. Los retornos cortos se apoyan en estimaciones, que al principio son malas; los largos suman muchas recompensas aleatorias, que varían; un n intermedio suele funcionar mejor que cualquiera de los extremos. Un n más grande también separa dos escalas de tiempo que los métodos de un paso amarran entre sí: un agente puede tener que elegir una acción cada fracción de segundo, mientras que un cambio de estado significativo toma muchos de esos pasos, y el bootstrapping funciona mejor a través de un cambio que importa.

3n-step Sarsa

Para control, la misma idea funciona con valores de acción: se reemplazan los estados por pares estado–acción y se actúa de forma ε-greedy con respecto a Q. El retorno de n pasos termina en la estimación del par al que se llega después de n pasos,

para n ≥ 1 y 0 ≤ t < T − n, y es el retorno completo G_t cuando t + n ≥ T. La actualización es la misma que para estados:

Con n = 1 es Sarsa de un paso, también llamado Sarsa(0). La ganancia se nota más cuando las recompensas son escasas. Toma un robot que cruza una sala abierta hasta su cargador, con recompensa 0 en cada movimiento salvo +1 al llegar, todos los valores de acción en 0 al principio, γ = 1 y α = 0.5. Su primer episodio da vueltas durante nueve movimientos.

Durante el episodio todos los objetivos son 0, porque las recompensas son 0 y la tabla sigue toda en cero, hasta que los retornos empiezan a llegar al cargador. El único retorno así de Sarsa de un paso es el del último movimiento, así que sube un solo valor, a 0.5; con n = 4, los retornos de los cuatro últimos movimientos llegan al cargador, y suben cuatro valores a 0.5. Cuando las recompensas son escasas, un episodio de n-step Sarsa deja detrás de una recompensa un rastro de hasta n movimientos en vez de uno. Aquí el siguiente episodio que pase por esas celdas encuentra un rastro de cuatro movimientos.

La figura ejecuta 4-step Sarsa en el acantilado del apunte de TD, con los mismos parámetros, α = 0.5, γ = 1 y ε = 0.1. Sus marcas:

• la ventana de cuatro movimientos de un objetivo tiene borde azul, desde S_τ;
• el movimiento elegido después de ella, en cuya estimación se apoya el objetivo, tiene borde rojo.

Los primeros movimientos muestran cómo las actualizaciones esperan cuatro recompensas.

n-step Expected Sarsa

Expected Sarsa, en cambio, termina su retorno en el valor promedio de las acciones en S_t+n bajo la política objetivo π:

para t + n < T, y el retorno completo en otro caso. V_t(s), el valor aproximado esperado de s, es 0 en un estado terminal. Las acciones del camino son las que se tomaron de verdad; solo el último paso promedia sobre todas.

4Aprendizaje off-policy de n pasos

El aprendizaje off-policy aprende los valores de una política objetivo π a partir de experiencia que sigue una política de comportamiento b: muchas veces π es greedy con respecto a Q y b es ε-greedy. Q-learning de un paso no necesita corregir la diferencia, pero un retorno de n pasos sí. Sus recompensas dependen de las acciones tomadas en el camino, y las eligió b, no π.

La corrección pondera la actualización por ella:

• Si π nunca tomaría una de esas acciones, la razón es 0 y el retorno se ignora.
• Si π las toma más seguido que b, la razón es mayor que 1 y el retorno cuenta más, lo que compensa lo poco que b produce lo que π haría.
• Cuando las dos políticas son la misma, cada factor es 1, y las actualizaciones de abajo se vuelven las de las secciones 2 y 3.

Para valores de estado, la actualización de S_t se pondera por la razón de las n acciones de A_t a A_t+n−1:

Para valores de acción, la razón empieza y termina un paso más tarde:

El par que se actualiza ya contiene su acción A_t, así que no importa cuán probable era que b la eligiera: el valor de (S_t, A_t) trata de lo que pasa después de tomar A_t. Las acciones siguientes, de A_t+1 a A_t+n, sí se ponderan, incluida la última, porque el retorno termina en su valor Q(S_t+n, A_t+n).

Por ejemplo, sea π greedy y b ε-greedy con ε = 0.2 y dos acciones, de modo que b toma la acción greedy con probabilidad 0.9. Cada acción aporta un factor, y la razón es su producto. En 3-step Sarsa:

Solo los tramos de conducta greedy enseñan sobre la política greedy. Un producto de muchas razones puede variar mucho, así que estas actualizaciones son más ruidosas que las on-policy.

5Resumen

Las ideas clave junto a sus equivalentes en NumPy. Los arreglos s, a y r guardan un episodio, con r[i] para R_i, y v y q son las tablas.