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:
- 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}
- Seleccionar aleatoriamente un bandido en base a la probabilidad calculada en el paso anterior.
- Obtener la recompensa y actualizar a la recompensa promedio para el bandido seleccionado en el paso anterior.
- 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.
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.
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