Den epsilon-grådige ($\varepsilon$-grådige) algoritmen er en enkel, men svært effektiv strategi for å løse multi-armede bandittproblemer. Selv om den kanskje ikke er like robust som enkelte andre metoder for denne spesifikke oppgaven, gjør dens enkelhet og allsidighet den mye brukt innenfor forsterkende læring.

Hvordan det fungerer

Algoritmen følger disse stegene:

1. Initialiser handlingsverdiestimatene $Q(a)$ for hver handling $a$;
2. Velg en handling ved å bruke følgende regel:
   • Med sannsynlighet $\varepsilon$: velg en tilfeldig handling (utforskning);
   • Med sannsynlighet $1 - \varepsilon$: velg handlingen med høyest estimert verdi (utnyttelse).
3. Utfør handlingen og observer belønningen;
4. Oppdater handlingsverdiestimatet $Q(a)$ basert på observert belønning;
5. Gjenta steg 2-4 et fast antall tidssteg.

Hyperparameteren $\varepsilon$ (epsilon) styrer balansen mellom utforskning og utnyttelse:

• En høy $\varepsilon$ (f.eks. 0,5) oppmuntrer til mer utforskning;
• En lav $\varepsilon$ (f.eks. 0,01) favoriserer utnyttelse av den best kjente handlingen.

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]

Tilleggsinformasjon

Effektiviteten til $\varepsilon$-grådig algoritme avhenger i stor grad av verdien til $\varepsilon$. To strategier brukes ofte for å velge denne verdien:

• Fast $\varepsilon$: dette er det mest generelle alternativet, hvor verdien til $\varepsilon$ velges som en konstant (f.eks. 0.1);
• Avtagende $\varepsilon$: verdien til $\varepsilon$ reduseres over tid etter en bestemt plan (f.eks. starter på 1, og avtar gradvis til 0) for å oppmuntre til utforskning i de tidlige fasene.

Sammendrag

$\varepsilon$-grådig algoritme er en grunnleggende tilnærming for å balansere utforskning og utnyttelse. Selv om den er enkel, fungerer den som et fundament for å forstå mer avanserte strategier som upper confidence bound (UCB) og gradient banditter.