Fórmulas intermedias entre Monte Carlo y TD a un paso

Las dos reglas del tema anterior tienen exactamente la misma forma y se diferencian en una sola cosa: de dónde sale el objetivo.

\[ V(S_t) \leftarrow V(S_t) + \alpha\big[\,G_t - V(S_t)\,\big] \qquad\text{(Monte Carlo)} \] \[ V(S_t) \leftarrow V(S_t) + \alpha\big[\,R_{t+1} + \gamma V(S_{t+1}) - V(S_t)\,\big] \qquad\text{(TD a un paso)} \]

El objetivo de Monte Carlo es el retorno real \(G_t\): hay que esperar a que el episodio termine para conocerlo. El objetivo de TD trae todo el futuro a un paso: una recompensa real, \(R_{t+1}\), y una estimación, \(\gamma V(S_{t+1})\), que resume de golpe todo lo que venga después. Esa asimetría —una recompensa real frente a todo lo demás estimado— es lo que este bloque va a graduar.

Nada obliga a arrancar exactamente en el paso siguiente. Se pueden usar dos recompensas reales y estimar a partir de la tercera; o tres; o \(n\). En un extremo, \(n=1\), está TD(0); en el otro, cuando \(n\) llega o supera la longitud del episodio, no queda ninguna estimación en el objetivo y lo que queda es Monte Carlo. Todo lo de en medio son métodos legítimos, con nombre propio: métodos de \(n\) pasos.

El libro es explícito sobre por qué merecen un capítulo: “los mejores métodos suelen ser intermedios entre los dos extremos”. Y da una segunda razón, menos citada: los métodos de \(n\) pasos liberan de la tiranía del paso de tiempo. Con TD a un paso, el mismo intervalo decide dos cosas distintas —cada cuánto se puede cambiar de acción y sobre cuánto tiempo se arranca la estimación—, y a menudo interesa actuar deprisa y arrancar despacio.

La definición es la que cabe esperar: \(n\) recompensas reales y, en lugar del resto del episodio, la estimación que se tenía del estado al que se llega.

\[ G_{t:t+n} \;\doteq\; R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{n-1}R_{t+n} + \gamma^{n} V_{t+n-1}(S_{t+n}) \]

\[ V_{t+n}(S_t) \;\doteq\; V_{t+n-1}(S_t) + \alpha\big[\,G_{t:t+n} - V_{t+n-1}(S_t)\,\big] \]

Si \(t+n \ge T\), es decir, si la ventana de \(n\) pasos llega a la terminación o la pasa, todos los términos que faltan se toman como cero y el retorno a \(n\) pasos se define igual al retorno completo: \(G_{t:t+n} \doteq G_t\). Es lo que hace que \(n\) muy grande sea exactamente Monte Carlo y no una aproximación suya.

Y ahora la pregunta con la que cierra la diapositiva: “supón que tomamos \(n=10\), ¿qué pasa al principio de un episodio?”. Pasa que no se actualiza nada. \(G_{0:10}\) necesita \(R_{10}\) y \(V_9(S_{10})\), que no existen hasta el paso 10; en general, no hay ninguna actualización durante los primeros \(n-1\) pasos de cada episodio. Para compensar, al terminar el episodio se hacen \(n-1\) actualizaciones adicionales, ya sin más experiencia que la que hay en el buffer. El total sigue siendo exactamente \(T\) actualizaciones por episodio, sea cual sea \(n\): lo que cambia es cuándo se hacen y con qué objetivo.

n-step TD para estimar V ≈ v_π
Entrada: una política π
Parámetros: tasa de aprendizaje α ∈ (0,1], entero positivo n
Inicializar V(s) arbitrariamente, para todo s ∈ S⁺, con V(terminal) = 0
Los accesos a S_t y R_t pueden indexarse módulo n+1

