Aprendizaje por refuerzo (RL) — Capítulo 3: Multi-armed bandit — Parte 2: UCB, Softmax y muestreo de Thompson

14 min readDec 6, 2023

Arrancamos este segunda parte del capítulo de Multi-armed bandit donde vamos a ver las estrategias de Upper Confidence Bound, Softmax y Multi-armed bandit con muestreo de Thompson que nos permite potenciar aún mas los algoritmos que vimos en la parte anterior.

Listos?, manos a la obra!

Upper Confidence Bound

En el contexto del aprendizaje por refuerzo, específicamente en la aplicación de los algoritmos Multi-armed bandit con Epsilon-greedy o Epsilon-decreasing, surge una cuestión que merece nuestra atención. Este problema se relaciona con la necesidad de seleccionar adecuadamente el valor de ϵ o controlar cómo disminuye en el caso del algoritmo Epsilon-decreasing. Aunque esta decisión puede parecer trivial, es importante destacar que deseamos minimizar la dependencia de nuestro agente de nuestras elecciones y configuraciones específicas.

En contraste, el algoritmo Upper Confidence Bound (UCB) se distingue por su capacidad para ajustar automáticamente el equilibrio entre la exploración y la explotación a medida que acumula más información sobre el entorno. Esta característica permite al agente tomar decisiones basadas en la exploración de opciones menos conocidas o, en su lugar, seleccionar la acción que promete la recompensa estimada más alta.

Un aspecto fundamental del enfoque de UCB radica en su búsqueda por estimar la recompensa asociada a cada acción en lugar de intentar predecir su valor exacto. Esta metodología nos brinda la ventaja de no solo estimar la recompensa esperada, sino también de incorporar la incertidumbre asociada a dicha recompensa.

La representación de la función de recompensa para cada acción se puede entender como una estimación puntual basada en la tasa promedio de recompensa observada. Inspirados en la intuición de los intervalos de confianza, podemos enriquecer aún más nuestras estimaciones al introducir un límite de incertidumbre alrededor de cada valor estimado. Esta adición proporciona una visión más completa y realista de la recompensa potencial de cada acción, lo que contribuye a la toma de decisiones más informadas y adaptativas por parte del agente.

Con UCB la acción elegida en cada paso viene dada por:

Donde Q(a) es el valor estimado de la acción a, al igual que con el algoritmo que estudiamos anteriormente. Nₐ es el número de veces que se ha seleccionado la acción a, equivalente a k en los algoritmos de Epsilon-greedy y Epsilon-decreasing. N es la cantidad de acciones totales tomadas (N = ∑ Nₐ), y finalmente c es un valor de confianza que controla el nivel de exploración.

La ecuación de UCB (Upper Confidence Bound) se descompone en dos componentes esenciales. Por un lado, tenemos la parte de explotación representada por la función Q(a’). Esta parte se basa en el principio de “optimismo ante la incertidumbre”, lo que significa que cuando no estamos seguros de cuál acción es la mejor, elegimos la que parece ser la mejor hasta el momento. Esta primera parte de la ecuación refleja precisamente este concepto.

Ahora, profundicemos más en la expresión de la raíz a la derecha de la ecuación para entender su origen. Esta expresión se deriva de la desigualdad de Hoeffding, que establece un límite superior para la probabilidad de que la suma de variables aleatorias independientes y acotadas se aleje de su valor esperado en una cantidad específica.

La segunda parte de la ecuación introduce el componente exploratorio mediante el factor c, que permite controlar el nivel de exploración. Esta expresión aporta a la ecuación una medida de la incertidumbre asociada con la estimación de las recompensas al tomar una acción determinada. Esta expresión consta de dos factores clave. En primer lugar, tenemos el término Nₐ, que será pequeño si una acción no se ha seleccionado con frecuencia. Dado que este factor es el denominador de la expresión, cuando es pequeño, la incertidumbre es alta, lo que aumenta la probabilidad de seleccionar esa acción. Por otro lado, si una acción se selecciona con mayor frecuencia, el término Nₐ será grande, lo que disminuirá la incertidumbre y, por lo tanto, será menos probable seleccionar esa acción, a menos que el término de explotación sea significativamente alto, lo que indica que la acción es altamente rentable.

El segundo término relevante es log(N). Cuando una acción no se ha seleccionado, el valor de N aumentará, pero Nₐ permanecerá igual. Por lo tanto, la expresión de la derecha será mayor, lo que aumentará las posibilidades de seleccionar esa acción en la próxima iteración debido a que su incertidumbre ha aumentado en comparación con la acción previamente seleccionada.

