Algoritmen epsilon-greedy ($\varepsilon$-greedy) er en enkel, men yderst effektiv strategi til at løse multi-armed bandit-problemet. Selvom den måske ikke er lige så robust som nogle andre metoder til denne specifikke opgave, gør dens enkelhed og alsidighed den bredt anvendelig inden for reinforcement learning.

Sådan fungerer det

Algoritmen følger disse trin:

1. Initialiser estimater for handlingsværdier $Q(a)$ for hver handling $a$;
2. Vælg en handling ved hjælp af følgende regel:
   • Med sandsynlighed $\varepsilon$: vælg en tilfældig handling (udforskning);
   • Med sandsynlighed $1 - \varepsilon$: vælg handlingen med den højeste estimerede værdi (udnyttelse).
3. Udfør handlingen og observer belønningen;
4. Opdater estimatet for handlingsværdien $Q(a)$ baseret på den observerede belønning;
5. Gentag trin 2-4 i et fast antal tidsintervaller.

Hyperparameteren $\varepsilon$ (epsilon) styrer balancen mellem udforskning og udnyttelse:

• En høj $\varepsilon$ (f.eks. 0,5) fremmer mere udforskning;
• En lav $\varepsilon$ (f.eks. 0,01) favoriserer udnyttelse af den bedst kendte handling.

Eksempelkode

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]

Yderligere information

Effektiviteten af $\varepsilon$-grådig algoritme afhænger i høj grad af værdien af $\varepsilon$. To strategier anvendes ofte til at vælge denne værdi:

• Fast $\varepsilon$: dette er den mest generelle mulighed, hvor værdien af $\varepsilon$ vælges som en konstant (f.eks. 0,1);
• Aftagende $\varepsilon$: værdien af $\varepsilon$ falder over tid i henhold til en tidsplan (f.eks. starter ved 1 og falder gradvist til 0) for at fremme udforskning i de tidlige faser.

Resumé

$\varepsilon$-grådig algoritme er en grundlæggende tilgang til at balancere udforskning og udnyttelse. Selvom den er simpel, danner den grundlag for forståelsen af mere avancerede strategier som upper confidence bound (UCB) og gradient banditter.