Epsilon-girig ($\varepsilon$-greedy) algoritmen är en enkel men mycket effektiv strategi för att hantera multi-armed bandit-problemet. Även om den kanske inte är lika robust som vissa andra metoder för denna specifika uppgift, gör dess enkelhet och mångsidighet den allmänt användbar inom området förstärkningsinlärning.

Hur det fungerar

Algoritmen följer dessa steg:

1. Initiera uppskattningar av åtgärdsvärden $Q(a)$ för varje åtgärd $a$;
2. Välj en åtgärd enligt följande regel:
   • Med sannolikhet $\varepsilon$: välj en slumpmässig åtgärd (utforskning);
   • Med sannolikhet $1 - \varepsilon$: välj åtgärden med högst uppskattat värde (exploatering).
3. Utför åtgärden och observera belöningen;
4. Uppdatera uppskattningen av åtgärdsvärdet $Q(a)$ baserat på observerad belöning;
5. Upprepa steg 2-4 under ett fast antal tidssteg.

Hyperparametern $\varepsilon$ (epsilon) styr avvägningen mellan utforskning och exploatering:

• Ett högt $\varepsilon$ (t.ex. 0,5) uppmuntrar mer utforskning;
• Ett lågt $\varepsilon$ (t.ex. 0,01) gynnar exploatering av den bäst kända åtgärden.

Exempelkod

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]

Ytterligare information

Effektiviteten hos $\varepsilon$-greedy-algoritmen beror starkt på värdet av $\varepsilon$. Två strategier används vanligtvis för att välja detta värde:

• Fast $\varepsilon$: detta är det mest generella alternativet, där värdet på $\varepsilon$ väljs som en konstant (t.ex. 0.1);
• Avtagande $\varepsilon$: värdet på $\varepsilon$ minskar över tid enligt ett schema (t.ex. börjar på 1 och minskar gradvis till 0) för att uppmuntra utforskning i de tidiga stadierna.

Sammanfattning

$\varepsilon$-greedy-algoritmen är en grundläggande metod för att balansera utforskning och exploatering. Trots sin enkelhet fungerar den som en grund för att förstå mer avancerade strategier som upper confidence bound (UCB) och gradient bandits.