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ä erityistehtävässä, sen yksinkertaisuus ja monipuolisuus tekevät siitä laajasti käytetyn vahvistusoppimisen alalla.

Toimintaperiaate

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 (explorointi);
   • Todennäköisyydellä $1 - \varepsilon$: valitse toiminto, jolla on korkein arvioitu arvo (eksploitointi).
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 exploraation ja eksploitaation välistä tasapainoa:

• Korkea $\varepsilon$ (esim. 0.5) kannustaa enemmän explorointiin;
• Matala $\varepsilon$ (esim. 0.01) suosii parhaan tunnetun toiminnon eksploitaatiota.

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$-ahne 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 vähitellen arvoon 0) 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 ylärajan luottamusväli (UCB) ja gradienttibanditit, ymmärtämiselle.