Es importante destacar que el término N crece de manera logarítmica, mientras que Nₐ lo hace de manera lineal. Esto significa que con el tiempo y a medida que acumulamos más información sobre el entorno, la componente de incertidumbre converge gradualmente a cero. Eventualmente, las acciones se seleccionan exclusivamente en función del término de explotación.

Esto confiere a UCB una característica similar a la estrategia Epsilon-decreasing, donde la exploración inicial tiene un peso mayor y gradualmente el agente se enfoca en explotar la acción con el mayor retorno esperado a medida que adquiere más conocimiento del entorno.

Finalmente, ahora que ya tenemos un conocimiento profundo respecto a como se deriva UCB, vamos a encargarnos de entender como realizar esta implementación. Existen diferentes variantes de los algoritmos UCB, pero aquí nos dedicaremos exclusivamente al algoritmo UCB1, que no es mas que setear el parámetro c como la raíz de 2. Por lo tanto en UCB1 la ecuación nos queda de la forma:

La implementación del algoritmo es igual a como hicimos en la parte anterior, solo se modifica la forma en la que se selecciona la acción, que en vez de ser seleccionada a partir de un valor aleatorio controlado por épsilon, ahora esa selección se hace a partir de la propia incertidumbre de nuestra estimación de la acción:

Y con estas simples modificaciones a nuestra versión anterior de Multi-armed bandit tenemos implementado UCB1.

Si realizamos la implementación UCB1 podremos observar como a medida que pasa el tiempo los niveles de confianza de nuestras acciones mas lucrativas disminuyen su nivel de incertidumbre ya que estas se eligieron con mayor frecuencia que el resto. Por otro lado, las acciones que tienen menos retorno esperado, tienen una mayor incertidumbre lo que le permite superar a las acciones con mayor retorno y por lo tanto estas acciones siguen teniendo oportunidad de ser seleccionadas.

A continuación puede ver una animación del entrenamiento. En la columna izquierda se encuentra la estimación del valor de la acción y el punto blanco indica la acción seleccionada en cada paso. Las franjas indican la incertidumbre de la estimación de valor de la acción. La segunda columna muestra las probabilidades reales de cada “tragamoneda”.

Podemos observar como, a pesar de que algunas acciones tienen una estimación de valor promedio baja, su incertidumbre es alta por lo que el agente sigue explorando esas acciones. Por otro lado la acción de la derecha tiene una estimación de valor promedio mas alta por lo que el agente tiene mayor preferencia por dicha acción lo que hace que la incertidumbre de dicha acción se reduzca rápidamente.

Softmax Algorithm

A continuación, exploraremos un tercer algoritmo en el contexto de problemas de selección de acciones. Antes de sumergirnos en este nuevo algoritmo, consideremos un escenario ilustrativo que nos ayudará a comprender su utilidad.

Imaginemos que nos encontramos ante dos situaciones distintas en las que debemos tomar decisiones entre dos acciones, ambas con recompensas promedio esperadas desconocidas para nosotros. En el primer caso, nuestras opciones son una acción con una recompensa promedio esperada de 0.5 y otra con 0.95. En el segundo caso, nuevamente enfrentamos dos opciones, pero ahora las recompensas promedio esperadas son de 0.5 y 0.51, respectivamente.

Si en ambos casos decidimos utilizar el enfoque Epsilon Greedy con un valor de epsilon específico, nuestro algoritmo seleccionará aleatoriamente entre ambas acciones en ambas situaciones con igual probabilidad. Esto significa que, a pesar de las notables diferencias en las recompensas potenciales entre los dos casos, nuestro proceso de exploración no toma en cuenta estas diferencias al determinar qué acciones explorar. Aquí es donde surge una oportunidad para mejorar este algoritmo.

En lugar de explorar las acciones de manera uniforme en ambos casos, sería beneficioso que nuestra estrategia de exploración tenga en cuenta la diferencia actual entre las recompensas promedio de las acciones disponibles. Es precisamente esto lo que propone la variante softmax del problema de Multi-armed bandit.

La variante softmax introduce una dimensión más sofisticada en nuestra estrategia de exploración. En lugar de una elección completamente aleatoria, la probabilidad de seleccionar una acción se basa en la diferencia entre sus recompensas promedio actuales. Esto nos permite asignar una mayor probabilidad de exploración a las acciones que tienen recompensas promedio más altas, lo que puede conducir a una toma de decisiones más efectiva y eficiente en situaciones donde las recompensas son desiguales.

