En entradas anteriores hemos aprendido a abordar el problema del Bandido Multibrazo utilizando para ello la estrategia llamada Epsilon-Greedy. Estrategia con la que se obtienen mejores resultados que los de un test A/B. Aunque Epsilon-Greedy tiene un problema cuando el número de episodios a jugar es elevado, continúa explorando los peores bandidos con una probabilidad fija épsilon. Para solucionar esto, la semana pasada, introdujimos la opción de que este parámetro se reduzca con el tiempo. Comprobando que así se obtienen mejores resultados a largo plazo. Ya que una vez se ha identificado al bandido que ofrece la mayor recompensa promedio el agente estará más tiempo explotando este, en lugar de explorar el resto de los bandidos. Pero aún así es posible reducir la fase de exploración si se cuenta con una estimación optimista de la recompensa de cada bandido. Una estrategia a la que se conoce como valores iniciales optimistas y vamos a ver a continuación cómo implementarla en Python.
Tabla de contenidos
- 1 Valores iniciales optimistas para un problema Bandido Multibrazo
- 2 ¿Por qué tienen que ser optimistas los valores iniciales?
- 3 Problemas con valores iniciales optimistas
- 4 Implementación en Python
- 5 Evaluación de los resultados y comparación con Epsilon-Greedy
- 6 Resultados cuando los valores iniciales no son óptimos
- 7 Conclusiones
Valores iniciales optimistas para un problema Bandido Multibrazo
Supongamos que al comenzar disponemos de una estimación de cuál es la recompensa promedio que nos puede ofrecer cada uno de los bandidos. Entonces se puede usar este punto de partida para seleccionar el bandido mediante una estrategia puramente avariciosa, esto es, con épsilon igual a cero. Así, si la estimación es correcta siempre se explotará el mejor bandido, obteniendo de este modo la mayor recompensa posible. Solamente se ha jugado con el mejor bandido. Por otro lado, si no es así, al actualizar el valor esperado de la recompensa con los datos reales se podrá comparar esta estimación con las iniciales. En caso de que la estimación para otro bandido sea mejor, se pasará a jugar con este. Así hasta que se pase a jugar siempre con el bandido que ofrece las mayores recompensas.
¿Por qué tienen que ser optimistas los valores iniciales?
La estrategia se llama valores iniciales óptimas y esto es así porque los valores tienen que ser realmente optimistas para que esta pueda funcionar de forma correcta. Para esto nos podemos fijar en un ejemplo. Supongamos que tenemos dos bandidos con una recompensa promedio de 1 y 2 respectivamente. Así, si fijamos unos valores iniciales de 3 y 2 el agente jugará inicialmente con el primero de los bandidos, al que se le ha asignado una recompensa promedio de 3. Siendo esto así hasta que se compruebe que la recompensa real del primero es inferior a 2, el valor que se le ha asignado al segundo bandido. Por lo que el agente para a explotar únicamente el segundo de los bandidos, ya que su recompensa esperada es 2.
Por otro lado, si los valores iniciales no son optimistas el agente puede explotar un bandido que no sea óptimo. Algo que se puede comprobar si se asigna valores iniciales de 0,5 y 0,2. En este caso el agente jugará solamente con el primero ya que la recompensa esperada es 1 y esta es mayor que 0,2, la asignada al segundo. Por lo que la solución obtenida no será la óptima.
Problemas con valores iniciales optimistas
A la hora de aplicar esta estrategia hay que tener en cuenta que es posible que es posible que esta estrategia no obtenga un resultado óptimo. Algo que se produce porque el agente no explora en ningún momento otras opciones.
Como se ha visto una posible causa sería no seleccionar correctamente los valores iniciales. Lo que llevaría al agente a seleccionar una solución que no es óptima. Por otro lado, también se puede dar este problema si la recompensa promedio de dos bandidos es muy parecida. En este caso, si en algún momento, debido al carácter aleatorio de las recompensas, la recompensa estimada para un bandido es inferior a la real y existe otro bandido con una mejor, es posible que se seleccione el segundo y no se vuelva al primero en ningún momento. Por lo que la solución final no será la óptima.
Un problema similar también se puede dar con Epsilon-Greedy, aunque en este caso, al explorar siempre las recompensas de todos los bandidos, el problema suele ser puntual. Esto es, solo hasta que se comprueba que la solución no es la óptima.
Implementación en Python
Para implementar esta estrategia se puede usar la clase Epsilon que se implementó la estrategia de Epsilon-Greedy con decaimiento. Para lo que solamente se tiene que hacer unos ligeros cambios.
En primer lugar, se debe aceptar un nuevo parámetro, al que llamaremos initial, al que se le debe indicar el valor inicial para para cada uno de los bandidos. Valor que se asigna a la propiedad _mean en los casos que esta se indique.
Cuando se asigna un valor inicial es importante asignar a la propiedad _plays, el número de jugadas para cada agente, el valor 1 en lugar de 0. Esto es así porque en caso contrario al actualizar el valor esperado se ignorará el valor. Algo que no es bueno. Debido a que, en el caso de que se ignore el valor inicial al calcular las primeras medidas, el peso de la primera tirada será clave, ya que esta pasará a ser la media empleada para seleccionar el bandido con solo una observación. Lo que hará que el resultado dependa en gran medida del azar.
Por otro lado, para que no se seleccione nunca al azar el bandido es necesario que el valor de la propiedad _epsilon sea cero. Lo que hará que la estrategia sea puramente avariciosa.
Así la clase Epsilon puede quedar de la siguiente forma:
import numpy as np
import matplotlib.pyplot as plt
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
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):
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
# 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 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 = initialEvaluación de los resultados y comparación con Epsilon-Greedy
Ahora, con la nueva clase, para crear un agente que emplee valores iniciales optimistas solamente hay que asignar estos valores. De este modo se puede comparar el rendimiento de las tres estrategias vistas hasta ahora para 20.000 tiradas con el siguiente código.
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)
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])
epsilon.run(20000)
decay.run(20000)
optimistic.run(20000)
epsilon.plot(True, label='Epsilon')
decay.plot(True, label='Decay')
optimistic.plot(True, True, label='Optimistic')
plt.legend()Pudiéndose ver los resultados en la siguiente gráfica.
Aquí se puede observar como valores iniciales optimistas, bien configurado, es el método que se da observa antes cuál es el mejor bandido. Para comparar los algoritmos también nos podemos fijar en el número de veces que ha jugado cada uno con las soluciones que no son óptimas. En el caso de Epsilon-Greedy han sido 381 y 355 con el primero y segundo bandido. Valores que mejorar ligeramente con en el caso de Epsilon-Greedy con decaimiento, 333 y 352 para el primero y segundo. Finalmente, en el caso de valores iniciales optimistas solamente se han explorado los dos primeros bandidos en 90 y 16 casos respectivamente. Lo que supone más de 500 tiradas en las que se ha jugado con el mejor bandido.
Resultados cuando los valores iniciales no son óptimos
Aunque, en caso de que se configure mal no será así. Por ejemplo, en caso de fijar los valores iniciales a 0.09, es posible que el agente nunca seleccioné el tercer mejor bandido, como se puede ver en el siguiente ejemplo.
np.random.seed(0) optimistic = Epsilon(bandits, initial=[0.09, 0.09, 0.09]) print(optimistic.run(20000)) optimistic.plot(True, True, label='Optimistic')
En este caso lo que se puede ver observar es que el agente ha jugado principalmente con el segundo bandido, ya que los valores iniciales han provocado que juegue poco con el tercero. Provocando que la estimación de la recompensa esperada no sea la correcta. En concreto solamente ha jugado seis veces con el último bandido, con lo que ha estimado que su recompensa promedio es 0,015, muy por debajo de la real y la del segundo bandido.
Conclusiones
En esta ocasión se ha visto la estrategia valores iniciales optimistas para un problema Bandido Multibrazo. Una estrategia que, si se configura correctamente, puede ofrecer mejores resultados que Epsilon-Greedy al reducir la fase de exploración. Aunque en su contra requiere disponer de un conocimiento previo de los bandidos que existe en muchos casos.
Imagen de Free-Photos en Pixabay
Deja una respuesta