Aprendizaje por refuerzo (RL) — Capítulo 2: Introducción — Parte 3: Funciones de valor

11 min readDec 5, 2023

Bienvenidos a la tercer y última parte de este capítulo donde nos vamos a centrar en las funciones de valor, que evalúan la utilidad de estar en un estado o realizar una acción en un estado dado. Se explica cómo estas funciones se relacionan con políticas y cómo se pueden estimar mediante métodos de Monte Carlo o funciones parametrizadas. Además, se introduce la función de valor óptima y cómo se busca una política óptima en un proceso de toma de decisiones a largo plazo. Finalmente, se hace una introducción a los algoritmos de aprendizaje por refuerzo y se clasifican en diferentes tipos según el acceso a un modelo del entorno y el enfoque en políticas o valores.

Así que empecemos.

Funciones de valor

La mayoría de los algoritmos de aprendizaje por refuerzo se fundamentan en la estimación de funciones de valor. Estas funciones se aplican a estados individuales o pares estado-acción, y su propósito es evaluar cuán beneficioso es para el agente encontrarse en un estado dado o que tan bueno es realizar una acción específica en un estado determinado.

La idea subyacente detrás de esta evaluación de “beneficio” se articula en términos de recompensas futuras que se pueden anticipar, o para ser más preciso, en términos de desempeño esperado. Es importante destacar que las recompensas que un agente puede anticipar en el futuro están intrínsecamente vinculadas a las acciones que decide emprender en el presente. Por lo tanto, las funciones de valor se definen en función de políticas específicas.

Es relevante recordar que una política, representada como π(s,a), proporciona información sobre la probabilidad de tomar una acción a cuando el agente se encuentra en el estado s. En términos más informales, el valor de un estado bajo una política particular π, que se denota como Vπ(s), representa la expectativa de rendimiento al comenzar en dicho estado s y seguir la política π establecida. Esta evaluación del valor del estado guía al agente para tomar decisiones informadas y optimizar su comportamiento a lo largo del tiempo. Podemos definir Vπ(s) de manera formal cómo:

Donde Eπ denota el valor esperado dado que el agente sigue la política π, y t es cualquier paso de tiempo. Tenga en cuenta que el valor del estado terminal, si lo hay, es siempre cero.

Llamamos a la función de Vπ la función de estado-valor para la política π.

De manera similar, podemos definir el valor de tomar una acción a en el estado s bajo una política π, denotado Qπ(s,a) como el retorno esperado a partir del estado s, al tomar la acción a y luego seguir la política π:

Llamamos Qπ la función de acción-valor.

El cálculo de los valores V y Q puede obtenerse mediante la aplicación de técnicas basadas en la experiencia. Por ejemplo, cuando un agente sigue una política y registra el promedio de los retornos reales que resultan de cada estado visitado, este promedio tenderá a converger hacia el valor del estado Vπ(s) a medida que la frecuencia de visitas a dicho estado se acerca a infinito.

De manera análoga, si mantenemos registros de los promedios de los retornos para cada acción tomada en un determinado estado, estos promedios convergerán hacia los valores de la acción Qπ(s,a).

Estos enfoques de estimación son conocidos como métodos de Monte Carlo, debido a que involucran el promediado de múltiples muestras aleatorias de rendimientos reales. Sin embargo, es importante tener en cuenta que cuando hay una gran cantidad de estados, mantener promedios individuales para cada uno puede volverse impráctico. En estos casos, el agente puede optar por representar V y Q como funciones parametrizadas (por ejemplo, con redes neuronales) y ajustar sus parámetros para que se ajusten de manera más precisa a los rendimientos observados. Este enfoque permite una generalización efectiva a través de diferentes estados, lo que es esencial en problemas de alta dimensionalidad.

Una propiedad fundamental de las funciones de valor utilizadas en el aprendizaje por refuerzo y la programación dinámica es que satisfacen relaciones recursivas particulares. Para cualquier política y cualquier estado, se cumple la siguiente condición de coherencia entre el valor del estado y el valor de sus posibles estados sucesores:

Donde recordemos que P(s,a,s’) nos dice la probabilidad de que si en el estado s tomamos una acción a lleguemos al estado s’:

Y R(s,a,s’) es el valor esperado de la recompensa si en el estado s tomamos una acción a y llegamos al estado s’:

