Epsilon-greedy ($\varepsilon$-greedy) -algoritmi on suoraviivainen mutta erittäin tehokas strategia multi-armed bandit -ongelman ratkaisemiseen. Vaikka se ei välttämättä ole yhtä vankka kuin jotkin muut menetelmät tässä tehtävässä, sen yksinkertaisuus ja monipuolisuus tekevät siitä laajasti käytetyn vahvistusoppimisen alalla.

Miten se toimii

Algoritmi etenee seuraavasti:

1. Alusta toimintojen arvoestimaatit $Q(a)$ jokaiselle toiminnolle $a$;
2. Valitse toiminto seuraavan säännön mukaisesti:
   • Todennäköisyydellä $\varepsilon$: valitse satunnainen toiminto (etsintä);
   • Todennäköisyydellä $1 - \varepsilon$: valitse toiminto, jolla on korkein arvioitu arvo (hyödyntäminen).
3. Suorita toiminto ja havainnoi palkkio;
4. Päivitä toiminnon arvoestimaatti $Q(a)$ saadun palkkion perusteella;
5. Toista vaiheet 2-4 ennalta määrätyn ajan.

Hyperparametri $\varepsilon$ (epsilon) säätelee etsinnän ja hyödyntämisen välistä tasapainoa:

• Korkea $\varepsilon$ (esim. 0.5) kannustaa enemmän etsintään;
• Matala $\varepsilon$ (esim. 0.01) suosii parhaan tunnetun toiminnon hyödyntämistä.

Esimerkkikoodi

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]

Lisätietoa

$\varepsilon$-ahneen algoritmin tehokkuus riippuu voimakkaasti $\varepsilon$-arvosta. Kaksi strategiaa on yleisesti käytössä tämän arvon valitsemiseksi:

• Kiinteä $\varepsilon$: yleisin vaihtoehto, jossa $\varepsilon$-arvo valitaan vakioksi (esim. 0,1);
• Vähenevä $\varepsilon$: $\varepsilon$-arvo pienenee ajan myötä tietyn aikataulun mukaisesti (esim. alkaa arvosta 1 ja pienenee asteittain kohti nollaa) kannustaen tutkimista alkuvaiheessa.

Yhteenveto

$\varepsilon$-ahne algoritmi on peruslähestymistapa tutkimisen ja hyödyntämisen tasapainottamiseen. Vaikka se on yksinkertainen, se toimii perustana kehittyneempien strategioiden, kuten upper confidence bound (UCB) ja gradienttibanditit, ymmärtämiselle.