Aprendizaje por refuerzo (RL) — Capítulo 5: Programación dinámica — Parte 1: Teoría

11 min readDec 19, 2023

Y llegamos al quinto capítulo sobre programación dinámica.

La programación dinámica es un pilar fundamental en el mundo del aprendizaje por refuerzo, una técnica revolucionaria que permite a las máquinas aprender a tomar decisiones óptimas a partir de su interacción con el entorno. Este enfoque, basado en principios de optimización y toma de decisiones secuenciales, se ha convertido en una herramienta esencial para resolver problemas complejos en campos tan variados como la robótica, los juegos y la gestión de recursos. En este capítulo, exploraremos cómo la programación dinámica facilita el aprendizaje de estrategias efectivas en entornos inciertos y cambiantes, proporcionando una visión detallada y accesible de sus fundamentos.

¡Prepárate para sumergirte en un viaje fascinante donde la inteligencia artificial y la teoría de decisiones se entrelazan para crear sistemas más inteligentes y adaptativos!

Introducción

El concepto de “programación dinámica” (DP) abarca un conjunto de métodos algorítmicos diseñados para derivar políticas óptimas en contextos donde el entorno se modela perfectamente, como en los Procesos de Decisión de Markov (MDP). En el ámbito del aprendizaje por refuerzo, la aplicabilidad de los algoritmos clásicos de DP se ve restringida debido a dos factores principales:

La suposición de un modelo ambiental impecable.
Su elevado coste computacional.

No obstante, su relevancia teórica es indiscutible. DP constituye un pilar fundamental para entender los métodos avanzados en este campo. De hecho, muchos de estos métodos avanzados se pueden interpretar como esfuerzos por emular la efectividad de DP, pero con requerimientos computacionales reducidos y sin depender de un modelo ambiental perfecto.

A partir de este punto, se adopta la premisa de que el entorno se ajusta a un MDP finito, cuya dinámica se define mediante probabilidades de transición específicas. Aunque los principios de DP son aplicables en escenarios con espacios de acción y estado continuos, las soluciones exactas se limitan a ciertas situaciones excepcionales.

La esencia de la programación dinámica radica en la utilización de funciones de valor para estructurar y optimizar la búsqueda de políticas eficientes. Como se mencionó previamente, la identificación de funciones de valor óptimas facilita significativamente la formulación de políticas óptimas.

Este enfoque subraya la importancia de comprender y calcular adecuadamente estas funciones de valor para el desarrollo de estrategias efectivas en aprendizaje por refuerzo.

Los algoritmos DP se obtienen convirtiendo estas ecuaciones de Bellman en asignaciones, es decir, en reglas de actualización para mejorar las aproximaciones de las funciones de valor deseadas.

Evaluación de políticas

Primero, consideramos cómo calcular la función de valor de estado Vπ para una política arbitraria π. Esto se denomina evaluación de políticas en la literatura del DP. También nos referimos a él como el problema de la predicción.

Si recordamos de lo que vimos anteriormente, tenemos que:

Donde π(s,a) es la probabilidad de emprender acciones a en el estado s según la política \pi. La existencia y unicidad de Vπ están garantizadas siempre que se cumpla que γ < 1 o que se garantice la terminación del episodio.

Si la dinámica del entorno se conoce por completo, entonces tenemos un sistema de ecuaciones lineales. En principio, su solución es un cálculo sencillo, aunque tedioso, así que para nuestros propósitos, los métodos de solución iterativos son los más adecuados.

Considere una secuencia de funciones de valor aproximado V₀, V₁, V₂, etc. La aproximación inicial V₀ se elige arbitrariamente (excepto que al estado terminal, si lo hay, se le debe dar el valor 0), y cada aproximación sucesiva se obtiene usando la ecuación de Bellman como una regla de actualización:

Este algoritmo se denomina evaluación de políticas iterativa.

Para producir cada aproximación sucesiva de Vₖ₊₁ a partir de Vₖ, la evaluación de política iterativa aplica la misma operación a cada estado s. Es decir, reemplaza el antiguo valor de s con un nuevo valor obtenido de los antiguos valores de los estados sucesores de s, y las recompensas inmediatas esperadas, a lo largo de todas las transiciones de pasos posibles bajo la política que se está evaluando.