La ecuación de Vπ(s) anterior, es la ecuación de Bellman. Esta ecuación expresa una relación entre el valor de un estado y los valores de sus estados sucesores. La ecuación de Bellman promedia todas las posibilidades, ponderando cada una por su probabilidad de ocurrir. Establece que el valor del estado inicial debe ser igual al valor (descontado) del siguiente estado esperado, más la recompensa esperada en el camino. Mas adelante veremos cómo esta ecuación forma la base para estimar Vπ, o en su forma equivalente para pares de estado-acción, para estimar Qπ.

Función de valor óptima

Resolver una tarea de aprendizaje por refuerzo significa, en términos generales, encontrar una política que logre muchas recompensas a largo plazo. Para MDP finitos, podemos definir con precisión una política óptima.

Una política π se define como mejor o igual que una política π’ si su rendimiento esperado es mayor o igual que π’ para todos los estados. En otras palabras, π ≥ π’ si y solo si Vπ(s) ≥ Vπ’(s) para todos los estados s. Siempre hay al menos una política que es mejor o igual que todas las demás políticas, esta es la política óptima, aunque puede haber más de una, todas las políticas óptimas las denotamos por π* y comparten la misma función de valor de estado, llamada función óptima de valor-estado V*, definida como:

Las políticas óptimas también comparten la misma función de valor-acción, definida como:

Para el par estado-acción, esta función da el retorno esperado por tomar acción a en el estado s y luego seguir una política óptima. Por lo tanto, podemos escribir Q* en términos de V* de la siguiente manera:

Dado que V* es la función de valor para una política, debe satisfacer la condición de autoconsistencia dada por la ecuación de Bellman. Sin embargo, debido a que es la función de valor óptimo, la condición de coherencia se puede escribir en una forma especial sin hacer referencia a ninguna política específica. Esta es la ecuación de Bellman V* o la ecuación de optimalidad de Bellman. Intuitivamente, la ecuación de optimalidad de Bellman expresa el hecho de que el valor de un estado bajo una política óptima debe ser igual al rendimiento esperado para la mejor acción de ese estado:

De forma similar, la ecuación de optimalidad de Bellman para Q* es:

En el contexto de los Procesos de Decisión de Markov (MDP) finitos, surge la interesante ecuación de optimalidad de Bellman, que nos ofrece una solución única y, lo que es aún más intrigante, independiente de la política en juego. Esta ecuación, en realidad, representa un sistema de ecuaciones, siendo una ecuación para cada estado. En otras palabras, si consideramos que existen N estados en nuestro problema, también existen N ecuaciones con N incógnitas. Esta relación matemática se basa en la dinámica subyacente del entorno, que se caracteriza por las funciones P(s, a, s’) y R(s, a, s’). Con este conocimiento en mano, teóricamente, podemos resolver este sistema de ecuaciones.

Una vez que hemos logrado obtener la solución y hemos identificado el valor óptimo V*, se facilita en gran medida la tarea de determinar una política óptima. Para cada estado s, se revelará una o más acciones que maximizan el valor en la ecuación de optimalidad de Bellman. Cualquier política que asigne una probabilidad distinta de cero únicamente a estas acciones es considerada una política óptima. Podemos concebir esto como una especie de búsqueda a corto plazo. Si contamos con la función de valor óptimo, entonces las acciones que surgen como las más ventajosas después de una sola búsqueda se convierten en las acciones óptimas. Otra manera de expresar esto es que cualquier política que siga una estrategia codiciosa con respecto a la función de valor óptimo es, en realidad, una política óptima.

El término “codicioso” se emplea en el ámbito informático para describir un proceso de búsqueda o toma de decisiones que se basa únicamente en consideraciones locales o inmediatas, sin tener en cuenta la posibilidad de que dicha elección pueda bloquear el acceso a alternativas potencialmente mejores en el futuro. En otras palabras, se refiere a políticas que eligen acciones basándose únicamente en sus resultados a corto plazo. La belleza inherente a la función V* radica en el hecho de que, al usarla para evaluar las consecuencias a corto plazo de las acciones, especialmente aquellas que resultan de un solo paso, una política codiciosa se convierte en óptima en el sentido a largo plazo que nos interesa. Esto se debe a que V* ya tiene en cuenta las consecuencias de recompensa de cualquier posible comportamiento futuro. Por lo tanto, llevar a cabo una búsqueda a corto plazo nos conduce a las acciones óptimas en el largo plazo. Esta perspicaz relación entre el corto y largo plazo hace que el proceso de toma de decisiones sea altamente efectivo en el marco de los MDP finitos.

