Softmax para un problema Bandido Multibrazo (Multi-Armed Bandit)

Publicado el 19 marzo 2021 por Daniel Rodríguez @analyticslane

Epsilon-Greedy es una estrategia que ofrece buenos resultados en la optimización de un problema Bandido Multibrazo (Multi-Armed Bandit). Aunque durante la fase de exploración selecciona todos los bandidos con la misma probabilidad. Algo que se puede optimizar seleccionando en esta fase los bandidos en base al valor de su recompensa esperada. Con lo que el agente solamente se centrará en identificar a los mejores bandidos. Ignorando aquellos en los que sabe que la recompensa es inferior. Esto es algo que soluciona la estrategia Softmax, en la que el agente selecciona los bandidos en proporción al conocimiento que tiene en cada momento de su recompensa esperada. Veamos en esta entrada como implementar Softmax para un problema Bandido Multibrazo (Multi-Armed Bandit).

El problema de Epsilon-Greedy en la fase de exploración

En la fase de exploración Epsilon-Greedy selecciona los bandidos aleatoriamente. Algo que sucede independientemente del uso de un factor de decaimiento o no. Esto hace que, en caso de tener tres bandidos con una recompensa esperada de 1, 2 y 3 experimente con todos ellos con la misma probabilidad. Por otro lado, en caso de que las recompensas sean 1, 20 y 21, hará exactamente lo mismo. Siendo mejor en este segundo que se centre en el segundo y tercer bandido para saber con certeza cuál de ellos es el mejor. Lo que puede hacer que tarde un número mayor de tiradas en seleccionar el tercero.

A medida que el conocimiento de la recompensa de cada uno de los bandidos aumenta una posible mejora es centrarse únicamente en los ofrecen mayor recompensa. Una mejora que implementa Softmax.

Softmax para un problema Bandido Multibrazo

El algoritmo Sofmax propone seleccionar a cada uno de los bandidos con una probabilidad proporcional al valor de su recompensa esperada actualmente. Probabilidad que se calculará con la siguiente expresión

P_i = \frac{e^{\frac{r_i}{\tau}}}{\sum e^{\frac{r_j}{\tau}}}

donde r_i es la recompensa promedio actual del bandido i y \tau. es un hiperparámetro que indica la proporción con la que se selecciona aleatoriamente un bandido.

Así, en cada una de las tiradas se selecciona al bandido con el que se jugará proporcionalmente a P_i. Siendo de este modo más probable jugar con los mejores bandidos y menos con los peores. Evitando seleccionar las peores opciones. Lo que aumenta las esperanza de obtener mejores recompensas que explorando los bandidos de una forma completamente aleatoria.

Selección del hiperparámetro \tau.

En Softmax, la selección del valor de \tau. es clave, ya que es el valor que determina el porcentaje de veces que se selecciona un bandido al azar. Esto es, determina las tiradas dedicadas a la exploración. Teniendo un efecto similar al de épsilon en Epsilon-Greedy.

Al aumentar el valor de \tau., el porcentaje de veces que se selecciona un bandido al azar aumenta. Por otro lado, si se reduce el valor de \tau., la fase de exploración se reduce. Por lo que la recompensa esperada aumentará.

Esto se puede ver con un ejemplo, si tenemos bandidos con una recompensa promedio de 0,02, 0,06 y 0.10 se puede obtener la probabilidad de jugar con el siguiente código

import numpy as np

mean = [0.02, 0.06, 0.10]

for tau in [1, 0.1, 0.01]:
    prob = [np.exp(m / tau) for m in mean]
    prob /= np.sum(prob)
    
    print(f'tau: {tau} recompensas: {prob}')
tau: 1 recompensas: [0.32009241 0.33315563 0.34675197]
tau: 0.1 recompensas: [0.21198272 0.31624106 0.47177622]
tau: 0.01 recompensas: [3.29320439e-04 1.79802867e-02 9.81690393e-01]

Lo que indica que, si el valor de \tau. es 1, prácticamente jugará con todos los bandidos con la misma probabilidad. Por otro lado, si el valor es 0.1 seleccionará el mejor un 47%. Algo que no es lo óptimo para este problema. Finalmente, si el valor es 0.01 el 98% de las veces seleccionará al mejor de los bandidos, seleccionado menos del 2% de las veces al resto. Una solución que aumenta la probabilidad de maximizar la recompensa total obtenida.

Implementación en Python Softmax para un problema Bandido Multibrazo

En este caso vamos a crear una clase Softmax para implementar este algoritmo. Clase que vamos a basar en la clase Epsilon empleada en la entrada anterior sobre valores iniciales optimistas. Además, como implementación del bandido se usará la clase Bandit de esta entrada.

En la nueva clase Softmax es necesario cambiar el método de inicialización, ya que los parámetros han cambiado, y el método run() en el que se selecciona y juega con un bandido. Esta es la clase que se muestra a continuación.

