Aproximación de la función de valor

Esta página cubre las 37 diapositivas del tema, pero no en el orden en que se proyectan. Se ha movido una sola cosa, y por una razón: en clase, tile coding (#slide-23 y #slide-24) va detrás del control, porque lo que lo justifica es la tarea de la práctica 3 de #slide-22. Aquí sube al bloque de la representación del estado, junto a la aproximación lineal y al caso tabular, porque es la respuesta a dos preguntas que quedan abiertas arriba: «¿qué alternativas tenemos para construir la señal de estado?» (#slide-9) y «¿hay algún tipo de aproximación en el caso tabular?» (#slide-11). Con tile coding al final, esas dos preguntas se quedan catorce diapositivas sin responder.

La diapositiva pone los ejemplos: ajedrez, Go, conducción autónoma, finanzas. El libro añade el argumento que suele faltar: el problema de un espacio de estados grande no es solo la memoria que ocupa la tabla, sino el tiempo y los datos que hacen falta para rellenarla con precisión. En muchas tareas, casi todos los estados que el agente se encuentra no los ha visto nunca antes, y una tabla no tiene nada que decir sobre un estado nuevo. Aproximar no es una concesión a la memoria: es la única forma de decir algo sobre lo que no se ha visto.

Se sustituye la tabla por una forma funcional con parámetros: \(\hat v(s,w)\) o \(\hat q(s,a,w)\), con \(w \in \mathbb R^d\) y \(d\) mucho menor que el número de estados. Tres arquitecturas posibles, que son las de #slide-5: una que recibe \(s\) y devuelve \(\hat v(s,w)\); otra que recibe el par \((s,a)\) y devuelve \(\hat q(s,a,w)\); y una tercera que recibe \(s\) y devuelve una salida por acción, \(\hat q(s,a_1,w)\dots\hat q(s,a_{|\mathcal A|},w)\) —que es exactamente la de DQN, y es la que hace que el \(\max_a\) cueste una sola pasada—.

El curso se centra en aproximadores diferenciables (#slide-6), y el libro explica por qué no vale cualquier método de aprendizaje supervisado: hay que aprender en línea, con datos que llegan de uno en uno, y con objetivos no estacionarios —el objetivo cambia porque los propios pesos cambian, y porque la política mejora—. Un método que no tolere esa no estacionariedad no sirve aquí.

\[ \hat v(s,w) \approx v_\pi(s) \qquad\text{o}\qquad \hat q(s,a,w) \approx q_\pi(s,a), \qquad w \in \mathbb R^d,\; d \ll |\mathcal S| \]

En el caso tabular no hacía falta ninguna medida de calidad: los valores aprendidos podían acabar siendo exactamente los verdaderos, y estaban desacoplados —actualizar un estado no afectaba a ningún otro—. Con aproximación de verdad, actualizar un estado afecta a muchos, y como hay muchos más estados que pesos, hacer más preciso un estado significa inevitablemente hacer menos precisos otros. Estamos obligados, entonces, a decir qué estados nos importan más.

Eso es \(\mu(s)\): una distribución sobre los estados, \(\mu(s)\ge 0\) y \(\sum_s \mu(s) = 1\), que casi siempre se toma como la fracción del tiempo que se pasa en \(s\). Con ella se escribe el objetivo del tema, el error cuadrático medio de valor. La baraja de Álvaro escribe \(J(w) = \mathbb E_\pi[(v_\pi(S) - \hat v(S,w))^2]\) y no dice bajo qué distribución se toma esa esperanza: es la misma cosa cuando la esperanza se toma bajo \(\mu\), y es Lucía quien lo escribe explícitamente.

\[ \overline{VE}(w) \;\doteq\; \sum_{s\in\mathcal S} \mu(s)\big[v_\pi(s) - \hat v(s,w)\big]^2 \]

Para tareas episódicas, \(\mu\) se calcula contando visitas: si \(h(s)\) es la probabilidad de que un episodio empiece en \(s\), el número esperado de visitas a \(s\) por episodio cumple \(\eta(s) = h(s) + \sum_{\bar s}\eta(\bar s)\sum_a \pi(a\mid\bar s)p(s\mid\bar s,a)\), y \(\mu(s) = \eta(s)/\sum_{s'}\eta(s')\). En el módulo 1 se resuelve ese sistema para el paseo de 1000 estados y se ve la forma de \(\mu\): un triángulo con el pico en el estado de inicio.

→ módulo 1: mueve el número de grupos y mira qué le pasa a \(\sqrt{\overline{VE}}\) y a la escalera de valores.

Si el valor verdadero estuviera disponible, cada estado visitado sería un ejemplo de aprendizaje supervisado \(S_t \mapsto v_\pi(S_t)\) y bastaría con bajar por el gradiente del error cuadrático de ese ejemplo. Al derivar \([v_\pi(S_t)-\hat v(S_t,w_t)]^2\) sale un 2 que se cancela con el \(\tfrac12\), y queda la regla que se usa en todo el tema.

\[ w_{t+1} \doteq w_t - \tfrac12\,\alpha\,\nabla\big[v_\pi(S_t)-\hat v(S_t,w_t)\big]^2 \;=\; w_t + \alpha\big[v_\pi(S_t)-\hat v(S_t,w_t)\big]\nabla\hat v(S_t,w_t) \]

Como no se conoce \(v_\pi\), se pone en su lugar un objetivo \(U_t\), y la regla vale para cualquiera de ellos: \(U_t = G_t\) da Monte Carlo, \(U_t = R_{t+1} + \gamma\hat v(S_{t+1},w_t)\) da TD(0). Si \(U_t\) es un estimador no sesgado de \(v_\pi(S_t)\), \(w_t\) converge a un óptimo local con las condiciones habituales de \(\alpha\).

\[ w_{t+1} \;\doteq\; w_t + \alpha\big[U_t - \hat v(S_t,w_t)\big]\,\nabla\hat v(S_t,w_t) \]

Con un objetivo que hace bootstrapping —el de TD, el de \(n\) pasos, el de DP— el objetivo depende del propio \(w_t\), y ahí se rompe el paso de la primera fórmula a la segunda, que suponía un objetivo independiente de \(w\). La actualización tiene en cuenta el efecto de cambiar \(w\) sobre la estimación, pero ignora su efecto sobre el objetivo: incluye solo una parte del gradiente. Por eso se llaman métodos semi-gradiente, y por eso no son el gradiente de ninguna función objetivo: no se pueden apoyar en los resultados clásicos de convergencia del descenso estocástico.

La contrapartida es la de siempre: los métodos semi-gradiente no convergen tan robustamente, pero convergen con fiabilidad en los casos importantes —el lineal, entre ellos—, aprenden mucho más rápido y permiten aprender en línea sin esperar al final del episodio. En la baraja de Álvaro la palabra «semi-gradiente» solo aparece dentro del título en inglés de la caja de #slide-19 y en la anotación manuscrita de clase; el concepto está desarrollado en Lucía, Tema5_1_Aproximacion#slide-14.

La diapositiva lanza cuatro preguntas y no responde ninguna en pantalla. Se responden en clase, a mano. Son estas:

El libro añade un matiz que conviene tener a mano: la aproximación de funciones hace el RL aplicable a problemas parcialmente observables, pero lo que no puede hacer es aumentar la representación del estado con memoria del pasado. Apilar cuatro fotogramas, como en DQN, es exactamente eso: ampliar la señal a mano para que se parezca más a un estado de Markov.

A cada estado se le asocia un vector de características \(x(s) = (x_1(s),\dots, x_d(s))^\top\), con tantas componentes como pesos, y el valor aproximado es el producto escalar. Cada \(x_i\) es una función \(x_i:\mathcal S\to\mathbb R\); en el caso lineal las características son funciones base, porque forman una base lineal del conjunto de funciones aproximables.

\[ \hat v(s,w) \doteq w^\top x(s) = \sum_{i=1}^{d} w_i\,x_i(s), \qquad \nabla\hat v(s,w) = x(s) \]

Que el gradiente sea el propio vector de características es lo que hace tan simple el caso lineal, y es el paso que #slide-10 deja en blanco. Sustituyéndolo en la regla genérica queda la regla que se usa en todo el tema:

\[ w_{t+1} \;\doteq\; w_t + \alpha\big[U_t - \hat v(S_t,w_t)\big]\,x(S_t) \]

En el caso lineal hay un solo óptimo (o, en casos degenerados, un conjunto de óptimos igual de buenos), así que cualquier método con garantía de converger a un óptimo local queda automáticamente garantizado a converger al global. Es la razón por la que casi todos los resultados de convergencia útiles del RL son para aproximación lineal o más simple, y es la razón por la que la columna «Lineal» de las tablas de #slide-16 tiene tantos «SÍ».

Tómese \(x(s) = e_s\), el vector con un 1 en la posición de \(s\) y ceros en el resto —one-hot—. Entonces \(\hat v(s,w) = w_s\), \(\nabla\hat v(s,w) = e_s\), y la regla lineal se convierte en \(w_s \leftarrow w_s + \alpha[U_t - w_s]\): literalmente la actualización tabular de los temas 3 y 4. El caso tabular no es otra cosa: es aproximación lineal con \(d = |\mathcal S|\).

#slide-11 pregunta: «¿Consideras que hay algún tipo de aproximación?». No la hay: con one-hot los pesos pueden reproducir \(v_\pi\) exactamente, así que \(\min_w \overline{VE} = 0\) y no hay ningún error que repartir entre estados. La aproximación aparece en el momento en que se agrupan estados —que es la respuesta que se da en clase—: eso es la agregación de estados, un peso por grupo, y es el primer aproximador de verdad del tema.

\[ x(s) = e_s \;\Longrightarrow\; \hat v(s,w) = w_s,\quad \nabla\hat v(s,w) = e_s,\quad w_s \leftarrow w_s + \alpha\big[U_t - w_s\big] \]

La agregación de estados es un caso particular de la regla general en el que el gradiente vale 1 en la componente del grupo de \(S_t\) y 0 en las demás. Es decir: es one-hot, pero sobre grupos en lugar de sobre estados.

→ módulo 2: cambia la representación y mira qué componentes de \(x(s)\) se encienden y a qué estados salpica una sola actualización.

Antes de los mosaicos, la idea general: la codificación gruesa (coarse coding) usa características binarias asociadas a campos receptivos solapados. Dado un estado, las características que valen 1 dicen dentro de qué campos cae, y eso codifica su posición. Cuánto generaliza una actualización de \(s\) a \(s'\) depende de cuántos campos receptivos comparten. El tamaño y la forma de los campos controlan la generalización inicial; la precisión final —la discriminación más fina posible— la controla más el número total de características, no su anchura.

Tile coding es la forma de codificación gruesa para espacios continuos multidimensionales que resulta práctica de calcular. Los campos receptivos se agrupan en particiones del espacio de estados: cada partición se llama un mosaicado (tiling) y cada elemento de la partición, un mosaico (tile). Con \(m\) mosaicados desplazados entre sí, cada estado cae en exactamente un mosaico de cada mosaicado, así que hay exactamente \(m\) características activas, siempre, para cualquier estado.

Que el número de características activas sea siempre el mismo permite fijar \(\alpha\) de forma intuitiva. Con \(\alpha = 1/m\) se consigue aprendizaje exacto en un solo ensayo: si se entrena el ejemplo \(s\mapsto u\), sea cual fuera la estimación previa, la nueva es exactamente \(u\). Normalmente se quiere ir más despacio, para dejar sitio a la generalización y al ruido de los objetivos: con \(\alpha = 1/(10m)\) la estimación del estado entrenado se mueve exactamente una décima parte del camino hacia el objetivo, y los estados vecinos se mueven menos, en proporción al número de mosaicos que comparten.

\[ \alpha \;\doteq\; \big(\tau\,\mathbb E[x^\top x]\big)^{-1} \;\stackrel{\text{tile coding}}{=}\; \frac{1}{\tau\,m} \]

La primera igualdad es la regla general del libro para métodos lineales, con \(\tau\) = el número de experiencias con el mismo vector de características en las que se quiere aprender. La segunda vale porque con tile coding las características son binarias y hay exactamente \(m\) activas, luego \(x^\top x = m\) es constante. De ahí salen el \(1/m\) y el \(1/(10m)\) de arriba, con \(\tau=1\) y \(\tau=10\). Y de ahí sale también que las figuras del libro escriban \(\alpha\) como \(0{,}5/8\) o rotulen el eje «\(\alpha\times\) número de mosaicados (8)»: están normalizando por \(m\).

Los mosaicados se desplazan entre sí una fracción del ancho de mosaico. Si \(\ell\) es el ancho y \(m\) el número de mosaicados, \(\ell/m\) es la unidad fundamental: dentro de un cuadrado de lado \(\ell/m\) todos los estados activan los mismos mosaicos y tienen el mismo valor aproximado. Si todos los mosaicados se desplazan por igual en cada dimensión —vector de desplazamiento \((1,1)\)— la generalización sale con artefactos diagonales y varía mucho de un punto a otro; ésa es la mitad superior de la figura de #slide-24. Con desplazamientos asimétricos la generalización sale más esférica y homogénea: es la mitad inferior. La receta del libro para un espacio de dimensión \(k\) es usar los primeros enteros impares \((1,3,5,\dots,2k-1)\) con \(m\) igual a una potencia de 2 mayor o igual que \(4k\); para \(k=2\), eso es \(m=8\) y el vector \((1,3)\), que es exactamente lo que usa Mountain Car en el módulo 5.

Dos cosas más que la figura no dice. Una: la ventaja de cálculo. Como las características son 0 o 1, el producto escalar no cuesta \(d\) multiplicaciones: se calculan los índices de las \(m \ll d\) características activas y se suman \(m\) pesos. Dos: el hashing, un colapso pseudoaleatorio y consistente de un mosaicado grande en un conjunto pequeño de mosaicos; produce mosaicos formados por trozos dispersos, pero sigue siendo una partición, y reduce la memoria mucho con poca pérdida. Es lo que libera a tile coding de la maldición de la dimensionalidad: la memoria no tiene que ser exponencial en el número de dimensiones, solo tiene que ajustarse a lo que la tarea pide de verdad.

→ módulo 2, segunda mitad: sube el número de mosaicados y mira cómo cambia el perfil de generalización.

#slide-12 avisa de lo que cambia: hasta aquí las fórmulas contenían el valor real al que hay que aproximarse, pero RL no es aprendizaje supervisado —solo se dispone de la recompensa—. Así que en \(U_t\) se pone lo que sí se tiene. Con Monte Carlo, el retorno observado; con TD(0), la recompensa más el valor estimado del estado siguiente.

\[ \text{MC gradiente:}\quad \Delta w = \alpha\big[G_t - x(S_t)^\top w\big]\,x(S_t) \] \[ \text{TD(0) semi-gradiente:}\quad \Delta w = \alpha\big[R_{t+1} + \gamma\,x(S_{t+1})^\top w - x(S_t)^\top w\big]\,x(S_t) \]

Las listas de muestras de entrenamiento de #slide-13 y #slide-14 son exactamente esto, escrito como pares entrada-objetivo: \(\langle S_0,G_0\rangle,\dots,\langle S_{T-1},G_{T-1}\rangle\) para MC, y \(\langle S_0, R_1+\gamma\hat v(S_1,w)\rangle,\dots, \langle S_{T-1},R_T\rangle\) para TD(0). Fíjate en el último par de la lista de TD: no lleva bootstrapping. La razón es que \(\hat v(\text{terminal},w) = 0\) por definición, algo que la caja del libro exige explícitamente y que la baraja no dice en ninguna parte.

\[ \hat v(\text{terminal},w) \;=\; 0 \quad\text{siempre, para todo } w \]

#slide-13 dice que MC converge al óptimo global en el caso lineal, y es cierto: el retorno es un estimador no sesgado de \(v_\pi(S_t)\), la regla es descenso del gradiente de verdad, y en el caso lineal el óptimo local es el global. #slide-14 dice que TD(0) converge a un punto cercano al óptimo global; eso es una simplificación didáctica de algo más preciso, y es el bloque siguiente.

→ módulo 3: las dos reglas sobre el mismo entorno, con los mismos episodios y la misma semilla.

«Cercano» tiene una medida exacta, y no está en la baraja. En el caso lineal continuo, la actualización de TD(0) en esperanza se escribe con dos objetos: una matriz \(A\) y un vector \(b\). TD(0) lineal converge al punto donde \(b - Aw = 0\), que se llama punto fijo TD.

\[ A \doteq \mathbb E\big[x_t(x_t - \gamma x_{t+1})^\top\big], \qquad b \doteq \mathbb E\big[R_{t+1}\,x_t\big], \qquad w_{TD} \doteq A^{-1}b \]

Ese punto no es el óptimo global de \(\overline{VE}\), y el libro acota cuánto peor puede ser: el error asintótico de TD no pasa de \(1/(1-\gamma)\) veces el error mínimo posible, que es el que alcanza Monte Carlo en el límite.

\[ \overline{VE}(w_{TD}) \;\le\; \frac{1}{1-\gamma}\,\min_w \overline{VE}(w) \]

Tres cosas más que el libro añade y que sirven para leer las tablas del módulo 6: la misma cota vale para DP semi-gradiente cuando las actualizaciones siguen la distribución on-policy; vale, con una cota análoga, para SARSA(0) semi-gradiente —con política constante—; y es crítico que las actualizaciones sigan la distribución on-policy: con otras distribuciones, los métodos con bootstrapping y aproximación pueden divergir a infinito. Ése es el bloque siguiente.

→ módulo 3: los dos puntos de convergencia se calculan exactos y se dibujan como dos líneas horizontales sobre las curvas de aprendizaje.

#slide-15 proyecta una figura del libro con los pesos disparándose y una línea de texto: «Evolución de los pesos en el contraejemplo de Baird (predicción TD)». No dice qué MDP es el de Baird, ni que el entrenamiento es off-policy, ni por qué divergen los pesos. Es la afirmación más fuerte del tema apoyada en la figura más muda, así que empezamos por el ejemplo más pequeño que existe, que sí se sigue a mano.

Dos estados y un solo peso. El primer estado tiene valor estimado \(w\) y el segundo \(2w\) —es decir, características escalares \(x=1\) y \(x=2\)—. Del primero sale una única acción, que lleva determinísticamente al segundo con recompensa 0. El error TD de esa transición es \(\delta = 0 + \gamma\cdot 2w - w = (2\gamma-1)w\), y la actualización semi-gradiente deja:

\[ w_{t+1} \;=\; w_t + \alpha\,\delta_t\,\nabla\hat v(S_t,w_t) \;=\; w_t + \alpha(2\gamma-1)w_t\cdot 1 \;=\; \big(1 + \alpha(2\gamma-1)\big)\,w_t \]

Si ese factor pasa de 1, el sistema es inestable y \(w\) se va a \(+\infty\) o a \(-\infty\) según su valor inicial. Y pasa de 1 exactamente cuando \(\gamma > 0{,}5\). Lo importante: la estabilidad no depende del tamaño de paso, mientras \(\alpha > 0\). Un \(\alpha\) más pequeño cambia la velocidad a la que \(w\) se va a infinito, no si se va.

La clave del ejemplo es que esa transición ocurre repetidamente sin que \(w\) se actualice en las demás transiciones. Eso es posible off-policy, porque la política de comportamiento puede elegir, en esas otras transiciones, acciones que la política objetivo nunca elegiría: para ellas la razón de importancia es cero y no se actualiza nada. On-policy, esa razón vale siempre uno. Como lo dice el libro: al final, al gaitero hay que pagarle. On-policy, la promesa de recompensa futura hay que cumplirla y el sistema se mantiene a raya; off-policy se puede prometer y luego, tras tomar una acción que la política objetivo nunca tomaría, olvidar y perdonar.

El contraejemplo de Baird es este mismo mecanismo, completo y sin trucos. Un MDP episódico de siete estados y dos acciones; la acción de trazo discontinuo lleva a uno de los seis estados superiores con igual probabilidad, la de trazo continuo lleva al séptimo. La política de comportamiento elige la discontinua 6 de cada 7 veces, de modo que la distribución del estado siguiente es uniforme; la política objetivo elige siempre la continua, y su distribución está concentrada en el séptimo estado. La recompensa es cero en todas las transiciones, \(\gamma = 0{,}99\), y hay ocho pesos para siete estados no terminales, con características linealmente independientes: el valor verdadero es \(v_\pi(s)=0\) para todo \(s\) y se puede representar exactamente con \(w=0\). Todo favorable. Y aun así, con \(\alpha = 0{,}01\) y \(w_0 = (1,1,1,1,1,1,10,1)^\top\), los pesos divergen.

Dos cosas que suelen sorprender. No es cuestión del tamaño de paso: la inestabilidad ocurre para cualquier \(\alpha>0\), por pequeño que sea. Y no es cuestión de muestreo ni de asincronía: con actualizaciones de DP semi-gradiente —que barren todos los estados, sin nada de azar, exactamente como una barrida clásica de programación dinámica— el sistema sigue siendo inestable. Lo que lo arregla no es el algoritmo: es la distribución. Si en el contraejemplo de Baird se cambia solo la distribución de las actualizaciones, de uniforme a la distribución on-policy, la convergencia queda garantizada con el error acotado por la cota del bloque anterior.

→ módulo 4: mueve \(\gamma\) por encima y por debajo de 0,5, y después mueve \(\alpha\) para comprobar que no cambia nada.

El peligro de inestabilidad y divergencia aparece cuando se combinan los tres elementos siguientes, y no antes:

Si están presentes dos cualesquiera de los tres, pero no los tres, la inestabilidad se puede evitar. Así que lo natural es preguntarse cuál se puede soltar. La aproximación, no: hace falta escalar, y la agregación o los métodos no paramétricos son demasiado débiles o demasiado caros —los de mínimos cuadrados, como LSTD, son de complejidad cuadrática y por tanto demasiado caros para problemas grandes—. El bootstrapping se puede soltar, pero se paga en eficiencia de cálculo y de datos, y es demasiado valioso. Queda el off-policy, y ahí el libro da la receta concreta para el RL sin modelo: usar SARSA en lugar de Q-learning. Que es exactamente lo que dice la tabla de control de #slide-21, donde SARSA lineal es «(SÍ)» y Q-learning lineal es «NO».

Álvaro llama a estos tres «inductores de inestabilidad», y es el nombre que usa esta página. En el libro y en las diapositivas de Lucía se llaman «la tríada mortal» (deadly triad); es el mismo trío, y conviene reconocer las dos etiquetas porque el examen y la bibliografía pueden usar cualquiera de ellas.

→ módulo 6: enciende y apaga los tres inductores y mira en qué casilla caes, con la cita del libro que la sostiene.

La extensión a valores de acción es directa: donde antes había ejemplos \(S_t \mapsto U_t\), ahora hay ejemplos \(S_t,A_t \mapsto U_t\), y el objetivo \(U_t\) puede ser cualquier aproximación de \(q_\pi(S_t,A_t)\) —el retorno completo de Monte Carlo, o cualquiera de los retornos de SARSA a \(n\) pasos—. La respuesta al ejercicio de #slide-18 son estas cuatro líneas:

\[ \hat q(S,A,w) \approx q_\pi(S,A), \qquad J(w) = \mathbb E_\pi\big[\big(q_\pi(S,A)-\hat q(S,A,w)\big)^2\big] \] \[ -\tfrac12\nabla_w J(w) = \mathbb E_\pi\big[\big(q_\pi(S,A)-\hat q(S,A,w)\big)\nabla_w \hat q(S,A,w)\big] \] \[ \Delta w = \alpha\big(q_\pi(S,A)-\hat q(S,A,w)\big)\,\nabla_w \hat q(S,A,w) \qquad\text{(la versión muestral)} \]

En el caso lineal, \(\hat q(s,a,w) \doteq w^\top x(s,a)\), con un vector de características por cada par estado-acción. Y para hacer control hace falta acoplar esto con la mejora de la política: si el conjunto de acciones es discreto y no demasiado grande, se calcula \(\hat q(S_t,a,w_t)\) para cada acción disponible, se toma \(A^*_t = \arg\max_a \hat q(S_t,a,w_t)\) y se hace la política \(\varepsilon\)-greedy sobre eso.

\[ \hat q(s,a,w) \doteq w^\top x(s,a) = \sum_{i=1}^{d} w_i\,x_i(s,a) \]

SARSA semi-gradiente episódico, para estimar q̂ ≈ q_*

Entrada: una parametrización derivable q̂ : S × A × R^d → R
Parámetros: paso α > 0, exploración ε > 0 pequeña
Inicializar los pesos w ∈ R^d arbitrariamente (p. ej. w = 0)

Repetir para cada episodio:
    S, A ← estado y acción iniciales del episodio (p. ej. ε-greedy)
    Repetir para cada paso del episodio:
        Tomar la acción A; observar R, S′
        Si S′ es terminal:
            w ← w + α[R − q̂(S,A,w)] ∇q̂(S,A,w)
            pasar al episodio siguiente
        Elegir A′ en función de q̂(S′,·,w)   (p. ej. ε-greedy)
        w ← w + α[R + γ q̂(S′,A′,w) − q̂(S,A,w)] ∇q̂(S,A,w)
        S ← S′
        A ← A′

Detalle que se pierde al resumir y que hay que respetar al implementar: el caso terminal tiene su propia línea, sin el término \(\gamma\hat q(S',A',w)\). Es la misma condición de \(\hat v(\text{terminal},w)=0\) del bloque de predicción, escrita para \(q\).

#slide-20 es una diapositiva con el enunciado y la pantalla vacía: «Identifica las líneas que difieren de SARSA y define cómo serían para Q-learning». Difieren dos, y en realidad es una sola idea. La línea «Elegir \(A'\)» deja de existir como elección de la acción a ejecutar: en Q-learning esa acción no se toma, solo se usa para el objetivo. Y el objetivo pasa de \(\hat q(S',A',w)\) —la acción realmente elegida por la política de comportamiento— a \(\max_a \hat q(S',a,w)\).

\[ \text{SARSA:}\quad w \leftarrow w + \alpha\big[R + \gamma\,\hat q(S',A',w) - \hat q(S,A,w)\big]\nabla\hat q(S,A,w) \] \[ \text{Q-learning:}\quad w \leftarrow w + \alpha\big[R + \gamma\,\max_a \hat q(S',a,w) - \hat q(S,A,w)\big]\nabla\hat q(S,A,w) \]

Ese \(\max\) es lo que convierte el método en off-policy, y por tanto lo que le añade el tercer inductor de B12. En el caso lineal, con \(\nabla\hat q(S,A,w) = x(S,A)\), las dos reglas se escriben \(\Delta w = \alpha\,\delta\,x(S,A)\), con el \(\delta\) que corresponda.

En el caso tabular, la traza se incrementaba en 1 en la casilla del par visitado y se desvanecía en las demás. Ese 1 no es un valor arbitrario: 4_Tema4_2#slide-16 dice que es el gradiente de la función de valor en el caso de aproximación lineal con codificación one-hot de los estados. Es exactamente el argumento de #slide-11 —el caso tabular es aproximación lineal con one-hot— contado del revés. Y leído así, la generalización es inmediata: donde había un 1, va el gradiente.

\[ z_{-1} \doteq 0, \qquad z_t \doteq \gamma\lambda\,z_{t-1} + \nabla\hat q(S_t,A_t,w_t) \;=\; \gamma\lambda\,z_{t-1} + x(S_t,A_t), \qquad w_{t+1} \doteq w_t + \alpha\,\delta_t\,z_t \]

De ahí sale lo único que hay que memorizar de este bloque: \(z_t\) vive en el espacio de los pesos. Tiene la misma dimensión que \(w\), es decir \(d\), y no \(|\mathcal S|\times|\mathcal A|\). Con aproximación no hay una casilla por par estado-acción: hay \(d\) pesos, y la traza lleva un número por peso, que dice cuánto ha contribuido ese peso a lo que se acaba de vivir. Si en el examen escribes una traza del tamaño de la tabla, has vuelto al tema 4.

Dos formas de acumular la visita, las mismas que en el caso tabular. La acumulativa suma el gradiente, \(z_t = \gamma\lambda z_{t-1} + x(S_t,A_t)\): si una componente se repite, su traza pasa de \(1\) a \(1+\gamma\lambda\). La de reemplazo desvanece primero y después pone a 1 las componentes activas, así que una componente repetida se queda en 1. La de reemplazo está definida para características binarias —el caso de tile coding— y es la que se usa con mosaicos; con características de valor real, como las del ejemplo de abajo, la que aplica es la acumulativa.

Dos detalles de implementación que son también detalles conceptuales. Uno: la traza se reinicia a cero al empezar cada episodio; no arrastra crédito de un episodio al siguiente, porque el anterior ya terminó. Dos: con \(\lambda = 0\) la recurrencia se queda en \(z_t = x(S_t,A_t)\) y la actualización de pesos es \(w \leftarrow w + \alpha\delta_t\,x(S_t,A_t)\), que es exactamente el algoritmo de un paso de B14. No parecido: el mismo, peso a peso.

Resuelto al estilo del examen

Un robot que navega hacia un objetivo. La observación son seis variables —posición en \(x\), posición en \(y\), distancia mínima a un obstáculo, demora del obstáculo, distancia al objetivo y demora del objetivo— y hay tres acciones: avanzar (\(A_0\)), girar 90° a la izquierda (\(A_1\)) y girar 90° a la derecha (\(A_2\)). Ésta es la evolución de la observación, y no hay más datos que éstos:

Paso 1: construir \(x(s,a)\). Las seis variables van al bloque de la acción tomada y los otros dos bloques van a cero. Tres acciones × seis variables ⟹ \(d = 18\) pesos, que se almacenan como un vector de 18 o como una matriz \(3\times 6\), una fila por acción. Y las trazas, exactamente igual: 18. Ésa es la respuesta a los dos apartados que preguntan por dimensiones y almacenamiento.

Paso 2: leer las acciones de la tabla. De \(t=0\) a \(t=1\) la posición cambia (\(x_0: 2\to 3\)) y la distancia al objetivo baja: el robot avanzó, \(A_0\). De \(t=1\) a \(t=2\) no cambia ni una de las seis variables: las demoras son respecto al norte en un sistema de referencia estático, así que girar no cambia ninguna ⟹ fue un giro. De \(t=2\) a \(t=3\) la posición vuelve a cambiar: avanzó otra vez, \(A_0\).

Paso 3: la recurrencia. Con \(\gamma = 0{,}9\) y \(\lambda = 0{,}5\), \(\gamma\lambda = 0{,}45\). Traza acumulativa —las características son de valor real— y \(z = 0\) antes de empezar.

Primera actualización (la que el enunciado llama \(t=1\)): \(z = 0{,}45\cdot 0 + x(S_0,A_0) = x(S_0,A_0)\), es decir el bloque de \(A_0\) con la columna \(t=0\), \((2,\,2,\,2,\,0,\,4{,}2,\,45)\), y cero en los bloques de \(A_1\) y \(A_2\).

Segunda actualización (\(t=2\)): \(z = 0{,}45\cdot z_{\text{anterior}} + x(S_1,A_1)\). El primer término desvanece el bloque de \(A_0\): \(0{,}45\cdot(2,\,2,\,2,\,0,\,4{,}2,\,45) = (0{,}9,\,0{,}9,\,0{,}9,\,0,\,1{,}89,\,20{,}25)\). El segundo suma la columna \(t=1\) en el bloque del giro: \((3,\,2,\,2,\,0,\,3{,}6,\,33{,}7)\).

Dieciocho números, diez de ellos no nulos, y ni uno solo indexado por estado. Dos comprobaciones más del mismo enunciado, que salen gratis: el gradiente en \(t=2\) es \(\nabla_w\hat q(S_2,A_2,w) = x(S_2,A_2)\), donde \(A_2\) es la acción tomada en \(t=2\) —avanzar, porque la posición cambia en \(t=3\)—, o sea la columna \(t=2\) escrita en el bloque de avanzar; y con todos los pesos inicializados a 2, \(\hat q(S_2,A_2,w) = 2\cdot(3+2+2+0+3{,}6+33{,}7) = 2\cdot 44{,}3 = \mathbf{88{,}6}\).

→ módulo 5: sube \(\lambda\) por encima de 0 sobre Mountain Car y mira qué cambia en las curvas —y qué no.

#slide-26 pregunta: «¿Cómo es el ciclo de vida de la experiencia que nos llega?». La respuesta —que en la baraja de Álvaro no está, y sí en Lucía— es breve: cada dato se usa una sola vez. Se genera una transición, se hace una actualización, y se tira. De ahí las dos motivaciones del bloque: eficiencia de datos —reutilizar lo ya vivido— y correlaciones, porque las muestras consecutivas de una trayectoria no son independientes.

La idea de la predicción por mínimos cuadrados es: guardar un conjunto de experiencia \(\mathcal D\) y buscar los pesos que minimizan el error sobre todo \(\mathcal D\), no sobre la última muestra. Y la repetición de experiencia (experience replay) es la forma incremental de hacerlo: muestrear al azar de \(\mathcal D\) y aplicar la regla de siempre; en el límite, eso converge a la solución de mínimos cuadrados.

\[ \mathcal D = \big\{\langle s_1, v_1^\pi\rangle, \dots, \langle s_T, v_T^\pi\rangle\big\}, \qquad LS(w) = \sum_{t=1}^{T}\big(v_t^\pi - \hat v(s_t,w)\big)^2, \qquad w^\pi = \arg\min_w LS(w) \]

En el caso lineal la condición de óptimo es que el incremento esperado sea cero, y de ahí sale la ecuación normal. Las dos colecciones llegan hasta aquí y se paran, aunque el texto prometa que «podemos calcular directamente el valor de \(w\)». La solución cerrada es ésta:

\[ \mathbb E_{\mathcal D}[\Delta w] = 0 \;\Longleftrightarrow\; \alpha\sum_{t=1}^{T} x(s_t)\big(v_t^\pi - x(s_t)^\top w\big) = 0 \;\Longrightarrow\; w = \Big(\sum_{t=1}^{T} x(s_t)x(s_t)^\top\Big)^{-1}\sum_{t=1}^{T} x(s_t)\,v_t^\pi \]

Invertir esa matriz cuesta \(O(d^3)\) en general, con \(d\) el número de pesos. Pero es una suma de productos externos, y su inversa se puede actualizar de forma incremental con la fórmula de Sherman-Morrison, que solo tiene productos matriz-vector y vector-vector: \(O(d^2)\). Compárese con el \(O(d)\) por paso de TD(0) semi-gradiente.

Lo que el libro tiene de esto se llama LSTD (Least-Squares TD, §9.8): estimar \(A\) y \(b\) con las sumas muestrales y calcular directamente el punto fijo TD, \(w_t = \hat A_t^{-1}\hat b_t\). Es la forma más eficiente en datos de TD(0) lineal, y es más caro de calcular. Y tiene tres peros que suelen omitirse: no necesita \(\alpha\), pero sí necesita un \(\varepsilon\) de regularización —si es demasiado pequeño la sucesión de inversas oscila salvajemente, si es demasiado grande el aprendizaje se frena—; nunca olvida, lo que es un problema cuando la política objetivo cambia, como pasa en control; y por eso, en aplicaciones de control, LSTD suele necesitar algún mecanismo añadido que induzca olvido, con lo que la ventaja inicial de no tener paso se desvanece.

Lo primero, para no perderse: DQN no es un algoritmo nuevo. Es Q-learning semi-gradiente con una red convolucional profunda como aproximador, más tres añadidos de ingeniería. La actualización base es la del bloque B14, con la red calculando \(\hat q\) y el gradiente por retropropagación:

\[ w_{t+1} = w_t + \alpha\big[R_{t+1} + \gamma\max_a \hat q(S_{t+1},a,w_t) - \hat q(S_t,A_t,w_t)\big]\nabla\hat q(S_t,A_t,w_t) \]

Y hay una razón concreta para que sea Q-learning y no SARSA: la repetición de experiencia exige un algoritmo off-policy. Al muestrear transiciones sueltas de un búfer, ya no se está siguiendo una trayectoria conectada con la política actual, y solo un método off-policy puede aprender de eso. Ser sin modelo y off-policy hacía de Q-learning la elección natural.

La red: tres capas convolucionales ocultas, después una capa oculta totalmente conectada, después la capa de salida. Las tres convolucionales producen 32 mapas de características de 20×20, 64 de 9×9 y 64 de 7×7, con rectificador \(\max(0,x)\) como activación; las 3.136 unidades de la tercera (64×7×7) se conectan a 512 unidades totalmente conectadas, y ésas a 18 unidades de salida, una por acción posible en un juego de Atari. La entrada son los cuatro últimos fotogramas preprocesados a 84×84 valores de luminancia, es decir 84×84×4: los fotogramas se apilan porque el estado completo de muchos juegos no es observable en una sola imagen, y apilar cuatro los hace más markovianos —que es exactamente la respuesta a la tercera pregunta de B5—.

Cada salida es el valor de acción estimado del par correspondiente; como el número de acciones válidas iba de 4 a 18 según el juego, no todas las salidas tenían función en todos los juegos. Ayuda pensar en la red como 18 redes separadas que comparten las primeras capas: la retropropagación de una actualización se aplica solo a la salida de la acción que se tomó.

DQN aprendió una política distinta para cada uno de 49 juegos de Atari 2600 —los pesos se reinicializaban en cada juego— pero con la misma entrada, la misma arquitectura y los mismos hiperparámetros en todos. Cada juego, 50 millones de fotogramas de interacción, unos 38 días de experiencia. Jugó mejor que el mejor sistema de RL anterior en todos menos 6, y mejor que el jugador humano profesional en 22; tomando como «nivel humano» el 75 % de la puntuación humana, alcanzó o superó ese nivel en 29 juegos. Y en la ablación —repetición de experiencia y red objetivo, con las cuatro combinaciones de estar o no estar, sobre 5 de los juegos— cada una de las dos por separado mejoró significativamente el rendimiento, y juntas lo mejoraron de forma espectacular.

DQN demostró que un solo agente puede aprender las características específicas de cada problema y alcanzar habilidad competitiva con la humana en un rango de tareas. No produjo un agente que destacara en todas a la vez —el aprendizaje era separado para cada juego—, y en algunos juegos se quedó muy por debajo del nivel humano: los más difíciles para DQN, como Montezuma's Revenge —donde aprendió a jugar más o menos como el jugador aleatorio—, exigen planificación profunda, que es algo para lo que DQN no está diseñado.

Aviso práctico, porque esto sale en el examen final y está a caballo entre dos temas. El problema práctico del final pide, sobre un robot con tres acciones y aproximación lineal: cuántos pesos hacen falta y cómo se almacenan, las acciones que tomó el agente, \(\nabla_w \hat q(S,A,w)\) y \(\hat q(S,A,w)\) en un instante dado, las dimensiones y el almacenamiento de las trazas de elegibilidad, y los pesos y las trazas en el paso siguiente. La construcción de \(x(s,a)\) es de este tema —B13 y B14—; las trazas con aproximación son del tema 4.3, y están resueltas en B14b, con el ejemplo numérico completo.

Los apartados, y dónde está cada respuesta. Cuántos pesos y cómo se almacenan: B13 y B14, y resuelto con \(d=18\) en B14b. Qué acciones tomó el agente: se leen de la tabla de la observación, B14b. \(\nabla_w\hat q(S,A,w)\): es \(x(S,A)\), B6 y B14. \(\hat q(S,A,w)\): el producto escalar, con el número hecho en B14b. Dimensiones y almacenamiento de las trazas: B14b, y la respuesta es \(d\). Las trazas en el paso siguiente: la recurrencia de B14b, resuelta paso a paso.

Lo que no entra en esta página, y está publicado: el dilema frecuencia/recencia de las trazas, el retorno \(\lambda\), TD(λ) hacia adelante y la equivalencia entre las dos vistas. Todo eso es la segunda página del tema 4 y el capítulo 12 del libro. Aquí entra exactamente lo que el examen pide con aproximación, y nada más.

El tema se cierra donde el libro pone el límite: con acciones continuas o conjuntos de acciones muy grandes, el \(\arg\max_a \hat q(s,a,w)\) deja de ser calculable y no hay solución cerrada. La salida es dejar de aproximar el valor y aproximar directamente la política, con su propio vector de parámetros —que es \(\theta\), el símbolo que este tema ha estado protegiendo—. Ése es el tema 6.

Qué hay que llevarse

• Con \(d\) pesos y \(|\mathcal S|\) estados no se puede acertar en todos: el módulo 1 lo enseña con 1000 estados y 10 pesos, y el valor de cada grupo resulta ser la media de los valores verdaderos ponderada por \(\mu\), no la media sin más.
• El caso tabular es aproximación lineal con \(x(s)\) one-hot, y ahí \(\min_w\overline{VE}=0\): en el módulo 2, con un grupo por estado, el error baja exactamente a cero.
• Con \(m\) mosaicados hay exactamente \(m\) características activas para cualquier estado, y por eso \(\alpha\) se divide por \(m\): con \(\alpha=1/m\) el estado entrenado alcanza el objetivo en un solo paso.
• Monte Carlo y TD(0) no convergen al mismo sitio: en el módulo 3 las dos asíntotas se calculan exactas y se dibujan, y la de TD queda por encima.
• Los pesos pueden divergir, y no es culpa de \(\alpha\): en el módulo 4, con \(\gamma>0{,}5\) el factor de crecimiento pasa de 1 para cualquier \(\alpha>0\), y mover \(\alpha\) solo cambia la pendiente.
• La inestabilidad necesita los tres inductores a la vez; con dos, no. En el módulo 6 se apaga uno cualquiera y la casilla cambia de veredicto.
• En control, la única línea que separa SARSA de Q-learning es el objetivo (\(\hat q(S',A',w)\) frente a \(\max_a\hat q(S',a,w)\)), y eso es lo que le añade el tercer inductor: en el módulo 5 se conmutan las dos sobre el mismo Mountain Car y la misma semilla.
• La traza de elegibilidad con aproximación tiene la dimensión de \(w\), no la de la tabla: en el ejemplo resuelto de B14b son 18 números para tres acciones y seis variables, y en el módulo 5 son 1944, los mismos que pesos. Y con \(\lambda = 0\) el algoritmo es exactamente el de un paso.