Tener Q* hace que elegir las acciones óptimas sea aún más fácil. Con Q*, el agente ni siquiera tiene que hacer una búsqueda de un paso adelante: para cualquier estado s, simplemente puede encontrar cualquier acción que maximice Q*. La función de valor de acción almacena en caché los resultados de todas las búsquedas de un paso adelante. Por tanto, a costa de representar una función de pares estado-acción, en lugar de solo estados, la función óptima acción-valor permite seleccionar acciones óptimas sin tener que saber nada sobre posibles estados sucesores y sus valores, es decir, sin tener que saber algo sobre la dinámica del entorno.

Resolver explícitamente la ecuación de optimalidad de Bellman proporciona una ruta para encontrar una política óptima y, por lo tanto, para resolver el problema del aprendizaje por refuerzo. Sin embargo, esta solución rara vez es directamente útil. Es similar a una búsqueda exhaustiva, mirando hacia adelante en todas las posibilidades, calculando sus probabilidades de ocurrencia y su deseabilidad en términos de recompensas esperadas. Esta solución se basa en al menos tres supuestos que rara vez son ciertos en la práctica:

Conocemos con precisión la dinámica del medio ambiente.
Tenemos suficientes recursos computacionales para completar el cálculo de la solución.
La propiedad de Markov.

Para los tipos de tareas que nos interesan, la implementación de una solución exacta suele ser inviable debido a la infracción de varios supuestos fundamentales. Por ejemplo, aunque los primer y tercer supuestos no presentan obstáculos en el contexto del juego de backgammon, el segundo supuesto representa una barrera significativa. Este juego cuenta con alrededor de 10²⁰ estados posibles, lo que implicaría la necesidad de miles de años de cálculos incluso en las computadoras más avanzadas de hoy en día para resolver la ecuación de Bellman y obtener los valores óptimos de V* o Q*. En el campo del aprendizaje por refuerzo, a menudo debemos conformarnos con soluciones aproximadas.

Existen diversos enfoques para abordar la resolución aproximada de la ecuación de optimalidad de Bellman, como los métodos de programación dinámica. Muchos de los métodos utilizados en el aprendizaje por refuerzo pueden ser entendidos de manera clara como soluciones aproximadas de esta ecuación, empleando experiencias reales de transiciones en lugar de depender únicamente del conocimiento de las transiciones esperadas. A lo largo de esta serie, exploraremos varios de estos métodos en detalle.

Algoritmos de aprendizaje por refuerzo

Existen varios tipos de aprendizaje por refuerzo, pero en general estos se pueden diferenciar en cinco clases:

Tipos de modelos de aprendizaje por refuerzo.

Uno de los puntos de ramificación más importantes en un algoritmo aprendizaje por refuerzo es la cuestión de si el agente tiene acceso a un modelo del entorno y a la vez, si tiene acceso, si este es aprendido o dado. Este punto ya lo discutimos en una sección anterior. La Segunda ramificación importante se da en los algoritmos libre de modelos donde estos pueden ser basado en políticas o en valores, o un híbrido entre ambos. Un método de aprendizaje por refuerzo basado en valores, intenta maximizar una función de valor Vπ o Qπ, y es en base a maximizar esta función de valor que construimos nuestra política. En un método de aprendizaje por refuerzo basado en políticas, se intenta idear una política tal que la acción realizada en cada estado sea óptima para obtener la máxima recompensa en el futuro. Aquí, no está involucrada ninguna función de valor, directamente se busca obtener la política óptima sin necesidad de una función de valor intermediaria.

Todos los conceptos que tratamos en este capitulo los vamos a ir repasando a medida que vamos tratando cada uno de los temas, así que no se preocupe si no entiende todos los conceptos por ahora, mas adelante van a quedar mucho mas en claro.

Y hasta aquí este capítulo introductorio sobre el aprendizaje por refuerzo. En el próximo capítulo, exploraremos en detalle los métodos relacionados con el dilema del “Multi-armed bandit”.

Este dilema se asemeja a la situación de un jugador en un casino que se enfrenta a una fila de máquinas tragamonedas (bandits) con diferentes tasas de pago desconocidas. El jugador debe decidir en cuál máquina apostar en cada turno para maximizar sus ganancias a largo plazo. Cada vez que el jugador tira de una palanca, recibe una recompensa en forma de ganancia o pérdida. El desafío radica en encontrar una estrategia óptima para seleccionar las máquinas y maximizar las ganancias.

En el próximo capítulo, profundizaremos en los métodos específicos utilizados para abordar este dilema, explorando en detalle sus enfoques y algoritmos clave. Esta comprensión es esencial para construir una base sólida en el aprendizaje por refuerzo y avanzar en la creación de agentes inteligentes capaces de tomar decisiones efectivas en una variedad de entornos. ¡No te pierdas el próximo capítulo!.