Aprendizaje por refuerzo sin modelo

Los tres temas anteriores han tenido siempre el mismo suelo debajo: la dinámica \(p(s',r\mid s,a)\). Con ella se escriben las ecuaciones de Bellman, y con ellas la programación dinámica calcula \(v_\pi\), \(v_*\) y una política óptima sin interactuar ni una vez con el entorno. A partir de aquí ese suelo desaparece.

El libro no plantea la distinción como “con modelo / sin modelo”, sino como algo más fino: distribución explícita frente a muestras. Aprender de la experiencia solo necesita secuencias de estados, acciones y recompensas; la programación dinámica necesita la distribución completa de todos los sucesores posibles. Y hay casos —el blackjack es el ejemplo del libro— en los que el entorno se conoce por completo y aun así calcular \(p\) es un ejercicio penoso y propenso a errores, mientras que generar partidas de muestra es trivial.

«Los métodos de Monte Carlo solo requieren experiencia: secuencias muestrales de estados, acciones y recompensas de la interacción real o simulada con un entorno.» — Sutton & Barto, cap. 5, primer párrafo.

“Monte Carlo methods require only experience—sample sequences of states, actions, and rewards from actual or simulated interaction with an environment.”

Y hay una segunda consecuencia, menos evidente y mucho más determinante: sin el modelo, una tabla de valores de estado no sirve para recuperar una política. Con modelo se mira un paso adelante —\(\pi(s)=\arg\max_a \sum_{s',r} p(s',r\mid s,a)[r+\gamma v_\pi(s')]\)— y listo. Sin modelo esa expresión no se puede evaluar: falta justamente el factor que no tienes. Por eso todo el tema estima valores de acción: con \(q\), la política sale de un \(\arg\max\) que no necesita nada más.

\[ \pi(s) \;=\; \arg\max_a \sum_{s',r} p(s',r\mid s,a)\big[\,r+\gamma v_\pi(s')\,\big] \qquad\text{frente a}\qquad \pi(s) \;\doteq\; \arg\max_a q(s,a) \]

La primera es la del Tema 3 y necesita \(p\). La segunda es la ecuación (5.1) del libro y no necesita nada. Esa asimetría es la razón de que a partir de ahora todos los algoritmos —MC, SARSA, Q-learning, Expected SARSA— trabajen sobre \(Q(s,a)\) y no sobre \(V(s)\), salvo cuando el problema es de predicción pura, donde \(V\) basta porque no hay que elegir nada.

La cadena lógica completa del tema, en seis pasos:

• Sin \(p\) no puedo calcular esperanzas → aprendo de muestras.
• Con muestras y sin \(p\), \(v\) no me da la política → necesito \(q\).
• Con \(q\) y una política determinista no veo todas las acciones → necesito exploración.
• Si exploro, la política que sigo no es la que quiero evaluar → on-policy con ε-soft, o off-policy con muestreo de importancia.
• Esperar al final del episodio es caro, y no vale para tareas continuas → bootstrapping, TD.
• TD a un paso y Monte Carlo son los dos extremos de un mismo espectro → n pasos, en la página siguiente.

Continúa en el módulo 1 →

La baraja del tema empieza con seis diapositivas de repaso. No son relleno: cada una aporta una pieza que el Tema 4 va a reutilizar tal cual.

Las dos figuras del repaso —el diagrama de flujo de la búsqueda de una política (#slide-6) y el triángulo de la iteración generalizada (#slide-7)— se comentan de palabra en clase. Aquí van con su glosa escrita, para estudiarlas por tu cuenta.

La diapositiva lo reduce a dos cosas: (1) un método para estimar los valores de acción de una política dada, y (2) un método para mejorar la política. La segunda ya la tenemos —es el operador greedy del Tema 3, y funciona igual con \(Q\) que con \(v\)—. Lo que falta, y es todo el Tema 4, es la primera: evaluar sin modelo.

Dicho de otra manera: el control ya sabemos plantearlo. Lo que no sabemos es de dónde sacar los números cuando no hay \(p\). La respuesta del tema es siempre la misma: de un flujo de experiencia.

Conviene fijar desde el principio los dos ejes que separan los métodos, porque son independientes y se confunden todo el rato:

Que los dos ejes sean independientes lo dice el libro con todas las letras al cerrar el capítulo 5: Monte Carlo se diferencia de la programación dinámica en dos cosas, opera sobre experiencia muestral y no hace bootstrapping, «y esas dos diferencias no están fuertemente ligadas, se pueden separar». El capítulo 6 es exactamente eso: aprender de la experiencia y además hacer bootstrapping.

La idea cabe en una frase: si \(v_\pi(s)\) es la esperanza del retorno desde \(s\), estímala promediando los retornos que de verdad has observado tras visitar \(s\). No hace falta nada más: ni \(p\), ni ecuaciones, ni resolver ningún sistema. Hace falta experiencia, y hace falta que los episodios terminen.

\[ v_\pi(s) \;\doteq\; \mathbb{E}_\pi\!\left[\,G_t \mid S_t = s\,\right] \qquad\Longrightarrow\qquad V(s) \;\leftarrow\; \text{media}\big(\text{Retornos}(s)\big) \]

Cada aparición de \(s\) en un episodio es una visita. El método de primera visita promedia los retornos que siguen a la primera visita de cada episodio; el de cada visita promedia los de todas. Los dos convergen a \(v_\pi(s)\) cuando el número de visitas tiende a infinito. El de primera visita es más fácil de analizar —sus retornos son independientes e idénticamente distribuidos, el estimador es insesgado y su error típico cae como \(1/\sqrt{n}\)—; el de cada visita converge también, pero sus retornos están correlacionados dentro del mismo episodio y el libro se limita a decir que converge cuadráticamente, remitiendo a Singh y Sutton (1996).

Predicción MC de primera visita, para estimar V ≈ v_π

Entrada: la política π que se quiere evaluar
Inicializar:
    V(s) ∈ R, arbitrariamente, para todo s ∈ S
    Retornos(s) ← lista vacía, para todo s ∈ S
Repetir para siempre (para cada episodio):
    Generar un episodio siguiendo π:  S_0, A_0, R_1, S_1, A_1, R_2, …, S_{T−1}, A_{T−1}, R_T
    G ← 0
    Para cada paso del episodio, t = T−1, T−2, …, 0:
        G ← γG + R_{t+1}
        Salvo que S_t aparezca en S_0, S_1, …, S_{t−1}:
            Añadir G a Retornos(S_t)
            V(S_t) ← media(Retornos(S_t))

Dos propiedades que se preguntan mucho. La primera: las estimaciones de cada estado son independientes. La de un estado no se construye sobre la de ningún otro, al contrario de lo que pasa en programación dinámica. Monte Carlo no hace bootstrapping. La segunda, que es consecuencia de la primera: el coste de estimar el valor de un estado no depende del número de estados. Si solo te interesan diez estados de un millón, puedes generar episodios que empiecen ahí y olvidarte del resto.

La diapositiva del tema proyecta un episodio completo sobre el gridworld 3×3 del Tema 2 y anuncia «cómo evolucionan los valores de estado». Aquí está la cuenta entera, con \(\gamma = 1\) y el método de primera visita de la diapositiva anterior.

S_0 = 1,  A_0 = derecha,  R_1 = −1
S_1 = 2,  A_1 = abajo,    R_2 = −1
S_2 = 5,  A_2 = derecha,  R_3 = −1
S_3 = 6,  A_3 = abajo,    R_4 = −1
S_4 = T

La diapositiva abrevia las acciones con la inicial inglesa: r es right (derecha) y d es down (abajo). Aquí van escritas enteras para que no se confunda la d de down con la de derecha.

El bucle va hacia atrás, de \(t=T-1\) a \(t=0\), acumulando \(G \leftarrow \gamma G + R_{t+1}\); por eso el primer retorno que se calcula es el del último estado visitado. Con \(\gamma = 1\) y \(r=-1\) en cada paso, \(G_t\) es simplemente menos el número de pasos que quedaban hasta terminar. Los cuatro estados aparecen una sola vez en el episodio, así que primera visita y cada visita dan exactamente lo mismo.

Y ahí está la limitación en una línea: después de un episodio se sabe algo de cuatro de los ocho estados, y nada de los otros cuatro. Con \(\gamma=1\), los valores óptimos de esta rejilla son \(v_*(s) = -d(s)\), donde \(d(s)\) es la distancia mínima al terminal: \(-4,\,-3,\,-2\) en la fila de arriba, \(-3,\,-2,\,-1\) en la de en medio y \(-2,\,-1,\,0\) en la de abajo. La estimación de \(V(1)=-4\) que da este único episodio coincide con \(v_*(1)\) por pura suerte: el episodio siguió, sin saberlo, un camino mínimo.

Las limitaciones que la diapositiva enumera son cuatro: solo vale para MDP episódicos, porque hace falta que el episodio acabe para conocer \(G_t\); el estimador es insesgado pero de varianza alta, así que el aprendizaje es lento; con políticas deterministas hay pares estado-acción que nunca se visitan, y sin visitas no hay nada que promediar; y todo esto se agrava al estimar valores de acción, que es justo lo que el tema necesita.

El problema de fondo tiene nombre en el libro: mantener la exploración. Si \(\pi\) es determinista, siguiendo \(\pi\) solo se observan retornos de una acción por estado, y las estimaciones de las demás no mejoran nunca. Hay tres salidas, y el capítulo 5 las recorre en este orden:

1. Arranques exploratorios (exploring starts): exigir que cada episodio empiece en un par \((s,a)\) elegido de forma que todos tengan probabilidad no nula. Garantiza visitar todos los pares, pero es una hipótesis irreal en cuanto se aprende de la interacción real: las condiciones iniciales rara vez son tan complacientes.
2. Políticas ε-soft, on-policy: exigir \(\pi(a\mid s) \ge \varepsilon/|A(s)|\) para todo estado y toda acción. Las ε-greedy son el caso de esta familia más cercano a la greedy. Se explora siempre un poco, y se aprende sobre la política que de verdad se está siguiendo.
3. Dos políticas, off-policy: una que genera el comportamiento y otra que se aprende. Es el bloque B10.

Control MC de primera visita on-policy (para políticas ε-soft), estima π ≈ π_*

Parámetro del algoritmo: ε > 0 pequeño
Inicializar:
    π ← una política ε-soft cualquiera
    Q(s,a) ∈ R, arbitrariamente, para todo s ∈ S, a ∈ A(s)
    Retornos(s,a) ← lista vacía, para todo s ∈ S, a ∈ A(s)
Repetir para siempre (para cada episodio):
    Generar un episodio siguiendo π:  S_0, A_0, R_1, …, S_{T−1}, A_{T−1}, R_T
    G ← 0
    Para cada paso del episodio, t = T−1, T−2, …, 0:
        G ← γG + R_{t+1}
        Salvo que el par S_t, A_t aparezca en S_0,A_0, …, S_{t−1},A_{t−1}:
            Añadir G a Retornos(S_t, A_t)
            Q(S_t, A_t) ← media(Retornos(S_t, A_t))
            A* ← argmax_a Q(S_t, a)      (empates deshechos arbitrariamente)
            Para todo a ∈ A(S_t):
                π(a|S_t) ← 1 − ε + ε/|A(S_t)|   si a = A*
                π(a|S_t) ← ε/|A(S_t)|           si a ≠ A*

GLIE —greedy in the limit with infinite exploration— son dos condiciones sobre la sucesión de políticas que el algoritmo va siguiendo:

1. Exploración infinita: todo par estado-acción se visita infinitas veces, \(N_k(s,a)\to\infty\). Es lo que hace falta para que la media muestral de cada par converja a su valor; sin ella hay acciones sobre las que nunca se sabe nada.
2. Greedy en el límite: la política converge a la greedy respecto de \(Q\), es decir \(\pi_k(a\mid s)\to 1\) para \(a = \arg\max_a Q_k(s,a)\). Es lo que elimina el coste residual de explorar.

Las dos a la vez parecen incompatibles —explorar siempre y acabar siendo greedy— y no lo son: basta con que \(\varepsilon\) baje, pero despacio. Una política ε-greedy con \(\varepsilon_k = 1/k\) las cumple las dos, porque \(1/k\) nunca llega a cero (se sigue explorando en todo momento) pero tiende a cero (la política se vuelve greedy). Con GLIE, el control de Monte Carlo converge a \(q_*\) y la política a \(\pi_*\). Sin GLIE, con \(\varepsilon\) fijo, se converge a la mejor política ε-soft y ahí se queda: es exactamente el caso del recuadro anterior.

Un aviso que conviene no pasar por alto: Monte Carlo con arranques exploratorios no tiene demostración de convergencia. El libro lo dice literalmente y añade que es «una de las preguntas teóricas abiertas más fundamentales del aprendizaje por refuerzo» (§5.3, p. 121). Si alguien te lo cuenta como un teorema, no lo es. La garantía con GLIE, en cambio, sí está demostrada.

Monte Carlo obliga a esperar al final del episodio: hasta que no acaba, no se conoce \(G_t\) y no hay nada que promediar. La diapositiva plantea la salida como una pregunta al aula —«¿y si usamos nuestra estimación del estado siguiente para actualizar la del estado actual? ¿y si hacemos bootstrap?»— y la respuesta ya estaba escrita en el Tema 2:

\[ v_\pi(s) \;\doteq\; \mathbb{E}_\pi[\,G_t \mid S_t=s\,] \tag{6.3} \] \[ = \mathbb{E}_\pi[\,R_{t+1} + \gamma G_{t+1} \mid S_t=s\,] \tag{de (3.9)} \] \[ = \mathbb{E}_\pi[\,R_{t+1} + \gamma\, v_\pi(S_{t+1}) \mid S_t=s\,] \tag{6.4} \]

Monte Carlo usa una estimación de (6.3) como objetivo: sustituye la esperanza por un retorno muestreado. La programación dinámica usa una estimación de (6.4): las esperanzas las calcula exactas con el modelo, pero \(v_\pi(S_{t+1})\) no lo conoce y usa \(V(S_{t+1})\) en su lugar. TD aproxima por las dos razones a la vez: muestrea la esperanza y hace bootstrapping sobre su propia estimación. Es la frase que resume el capítulo entero.

\[ \text{MC de paso constante:}\qquad V(S_t) \;\leftarrow\; V(S_t) + \alpha\big[\,G_t - V(S_t)\,\big] \tag{6.1} \] \[ \text{TD(0):}\qquad V(S_t) \;\leftarrow\; V(S_t) + \alpha\big[\,R_{t+1} + \gamma V(S_{t+1}) - V(S_t)\,\big] \tag{6.2} \]

Debajo de las dos está el patrón que ya apareció en el Tema 1 y que no va a dejar de aparecer: Nueva estimación ← Estimación anterior + PasoDeAprendizaje · [Objetivo − Estimación anterior]. Lo único que distingue a un algoritmo de otro en todo este tema es de dónde sale el objetivo. En MC el objetivo es \(G_t\), que exige terminar el episodio. En TD(0) es \(R_{t+1} + \gamma V(S_{t+1})\), que está disponible un paso después.

TD(0) tabular, para estimar v_π

Entrada: la política π que se quiere evaluar
Parámetro del algoritmo: paso de aprendizaje α ∈ (0,1]
Inicializar V(s) para todo s ∈ S⁺, arbitrariamente salvo que V(terminal) = 0
Repetir para cada episodio:
    Inicializar S
    Repetir para cada paso del episodio:
        A ← acción dada por π para S
        Ejecutar A, observar R y S'
        V(S) ← V(S) + α [ R + γV(S') − V(S) ]
        S ← S'
    hasta que S sea terminal

El corchete tiene nombre propio y va a aparecer en todo lo que queda de asignatura, incluidas las trazas de elegibilidad y el gradiente de política:

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

Se lee como la diferencia entre lo que esperabas obtener desde \(S_t\) —eso es \(V(S_t)\)— y lo que la experiencia recién observada más el bootstrap dicen que deberías esperar. Un detalle que se pregunta: \(\delta_t\) es el error de \(V(S_t)\), pero no está disponible hasta el instante \(t+1\), porque depende de \(R_{t+1}\) y de \(S_{t+1}\).

Sumando los errores TD de un episodio se recupera exactamente el error de Monte Carlo: \(G_t - V(S_t) = \sum_{k=t}^{T-1}\gamma^{k-t}\delta_k\) (ecuación 6.6). La identidad solo es exacta si \(V\) no cambia durante el episodio, y TD(0) sí lo cambia; con \(\alpha\) pequeño se cumple de forma aproximada. Es la bisagra con la vista hacia adelante y hacia atrás de la segunda página.

Aquí se escribe \(V\) en mayúscula, no \(v\). Es deliberado: \(v_\pi\) es la función de valor verdadera y \(V\) es el array de estimaciones, y este tema entero trata justamente de la diferencia entre las dos.

El ejemplo con el que la diapositiva plantea el contraste es volver a casa en coche (Driving Home). Sales de la oficina un viernes a las seis y vas actualizando tu predicción del tiempo total de viaje a medida que pasan cosas. Las recompensas son los minutos de cada tramo; el valor de un estado es el tiempo esperado que queda; y como aquí solo se predice, se usan números positivos y \(\gamma = 1\).

Con Monte Carlo (y \(\alpha=1\)) todas las correcciones apuntan al mismo sitio: al resultado final, 43. Con TD, cada estimación se desplaza hacia la que le sigue inmediatamente: al llegar al coche bajo la lluvia ya sabes que 30 minutos era optimista, y puedes corregir la predicción inicial sin esperar a llegar a casa. La pregunta del libro lo dice mejor que ninguna explicación: «¿tienes que esperar a llegar a casa para subir tu estimación del estado inicial?»

El resumen que se proyecta en clase, ordenado y con dos matices añadidos:

Y una advertencia sobre la afirmación “TD converge más rápido”. El libro es explícito: «nadie ha sido capaz de demostrar matemáticamente que un método converja más rápido que el otro. De hecho, ni siquiera está claro cuál es la forma más apropiada de plantear formalmente la pregunta» (§6.2, p. 146). Lo que sí hay es evidencia empírica: en tareas estocásticas, TD suele llegar antes. Eso es lo que se puede comprobar en el módulo siguiente, y es también todo lo que se puede afirmar.

Continúa en el módulo 2 →

Los tres métodos que ya conoces se distinguen a la vista si se dibuja qué parte del árbol de futuros usa cada actualización.

La diapositiva siguiente proyecta la “visión unificada”: un cuadrado con dos ejes y cuatro esquinas. Los dos ejes son justamente lo que hay que llevarse:

1. El eje horizontal, anchura de la actualización, mide cuántos de los sucesores posibles entran en el objetivo. A la izquierda, uno muestreado (actualización muestral); a la derecha, todos, ponderados por \(p\) (actualización esperada). Es el eje del modelo.
2. El eje vertical, profundidad de la actualización, mide cuántos pasos se miran antes de cortar con una estimación. Arriba, uno (bootstrapping puro); abajo, hasta el final del episodio (sin bootstrapping). Es el eje del retorno.

Las cuatro esquinas son entonces: TD (una rama, un paso), programación dinámica (todas las ramas, un paso), Monte Carlo (una rama, hasta el final) y búsqueda exhaustiva (todas las ramas, hasta el final). Y el interior del cuadrado no está vacío: el eje vertical se recorre con los métodos a \(n\) pasos y con TD(λ), que son la segunda página de este tema.

El esquema del control no cambia respecto al Tema 3: iteración generalizada de la política. Se alterna evaluación y mejora, y se converge cuando las dos dejan de mover nada. Lo único que cambia —y es todo lo que cambia— es que la evaluación ya no resuelve un sistema de ecuaciones, sino que promedia retornos, y que lo que se evalúa es \(Q\), no \(V\).

\[ \pi_0 \xrightarrow{\;E\;} q_{\pi_0} \xrightarrow{\;I\;} \pi_1 \xrightarrow{\;E\;} q_{\pi_1} \xrightarrow{\;I\;} \pi_2 \xrightarrow{\;E\;} \cdots \xrightarrow{\;I\;} \pi_* \xrightarrow{\;E\;} q_* \]

La mejora es la ecuación (5.1), \(\pi(s) \doteq \arg\max_a q(s,a)\), y la sostiene el mismo teorema de mejora de la política del Tema 3, sin ninguna variante: \(q_{\pi_k}(s,\pi_{k+1}(s)) = \max_a q_{\pi_k}(s,a) \ge q_{\pi_k}(s,\pi_k(s)) \ge v_{\pi_k}(s)\). No hay teoría nueva; hay un objeto nuevo.

Con Monte Carlo lo natural es aplicar la mejora después de un solo episodio, sin esperar a que la evaluación converja. No es obligatorio, pero es lo que se hace, y es exactamente la misma idea de truncar la evaluación que en el Tema 3 llevó de la iteración de política a la iteración de valor.

Para que este esquema tenga garantías hacen falta dos hipótesis poco realistas: (1) que los episodios tengan arranques exploratorios y (2) que la evaluación se haga con infinitos episodios. La segunda se elimina igual que en programación dinámica: no completando la evaluación antes de mejorar. La primera es la que obliga a elegir entre políticas ε-soft (bloque B5) y métodos fuera de política (bloque B10).

Hay dos formas de resolver la tensión entre “quiero aprender sobre la política óptima” y “necesito explorar”. On-policy (on-policy) se aprende sobre la misma política que genera la experiencia, y se acepta que esa política tenga que ser un poco exploratoria para siempre. Off-policy (off-policy) se usan dos: la política objetivo \(\pi\), que es la que se quiere aprender, y la política de comportamiento \(b\), que es la que se ejecuta y la que explora.

Aquí las dos colecciones usan símbolos distintos para lo mismo. En clase se escribe μ para la política de comportamiento (4_Tema4#slide-29); en la otra colección, b (Tema4_1_ModelFree#slide-11). Esta página usa \(b\), que es la de Sutton & Barto 2.ª edición y la que aparece en el libro de referencia de la asignatura. Si en la diapositiva ves μ, es lo mismo.

Los métodos off-policy son más generales —los de on-policy son el caso particular \(\pi = b\)— y también más ruidosos: mayor varianza y convergencia más lenta. A cambio, permiten aprender de experiencia ajena: de un registro histórico, de otro agente, o de una política antigua. Es la puerta por la que entrará la repetición de experiencia del Tema 5.

Para que esto funcione hace falta una condición, y es la única: cobertura. Toda acción que \(\pi\) pueda tomar tiene que ser posible también bajo \(b\): \(\pi(a\mid s) > 0 \Rightarrow b(a\mid s) > 0\). De ahí se sigue que \(b\) tiene que ser estocástica en los estados donde no coincida con \(\pi\). A la pregunta que plantea la diapositiva de clase, “¿cómo deben ser \(\pi\) y \(b\)?”, la respuesta es exactamente ésa, ni más ni menos. En particular \(\pi\) sí puede ser determinista, y de hecho suele serlo (la greedy respecto a \(Q\)).

El problema técnico es que los retornos observados vienen de \(b\) y hacen falta esperanzas bajo \(\pi\). Se corrige pesando cada retorno por la razón de muestreo de importancia: el cociente entre la probabilidad de la trayectoria bajo \(\pi\) y bajo \(b\).

\[ \rho_{t:T-1} \;\doteq\; \frac{\prod_{k=t}^{T-1} \pi(A_k\mid S_k)\, p(S_{k+1}\mid S_k,A_k)} {\prod_{k=t}^{T-1} b(A_k\mid S_k)\, p(S_{k+1}\mid S_k,A_k)} \;=\; \prod_{k=t}^{T-1} \frac{\pi(A_k\mid S_k)}{b(A_k\mid S_k)} \tag{5.3} \]

Mira lo que acaba de pasar: las probabilidades de transición \(p\) aparecen idénticas en el numerador y en el denominador y se cancelan. La razón de importancia depende solo de las dos políticas y de la secuencia de acciones observada, no del MDP. Ése es el motivo por el que el método es sin modelo, y es la razón por la que la diapositiva puede decir que el muestreo de importancia «permite pasar de una política a otra sin depender del modelo de dinámicas».

Con los retornos ya pesados hay dos maneras de promediarlos, y sus propiedades son opuestas:

\[ \text{ordinario:}\quad V(s) \doteq \frac{\sum_{t\in\mathcal{T}(s)} \rho_{t:T(t)-1}\,G_t}{|\mathcal{T}(s)|} \tag{5.5} \] \[ \text{ponderado:}\quad V(s) \doteq \frac{\sum_{t\in\mathcal{T}(s)} \rho_{t:T(t)-1}\,G_t}{\sum_{t\in\mathcal{T}(s)} \rho_{t:T(t)-1}} \tag{5.6} \]

El ordinario es insesgado y el ponderado es sesgado (aunque el sesgo tiende a cero). Pero la varianza del ordinario no está acotada, porque las razones tampoco lo están, mientras que en el ponderado el peso máximo de un solo retorno es 1. En la práctica se prefiere el ponderado, con diferencia. Ojo con el orden de esa frase: la confusión típica es al revés, creer que el ponderado gana por ser insesgado, cuando gana a pesar de ser sesgado. Y una nota fina: el ponderado vale cero si el denominador es cero.

En el pseudocódigo del control MC off-policy aparece la línea \(W \leftarrow W \cdot \tfrac{1}{b(A_t\mid S_t)}\), y al lado, con una flecha y un signo de interrogación, la forma general \(W \leftarrow W \cdot \tfrac{\pi(A_t\mid S_t)}{b(A_t\mid S_t)}\). ¿Por qué desaparece el numerador? Porque en ese algoritmo la política objetivo es la greedy determinista respecto a \(Q\), y la línea inmediatamente anterior dice «si \(A_t \neq \pi(S_t)\), salir del bucle interno». Es decir: cuando se llega a esa línea, la acción tomada es la que \(\pi\) habría tomado, luego \(\pi(A_t\mid S_t)=1\) y el numerador se cae solo. No es una simplificación: es una consecuencia.

El símbolo \(C(s,a)\) que aparece en la misma caja es la suma acumulada de los pesos, y es lo que convierte la media ponderada en incremental: sin él habría que guardar todos los retornos y todas las razones.

El paso de la predicción al control es literalmente cambiar \(V(s)\) por \(Q(s,a)\). El libro lo dice sin ceremonia: formalmente los dos casos son idénticos —los dos son cadenas de Markov con proceso de recompensa— y los teoremas de convergencia de TD(0) para valores de estado valen igual para valores de acción. La regla es la misma con otro objeto:

\[ Q(S_t,A_t) \;\leftarrow\; Q(S_t,A_t) + \alpha\big[\,R_{t+1} + \gamma\,Q(S_{t+1},A_{t+1}) - Q(S_t,A_t)\,\big] \tag{6.7} \]

La actualización usa los cinco elementos de la transición de un par estado-acción al siguiente: \((S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})\). De esa quíntupla sale el nombre. Y hay un detalle que se olvida al implementarlo: si \(S_{t+1}\) es terminal, entonces \(Q(S_{t+1},A_{t+1})\) vale cero por definición.

SARSA (control TD on-policy), para estimar Q ≈ q_*

Parámetros del algoritmo: paso de aprendizaje α ∈ (0,1], ε > 0 pequeño
Inicializar Q(s,a) para todo s ∈ S⁺, a ∈ A(s), arbitrariamente salvo que Q(terminal,·) = 0
Repetir para cada episodio:
    Inicializar S
    Elegir A desde S con una política derivada de Q (por ejemplo, ε-greedy)
    Repetir para cada paso del episodio:
        Ejecutar A, observar R y S'
        Elegir A' desde S' con una política derivada de Q (por ejemplo, ε-greedy)
        Q(S,A) ← Q(S,A) + α [ R + γQ(S',A') − Q(S,A) ]
        S ← S';  A ← A'
    hasta que S sea terminal

SARSA converge con probabilidad 1 a una política óptima y a \(q_*\) siempre que se cumplan tres cosas: las condiciones habituales sobre \(\alpha\), que todos los pares estado-acción se visiten infinitas veces, y que la política converja en el límite a la greedy —lo que se consigue, por ejemplo, con \(\varepsilon = 1/t\)—. Las tres, no dos.

El ejemplo con el que se proyecta el rendimiento de SARSA es el Windy Gridworld: una rejilla de 7 filas por 10 columnas con una corriente ascendente que empuja al agente \(0,0,0,1,1,1,2,2,1,0\) celdas hacia arriba según la columna en la que esté, además del efecto de su propia acción. Cuatro acciones, \(r=-1\) por paso, sin descuento.

La gráfica que se proyecta —episodios completados frente a pasos de tiempo— no trae ni un solo hiperparámetro: ni \(\alpha\), ni \(\varepsilon\), ni \(\gamma\), ni la recompensa por paso, ni cuántas ejecuciones se promedian. Los del libro son: \(\varepsilon = 0{,}1\), \(\alpha = 0{,}5\), \(Q\) inicial a cero, \(r=-1\) por paso, 8 000 pasos de tiempo y una sola ejecución. El resultado: hacia el final la política greedy ya era óptima desde hacía rato, pero la exploración ε-greedy mantenía la longitud media del episodio en unos 17 pasos, dos por encima del mínimo de 15.

El mínimo de 15 pasos no es un dato del que haya que fiarse: se comprueba. Con esa geometría y esos vientos, una búsqueda en anchura desde \(S\) hasta \(G\) da exactamente 15, que es lo que dice el libro. Es la forma de confirmar que la fila de vientos leída de la figura es la correcta.

Dos cosas que decir sobre esa curva. La primera: la pendiente es la velocidad de resolución de episodios, así que lo que hay que mirar no es la altura, es cuándo despega. La segunda, más importante: a priori no se puede saber si has llegado al óptimo, ni siquiera cuando has terminado de entrenar. En la práctica no se busca el óptimo global, se busca un agente que funcione bien y sea robusto.

Y un apunte que justifica todo el capítulo 6: en este entorno Monte Carlo no se puede usar con comodidad, porque la terminación no está garantizada para todas las políticas. Si en algún momento se llega a una política que deja al agente quieto, el episodio no termina nunca y MC no tiene nada que promediar. SARSA no tiene ese problema porque aprende durante el episodio y abandona enseguida esas políticas.

La diapositiva de clase deriva el objetivo paso a paso. Empieza por la regla de SARSA, se pregunta qué pasa si la acción siguiente la elige la política greedy en lugar de la de comportamiento, y llega al \(\max\):

\[ R_{t+1} + \gamma\,Q(S_{t+1}, A') \;=\; R_{t+1} + \gamma\,Q\Big(S_{t+1}, \arg\max_{a'} Q(S_{t+1},a')\Big) \;=\; R_{t+1} + \gamma \max_{a'} Q(S_{t+1},a') \]

\[ Q(S_t,A_t) \;\leftarrow\; Q(S_t,A_t) + \alpha\Big[\,R_{t+1} + \gamma \max_a Q(S_{t+1},a) - Q(S_t,A_t)\,\Big] \tag{6.8} \]

La política de comportamiento es ε-greedy respecto a \(Q\); la política objetivo es la greedy respecto a \(Q\). Son distintas, y por eso Q-learning es off-policy. Ojo a la razón: no es off-policy por usar ε-greedy —SARSA también la usa y es on-policy—, sino porque su objetivo evalúa la política greedy mientras se comporta con otra.

La consecuencia es fuerte: \(Q\) aproxima \(q_*\) independientemente de la política que se esté siguiendo. La política solo decide qué pares se visitan y se actualizan; y lo único que hace falta para converger es que todos se sigan actualizando (más las condiciones habituales sobre \(\alpha\)).

Q-learning (control TD off-policy), para estimar π ≈ π_*

Parámetros del algoritmo: paso de aprendizaje α ∈ (0,1], ε > 0 pequeño
Inicializar Q(s,a) para todo s ∈ S⁺, a ∈ A(s), arbitrariamente salvo que Q(terminal,·) = 0
Repetir para cada episodio:
    Inicializar S
    Repetir para cada paso del episodio:
        Elegir A desde S con una política derivada de Q (por ejemplo, ε-greedy)
        Ejecutar A, observar R y S'
        Q(S,A) ← Q(S,A) + α [ R + γ max_a Q(S',a) − Q(S,A) ]
        S ← S'
    hasta que S sea terminal

Compara las dos cajas. La diferencia entera es dónde se elige la acción siguiente: en SARSA se elige antes de la actualización y se usa en ella; en Q-learning se elige después, y la actualización usa \(\max_a\). Todo lo demás es idéntico. De esa línea salen las dos curvas del módulo siguiente.

Una lectura que ayuda a fijar el objetivo: en SARSA, el objetivo es una muestra de la ecuación de Bellman para \(q_\pi\); en Q-learning, de la ecuación de optimalidad de Bellman para \(q_*\). Son los dos objetos del Tema 2, ahora estimados desde la experiencia.

Continúa en el módulo 3 →

Entre SARSA y Q-learning cabe un tercero. SARSA usa \(Q(S_{t+1},A_{t+1})\), donde \(A_{t+1}\) es una acción muestreada; Q-learning usa el \(\max\). Expected SARSA usa la esperanza bajo la política:

\[ Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha\Big[\,R_{t+1} + \gamma\,\mathbb{E}_\pi\big[Q(S_{t+1},A_{t+1})\mid S_{t+1}\big] - Q(S_t,A_t)\,\Big] \;=\; \cdots + \alpha\Big[\,R_{t+1} + \gamma\sum_a \pi(a\mid S_{t+1})\,Q(S_{t+1},a) - Q(S_t,A_t)\,\Big] \tag{6.9} \]

Se mueve de forma determinista en la misma dirección en la que SARSA se mueve en esperanza: de ahí el nombre. Cuesta más por paso —hay que recorrer todas las acciones— pero a cambio elimina la varianza que introduce el sorteo de \(A_{t+1}\). Con la misma cantidad de experiencia, suele ir algo mejor que SARSA.

Y hay una lectura que cierra el capítulo entero: en el ejemplo del acantilado, Expected SARSA se usa on-policy, pero en general puede comportarse con una política distinta de la objetivo, y entonces es un método off-policy. En particular: si \(\pi\) es la política greedy y el comportamiento es exploratorio, Expected SARSA es exactamente Q-learning. Expected SARSA subsume y generaliza a Q-learning.

Todos los algoritmos de control que se han visto hasta aquí toman un máximo sobre valores estimados para construir su política objetivo. Y ahí hay una trampa que no es obvia: el máximo de unas estimaciones se usa implícitamente como estimación del máximo, y esas dos cosas no son lo mismo.

El caso límite lo deja claro. Imagina un estado con muchas acciones cuyos valores verdaderos son todos exactamente cero, pero cuyas estimaciones \(Q(s,a)\) son inciertas y están repartidas por encima y por debajo de cero. El máximo de los valores verdaderos es 0. El máximo de las estimaciones es positivo, casi seguro. Es un sesgo positivo, y tiene nombre: sesgo de maximización.

La causa es concreta y merece una frase entera: se usa el mismo conjunto de estimaciones para dos cosas distintas —para elegir cuál es la acción máxima y para evaluar cuánto vale—. El error de estimación que hace que una acción parezca la mejor es el mismo error que después se copia como su valor.

La solución es separar las dos funciones. Se mantienen dos estimaciones independientes, \(Q_1\) y \(Q_2\). Una decide cuál es la acción maximizadora, \(A^* = \arg\max_a Q_1(a)\); la otra da su valor, \(Q_2(A^*)\). Esa estimación sí es insesgada: \(\mathbb{E}[Q_2(A^*)] = q(A^*)\). Se aprenden las dos y en cada paso se actualiza solo una, sorteada con probabilidad \(0{,}5\): el aprendizaje doble duplica la memoria pero no el cómputo por paso.

\[ Q_1(S_t,A_t) \leftarrow Q_1(S_t,A_t) + \alpha\Big[\,R_{t+1} + \gamma\,Q_2\big(S_{t+1},\arg\max_a Q_1(S_{t+1},a)\big) - Q_1(S_t,A_t)\,\Big] \tag{6.10} \]

Q-learning doble, para estimar Q_1 ≈ Q_2 ≈ q_*

Parámetros del algoritmo: paso de aprendizaje α ∈ (0,1], ε > 0 pequeño
Inicializar Q_1(s,a) y Q_2(s,a), para todo s ∈ S⁺, a ∈ A(s), con Q(terminal,·) = 0
Repetir para cada episodio:
    Inicializar S
    Repetir para cada paso del episodio:
        Elegir A desde S con la política ε-greedy en Q_1 + Q_2
        Ejecutar A, observar R y S'
        Con probabilidad 0,5:
            Q_1(S,A) ← Q_1(S,A) + α ( R + γ Q_2(S', argmax_a Q_1(S',a)) − Q_1(S,A) )
        si no:
            Q_2(S,A) ← Q_2(S,A) + α ( R + γ Q_1(S', argmax_a Q_2(S',a)) − Q_2(S,A) )
        S ← S'
    hasta que S sea terminal

Dos cosas que se implementan mal a menudo. Primera: la política de comportamiento es ε-greedy sobre la suma (o la media) de las dos tablas, no sobre una de ellas. Segunda: la moneda decide cuál de las dos tablas se actualiza, no cuál se usa para el \(\arg\max\); la que se actualiza es la que aporta el \(\arg\max\), y la otra aporta el valor. Si se cruzan mal, el algoritmo deja de corregir el sesgo y no se nota en las curvas hasta que es tarde.

La diapositiva de clase cierra el tema con la figura del experimento y el rótulo «¡el aprendizaje doble funciona!». Que funciona se ve; por qué funciona, y cuánto depende del número de acciones y del ruido, es lo que se manipula en el módulo siguiente.

Continúa en el módulo 4 →

Queda un cabo suelto, y es el que abre la segunda mitad del tema. TD(0) hace bootstrapping a un paso: trae todo el futuro a través de una única estimación. Monte Carlo no hace bootstrapping en absoluto: espera hasta el final. Entre esos dos extremos hay un continuo entero —mirar dos pasos, cuatro, \(n\)— y también la manera de promediarlos todos a la vez, que es TD(λ).

Ese continuo, el retorno a \(n\) pasos, SARSA a \(n\) pasos, el retorno λ y las trazas de elegibilidad están en la segunda página de este tema.

Continuar: Tema 4 (continuación) · Fórmulas intermedias entre Monte Carlo y TD a un paso →

Qué hay que llevarse

• Sin modelo, una tabla de valores de estado no determina ninguna política. En el módulo 1 hay dos entornos con \(v_\pi\) idéntica en los nueve estados y políticas greedy distintas. Por eso todo el tema estima \(q\).
• Lo único que distingue a MC de TD es de dónde sale el objetivo, y de ahí salen todas las demás diferencias: cuándo se puede actualizar, cuánto sesgo hay y cuánta varianza.
• TD suele ganar, pero no está demostrado que gane. En el módulo 2 lo ves con las \(\alpha\) del libro: TD baja el error más rápido con todos los valores, y con \(\alpha\) grande vuelve a subir después.
• Batch MC minimiza el error sobre los datos; batch TD acierta el modelo. Con los ocho episodios del ejemplo del predictor, \(V(A)=0\) y \(V(A)=3/4\) son las dos respuestas, y solo una de ellas cree en la propiedad de Markov.
• SARSA aprende el camino que le conviene a la política que está siguiendo; Q-learning, el que le convendría a la política greedy que no está siguiendo. En el acantilado eso son 17 pasos frente a 13, y \(-27\) frente a \(-50\) de rendimiento real.
• Con \(\varepsilon = 0\) los dos algoritmos dan lo mismo (\(-13\), camino de 13 pasos): la diferencia entre SARSA y Q-learning la crea la exploración, no el álgebra.
• El \(\max\) de unas estimaciones ruidosas está sesgado hacia arriba, siempre. Con diez acciones de valor verdadero \(-0{,}1\) y ruido de desviación 1, el máximo estimado vale en media \(+1{,}44\). El aprendizaje doble lo arregla separando quién elige de quién evalúa.