class Softmax(Epsilon):
    def __init__(self, bandits, tau):
        self.bandits = bandits
        self.tau = tau
        
        self.reset()
    
    
    def run(self, episodes=1):
        for i in range(episodes):
            prob = [np.exp(m / self.tau) for m in self._mean]
            prob /= np.sum(prob)
            prob = np.cumsum(prob)
            
            bandit = np.where(prob > np.random.random())[0][0]
            
            # Obtención de una nueva recompensa
            reward = bandits[bandit].pull()
            
            # Agregación de la recompensa al listado
            self._rewards.append(reward)
            
            # Actualización de la media
            self._plays[bandit] += 1
            self._mean[bandit] = (1 - 1.0/self._plays[bandit]) * self._mean[bandit] \
                                 + 1.0/self._plays[bandit] * reward
            
            
        return self.average_reward()
        
    
    def reset(self):
        self._rewards = []
        self._plays = [0] * len(self.bandits)
        self._mean = [0] * len(self.bandits)

Lo primero que vemos es que ahora, además del parámetro con los bandidos, solamente hay un parámetro tau. Con lo que se simplifica los métodos __init__() y run() de la nueva clase.

Los cambios más importantes se encuentran en método run(), donde se cambia el algoritmo de selección. Ahora se calcula la probabilidad de jugar con cada uno de los bandidos utilizando la expresión Softmax y posteriormente se selecciona el bandido aleatoriamente.

Comparación de los resultados

Ahora que tenemos la clase con la implementación del Softmax se puede comparar con los resultados obtenidos anteriormente. Lo que se puede hacer con el siguiente código (es necesario importar previamente las clases Bandit y Epsilon de la entrada anterior o usar la refactorización incluida en el apéndice de esta entrada).

np.random.seed(0)

bandits = [Bandit(0.02), Bandit(0.06), Bandit(0.10)]

epsilon = Epsilon(bandits)
decay = Epsilon(bandits, epsilon=1, decay=0.999)
optimistic = Epsilon(bandits, initial=[0.2, 0.2, 0.2])
softmax = Softmax(bandits, 0.01)

epsilon.run(20000)
decay.run(20000)
optimistic.run(20000)
softmax.run(20000)

epsilon.plot(True, label='Epsilon')
decay.plot(True, label='Decay')
optimistic.plot(True, label='Optimistic')
softmax.plot(True, True, label='Softmax')
plt.legend()

Lo que da como resultado el siguiente gráfico.

Comparación de la recompensa media obtenida en función del número de tiradas con Epsilon-Greedy, valores iniciales optimistas y Softmax

En este gráfico se puede ver que softmax es claramente el algoritmo que antes llega a una solución óptima, ya que desde las primeras tiradas usa la información disponible para seleccionar los bandidos.

Efecto de \tau. en los resultados

Aunque en el caso de Softmax es importante seleccionar correctamente el valor de \tau., ya que una selección incorrecta puede llevar soluciones que no son óptimas. Algo que se puede ver con el siguiente ejemplo.

np.random.seed(0)

bandits = [Bandit(0.02), Bandit(0.06), Bandit(0.10)]

softmax_a = Softmax(bandits, 0.1)
softmax_b = Softmax(bandits, 0.02)
softmax_c = Softmax(bandits, 0.01)

softmax_a.run(20000)
softmax_b.run(20000)
softmax_c.run(20000)

softmax_a.plot(True, label='0.1')
softmax_b.plot(True, label='0.02')
softmax_c.plot(True, True, label='0.01')
plt.legend()

Lo que da como resultado el siguiente gráfico.

Recompensa media obtenida en función del número de tiradas con Softmax en para diferentes valores de tau

Cuando se selecciona el valor de \tau. igual a 0,1 la solución no es óptima, es necesario bajar el valor hasta 0,02 o 0,01 para que esta sea la óptima. Valores que dependen de la relación entre los valores de las recompensas esperadas de los diferentes bandidos.

Conclusiones

En esta entrada hemos visto el uso de Softmax para un problema Bandido Multibrazo. Una estrategia que permite mejorar los resultados explorando los bandidos en base a su recompensa esperada, no aleatoriamente como es el caso de Epsilon-Greedy. Aunque los resultados dependen de una selección correcta del hiperparámetro, ya que como hemos visto una mala selección produce resultados que no son óptimos.

Apéndice: refactorización de las clases

Al sobrescribir el método run() de la clase Epsilon en Softmax nos podemos dar cuenta que se ha repetido el código de evaluación. Por lo que es una buena idea dividir este método en dos, para que no sean necesario repetir este código en futuras ocasiones. Así que se puede crear un método select() con el que se implemente el algoritmo y run() pueda ser el mismo para las dos clases. Así se puede rescindir el código como:

import numpy as np
import matplotlib.pyplot as plt

