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

Una estrategia bastante popular para solucionar los problemas tipo Bandido Multibrazo es EXP3. Siendo el nombre es una abreviatura de "Exponential-weight algorithm for Exploration and Exploitation" (Algoritmo de peso Exponencial para Exploración y Explotación). EXP3 se diferencia de otras estrategias populares como Epsilon Greedy o UCB1, siendo un algoritmo más tradicional de aprendizaje automático ya que aprende calculando pesos para identificar cual es el mejor bandido.

EXP3

El primer paso a la hora de trabajar con EXP3 es definir un vector de pesos (\omega) para cada uno de los k bandidos. Vector que se inicia con todos los valores igual a 1. Además, es necesario definir un parámetro de exploración (\gamma), el cual debe tomar un valor entre 0 y 1 sin incluir 0, esto es, debe estar en el rango (0,1]. Parámetro que define la probabilidad que tendrá el algoritmo de explorar los brazos al azar.

Una vez hecho esto se deben seguir los siguientes pasos:

1. Obtener la probabilidad para cada uno de los brazos empleando para ello la expresión p_j(t) = (1 - \gamma) \frac{\omega_j(t)}{\sum_{i=0}^{k} \omega_i(t)} + \frac{\gamma}{k}
2. Seleccionar aleatoriamente un bandido en base a la probabilidad calculada en el paso anterior.
3. Obtener la recompensa y actualizar a la recompensa promedio para el bandido seleccionado en el paso anterior.
4. Actualizar el peso mediante la expresión \omega_j(t+1) = \omega_j(t) e^{\gamma \bar{X_j}/k}

Lo que hace este algoritmo es explorar los estados aleatoriamente en base a una distribución de pesos obtenida a través de la experiencia. Priorizando la selección de aquellos bandidos con mayor rendimiento. Mediante el parámetro de exploración (\gamma) se define la probabilidad de seleccionar un bandido de forma aleatoria, siendo mayor a medida que aumente el valor. Ya que, cuando \gamma es 1, la selección es completamente aleatoria.

Implementación de EXP3 en Python

El algoritmo EXP3 se puede implementar en Python utilizando para ello la clase Epsilon implementada en su momento para Epsilon-Greedy con decaimiento. A partir de la cual se puede crear una clase hija en la que es necesario sobrescribir los métodos select() y run(). Lo que se muestra en el siguiente código.

class Exp3(Epsilon):
    def __init__(self, bandits, gamma=0.05):
        self.bandits = bandits
        self.gamma = gamma
        
        self.reset()
        
        
    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
            
            # Actualización de los pesos
            self._weights[bandit] *= np.exp(self._mean[bandit] * self.gamma / len(self.bandits))
        
        return self.average_reward()
    
    
    def select(self):
        num_bandits = len(self.bandits)
        total = len(self._rewards)
        
        if total < len(bandits):
            bandit = total
        else:
            exp3 = [0] * num_bandits
            
            total_weights = np.sum(self._weights)

            for i in range(num_bandits):
                exp3[i] = (1 - self.gamma) * self._weights[i] / total_weights + self.gamma / num_bandits
        
            bandit = np.random.choice(num_bandits, p=exp3)
            
        return bandit
    
    
    def reset(self, initial=None):
        self._rewards = []
        self._plays = [0] * len(self.bandits)
        self._mean = [0] * len(self.bandits)
        self._weights = [1] * len(self.bandits)

En el método run() se tiene que incluir la actualización de los pesos después de que juegue con un bandido. Valor que se actualiza en función de la recompensa obtenida y el valor del parámetro \gamma. Por otro lado, en el método select() se implementa el algoritmo mediante el cual se calcula el peso relativo que tendrá cada uno de los bandidos. Valor que se almacena en la variable exp3. Para, posteriormente, seleccionar un bandido en base a esta probabilidad, usando para ello la función np.random.choice() de NumPy.

Resultados

Tras la creación de una clase que implemente el algoritmo EXP3, compatible con los bandidos basados en la distribución binomial definidos en otra entrada anterior, se puede comparar el rendimiento de este con UCB1. Para ello se puede utilizar por ejemplo el siguiente pedazo de código.

np.random.seed(0)

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

exp3 = Exp3(bandits)
ucb_1 = UCB1(bandits)

exp3.run(220000)
ucb_1.run(220000)

exp3.plot(True, label='EXP3')
ucb_1.plot(True, True, label='UCB1')
plt.legend()

Con lo que se obtiene la siguiente gráfica.

Evolución de la recompensa promedio con el número de tiradas para EXP3 y UCB1 con tres bandidos basados en una distribución binomial

En este caso se puede ver que EXP3 ofrece un rendimiento inferior a UCB1. Algo que, en cierta medida es de esperar, ya que usa una aproximación en la que se realiza una exploración de los estados.

También se puede comprobar que, a medida que se aumenta el valor de \gamma el valor esperado a largo plazo será menor, ya que aumenta el porcentaje de jugadas al azar. Lo que se puede comprobar mediante el siguiente código.

np.random.seed(0)

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

exp3_01 = Exp3(bandits, 0.01)
exp3_05 = Exp3(bandits, 0.05)
exp3_10 = Exp3(bandits, 0.10)

exp3_01.run(220000)
exp3_05.run(220000)
exp3_10.run(220000)

exp3_01.plot(True, label='EXP3 0.01')
exp3_05.plot(True, label='EXP3 0.05')
exp3_10.plot(True, True, label='EXP3 0.10')
plt.legend()

A partir del cual se obtiene el siguiente resultado, con el que se confirman las sospechas.

Evolución de la recompensa promedio con el número de tiradas para EXP3 con diferentes parámetros gamma y tres bandidos basados en una distribución binomial

Conclusiones

En esta ocasión se ha visto una estrategia clásica para solucionar un problema de Bandido Multibrazo en la que se estima un peso con el que se seleccionará la probabilidad de seleccionar un bandido. El método ofrece generalmente un rendimiento inferior a los UCB ( UCB1, UCB2, UCB1-Tuned, UCB1-Normal, BayesUCB o KL-UCB) ya que es una estrategia más sencilla.

Imagen de Rudy and Peter Skitterians en Pixabay