Eligibility traces

1Promediar retornos de n pasos

El retorno de n pasos se queda con n recompensas y luego confía en la estimación del estado o par al que llega:

Esta es la forma general, para cualquier manera de estimar valores: v(s, w) es el valor estimado del estado s dado un vector de pesos w.

• Una tabla es el caso más simple, con un peso por estado, de modo que v(s, w) es simplemente la entrada V(s) de la tabla.
• Con valores de acción, el último término es en cambio la estimación del par (S_t+n, A_t+n), como en n-step Sarsa.

Cualquier retorno de n pasos es un objetivo válido, y también lo es cualquier promedio de ellos, siempre que los pesos sean positivos y sumen 1. Un promedio así conserva la propiedad de reducción del error de los retornos de n pasos, así que también lleva a un aprendizaje correcto.

Por ejemplo, una actualización hacia la mitad de un retorno de dos pasos y la mitad de uno de cuatro tiene que esperar cuatro pasos:

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, lo que fija los valores reales. La tabla del robot todavía es mala:

Desde la cocina, el retorno de un paso es 0 + 0.9 · 4 = 3.6, el de dos pasos 0.81 · 6 = 4.86, y el de tres pasos llega al cargador, 0.81 · 10 = 8.1. La mitad del primero y la mitad del último dan 5.85.

2El λ-return

El λ-return promedia todos los retornos de n pasos, con un peso que se achica por λ en cada paso extra:

λ está entre 0 y 1. Los pesos son 1 − λ para el retorno de un paso, (1 − λ)λ para el de dos pasos, (1 − λ)λ² para el de tres, y así sucesivamente. Suman 1, porque 1 + λ + λ² + ⋯ = 1/(1 − λ); el factor 1 − λ está para que sumen 1.

Una vez que un retorno de n pasos llega al final del episodio, es el retorno completo G_t, y también lo es cada retorno más largo. Juntar todos sus pesos da la forma que se usa con episodios:

Los dos extremos del rango son métodos que ya conocemos. Con λ = 1, la suma desaparece y Gλt = G_t: aprender de él es Monte Carlo. Con λ = 0, solo queda el retorno de un paso, Gλt = G_t:t+1: aprender de él es TD de un paso.

Desde la cocina, a dos pasos del último, el λ-return tiene tres términos. Con λ = 0.5 sus pesos son 0.5, 0.25 y 0.25:

De 3.6 con λ = 0 al retorno completo, 8.1, con λ = 1, el objetivo sube con λ: mientras más grande es λ, más se apoya el objetivo en recompensas reales y menos en las malas estimaciones.

3Aprender del λ-return

El λ-return puede reemplazar al objetivo de cualquier actualización. Sarsa hacia él queda

y lo mismo vale para valores de estado. Gλt necesita todas las recompensas hasta el final, así que el algoritmo más simple espera. El algoritmo off-line del λ-return no cambia nada durante el episodio; cuando este termina, hace una actualización por paso, hacia el λ-return de ese paso:

El gradiente ∇v dice qué pesos produjeron la estimación de S_t, y en qué medida. En una tabla vale 1 en la entrada de S_t y 0 en todas las demás, así que la actualización es la de siempre, V(S_t) ← V(S_t) + α[Gλt − V(S_t)].

En el ejemplo, con λ = 0.5 y α = 0.5, la tabla cambia al final del episodio:

¿Qué tan bien aprende? Más o menos como n-step TD con su mejor n, y un poco mejor en sus mejores configuraciones. Como con n, un λ intermedio suele funcionar mejor, y promediar todos los horizontes suele ser más robusto que apostar por un solo n.

Vista hacia adelante y vista hacia atrás

El λ-return es una vista hacia adelante (forward view): la actualización de cada estado mira hacia adelante en el tiempo. Una vista hacia atrás (backward view) lo da vuelta:

• Vista hacia adelante: usa todas las recompensas y estados que siguen al estado, así que actualiza solo después del final, como en Monte Carlo, y nunca en tareas que no terminan.
• Vista hacia atrás: envía el TD error actual hacia atrás, a los estados o pares visitados recientemente, así que cada estimación se actualiza un poco en cada paso, con información que ya existe.

La sección siguiente muestra por qué las dos vistas pueden coincidir.

4El λ-return como suma de TD errors

Toma el TD error de Sarsa, con la tabla fija durante el episodio:

Escribe el λ-return término a término, agrupa las recompensas y las estimaciones paso a paso, y las estimaciones se cancelan de a pares. Lo que queda es una suma descontada de los TD errors desde el tiempo t en adelante:

Para la cocina, los TD errors son δ₀ = 0 + 0.9 · 4 − 2 = 1.6, δ₁ = 0.9 · 6 − 4 = 1.4 y δ₂ = 10 − 6 = 4, y con γλ = 0.45 la suma es 1.6 + 0.45 · 1.4 + 0.2025 · 4 = 3.04, que es 5.04 − 2.