Para cada episodio:
    Inicializar y guardar S_0 ≠ terminal
    T ← ∞
    Para t = 0, 1, 2, …:
        Si t < T:
            Tomar una acción según π(·|S_t)
            Observar y guardar R_{t+1} y S_{t+1}
            Si S_{t+1} es terminal: T ← t + 1
        τ ← t − n + 1        (τ es el instante cuyo valor se actualiza)
        Si τ ≥ 0:
            G ← Σ_{i=τ+1}^{mín(τ+n, T)} γ^{i−τ−1} R_i
            Si τ + n < T:  G ← G + γ^n V(S_{τ+n})           (esto es G_{τ:τ+n})
            V(S_τ) ← V(S_τ) + α [ G − V(S_τ) ]
    hasta que τ = T − 1

Dos costes que conviene tener presentes: hay que guardar los últimos \(n\) estados y recompensas —memoria \(O(n)\), indexando módulo \(n+1\)— y hay más cómputo por paso que en un método a un paso. El capítulo 12 arreglará las dos cosas.

Continúa en el módulo 1 →

\(n\) es un hiperparámetro. Valores pequeños dan estimadores con más sesgo y menos varianza —el objetivo depende mucho de una estimación que todavía es mala—, y valores grandes, al revés: menos sesgo, porque hay más recompensas reales dentro, y más varianza, porque hay más aleatoriedad acumulada. Y hay una tercera consecuencia, que es la más operativa: \(n\) decide a cuántos estados llega el efecto de una sola muestra de experiencia.

El libro lo explica con un caso concreto: si el primer episodio va derecho del centro hasta salir por la derecha, un método a un paso solo cambia el valor del último estado visitado; a dos pasos, los dos últimos; y con \(n\) mayor o igual que la longitud del episodio, todos los estados visitados, y todos en la misma cantidad. Ese caso exacto es el que se puede recorrer en el módulo siguiente.

Cuidado con la diapositiva: la cadena que dibuja arriba es la de 5 estados del capítulo 6, y la gráfica de abajo es la del experimento del capítulo 7, que usa 19 estados, recompensa \(-1\) al salir por la izquierda (no 0) y valores iniciales a 0 (no 0,5). Son dos entornos distintos; mezclarlos da curvas que no se parecen a las del libro. Esta página usa el de 19 estados, que es el de la gráfica.

Existe un teorema que respalda la familia entera: la propiedad de reducción del error. Dice que el peor error de la esperanza del retorno a \(n\) pasos está acotado por \(\gamma^{n}\) veces el peor error de la estimación de partida. Ojo con la letra pequeña: es sobre la esperanza, en norma del máximo, y con \(\gamma=1\) la cota es trivial. Como el experimento del módulo 1 usa \(\gamma=1\), que el \(n\) intermedio gane es un resultado empírico, no un corolario del teorema.

\[ \max_s \Big| \mathbb{E}_\pi\big[G_{t:t+n}\mid S_t=s\big] - v_\pi(s) \Big| \;\le\; \gamma^{n}\max_s\big|V_{t+n-1}(s) - v_\pi(s)\big| \]

Continúa en el módulo 1 →

El paso al control es el de siempre: cambiar estados por pares estado-acción y usar una política \(\varepsilon\)-greedy. La única diferencia respecto de la predicción es que el retorno se cierra con un valor de acción en vez de un valor de estado.

\[ G_{t:t+n} \;\doteq\; R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{n-1}R_{t+n} + \gamma^{n} Q_{t+n-1}(S_{t+n},A_{t+n}) \]

\[ Q_{t+n}(S_t,A_t) \;\doteq\; Q_{t+n-1}(S_t,A_t) + \alpha\big[\,G_{t:t+n} - Q_{t+n-1}(S_t,A_t)\,\big] \]

A partir de aquí el libro rebautiza el algoritmo del capítulo anterior: el SARSA de una sola transición pasa a llamarse SARSA a un paso, o SARSA(0).

SARSA a n pasos para estimar Q ≈ q_* o q_π
Inicializar Q(s,a) arbitrariamente, para todo s ∈ S⁺, a ∈ A, con Q(terminal,·) = 0
Inicializar π como ε-greedy respecto a Q, o a una política fija dada
Parámetros: tasa de aprendizaje α ∈ (0,1], ε > 0 pequeño, entero positivo n
Los accesos a S_t, A_t y R_t pueden indexarse módulo n+1

