UCB1-Normal para un problema Bandido Multibrazo (Multi-Armed Bandit)

En entradas anteriores de esta serie se han visto diferentes versiones de las estrategias UCB aplicadas a la resolución de un problema tipo Bandido Multibrazo: UCB1, UCB2 y UCB-Tuned. Estrategias que han demostrado unos excelentes resultados. Otra versión de UCB con la que se suele obtener buenos resultados es UCB1-Normal, una modificación de UCB1 en la que se asume una distribución normal de las recompensas. Veamos a continuación cómo se puede implementar esta estrategia en Python.

UCB1-Normal

El método UCB1-Normal es una mejora de UCB1 en el que se asume que las recompensas de cada uno de los bandidos son generadas mediante una distribución normal. Lo que permite seleccionar al mejor bandido en base al nivel de confianza que se deduce de esta distribución. Minimizando de este modo el número de tiradas en fase de exploración.

En UCB1-Normal en primer lugar se fija un número mínimo de tiradas para cada bandido. Número que dependerá del número de tiradas totales realizadas hasta el momento. Así, si en alguno de los bandidos se han realizado menos tiradas que

n_{min} = \lceil 8 \log N \rceil,

donde N es el número total de tiradas, se jugará con este.

Por otro lado, en el caso de que todos los bandidos superen este valor umbral se jugará con aquel que maximice la siguiente expresión.

X_{UCB1-Normal} = \bar{X_j} + \sqrt{16 \frac{q_j - n_j \bar{X_j}^2}{n_j-1} \frac{\ln(N-1)}{n_j}},

donde X_j es la media de las recompensas obtenidas por el bandido j, q_j es la suma de los cuadrados de las recompensas obtenidas por el bandido j y n_j son las veces que se ha jugado con el bandido j.

Una de las características de este UCB1-Normal es el hecho de garantizar un mínimo de jugadas para cada uno de los bandidos. Evitando de este modo que algunos de los bandidos no se exploren debido a una mala racha inicial. Aunque esto puede conllevar una menor explotación de los resultados.

Implementación de UCB1-Normal en Python

Para implementar el método UCB1-Normal en Python nos basaremos en la clase Epsilon implementada en su momento para Epsilon-Greedy con decaimiento. En este caso es necesario agregar una nueva propiedad a la clase en la que se guarde el cuadrado de las recompensas obtenidas en cada bandido, propiedad a la que llamaremos _rewards2. Además es necesario modificar los métodos run() para guardar este valor y select() para seleccionar el bandido. La implementación que se propone se puede ver en el siguiente código.

class UCBNormal(Epsilon):
    def __init__(self, bandits):
        self.bandits = bandits
        
        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._rewards2[bandit] += reward ** 2
            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):
        num_bandits = len(self.bandits)
        total = len(self._rewards)
        
        # Número de veces mínimo que debe jugar cada bandido
        if total > 0:
            min_plays = np.ceil(8 * np.log(total))
        else:
            min_plays = 1
        
        # En caso de que algún bandido no jugase el mínimo de veces se selecciona ese
        if np.any(np.array(self._plays) < min_plays):
            min_bandit = np.where(np.array(self._plays) < min_plays)[0]
            bandit = np.random.choice(min_bandit)
        else:
            ucb = [0] * num_bandits
            
            for i in range(num_bandits):
                if self._plays[i] > 1:
                    bonus = 16 * (self._rewards2[i] - self._plays[i] * self._mean[i]**2) / (self._plays[i] - 1)
                    bonus *= np.log(total - 1) / self._plays[i]
                    bonus = np.sqrt(bonus)
                    ucb[i] = self._mean[i] + bonus
                else:
                    ucb[i] = self._mean[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._rewards2 = [0] * len(self.bandits)

Como se puede ver el método run() solamente se ha agregado una línea para agregar el cuadrado de la recompensa obtenida por cada bandido. Más interés tienen los cambios introducidos en el método select(). En este método en primer lugar se calcula el mínimo de veces que se debe jugar con cada bandido antes de pasar a una fase de explotación, valor que se guarda en la variable min_plays. Solamente en el caso de que se hubiese jugado con todos los bandidos por lo menos min_plays veces se usará el algoritmo para seleccionar el bandido, en caso contrario la selección sería aleatoria aquellos que no superan el umbral. Al igual que en las ocasiones anteriores, se calcula el bonus definido por el algoritmo y se agrega este a la media para seleccionar el bandido.

Resultados

Una vez implementado el algoritmo se puede comparar el rendimiento de UCB1-Normal con UCB1 empleando para ello los bandidos basados en una distribución binomial. Para lo que se puede utilizar el siguiente código.

np.random.seed(0)

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

ucb_n = UCBNormal(bandits)
ucb_1 = UCB1(bandits)

ucb_n.run(200000)
ucb_1.run(200000)
ucb_n.plot(True, label='UCB1-Normal')
ucb_1.plot(True, True, label='UCB-1')
plt.legend()

Obteniendo como resultado la rugiente gráfica.

En esta ocasión se puede ver que UCB1-Normal selecciona el primer más rápidamente el mejor bandido que UCB. Aunque, como en otros casos, a largo plazo los resultados la recompensa media obtenida es similar a la de UCB1. La mejora también se puede apreciar comparando el número de veces que el UCB1-Normal ha jugado con cada bandido respecto a UCB1. En el caso de UCB1-Normal solamente ha seleccionado 494 veces el primer frente a las 2.883 de UCB1, por lo que ha jugado con este bandido no óptimo solamente un quinto de las veces. Por otro lado, para el segundo bandido la diferencia es menor a 5.854 en el caso de UCB1-Normal frente a las 8.807 de UCB1. Lo que indica que UCB1-Normal ha seleccionado el bandido óptimo en más ocasiones que UCB1.

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

Nótese que los resultados obtenidos son buenos, aunque no se cumple uno de los supuestos de UCB1-Normal, que las recompensas obtenidas vienen de una distribución normal. Los bandidos empleados para comparar los resultados se basan en una distribución binomial.

Conclusiones

En esta ocasión hemos visto una nueva modificación de UCB1 con la que se obtiene experimentalmente unos resultados aún mejores.

Imagen de Jörg Vieli en Pixabay