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.

Toimintaperiaate

Algoritmi etenee seuraavasti:

1. Alustetaan toimintojen arviot $Q(a)$ jokaiselle toiminnolle $a$;
2. Valitaan toiminto seuraavan säännön mukaisesti:
   • Todennäköisyydellä $\varepsilon$: valitaan satunnainen toiminto (etsintä);
   • Todennäköisyydellä $1 - \varepsilon$: valitaan toiminto, jolla on korkein arvioitu arvo (hyödyntäminen).
3. Suoritetaan toiminto ja havaitaan palkkio;
4. Päivitetään toiminnon arviota $Q(a)$ saadun palkkion perusteella;
5. Toistetaan 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ätietoja

$\varepsilon$-ahneen algoritmin tehokkuus riippuu vahvasti $\varepsilon$-arvosta. Kaksi yleistä strategiaa tämän arvon valintaan ovat:

• 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), mikä kannustaa tutkimiseen 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 gradient bandits, ymmärtämiselle.