UCB-V para un problema Bandido Multibrazo (Multi-Armed Bandit)

El algoritmo UCB-V es una variante de la familia UCB que utiliza la varianza para seleccionar el bandido en problemas tipo Bandido Multibrazo (Multi-Armed Bandit). Un algoritmo genérico que puede ser utilizado en cualquier tipo de bandido.

UCB-V

En el algoritmo UCB-V se tiene que seleccionar en cada tirada aquel bandido que maximice la siguiente expresión.

X_{UCB1-V} = \bar{X_j} + \sqrt{ \frac{2 \sigma^2_j \log(N)}{n_j}} + \frac{b \log(N)}{N}

Donde $\sigma^2_j$ es la varianza empírica del bandido $j$ , $n_j$ es el número de veces que se ha jugado con el bandido $j$ , $N$ el número de veces que se ha jugado con todos los bandidos y $b$ es un hiper-parámetro en el que generalmente se utiliza el valor 3.

Implementación de UCB-V en Python

Al igual que en otras entradas anteriores, para implementar el algoritmo UCB-V en Python se puede usar la clase Epsilon que se había implementado para el algoritmo de valores iniciales optimistas. Dato que en este algoritmo es necesario la varianza, además de los valores que se guardan en la clase original, es necesario crear una nueva propiedad en la que se guarde el cuadrado de las recompensas. Valor con el que se puede obtener la varianza empírica usando la expresión

\sigma^2_j = \sum\frac{X_j(t)^2}{n_j} - \bar{X_j}^2

Así, una posible implementación de UCB-V es la que se muestra en la siguiente clase.

class UCBV(Epsilon):
    def __init__(self, bandits, b=3):
        self.bandits = bandits
        self.b = b
        
        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
            self._mean2[bandit] += reward**2
        
        return self.average_reward()
    
    
    def select(self):
        num_bandits = len(self.bandits)
        total = len(self._rewards)
        
        if total < num_bandits:
            bandit = total
        else:
            ucb = [0] * num_bandits
                
            for i in range(num_bandits):
                var = self._mean2[i] / self._plays[i] - self._mean[i]**2
                ucb[i] = self._mean[i]
                ucb[i] += np.sqrt(2 * var * np.log(total) / self._plays[i])
                ucb[i] += self.b * np.log(total) / self._plays[i]             
            
            max_bandits = np.where(ucb == np.max(ucb))[0]
            bandit = np.random.choice(max_bandits)
            
        return bandit
    
    
    def reset(self, initial=None):
        self._rewards = []
        self._plays = [0] * len(self.bandits)
        self._mean = [0] * len(self.bandits)
        self._mean2 = [0] * len(self.bandits)

Nótese que en este caso, además del método select(), ha sido necesario modificar los métodos run() para que guarde la suma de las recompensas al cuadrado y reset() para crear esta propiedad.

Resultados de UCB-V

Para evaluar el rendimiento de este algoritmo se puede comparar el rendimiento frente al que se obtienen con UCB1. De forma análoga a como se ha realizado en entradas anteriores. Para ello se puede emplear el siguiente código en el que se crean tres bandidos cuya recompensa se obtienen mediante una distribución binomial con diferente media. En el que posteriormente se compara el resultado que se obtiene después de 200.000 tiradas con UCB-V y UCB1.

np.random.seed(0)

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

ucbv = UCBV(bandits)
ucb1 = UCB1(bandits)

ucbv.run(200000)
ucb1.run(200000)

ucbv.plot(True, label='UCB-V')
ucb1.plot(True, True, label='UCB1')
plt.legend()

print(ucbv._plays)
print(ucb1._plays)

Al ejecutar el código se obtiene la siguiente figura.

Evolución de la recompensa promedio con el numero de tiradas para el algoritmo UCB-V y UCB1 con tres bandidos basados en una distribución binomial

En la que se puede ver como UCB-V obtiene mejores resultados a corto plazo que UCB1 para estos bandidos. Aunque a largo plazo, como sería de esperar, ambos tienen obtienen una recompensa promedio cercana a teórica del mejor bandido. La diferencia a corto plazo se debe a que UCB-V solamente selecciona el bandido optimo 196.844 veces frente a las 187.605. Lo que indica que ha necesitado menos tiradas para decantarse por este.

Conclusiones

En esta entrada hemos visto otro algoritmo de la familia UCB con el que se puede abordar un problema tipo Bandido Multibrazo (Multi-Armed Bandit). Un algoritmo que se basa en el uso de la varianza para seleccionar el bandido con el que jugar en cada ocasión. Por lo que se puede utilizar con cualquier tipo de bandido, independientemente de la distribución usada para generar la recompensa. Ofreciendo, en el caso analizado, mejores resultados que UCB1.

Imagen de Mier Chen en Pixabay