Programación dinámica

Del Tema 2 traemos dos cosas: las funciones de valor \(v_\pi\) y \(q_\pi\), que están siempre definidas respecto a una política, y la idea de que existe al menos una política óptima \(\pi_*\), que alcanza el máximo \(v_*(s)\) en todos los estados a la vez. Encontrar una de ellas es el objetivo central de la disciplina.

Casi siempre se empieza desde una política subóptima, a veces completamente arbitraria, y se usa esa política como punto de apoyo para buscar las óptimas. La programación dinámica es el conjunto de algoritmos que hacen eso cuando se dispone de un modelo perfecto del entorno en forma de MDP. Su receta cabe en una frase: convertir las ecuaciones de Bellman en reglas de actualización.

\[ v_\pi(s) = \sum_a \pi(a\mid s)\sum_{s',r} p(s',r\mid s,a)\,\big[\,r+\gamma v_\pi(s')\,\big] \]

Ojo con una diferencia que el Tema 4 hará explícita: la programación dinámica sustituye el valor antiguo por el nuevo. No hay tasa de aprendizaje \(\alpha\), no hay ninguna \(\alpha(\text{objetivo}-\text{estimación})\). Eso llegará cuando haya que aprender de muestras en vez de calcular esperanzas.

Las tres definiciones, tal como se enuncian en clase:

• Predicción: encontrar los valores de \(v\) y \(q\) bajo una cierta política. Es lo que el libro llama policy evaluation.
• Control: encontrar una política que maximice la función de valor, es decir, una política óptima.
• Planificación: lo mismo que el control, pero haciendo uso de un modelo del entorno. Es cualquier proceso de cómputo que toma un modelo como entrada y produce o mejora una política.

Los métodos de planificación suelen aprender más rápido, pero rara vez se dispone de un modelo que sea a la vez fiable y lo bastante barato como para ejecutarlo millones de veces. Por eso en la práctica lo habitual es enfrentarse al problema de control. Aun así, muchísimos métodos de control se construyen sobre algoritmos de programación dinámica: ése es el motivo de dedicarle un tema entero a un método de planificación que exige un modelo que a menudo no existe.

Dos avisos honestos. Primero: en el material de la asignatura conviven dos versiones. Una habla de tres problemas (3_Tema3#slide-2) y la otra de dos sub-problemas, predicción y control, con la planificación «implícita en el hecho de que nos apoyamos en el modelo» (Tema3_DP#slide-3, material de Lucía). Esta página sigue la de los tres. Segundo: el capítulo 4 del libro solo define ahí la predicción; «control» aparece por primera vez en el capítulo 5 y «planificación» se define en la §8.1. Que la programación dinámica sea planificación es una afirmación del capítulo 8, no del 4.

Dada una política, hay que obtener el valor de todos los estados. La ecuación de Bellman es un sistema de \(|\mathcal{S}|\) ecuaciones lineales con \(|\mathcal{S}|\) incógnitas: se puede resolver de golpe, y eso ya se hizo en el Tema 2. Aquí se resuelve iterando, que es lo que se hace en la práctica.

\[ v_{k+1}(s) \;\doteq\; \sum_a \pi(a\mid s)\sum_{s',r} p(s',r\mid s,a)\,\big[\,r+\gamma v_k(s')\,\big] \]

Cada iteración actualiza el valor de todos los estados una vez: a eso se le llama un barrido. La actualización se llama esperada porque promedia sobre todos los estados siguientes posibles, no sobre uno muestreado; ésa es justamente la diferencia que separará la programación dinámica de los métodos del Tema 4.

\(\mathcal{S}^+\) es el conjunto de estados incluyendo el terminal; \(\mathcal{S}\) son los no terminales. La inicialización de \(V\) es arbitraria salvo que \(V(\text{terminal})=0\), y el barrido recorre solo \(\mathcal{S}\). Si se olvida esa excepción, con \(\gamma=1\) la evaluación converge a algo que no es \(v_\pi\) y el error no está acotado.

El terminal está sombreado en dos esquinas de la figura, pero formalmente es un solo estado. En el motor de esta página hay dos casillas absorbentes de valor 0, lo cual es equivalente: ningún estado no terminal distingue a cuál de las dos llega.

El módulo 3 del Tema 2 ya iteraba la ecuación de Bellman sobre la rejilla 3×3 y anunciaba «…que es lo que hará la programación dinámica del Tema 3». Esto es la continuación: el mismo bucle, ahora sobre el tablero del libro, con el criterio de parada \(\Delta<\theta\) explícito y manipulable, y conectado con la mejora de la política.

Continúa en el módulo 1 →

Buscar directamente entre todas las políticas no es una opción: en esta rejilla de 14 estados no terminales y 4 acciones hay \(4^{14}\), más de 268 millones de políticas deterministas. La programación dinámica encuentra una óptima en tiempo polinómico en el número de estados y de acciones, y en ese sentido es exponencialmente más rápida que cualquier búsqueda directa.

La estrategia es un bucle de cuatro cajas: definir una primera política, predecir sus valores, preguntarse si se puede mejorar y, si se puede, mejorarla y volver a predecir. Fíjate en dónde se reengancha el bucle: entra otra vez en “predicción”, no en “definir la primera política”. La inicialización queda fuera del ciclo, y por eso cada evaluación arranca desde los valores de la política anterior en vez de desde cero.

Las dos piezas que faltan para cerrar ese bucle son las de los dos bloques siguientes: un criterio para saber si una política es mejor que otra (el teorema de mejora) y un procedimiento que produzca la política mejorada (el operador greedy).

Trabajamos con políticas deterministas. Sean \(\pi\) y \(\pi'\) dos de ellas. Si en todos los estados se cumple que la acción que elige \(\pi'\) vale, según \(\pi\), al menos tanto como lo que \(\pi\) obtiene ahí:

\[ q_\pi\big(s,\pi'(s)\big) \;\ge\; v_\pi(s) \qquad \text{para todo } s\in\mathcal{S} \]

entonces \(\pi'\) es igual de buena o mejor que \(\pi\) en todos los estados:

\[ v_{\pi'}(s) \;\ge\; v_\pi(s) \qquad \text{para todo } s\in\mathcal{S} \]

Y si la primera desigualdad es estricta en algún estado, la segunda también lo es en ese estado. El caso particular que se usa todo el rato es el más simple: \(\pi'\) idéntica a \(\pi\) salvo en un estado. Ahí la condición se cumple sola en los demás estados y basta con comparar \(q_\pi(s,a)\) con \(v_\pi(s)\) en el estado que se cambia.

¿Y si la nueva política greedy resulta ser igual de buena, pero no mejor? Entonces \(v_\pi = v_{\pi'}\) y esa función de valor cumple \(v_{\pi'}(s)=\max_a\sum_{s',r}p(s',r\mid s,a)[r+\gamma v_{\pi'}(s')]\), que es exactamente la ecuación de optimalidad de Bellman. Luego \(v_{\pi'}=v_*\) y las dos políticas son óptimas. Dicho al revés: la mejora de política da siempre una política estrictamente mejor, salvo cuando la de partida ya era óptima. Ésa es la razón por la que “la política no ha cambiado” es un criterio de parada legítimo.

Todo esto se extiende a políticas estocásticas sin cambios en el enunciado. Cuando varias acciones alcanzan el máximo no hace falta quedarse con una: se puede repartir la probabilidad entre ellas de cualquier manera, con la única condición de que las acciones no maximizadoras reciban probabilidad cero.

Continúa en el módulo 2 →

Para explotar el teorema y sacar algo práctico solo hace falta un operador de mejora: algo que, dada una función de valor, devuelva una política. El más común es el operador greedy: en cada estado, calcular el valor de acción de las cuatro acciones y quedarse con la que dé el máximo, rompiendo los empates de forma arbitraria.

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

Esa segunda igualdad es la que permite trabajar solo con \(v\) en todo el tema: con el modelo \(p(s',r\mid s,a)\) en la mano, las \(q\) se recuperan de las \(v\) con una suma de un paso. Por eso los algoritmos se presentan sobre la función de valor de estado, y las \(q\) aparecen únicamente donde hacen falta, dentro del argmax. El material usa esta identidad sin nombrarla; aquí queda dicha.

Por construcción el operador greedy cumple la hipótesis del teorema en todos los estados, así que la política que devuelve es siempre igual o mejor que la de partida. Ese “romper empates de forma arbitraria” parece un detalle inofensivo, y no lo es: es exactamente lo que hace que el algoritmo del bloque siguiente pueda no terminar nunca.

La palabra “operador” no es del capítulo 4. El libro escribe (4.9) y nada más; los operadores de Bellman con su punto fijo aparecen mucho más tarde, en la §11.5. Es vocabulario estándar y útil, pero no se lo atribuyas al capítulo 4.

Ya tenemos las dos piezas: un algoritmo para predecir la función de valor de una política y un operador para mejorar una política dada. Alternándolas sale la iteración de política:

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

\(E\) es una evaluación (evaluation) completa de la política, y \(I\) es una mejora (improvement). Cada política es una mejora estricta de la anterior salvo que ya sea óptima, y como un MDP finito tiene un número finito de políticas deterministas, el proceso termina en un número finito de iteraciones. Además cada evaluación arranca con la función de valor de la política anterior, lo que la acelera mucho: la función de valor cambia poco de una política a la siguiente.

El algoritmo, tal como se proyecta en clase:

Iteración de política, para estimar π ≈ π_*

1. Inicialización
   V(s) ∈ ℝ  y  π(s) ∈ A(s)  arbitrarios para todo s ∈ S

2. Evaluación de la política
   Repetir:
       Δ ← 0
       Para cada s ∈ S:
           v ← V(s)
           V(s) ← Σ_{s',r} p(s',r | s, π(s)) [ r + γ V(s') ]
           Δ ← max(Δ, |v − V(s)|)
   hasta que Δ < θ

3. Mejora de la política
   política-estable ← verdadero
   Para cada s ∈ S:
       acción-antigua ← π(s)
       π(s) ← argmax_a Σ_{s',r} p(s',r | s, a) [ r + γ V(s') ]
       Si acción-antigua ≠ π(s), entonces política-estable ← falso
   Si política-estable, parar y devolver V ≈ v_*  y  π ≈ π_*;  si no, ir a 2

Dos cosas que mirar en esa caja antes de pasar de página. La primera: la inicialización no dice \(V(\text{terminal})=0\), aunque las otras dos cajas del capítulo sí lo dicen. La segunda, más grave: la última línea no siempre para. Las dos se trabajan en el módulo 3.

Continúa en el módulo 3 →

La figura 4.1 del libro pone en dos columnas la sucesión \(v_k\) de la política equiprobable y la política greedy respecto a cada \(v_k\). Y dibuja, sin decirlo con palabras, el hecho más importante del tema: la etiqueta “optimal policy” apunta a \(k=3\), a \(k=10\) y a \(k=\infty\). Es decir, la política greedy ya es óptima en el tercer barrido, cuando los valores todavía están a 19 unidades de su límite.

El libro lo confirma dos veces: en el pie de la figura («todas las políticas a partir de la tercera iteración son óptimas») y en la §4.4 («las iteraciones de evaluación más allá de las tres primeras no tienen ningún efecto sobre la política greedy correspondiente»). Y añade que en este ejemplo una sola iteración de iteración de política encuentra la política óptima.

Cuidado con la lectura fácil: el teorema solo garantiza que la política greedy es una mejora. Que en esta rejilla salga óptima a la primera es una peculiaridad del ejemplo, no una propiedad general.

Continúa en el módulo 4 →

La pregunta que responde este algoritmo es la del bloque anterior: ¿hace falta esperar a que la evaluación converja para aplicar el operador de mejora? No. La evaluación se puede truncar de muchas formas sin perder las garantías de convergencia. El caso extremo —y el más eficiente por barrido— es truncarla a un solo barrido: greedificar después de cada actualización de todos los estados. Eso es la iteración de valor.

\[ v_{k+1}(s) \;\doteq\; \max_a \sum_{s',r} p(s',r\mid s,a)\,\big[\,r+\gamma v_k(s')\,\big] \]

Compárala con la de la evaluación: la única diferencia es que \(\sum_a \pi(a\mid s)\) se ha convertido en \(\max_a\). Es la ecuación de optimalidad de Bellman convertida en regla de actualización, igual que la de evaluación era la ecuación de Bellman para \(v_\pi\) convertida en regla de actualización. Y no hay política explícita dentro del bucle: se extrae una sola vez, al final, con un argmax.

Entre los dos extremos hay un continuo. Se puede intercalar cualquier número \(m\) de barridos de evaluación entre dos mejoras: con \(m=1\) sale la iteración de valor, con \(m\to\infty\) sale la iteración de política, y a menudo se converge antes con algún valor intermedio. Todas esas variantes convergen. \(m\) es notación de esta página, no del libro.

Guarda esta actualización: es la base de Q-learning. La versión para valores de acción, \(q_{k+1}(s,a)=\sum_{s',r}p(s',r\mid s,a)[\,r+\gamma\max_{a'}q_k(s',a')\,]\), es literalmente Q-learning con la esperanza calculada en vez de muestreada. En el Tema 4 la esperanza se sustituirá por una muestra y aparecerá la \(\alpha\).

Continúa en el módulo 5 →

Iteración generalizada de la política es el nombre que se le da a la idea de dejar que los procesos de evaluación y de mejora interactúen, sin importar su granularidad ni sus detalles. Iteración de política y iteración de valor son dos casos particulares. Casi todos los métodos de aprendizaje por refuerzo se describen bien como GPI.

Los dos procesos compiten y colaboran. Compiten porque tiran en direcciones opuestas: hacer la política greedy respecto a la función de valor deja la función de valor incorrecta para la nueva política, y hacer la función de valor consistente con la política deja de ser greedy a la política. Colaboran porque cuando los dos se estabilizan a la vez, la función de valor es consistente con la política y la política es greedy respecto a ella: eso es exactamente la ecuación de optimalidad de Bellman, y por tanto las dos son óptimas.

En la figura de las dos rectas, cada recta es un objetivo. La de arriba, \(v=v_\pi\), es el conjunto de puntos donde la función de valor es consistente con la política: llegar a ella es evaluar la política. La de abajo, \(\pi=\text{greedy}(v)\), es donde la política es greedy respecto a la función de valor: llegar a ella es mejorar la política. Se cortan en \(v_*,\pi_*\).

La geometría real es mucho más complicada que dos rectas; el diagrama solo sugiere lo que pasa. Y las flechas que dibuja el libro son iteración de política, y solo iteración de política: cada una lleva el sistema hasta alcanzar por completo uno de los dos objetivos. Sobre los métodos que dan pasos incompletos el libro dice una sola frase: que también se pueden dar “pasos más pequeños e incompletos hacia cada objetivo”.

Continúa en el módulo 6 →

Qué hay que llevarse

• Predicción, control y planificación no son sinónimos: la programación dinámica resuelve control usando un modelo, y por eso es planificación.
• Bajar el umbral \(\theta\) de \(10^{-1}\) a \(10^{-4}\) pasa de 47 a 173 barridos y no cambia ni una flecha de la política greedy.
• \(\pi'\) mejora a \(\pi\) exactamente cuando \(q_\pi(s,\pi'(s))\ge v_\pi(s)\); en la política de partida del módulo 2, solo 2 de los 56 cambios posibles mejoran de verdad.
• El operador greedy no promete mejora estricta: si hay igualdad, las dos políticas son óptimas. Ése es el criterio de parada de la iteración de política.
• La última línea del pseudocódigo compara acciones, no valores: con desempate aleatorio, la probabilidad de parar en una ronda es 1/256 en esta rejilla.
• La política óptima está lista en el barrido 3; la evaluación necesita 173 para llegar a \(-14/-20/-22\). Ésa es toda la motivación de la iteración de valor.
• Iteración de política e iteración de valor son el mismo esquema con distinto reparto de esfuerzo: \(m=\infty\) frente a \(m=1\). En esta rejilla, 178 barridos frente a 4.