Para cada episodio:
    Inicializar y guardar S_0 ≠ terminal
    Elegir y guardar una acción A_0 ~ π(·|S_0)
    T ← ∞
    Para t = 0, 1, 2, …:
        Si t < T:
            Tomar la acción A_t
            Observar y guardar R_{t+1} y S_{t+1}
            Si S_{t+1} es terminal:
                T ← t + 1
            si no:
                Elegir y guardar A_{t+1} ~ π(·|S_{t+1})
        τ ← t − n + 1
        Si τ ≥ 0:
            G ← Σ_{i=τ+1}^{mín(τ+n, T)} γ^{i−τ−1} R_i
            Si τ + n < T:  G ← G + γ^n Q(S_{τ+n}, A_{τ+n})   (esto es G_{τ:τ+n})
            Q(S_τ, A_τ) ← Q(S_τ, A_τ) + α [ G − Q(S_τ, A_τ) ]
            Si π se está aprendiendo, asegurar que π(·|S_τ) es ε-greedy respecto a Q
    hasta que τ = T − 1

La figura de la diapositiva es la explicación en una imagen. Un mismo episodio hasta la meta, con todos los valores empezando en cero y una única recompensa positiva al llegar. A la derecha del camino, dos paneles: SARSA a un paso refuerza una sola acción, la última; SARSA a 10 pasos refuerza las diez últimas, todas en la misma cantidad. Con el mismo episodio y sin ninguna suposición adicional, uno aprende diez veces más que el otro. Ése es el argumento entero.

El capítulo tiene tres piezas más que aquí solo se nombran: SARSA esperado a \(n\) pasos, que cambia el último valor por su esperanza \(\bar V_{t+n-1}(s)\doteq\sum_a \pi(a\mid s)Q_t(s,a)\); la versión off-policy con la razón de muestreo de importancia truncada \(\rho_{t:h}\); y el tree backup, que consigue aprendizaje off-policy sin muestreo de importancia. Están en §7.2, §7.3 y §7.5 del libro.

No hay ninguna obligación de elegir un solo \(n\). Una actualización es válida hacia cualquier media de retornos a \(n\) pasos, con la única condición de que los pesos sean positivos y sumen 1. El ejemplo de la diapositiva es el mismo del libro: media a partes iguales de un retorno a dos pasos y uno a cuatro.

\[ G^{\text{comp}}_t \;=\; \tfrac12\,G_{t:t+2} + \tfrac12\,G_{t:t+4} \]

A una actualización que promedia actualizaciones más simples el libro la llama actualización compuesta, y demuestra que hereda la propiedad de reducción del error de sus componentes; es decir, que las garantías de convergencia se conservan. Y entonces aparece la pregunta obvia, que es la que abre el capítulo 12: si vale cualquier media, ¿por qué elegir unos pocos \(n\) y no promediarlos todos?

TD(\(\lambda\)) es una forma concreta de promediar todos los retornos a \(n\) pasos: cada uno con peso proporcional a \(\lambda^{n-1}\), y todo normalizado por \(1-\lambda\) para que los pesos sumen exactamente 1.

\[ G_t^{\lambda} \;\doteq\; (1-\lambda)\sum_{n=1}^{\infty}\lambda^{\,n-1}\,G_{t:t+n} \]

El retorno a un paso se lleva el peso mayor, \(1-\lambda\); el de dos pasos, \((1-\lambda)\lambda\); el de tres, \((1-\lambda)\lambda^2\); y así, desvaneciéndose por \(\lambda\) a cada paso adicional. El área total bajo la curva de pesos vale 1.

Al llegar al estado terminal, todos los retornos a \(n\) pasos posteriores valen ya lo mismo: el retorno completo \(G_t\). Separando esos términos de la suma principal queda la forma que se usa en la práctica, con una cola que acumula de golpe todo el peso posterior a la terminación.

\[ G_t^{\lambda} \;=\; (1-\lambda)\sum_{n=1}^{T-t-1}\lambda^{\,n-1}G_{t:t+n} \;+\; \lambda^{\,T-t-1}G_t \]