Softmax propone la siguiente distribución de probabilidad de elegir cada acción:

Donde τ es un hiperparámetro que determina la cantidad de aleatorización al elegir una acción. Cuando τ es grande el término exponencial de cada acción es ≈1, por lo tanto todas las acciones se exploran con la misma probabilidad. Por otro lado, cuando τ es chico, el elemento exponencial de cada acción es exponencialmente proporcional a su rendimiento actual y por lo tanto las acciones con un rendimiento promedio mayor tendrán mas probabilidades de ser elegidas.

Este algoritmo, al igual que con UCB, combina aspectos de explotación y exploración en lugar de tener la necesidad de segmentar las pruebas en fases de exploración y explotación. Por otro lado, algo importante de destacar, es que este método no resulta ser tan robusto al determinar la mejor acción cuando estas tienen retornos similares, para lo cual Epsilon Greedy es más adecuado en esos casos.

Nuevamente podemos aprovechar toda la implementación que realizamos con los algoritmos anteriores, solo necesitamos cambiar la forma en la que seleccionamos las acciones:

A continuación puede ver una animación del entrenamiento. En la columna izquierda se encuentra la estimación del valor de la acción y el punto blanco indica la acción seleccionada en cada paso. La segunda columna muestra las probabilidades reales de cada “tragamoneda” y la tercera columna es la probabilidad de seleccionar cada acción según la ecuación:

Multi-armed bandit con muestreo de Thompson

Vamos a estudiar ahora la última variante de Multi-armed bandit, conocida como Multi-armed bandit con muestreo de Thompson, o también conocido como Bayesian Bandits.

Este algoritmo usa un método mas sofisticado que UCB para lidiar con el intercambio de exploración y explotación. Este, en vez de modelar el valor medio esperado y un rango de incertidumbre, genera una distribución para el retorno esperado de cada acción, conocida en las estadísticas como “a priori”. En principio esta distribución puede ser de cualquier tipo, pero la mas utilizada suele ser la distribución beta para modelar variables aleatorias.

La distribución beta está constituida de dos parámetros (α y β), los cuales son actualizados, de forma incremental, a medida que vamos interactuando con el entorno:

Donde Γ es la función gamma dada por:

Distribución beta para diferentes valores de α y β.

A medida que el agente lleva a cabo pruebas en su entorno, la distribución de cada acción se va volviendo más estrecha y elevada, convergiendo gradualmente hacia la tasa de retorno verdadera. En otras palabras, a medida que acumulamos más información sobre los resultados de una acción, la estimación del valor de esa acción se vuelve menos incierta. Este proceso guarda similitudes con el algoritmo de Upper Confidence Bound (UCB), donde también gestionábamos la incertidumbre, pero en este caso, la estimación se modela mediante una distribución.

Ahora, tenemos una comprensión de la distribución beta. Sin embargo, ¿Cómo determinamos qué acción elegir y cómo actualizamos la estimación del valor de cada acción?

La selección de la acción en cada paso de tiempo se lleva a cabo de la siguiente manera: dado que conocemos que el retorno de cada acción está representado por una distribución, esta distribución se convierte en la probabilidad de elegir una acción en ese momento. Es análogo a cómo aplicamos la variante Softmax, donde calculamos la probabilidad de cada acción. En este caso, generamos un valor aleatorio para cada acción, pero no cualquier valor, sino uno que siga la distribución de probabilidad de esa acción. Este proceso se repite para todas las acciones, y luego seleccionamos la acción que generó el valor más alto. Este enfoque garantiza que todas las acciones tengan la oportunidad de ser exploradas. De manera similar a UCB, aquellas acciones con menor incertidumbre (distribuciones más estrechas) y valores medios más altos tienen una mayor probabilidad de ser seleccionadas. Sin embargo, incluso las acciones con valores medios más bajos aún tienen la posibilidad de ser exploradas si la incertidumbre en los resultados de esa acción es alta.

En cuanto a la actualización de la distribución de la estimación de los retornos de la acción, tenemos dos objetivos claros. Por un lado, buscamos que la media de la distribución se acerque al valor real del retorno de la acción. Por otro lado, deseamos que la incertidumbre disminuya a medida que acumulamos más información específica sobre esa acción. Este proceso de actualización es fundamental para que el agente tome decisiones más informadas a lo largo del tiempo.

