Epsilon-Grådig Algoritme

Epsilon-greedy ($\varepsilon$-greedy) algoritmen 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 tidssteg.

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 algoritmen 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 generiske 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 som en grundlæggende tilgang til at balancere udforskning og udnyttelse. Selvom den er enkel, danner den grundlag for forståelse af mere avancerede strategier som upper confidence bound (UCB) og gradient bandits.