Llamamos a este tipo de operación una “copia de seguridad completa”. Cada iteración de la evaluación iterativa de políticas respalda el valor de cada estado una vez para producir la nueva función de valor aproximado Vₖ₊₁.

Hay varios tipos diferentes de copias de seguridad completas, dependiendo de si se está realizando una copia de seguridad de un estado (como aquí) o de un par de acción-estado, y según la forma precisa en que se combinan los valores estimados de los estados sucesores. Todas las copias de seguridad realizadas en algoritmos de DP se denominan copias de seguridad completas porque se basan en todos los siguientes estados posibles en lugar de en un estado siguiente de muestra.

Para escribir un programa de computadora secuencial para implementar la evaluación de políticas iterativa, según lo dado por:

se tendría que utilizar dos matrices, una para los viejos valores Vₖ, y uno de los nuevos valores Vₖ₊₁. De esta manera, los nuevos valores se pueden calcular uno por uno a partir de los valores anteriores sin que se modifiquen los valores anteriores.

Por supuesto, es más fácil usar una matriz y actualizar los valores “en su lugar”, es decir, con cada nuevo valor sobrescribiendo inmediatamente el anterior. Luego, dependiendo del orden en que se sobrescriban los estados, a veces se usan valores nuevos en lugar de los antiguos en el lado derecho de la ecuación. Este algoritmo ligeramente diferente también converge y, de hecho, generalmente converge más rápido que la versión de dos arreglos, como era de esperar, ya que usa nuevos datos tan pronto como están disponibles.

Otro punto de implementación se refiere a la terminación del algoritmo. Formalmente, la evaluación iterativa de políticas converge solo en el límite, pero en la práctica debe detenerse antes de llegar a este punto. Una condición de parada típica para la evaluación iterativa de políticas es probar la cantidad maxₛ(|Vₖ₊₁(s)-Vₖ(s)|) después de cada barrido y detenerse cuando sea lo suficientemente pequeño.

Veamos como se realiza la implementación de este algoritmo:

Donde π(s,a) es una política arbitraria, por ejemplo puede ser una política aleatoria.

Veamos como se comporta esto en un ejemplo. Para esto consideremos una grilla de 4x4 donde los estados superior izquierdo e inferior derecho son terminales. Para cada estado hay cuadro posibles acciones que son [arriba, abajo, izquierda, derecha] que determinísticamente causan las correspondientes transiciones de estado, excepto que las acciones que sacarían al agente de la red dejan el estado sin cambios.

La recompensa se fija en -1 para todas las transiciones hasta que se alcanza el estado terminal. Y por último supongamos que el agente sigue la política aleatoria equiprobable (todas las acciones son igualmente probables).

Convergencia de la evaluación iterativa de políticas.

La columna de la izquierda de la figura anterior es la secuencia de aproximaciones de la función de valor de estado para la política aleatoria. La columna de la derecha es la secuencia de políticas codiciosas correspondientes a las estimaciones de la función de valor (se muestran flechas para todas las acciones que logran el máximo):

Mejora de políticas

La razón para calcular la función de valor de una política es ayudar a encontrar mejores políticas. Suponga que hemos determinado la función de valor Vπ para una política determinista arbitraria π. Para algún estado s, nos gustaría saber si debemos o no cambiar la política para elegir de manera determinista una acción a. Sabemos lo bueno que es seguir la política actual, pero ¿sería mejor o peor cambiar a la nueva política?.

Para responder esto hacemos uso del teorema de mejora de políticas. Este teorema nos dice que: sea π y π’ cualquier par de políticas deterministas tales que, para todos los estados se cumple:

Entonces la política π’ debe ser tan buena o mejor que π. Es decir:

Hasta ahora hemos visto cómo, dada una política y su función de valor, podemos evaluar fácilmente un cambio en la política en un solo estado para una acción en particular. Es una extensión natural considerar cambios en todos los estados y en todas las acciones posibles, seleccionando en cada estado la acción que mejor aparece de acuerdo con Qπ(s,a), en otras palabras, considerar la nueva política codiciosa.

Por construcción, la política codiciosa cumple las condiciones del teorema de mejora de políticas, por lo que sabemos que es tan buena o mejor que la política original. El proceso de hacer una nueva política que mejore una política original, haciéndola codiciosa con respecto a la función de valor de la política original, se denomina mejora de la política.