Ahora lee la suma al revés. El TD error δ_k aparece en la actualización de cada par visitado antes o en el tiempo k, con peso (γλ)^k−t, donde k − t es hace cuántos pasos se visitó ese par. Así que no hace falta esperar: apenas se conoce δ_k, se puede pasar hacia atrás a cada par anterior.

5Sarsa(λ)

Sarsa(λ) lleva una traza z(s, a) para cada par, una memoria de corto plazo junto a la tabla de largo plazo Q. Cuando se visita un par, su traza sube en 1, y después de cada paso todas las trazas se achican por el factor γλ. Cada paso mueve entonces cada par según su parte del TD error actual:

Un par que nunca se visitó, o que se visitó hace mucho, tiene una traza cercana a 0 y casi no se mueve. Con λ = 0 solo el par actual tiene traza, y Sarsa(λ) es Sarsa de un paso. Con λ = 1 las trazas decaen solo por γ, y todos los pares del episodio comparten cada TD error como en Monte Carlo. La traza también se escribe e(s, a).

El algoritmo

Para un tamaño de paso α, un descuento γ, un decaimiento de traza λ y un ε > 0 pequeño, con Q(s, a) inicializada arbitrariamente salvo Q(terminal, ·) = 0, y en cada episodio:

1. Pon todas las trazas en 0: z(s, a) ← 0. Observa el primer estado S y elige A de forma ε-greedy con respecto a Q.
2. Toma A, y observa R y S′. Elige A′ en S′ de forma ε-greedy.
3. Calcula el TD error δ ← R + γQ(S′, A′) − Q(S, A), y marca el par recién visitado: z(S, A) ← z(S, A) + 1.
4. Para cada par: Q(s, a) ← Q(s, a) + αδz(s, a), y luego z(s, a) ← γλz(s, a).
5. Haz S ← S′ y A ← A′, y vuelve al paso 2 hasta que S sea terminal.

Este es el episodio del pasillo, con una sola acción por pieza, seguir, de modo que cada Q hace el papel del valor de la pieza. λ = 0.5 y α = 0.5, así que γλ = 0.45, y la tabla parte en 2, 4 y 6:

En t = 2, por ejemplo, la cocina se mueve 0.5 · 4 · 0.2025 = 0.405. La tabla final, 3.52, 5.6 y 8, es exactamente la que da el algoritmo off-line del λ-return, porque cada TD error se calculó con valores que todavía no habían cambiado. En general sí cambian durante el episodio, porque Sarsa(λ) actualiza sobre la marcha, así que un TD error posterior ya refleja actualizaciones anteriores. Entonces Sarsa(λ) no es equivalente al λ-return, pero es una aproximación cercana, y aprende en cada paso en vez de al final.

Crédito para todo un camino

Las trazas reparten cada TD error por todo el camino reciente. Toma un robot que cruza una sala abierta hasta su cargador, con recompensa 0 en cada movimiento salvo +1 al llegar, todos los valores en 0 al principio, γ = 1 y α = 0.5, y λ = 0.9. Su primer episodio da vueltas durante nueve movimientos. Todos los TD errors son 0 hasta el último movimiento, cuyo TD error es 1, y en ese momento la traza del movimiento que está k pasos antes del final es 0.9^k.

Las trazas no recuerdan qué movimientos fueron útiles, solo cuáles fueron recientes, así que el desvío en medio del camino también recibe crédito. Los episodios siguientes lo corrigen, porque los caminos que van directo cobran su recompensa antes.

La figura ejecuta Sarsa(λ) en el acantilado del apunte de TD, con λ = 0.9 como en la sala, γ = 1, ε = 0.1 y un tamaño de paso menor, α = 0.1: un movimiento que se repite una y otra vez suma 1 a su traza cada vez, así que su traza puede crecer muy por encima de 1, y con un α grande los valores se pasarían de largo.

• Cada vez que presionas Siguiente se ejecuta una línea del algoritmo de arriba.
• Cada movimiento con traza tiene un borde verde, tan marcado como su traza.
• El valor que usa el TD error tiene un borde rojo.

El mismo mecanismo funciona con cualquier forma de estimar valores. La traza es entonces un vector z_t, del tamaño del vector de pesos: cuando un peso participa en una estimación, su traza sube, y luego se desvanece. En una tabla, el peso que participa es la entrada del par recién visitado, que es el +1 del algoritmo de arriba.

6Resumen

Las ideas clave junto a sus equivalentes en NumPy. g_n guarda los retornos G_t:t+1 a G_t:T−1, g el retorno completo, y q y z la tabla y las trazas; λ es lam, porque lambda es una palabra reservada de Python.