L'algoritmo epsilon-greedy ($\varepsilon$-greedy) è una strategia semplice ma estremamente efficace per affrontare il problema del multi-armed bandit. Sebbene possa non essere robusto quanto altri metodi per questo compito specifico, la sua semplicità e versatilità lo rendono ampiamente applicabile nel campo del reinforcement learning.

Come funziona

L'algoritmo segue questi passaggi:

1. Inizializzare le stime dei valori d'azione $Q(a)$ per ogni azione $a$;
2. Scegliere un'azione utilizzando la seguente regola:
   • Con probabilità $\varepsilon$: selezionare un'azione casuale (esplorazione);
   • Con probabilità $1 - \varepsilon$: selezionare l'azione con il valore stimato più alto (sfruttamento).
3. Eseguire l'azione e osservare la ricompensa;
4. Aggiornare la stima del valore d'azione $Q(a)$ in base alla ricompensa osservata;
5. Ripetere i passaggi 2-4 per un numero fisso di intervalli temporali.

L'iperparametro $\varepsilon$ (epsilon) controlla il bilanciamento tra esplorazione e sfruttamento:

• Un alto $\varepsilon$ (ad esempio, 0.5) favorisce una maggiore esplorazione;
• Un basso $\varepsilon$ (ad esempio, 0.01) privilegia lo sfruttamento dell'azione migliore conosciuta.

Codice di esempio

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]

Informazioni aggiuntive

L'efficacia dell'algoritmo $\varepsilon$-greedy dipende fortemente dal valore di $\varepsilon$. Due strategie sono comunemente utilizzate per selezionare questo valore:

• $\varepsilon$ fisso: questa è l'opzione più generica, in cui il valore di $\varepsilon$ viene scelto come una costante (ad esempio, 0.1);
• $\varepsilon$ decrescente: il valore di $\varepsilon$ diminuisce nel tempo secondo una certa pianificazione (ad esempio, parte da 1 e diminuisce gradualmente fino a 0) per favorire l'esplorazione nelle fasi iniziali.

Riepilogo

L'algoritmo $\varepsilon$-greedy è un approccio di base per bilanciare esplorazione ed exploitazione. Pur essendo semplice, rappresenta una base per comprendere strategie più avanzate come il bound di confidenza superiore (UCB) e i gradient bandits.