Esta forma deja ver los dos extremos sin hacer ninguna cuenta. Con \(\lambda=1\) la suma principal se anula y solo queda \(G_t\): actualizar hacia el retorno \(\lambda\) es Monte Carlo. Con \(\lambda=0\), el retorno \(\lambda\) se reduce a \(G_{t:t+1}\), el retorno a un paso: es TD(0). De ahí el nombre del algoritmo original. Un solo parámetro entre 0 y 1 recorre todo lo que en el bloque anterior costaba elegir un \(n\) entero.

\[ V(S_t) \leftarrow V(S_t) + \alpha\big[\,G_t^{\lambda} - V(S_t)\,\big] \]

La forma de mirar que se ha usado hasta aquí tiene nombre: vista hacia adelante. Desde cada estado visitado se mira al futuro, se decide cómo combinar las recompensas que vendrán, se actualiza, y ya no se vuelve a tocar ese estado. Los estados futuros, en cambio, se miran una y otra vez, uno por cada punto de observación anterior.

Es la base teórica de todo lo anterior, y a la vez un algoritmo fuera de línea: \(G_t^\lambda\) no se conoce hasta que el episodio termina, así que no se puede aplicar nada durante el episodio. El libro llama a esto algoritmo del retorno \(\lambda\) fuera de línea y es honesto sobre su papel: “un ideal importante, pero de utilidad limitada”. En una tarea continua, directamente nunca se conoce.

\[ V(S_t) \leftarrow V(S_t) + \alpha\big[\,G_t^{\lambda} - V(S_t)\,\big], \qquad t = 0,\ldots,T-1 \]

Si el problema es que hay que esperar al final, la solución es darle la vuelta a la mirada. En la vista hacia atrás no se mira al futuro desde cada estado: se calcula el error TD del momento y se grita hacia atrás, repartiéndolo entre los estados ya visitados según cuánto haya contribuido cada uno a la situación actual. La imagen del libro es literalmente ésa: ir cabalgando sobre la corriente de estados, calcular \(\delta_t\) y gritárselo a los estados de detrás.

¿Cuánto ha contribuido cada estado? La diapositiva lo plantea con el ejemplo de David Silver: suena el timbre varias veces, se enciende la luz y llega una descarga eléctrica. ¿Qué la ha desencadenado? Una heurística de frecuencia culpa al timbre, que ha ocurrido más veces. Una de recencia culpa a la luz, que ha ocurrido justo antes. Las trazas de elegibilidad combinan las dos, y lo hacen con un único parámetro; cuál de las dos gana es exactamente lo que se puede medir en el módulo siguiente.

\[ z_0(s) = 0, \qquad z_t(s) \;=\; \gamma\lambda\, z_{t-1}(s) + \mathbb{1}(S_t = s) \]

Se lee sin esfuerzo: la traza de todos los estados se desvanece por \(\gamma\lambda\) a cada paso, y la del estado que se acaba de visitar sube 1. La memoria de los pesos es a largo plazo; la traza es una memoria a corto plazo, que normalmente dura menos que un episodio, y cuyo único efecto es decidir a quién le toca aprender cuando llegue un error.

\[ \delta_t \;=\; R_{t+1} + \gamma V(S_{t+1}) - V(S_t) \]

\[ V(s) \leftarrow V(s) + \alpha\,\delta_t\, z_t(s) \qquad \text{para \textit{todos} los } s \]

Con \(\lambda=0\), la traza del paso actual vale 1 y todas las demás valen 0: solo se actualiza el estado inmediatamente anterior, que es TD(0) exactamente. Con \(\lambda=1\) el crédito solo decae por \(\gamma\) a cada paso; y si además \(\gamma=1\), la traza no decae en absoluto y el método se comporta como Monte Carlo en una tarea episódica sin descuento. A ese caso el libro lo llama TD(1), y añade algo que suele omitirse en clase: TD(1) es más general que Monte Carlo, porque también sirve para tareas continuas descontadas y porque aprende durante el episodio en vez de al final.