class Bandit:
    """
    Implementación de un Bandido Multibrazo (Multi-Armed Bandit) basado
    en una distribución binomial

    Parámetros
    ----------
    number: integer
        Número de recompensas que puede devolver el agente
    probability : float
        Probabilidad de que el objeto devuelva una recompensa
    
    Métodos
    -------
    pull :
        Realiza una tirada en el bandido
        
    """
    def __init__(self, probability, number=1):
        self.number = number
        self.probability = probability
        
        self.reward = self.number * self.probability
        
        
    def pull(self):        
        return np.random.binomial(self.number, self.probability)
    
    
class Epsilon:
    """
    Agente que soluciona el problema del el Bandido Multibrazo
    (Multi-Armed Bandit) mediante el uso de una estrategia Epsilon
    Greedy
    
    Parámetros
    ----------
    bandits : array of Bandit
        Vector con los bandidos con los que se debe jugar
    epsilon : float
        Porcentaje de veces en las que el agente jugada de forma
        aleatoria
    decay : float
        Velocidad con la que decae la probabilidad de seleccionar una
        jugada al azar
    initial: array of float
        Valor inicial de la recompensa esperada para cada uno de
        bandidos
        
    Métodos
    -------
    run :
        Realiza una tirada en el bandido
    select :
        Selecciona un bandido para jugar en la próxima tirada
    average_reward :
        Obtención de la recompensa promedio
    plot :
        Representación gráfica del histórico de jugadas
    reset :
        Reinicia el agente
    """
    
    def __init__(self, bandits, epsilon=0.05, decay=1, initial=None):
        self.bandits = bandits
        self.epsilon = epsilon
        self.decay = decay
        
        self.reset(initial)
        
        
    def run(self, episodes=1):
        for i in range(episodes):
            # Selección del bandido
            bandit = self.select()
            
            # Obtención de una nueva recompensa
            reward = bandits[bandit].pull()
            
            # Agregación de la recompensa al listado
            self._rewards.append(reward)
            
            # Actualización de la media
            self._plays[bandit] += 1
            self._mean[bandit] = (1 - 1.0/self._plays[bandit]) * self._mean[bandit] \
                                 + 1.0/self._plays[bandit] * reward
        
        return self.average_reward()
    

    def select(self):
        prob = np.random.random()
            
        # Selección entre la jugada aleatoria o avariciosa
        if prob < self._epsilon:
            bandit = np.random.choice(len(bandits))
        else:
            max_bandits = np.where(self._mean == np.max(self._mean))[0]
            bandit = np.random.choice(max_bandits)
        
        # Decaimiento del parámetro epsilon
        self._epsilon *= self.decay
        
        return bandit
    
                
    def average_reward(self):
        return np.mean(self._rewards)
    
    
    def plot(self, log=False, reference=False, label=None):
        cumulative_average = np.cumsum(self._rewards) / (np.arange(len(self._rewards)) + 1)
        
        if label is None:
            plt.plot(range(len(self._rewards)), cumulative_average)
        else:
            plt.plot(range(len(self._rewards)), cumulative_average, label=label)
            
        if reference:
            for reward in [b.reward for b in self.bandits]:
                plt.plot([0, len(self._rewards)], [reward, reward],
                         label=f'reward={reward}')
                
        if log:
            plt.xscale('log')
    
    
    def reset(self, initial=None):
        self._rewards = []
        
        if initial is None:
            self._epsilon = self.epsilon
            self._plays = [0] * len(self.bandits)
            self._mean = [0] * len(self.bandits)
        else:
            self._epsilon = 0
            self._plays = [1] * len(self.bandits)
            self._mean = initial
            
            
class Softmax(Epsilon):
    """
    Agente que soluciona el problema del el Bandido Multibrazo
    (Multi-Armed Bandit) mediante el uso de una estrategia Softmax
    
    Parámetros
    ----------
    bandits : array of Bandit
        Vector con los bandidos con los que se debe jugar
    tau : float
        Hiperparámetro empleado para seleccionar al bandido 
        
    Métodos
    -------
    run :
        Realiza una tirada en el bandido
    select :
        Selecciona un bandido para jugar en la próxima tirada
    average_reward :
        Obtención de la recompensa promedio
    plot :
        Representación gráfica del histórico de jugadas
    reset :
        Reinicia el agente
    """
    def __init__(self, bandits, tau=0.01):
        self.bandits = bandits
        self.tau = tau
        
        self.reset()
    
    
    def select(self):
        # Calculo de la probabilidad de seleccionar un bandido
        prob = [np.exp(m / self.tau) for m in self._mean]
        prob /= np.sum(prob)
        prob = np.cumsum(prob)
        
        # Selección del bandido
        return np.where(prob > np.random.random())[0][0] 

    
    def reset(self, initial=None):
        self._rewards = []
        self._plays = [0] * len(self.bandits)
        self._mean = [0] * len(self.bandits)

Image by Larisa Koshkina from Pixabay