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.
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.
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