La diapositiva dice que las dos vistas “son fórmulas equivalentes, demostración disponible en Sutton & Barto”. Conviene precisar, porque el libro afirma algo más débil. Lo que demuestra es que TD(\(\lambda\)) aproxima al algoritmo del retorno \(\lambda\) fuera de línea: con \(\alpha\) óptimo o menor los dos rinden “prácticamente idéntico”, y con \(\alpha\) mayor de lo óptimo TD(\(\lambda\)) empeora mucho más y puede llegar a ser inestable. La igualdad exacta solo se da si las actualizaciones se calculan pero no se aplican durante el episodio —es decir, con los valores congelados—, que es el ejercicio 12.4 del libro. Y hay una equivalencia exacta demostrada de verdad, pero es entre otro par de algoritmos: el retorno \(\lambda\) en línea y true online TD(\(\lambda\)) (§12.5), ninguno de los cuales se ve en esta asignatura.

Es exactamente la misma letra pequeña que la de la identidad (6.6) del capítulo 6, la que escribe \(G_t - V(S_t)\) como suma de errores TD: también allí la igualdad exige que \(V\) no cambie durante el episodio. Dos veces en el mismo tema, y por la misma razón.

Las dos primeras filas coinciden hasta el último decimal porque en este episodio \(V\) no cambia hasta el final. La tercera aplica sus actualizaciones sobre la marcha y por eso se separa. La equivalencia entre las dos vistas es real, pero es esa.

Continúa en el módulo 2 →

Este último tramo adelanta material del Tema 5. Usa el vector de pesos \(w\), el vector de características \(x(s)\) y el gradiente \(\nabla\hat v(s,w)\), que se definen allí. Se incluye porque cierra el bloque y porque explica de dónde sale una constante que, tal como se ha presentado hasta aquí, parece sacada de la nada.

El argumento tiene tres eslabones. Primero: el caso tabular es un caso particular de la aproximación lineal, y el propio libro lo autoriza al abrir el capítulo —“todos estos resultados se aplican también a los casos tabular y de agregación de estados, porque son casos particulares de la aproximación lineal”—. Segundo: en aproximación lineal el gradiente del valor aproximado es el vector de características, \(\nabla\hat v(s,w) = x(s)\). Tercero: si \(x(s)\) es la codificación one-hot del estado —un 1 en la componente de \(s\) y ceros en el resto—, sumar \(x(S_t)\) al vector de trazas es exactamente sumar 1 a la componente del estado visitado y dejar que las demás decaigan. El \(\mathbb{1}(S_t=s)\) de la fórmula tabular es el gradiente.

\[ z_{-1} \doteq 0, \qquad z_t \;\doteq\; \gamma\lambda\,z_{t-1} + \nabla\hat v(S_t, w_t) \]

\[ w_{t+1} \;=\; w_t + \alpha\,\delta_t\, z_t \]

Y con eso queda hecho el enganche con el resto del temario: la actualización de los pesos depende del error TD, y el error TD depende del objetivo, que se construye de una u otra manera según el algoritmo —SARSA, Q-learning, SARSA esperado—. Cambiar de algoritmo es cambiar esa línea y nada más.

Última precisión: la traza de estas fórmulas se llama acumulativa porque el estado visitado suma 1 aunque su traza ya fuera positiva. Hay otras dos. La traza de reemplazo fija la traza a 1 en vez de sumarla, y está definida solo para el caso tabular o para características binarias. La traza dutch es la que usa true online TD(\(\lambda\)) y tiene mejor fundamento teórico; hoy el libro ve la de reemplazo como una aproximación tosca de la dutch. La diapositiva solo usa la acumulativa; en el módulo 2 se puede conmutar a la de reemplazo para ver qué cambia.

El paso es el mismo que el de \(n\) pasos: cambiar estados por pares estado-acción. Hay una traza por par, el error TD se construye con valores de acción, y la actualización se aplica a toda la tabla \(Q\) en proporción a su traza.