Iteración de políticas

Una vez que se ha mejorado una política π utilizando Vπ para producir una mejor política π’, podemos calcular Vπ’ y mejorarla de nuevo para producir una mejor política. Así podemos obtener una secuencia de políticas y funciones de valor que mejoran monótonamente.

Esta forma de encontrar una política óptima se denomina iteración de políticas. Tenga en cuenta que cada evaluación de política, es en sí misma un cálculo iterativo, se inicia con la función de valor de la política anterior. Por lo general, esto da como resultado un gran aumento en la velocidad de convergencia de la evaluación de políticas.

Iteración de valores

Un inconveniente de la iteración de políticas es que cada una de sus iteraciones implica una evaluación de políticas, que en sí misma puede ser un cálculo iterativo prolongado que requiere múltiples barridos a través del conjunto de estados.

El paso de evaluación de políticas de la iteración de políticas se puede truncar de varias formas sin perder las garantías de convergencia de la iteración de políticas. Un caso especial importante es cuando la evaluación de políticas se detiene después de un solo barrido, este algoritmo se llama iteración de valor.

La iteración de valor se obtiene simplemente convirtiendo la ecuación de optimalidad de Bellman en una regla de actualización. También observe cómo la copia de seguridad de iteración de valor es idéntica a la copia de seguridad de evaluación de políticas excepto que requiere que se tome el máximo en todas las acciones.

Finalmente, consideremos cómo termina la iteración de valor. Al igual que la evaluación de políticas, la iteración de valor requiere formalmente un número infinito de iteraciones para converger exactamente. En la práctica, nos detenemos una vez que la función de valor cambia solo una pequeña cantidad en un barrido.

La iteración de valor combina efectivamente, en cada uno de sus barridos, un barrido de evaluación de políticas y un barrido de mejora de políticas. En general, toda la clase de algoritmos de iteración de políticas truncados se puede considerar como secuencias de barridos, algunos de los cuales utilizan copias de seguridad de evaluación de políticas y otros utilizan copias de seguridad de iteración de valor. Todos estos algoritmos convergen en una política óptima para MDP finitos con descuento.

Y eso sería todo, notemos que los métodos de DP requieren un modelo completo del entorno y esto en la mayoría de situaciones no se dispone. Otro inconveniente importante de los métodos de DP que hemos discutido hasta ahora es que involucran operaciones en todo el conjunto de estados del MDP, es decir, requieren barridos del conjunto de estados. Si el conjunto de estados es muy grande, incluso un solo barrido puede resultar prohibitivamente caro. Por ejemplo, el juego de backgammon tiene más de 10²⁰ estados. Incluso si pudiéramos realizar la iteración de valor en un millón de estados por segundo, llevaría más de mil años completar un solo barrido.

Finalmente, notemos una última propiedad especial de los métodos DP. Estos actualizan estimaciones de los valores de los estados basándose en estimaciones de los valores de los estados sucesores, es decir, actualizan estimaciones sobre la base de otras estimaciones. A esto lo llamamos bootstrapping. Muchos métodos de aprendizaje por refuerzo realizan bootstrapping, incluso aquellos que no requieren, como lo requiere DP, un modelo completo y preciso del entorno. Pero eso lo veremos mas adelante.

Mientras tanto puedes ir consultando la notebook con la implementación de los algoritmos de programación dinámica en el repositorio de Git:

GitHub - jcerretani/AprendizajePorRefuerzo

Contribute to jcerretani/AprendizajePorRefuerzo development by creating an account on GitHub.

github.com

No te preocupes si no entendiste algo de la implementación de estos algoritmos, en la siguiente parte vamos a ver paso a paso como implementar estos algoritmos en Python y ahí va a quedar mucho mas claro.

El aprendizaje por refuerzo se destaca, en mi opinión personal, como uno de los enfoques más desafiantes en el campo de la ciencia de datos, y requieren releer varias veces la teoría y realizar la implementación en código manualmente para comprender a fondo los conceptos. Así que no te frustres, relee varias veces este articulo y si algo no queda claro siempre puedes consultarme.

Te espero en la siguiente parte de este capítulo!