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
Puzzle Bobble
Karate Blazers
Puzzle De Bloques
Magical Cat Adventure