\[ z_t(s,a) \;=\; \gamma\lambda\,z_{t-1}(s,a) + \mathbb{1}(S_t=s,\;A_t=a) \]

\[ \delta_t \;\doteq\; R_{t+1} + \gamma\,Q(S_{t+1},A_{t+1}) - Q(S_t,A_t) \]

\[ Q(s,a) \leftarrow Q(s,a) + \alpha\,\delta_t\,z_t(s,a) \qquad \text{para \textit{todos} los pares} \]

SARSA(λ) tabular  —  adaptación del caso lineal de Sutton & Barto §12.7
                      (el libro NO publica una versión tabular; ver el aviso de arriba)
Parámetros: α ∈ (0,1], λ ∈ [0,1], ε > 0, γ
Inicializar Q(s,a) arbitrariamente para todo s ∈ S⁺, a ∈ A(s), con Q(terminal,·) = 0

Para cada episodio:
    z(s,a) ← 0  para todo s, a
    Inicializar S;  elegir A ~ ε-greedy(Q, S)
    Para cada paso del episodio:
        Tomar la acción A, observar R y S'
        Elegir A' ~ ε-greedy(Q, S')      (si S' es terminal, Q(S',·) = 0)
        δ ← R + γ Q(S',A') − Q(S,A)
        z(S,A) ← z(S,A) + 1                        (traza ACUMULATIVA)
        Para todo s, a:
            Q(s,a) ← Q(s,a) + α δ z(s,a)
            z(s,a) ← γλ z(s,a)
        S ← S';  A ← A'
    hasta que S sea terminal

El libro remata con el mismo camino de la figura de SARSA a \(n\) pasos y un cuarto panel: con SARSA(\(\lambda\)) y \(\lambda=0{,}9\) se refuerzan todas las acciones del episodio, con intensidad decreciente hacia atrás. Un paso refuerza una; \(n\) pasos refuerzan \(n\), todas por igual; la traza refuerza todas, desvaneciéndose con la recencia. Y el pie de la figura remata: “la estrategia del desvanecimiento suele ser la mejor”.

Si se quiere practicar con lápiz: el problema 5 de la hoja usa \(\alpha=0{,}1\), \(\gamma=0{,}95\), \(\lambda=0{,}5\) y política \(\varepsilon\)-greedy con \(\varepsilon=0{,}5\) en predicción y \(\varepsilon=0{,}05\) en control. Con esos números y este pseudocódigo, el ejercicio sale.

De Q(\(\lambda\)) —la versión off-policy con trazas— basta saber que existe y que su dificultad propia es qué hacer con la traza cuando la política de comportamiento toma una acción que la política objetivo nunca tomaría: la respuesta clásica es cortarla a cero. El libro lo trata fuera del tramo §12.1-§12.7 que cubre este bloque.

Qué hay que llevarse

• Monte Carlo y TD(0) no son dos métodos rivales: son los dos extremos de una familia con un parámetro. Con \(n\) pasos el parámetro es un entero; con el retorno \(\lambda\), un número entre 0 y 1.
• Con \(n=10\) no se actualiza nada durante los nueve primeros pasos del episodio, y al terminar quedan nueve actualizaciones pendientes. Lo he contado paso a paso.
• El mejor \(n\) es intermedio y depende de \(\alpha\): con la semilla 2026, el mejor punto del barrido es \(n=4\) con \(\alpha=0{,}4\), y el mejor \(\alpha\) de \(n=1\) (0,8) es el peor posible para \(n=64\).
• \(\lambda=0\) es TD(0) y \(\lambda=1\) es Monte Carlo, y lo sé por dos vías: por la forma del retorno \(\lambda\) con la cola separada, y por la forma de la traza.
• Ante la descarga eléctrica, con \(\lambda\) grande la culpa se la lleva el timbre (frecuencia) y con \(\lambda\) pequeño, la luz (recencia). Con tres timbres el empate está en \(\lambda \approx 0{,}544\), y con dos, exactamente en la razón áurea.
• El “+1” de la traza tabular es el gradiente de la aproximación lineal con codificación one-hot: no es una convención, es un caso particular de lo que viene en el Tema 5.