Con un poco de aritmética sobre la ecuación de la distribución beta llegamos a que la media y la varianza de la distribución se puede expresar en términos de α y β como:

A partir de estas dos definiciones y un poco de esfuerzo, podemos ver que la siguiente actualización de parámetros satisface las dos condiciones que buscamos:

Estas dos ecuaciones lo que nos dice es que si tomamos la acción a y obtenemos una recompensa de r, entonces la distribución beta de dicha acción se actualiza modificando el parámetro α simplemente sumándole la recompensa obtenida, y el parámetro β sumándole 1 y restándole la recompensa obtenida al valor actual. Esta actualización nos va a disminuir la incertidumbre (hace la distribución mas angosta) de la distribución a medida que dicha acción es seleccionada y, al mismo tiempo, va a desplazar su media al retorno promedio esperado de dicha acción.

Al inicio, al menos que tengamos un conocimiento previo del entorno, α y β se inicializan ambos en 1 que corresponde a una distribución uniforme.

Finalmente los pasos para implementar este algoritmo se pueden resumir en:

Como hicimos con los algoritmos anteriores, veamos una animación del entrenamiento. A la izquierda se encuentran las distribuciones de la estimación del retorno de cada acción y a la derecha probabilidad de seleccionar cada acción según la ecuación:

Podemos ver que a medida que una acción es seleccionada mas veces su distribución se vuelve mas angosta al mismo tiempo que su centro converge a la probabilidad real del retorno esperado.

Y hasta aquí todo sobre los algoritmos de Multi-armed bandit, pero antes de terminar este capítulo me gustaría tratar un punto interesante.

Valores iniciales optimistas

En todos los métodos previamente abordados, existe una dependencia en cierta medida de las estimaciones iniciales del valor de la acción, denotadas como Q₀(a). Estas estimaciones iniciales se convierten efectivamente en un conjunto de parámetros que el usuario debe seleccionar, incluso si opta por asignarles un valor nulo. La ventaja de este enfoque radica en su capacidad para proporcionar un medio sencillo de incorporar conocimientos previos acerca del nivel de recompensas esperado. Asimismo, las estimaciones iniciales de los valores de acción pueden utilizarse para fomentar la exploración de manera eficaz.

Imaginemos una situación en la que, en lugar de configurar todas las estimaciones iniciales de los valores de acción en cero, como se ha hecho previamente, decidimos asignarles a todas un valor de +5. Por consiguiente, si conocemos que la recompensa máxima que podemos esperar es inferior a +5 (debido a un entendimiento previo del problema), esta estimación inicial tan optimista estimula la exploración. Sin importar qué acciones se elijan inicialmente, las recompensas obtenidas serán inferiores a las estimaciones iniciales, lo que lleva al agente a probar otras acciones con la sensación de estar “decepcionado” por las recompensas que recibe. Como resultado, se realizan múltiples intentos en todas las acciones antes de llegar a una decisión final. Este enfoque garantiza un nivel significativo de exploración, incluso si se opta por acciones avariciosas de manera constante.

Inicialmente, este método optimista puede parecer menos efectivo que la estrategia epsilon-greedy porque genera una exploración más intensiva. Sin embargo, con el tiempo, el método optimista supera a la estrategia epsilon-greedy ya que la exploración disminuye gradualmente. A esta técnica para fomentar la exploración se le conoce como “valores iniciales optimistas”.

Es importante destacar que este es un truco sencillo que puede ser bastante efectivo en problemas estacionarios. Sin embargo, no es una solución universalmente aplicable para promover la exploración y presenta limitaciones en escenarios no estacionarios. Cuando la tarea cambia y se crea una nueva necesidad de exploración, este método resulta insuficiente. En realidad, es improbable que cualquier enfoque que se base en las condiciones iniciales ofrezca una solución adecuada para problemas no estacionarios.

Y con esto finalizamos todos los algoritmos para resolver el problema de Multi-armed bandit que vamos a ver en este capítulo. Existen otras estrategias, mas y menos sofisticadas, pero todas se basan en el mismo principio, asi que por el momento lo dejamos hasta acá. En la próxima parte vamos a ver como implementar estos algoritmos en Python, pero mientras tanto puede ir consultando el repositorio de Git donde va a encontrar las notebooks donde se implementan las estrategias que vimos a lo largo de este capítulo: