El algoritmo epsilon-greedy ($\varepsilon$-greedy) es una estrategia sencilla pero altamente efectiva para abordar el problema del multi-armed bandit. Aunque puede no ser tan robusto como otros métodos para esta tarea específica, su simplicidad y versatilidad lo hacen ampliamente aplicable en el campo del aprendizaje por refuerzo.

Cómo funciona

El algoritmo sigue estos pasos:

1. Inicializar las estimaciones de valor de acción $Q(a)$ para cada acción $a$;
2. Elegir una acción utilizando la siguiente regla:
   • Con probabilidad $\varepsilon$: seleccionar una acción aleatoria (exploración);
   • Con probabilidad $1 - \varepsilon$: seleccionar la acción con el valor estimado más alto (explotación).
3. Ejecutar la acción y observar la recompensa;
4. Actualizar la estimación del valor de acción $Q(a)$ en función de la recompensa observada;
5. Repetir los pasos 2-4 durante un número fijo de pasos de tiempo.

El hiperparámetro $\varepsilon$ (epsilon) controla el equilibrio entre exploración y explotación:

• Un $\varepsilon$ alto (por ejemplo, 0.5) fomenta una mayor exploración;
• Un $\varepsilon$ bajo (por ejemplo, 0.01) favorece la explotación de la mejor acción conocida.

Código de ejemplo

class EpsilonGreedyAgent:
  def __init__(self, n_actions, epsilon):
    """Initialize an agent"""
    self.n_actions = n_actions # Number of available actions
    self.epsilon = epsilon # epsilon
    self.Q = np.zeros(self.n_actions) # Estimated action values
    self.N = np.zeros(self.n_actions) # Action selection counters

  def select_action(self):
    """Select an action according to the epsilon-greedy strategy"""
    # With probability epsilon - random action
    if np.random.rand() < self.epsilon:
      return np.random.randint(self.n_actions)
    # Otherwise - action with highest estimated action value
    else:
      return np.argmax(self.Q)

  def update(self, action, reward):
    """Update the values using sample average estimate"""
    # Increasing the action selection counter
    self.N[action] += 1
    # Updating the estimated action value
    self.Q[action] += (reward - self.Q[action]) / self.N[action]

Información adicional

La eficiencia del algoritmo $\varepsilon$-greedy depende en gran medida del valor de $\varepsilon$. Dos estrategias son comúnmente utilizadas para seleccionar este valor:

• $\varepsilon$ fijo: esta es la opción más genérica, donde el valor de $\varepsilon$ se elige como una constante (por ejemplo, 0.1);
• $\varepsilon$ decreciente: el valor de $\varepsilon$ disminuye con el tiempo según algún calendario (por ejemplo, comienza en 1 y disminuye gradualmente hasta 0) para fomentar la exploración en las etapas iniciales.

Resumen

El algoritmo $\varepsilon$-greedy es un enfoque de referencia para equilibrar la exploración y la explotación. Aunque es sencillo, sirve como base para comprender estrategias más avanzadas como upper confidence bound (UCB) y gradient bandits.