Bei der Behandlung von Multi-Armed-Bandit-Problemen schätzen traditionelle Methoden wie Epsilon-Greedy und UCB Aktionswerte, um zu entscheiden, welche Aktion ausgeführt werden soll. Gradienten-Banditen verfolgen jedoch einen anderen Ansatz — sie lernen Präferenzen für Aktionen anstatt deren Werte zu schätzen. Diese Präferenzen werden im Laufe der Zeit mithilfe von stochastischem Gradientenanstieg angepasst.

Präferenzen

Anstatt Aktionswertschätzungen $Q(a)$ zu führen, speichern Gradienten-Banditen Präferenzwerte $H(a)$ für jede Aktion $a$. Diese Präferenzen werden mit einem stochastischen Gradientenanstieg aktualisiert, um den erwarteten Ertrag zu maximieren. Die Wahrscheinlichkeit jeder Aktion wird mit einer Softmax-Funktion berechnet:

wobei:

• $H_t(a)$ die Präferenz für Aktion $a$ zum Zeitpunkt $t$ ist;
• $P(A_t = a)$ die Wahrscheinlichkeit ist, Aktion $a$ zum Zeitpunkt $t$ auszuwählen;
• Der Nenner stellt sicher, dass die Wahrscheinlichkeiten sich zu 1 summieren.

Softmax ist eine wichtige Funktion im maschinellen Lernen, die häufig verwendet wird, um Listen von reellen Zahlen in Listen von Wahrscheinlichkeiten umzuwandeln. Diese Funktion dient als glatte Annäherung an die $\argmax$-Funktion und ermöglicht eine natürliche Exploration, indem sie Aktionen mit niedrigerer Präferenz eine von Null verschiedene Auswahlwahrscheinlichkeit zuweist.

Aktualisierungsregel

Nach der Auswahl einer Aktion $A_t$ zum Zeitpunkt $t$ werden die Präferenzwerte nach folgender Regel aktualisiert:

wobei:

• $\alpha$ die Schrittweite ist;
• $R_t$ die erhaltene Belohnung ist;
• $\bar R_t$ der bisher beobachtete Durchschnitt der Belohnungen ist.

Intuition

In jedem Zeitschritt werden alle Präferenzen leicht verschoben. Die Verschiebung hängt hauptsächlich von der erhaltenen Belohnung und dem Durchschnitt der Belohnungen ab und lässt sich wie folgt erklären:

• Ist die erhaltene Belohnung höher als der Durchschnitt, wird die gewählte Aktion bevorzugter, während andere Aktionen weniger bevorzugt werden;
• Ist die erhaltene Belohnung niedriger als der Durchschnitt, nimmt die Präferenz der gewählten Aktion ab, während die Präferenzen der anderen Aktionen zunehmen, was die Erkundung fördert.

Beispielcode

def softmax(x):
  """Simple softmax implementation"""
  return np.exp(x) / np.sum(np.exp(x))

class GradientBanditsAgent:
  def __init__(self, n_actions, alpha):
    """Initialize an agent"""
    self.n_actions = n_actions # Number of available actions
    self.alpha = alpha # alpha
    self.H = np.zeros(n_actions) # Preferences
    self.reward_avg = 0 # Average reward
    self.t = 0 # Time step counter

  def select_action(self):
    """Select an action according to the gradient bandits strategy"""
    # Compute probabilities from preferences with softmax
    probs = softmax(self.H)
    # Choose an action according to the probabilities
    return np.random.choice(self.n_actions, p=probs)

  def update(self, action, reward):
    """Update preferences"""
    # Increase the time step counter
    self.t += 1
    # Update the average reward
    self.reward_avg += reward / self.t

    # Compute probabilities from preferences with softmax
    probs = softmax(self.H) # Getting action probabilities from preferences

    # Update preference values using stochastic gradient ascent
    self.H -= self.alpha * (reward - self.reward_avg) * probs
    self.H[action] += self.alpha * (reward - self.reward_avg)

Zusätzliche Informationen

Gradienten-Banditen besitzen mehrere interessante Eigenschaften:

• Relativität der Präferenzen: Die absoluten Werte der Aktionspräferenzen beeinflussen den Auswahlprozess nicht — nur ihre relativen Unterschiede sind relevant. Das Verschieben aller Präferenzen um denselben konstanten Wert (z. B. Hinzufügen von 100) führt zur gleichen Wahrscheinlichkeitsverteilung;
• Auswirkung der Basislinie in der Aktualisierungsregel: Obwohl die Aktualisierungsformel typischerweise den Durchschnitt der Belohnungen als Basislinie verwendet, kann dieser Wert durch eine beliebige Konstante ersetzt werden, die unabhängig von der gewählten Aktion ist. Die Basislinie beeinflusst die Konvergenzgeschwindigkeit, ändert jedoch nicht die optimale Lösung;
• Einfluss der Schrittweite: Die Schrittweite sollte auf die jeweilige Aufgabe abgestimmt werden. Eine kleinere Schrittweite sorgt für stabileres Lernen, während ein größerer Wert den Lernprozess beschleunigt.

Zusammenfassung

Gradienten-Banditen bieten eine leistungsstarke Alternative zu traditionellen Banditenalgorithmen, indem sie präferenzbasiertes Lernen nutzen. Ihr interessantestes Merkmal ist die Fähigkeit, Exploration und Ausbeutung auf natürliche Weise auszubalancieren.