Alle Herausforderungen
Einfach 0 gelöst 0% Erfolgsquote

Epsilon-Greedy-Multi-Armed-Bandit

Balanciere Erkundung und Ausnutzung bei einem Multi-Armed-Bandit mit Epsilon-Greedy-Aktionsauswahl.

Das lernst du

  • Erkunden und Ausnutzen ausbalancieren
  • Laufende Mittelwerte schrittweise aktualisieren
  • Sehen, warum rein gierige Agenten stecken bleiben

Problem

Ein Multi-Armed-Bandit ist eine Reihe von Spielautomaten (Arme) mit unbekannten Auszahlungen. Epsilon-Greedy balanciert Erkunden und Ausnutzen: Mit Wahrscheinlichkeit epsilon zieht es einen zufälligen Arm, sonst den Arm mit dem höchsten geschätzten Wert.

Damit der Ablauf testbar ist, werden die Zufallszahlen vorgegeben. Beginne mit einer Schätzung Q = 0 und einem Zähler N = 0 für jeden Arm. In jedem Schritt t:

  1. Wenn random_values[t] < epsilon, erkunde: arm = random_arms[t]. Sonst nutze aus: arm = der Arm mit dem höchsten Q (bei Gleichstand der kleinste Index).
  2. Erhalte reward = rewards[t][arm].
  3. N[arm] ← N[arm] + 1 und Q[arm] ← Q[arm] + (reward - Q[arm]) / N[arm], der laufende Mittelwert.

Implementiere epsilon_greedy(rewards, epsilon, random_values, random_arms).

Eingabe

rewards: Eine Zeile pro Schritt mit der Belohnung, die jeder Arm in diesem Schritt zahlen würde.

epsilon: Die Erkundungswahrscheinlichkeit.

random_values: Eine Zufallszahl in [0, 1) pro Schritt.

random_arms: Der Arm, der in jedem Schritt beim Erkunden gezogen wird.

Ausgabe

Gib die endgültigen Q-Schätzungen zurück, eine pro Arm.

Einschränkungen

1 ≤ Schritte ≤ 10.000, 1 ≤ Arme ≤ 100

0 ≤ epsilon ≤ 1, -100 ≤ jede Belohnung ≤ 100

Beispiele

Beispiel 1
Eingabe:
rewards = [
    [1.0, 3.0],
    [1.0, 3.0],
    [1.0, 3.0],
    [1.0, 3.0]
]
epsilon = 0.1
random_values = [0.5, 0.05, 0.7, 0.9]
random_arms = [0, 1, 0, 0]

Erwartete Ausgabe:
expected = [1.0, 3.0]
Eingabe:
std::vector<std::vector<double>> rewards = {
    {1.0, 3.0},
    {1.0, 3.0},
    {1.0, 3.0},
    {1.0, 3.0}
};
double epsilon = 0.1;
std::vector<double> random_values = {0.5, 0.05, 0.7, 0.9};
std::vector<long long> random_arms = {0, 1, 0, 0};

Erwartete Ausgabe:
std::vector<double> expected = {1.0, 3.0};
Eingabe:
double[][] rewards = new double[][] {
    new double[] {1.0, 3.0},
    new double[] {1.0, 3.0},
    new double[] {1.0, 3.0},
    new double[] {1.0, 3.0}
};
double epsilon = 0.1;
double[] random_values = new double[] {0.5, 0.05, 0.7, 0.9};
long[] random_arms = new long[] {0, 1, 0, 0};

Erwartete Ausgabe:
double[] expected = new double[] {1.0, 3.0};

Erläuterung

Schritt 0 nutzt aus; beide Q sind 0, also wird Arm 0 gezogen und Q = [1, 0]. Schritt 1 erkundet (0.05 < 0.1) und probiert Arm 1: Q = [1, 3]. Schritte 2 und 3 nutzen den besseren Arm 1 aus. Ergebnis: [1, 3].

Beispiel 2
Eingabe:
rewards = [
    [2.0, 5.0],
    [4.0, 5.0],
    [0.0, 5.0]
]
epsilon = 0.0
random_values = [0.5, 0.5, 0.5]
random_arms = [1, 1, 1]

Erwartete Ausgabe:
expected = [2.0, 0.0]
Eingabe:
std::vector<std::vector<double>> rewards = {
    {2.0, 5.0},
    {4.0, 5.0},
    {0.0, 5.0}
};
double epsilon = 0.0;
std::vector<double> random_values = {0.5, 0.5, 0.5};
std::vector<long long> random_arms = {1, 1, 1};

Erwartete Ausgabe:
std::vector<double> expected = {2.0, 0.0};
Eingabe:
double[][] rewards = new double[][] {
    new double[] {2.0, 5.0},
    new double[] {4.0, 5.0},
    new double[] {0.0, 5.0}
};
double epsilon = 0.0;
double[] random_values = new double[] {0.5, 0.5, 0.5};
long[] random_arms = new long[] {1, 1, 1};

Erwartete Ausgabe:
double[] expected = new double[] {2.0, 0.0};

Erläuterung

Mit epsilon = 0 erkundet der Agent nie. Er zieht immer Arm 0, dessen Mittelwert 2 → 3 → 2 verläuft, und erfährt nie, dass Arm 1 5 zahlt. Ergebnis: [2, 0].

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Wähle in jedem Schritt entweder den erzwungen zufälligen Arm oder den aktuell bestbewerteten Arm.

Hinweis 2

Aktualisiere den Wert jedes Arms mit einem gleitenden Mittelwert, damit alte Belohnungen mit mehr Ziehungen weniger ins Gewicht fallen.

Hinweis 3

Brich Gleichstände zugunsten des Arms mit dem kleinsten Index, und denk daran, dass sich pro Schritt nur der gewählte Arm ändert.

Erwartete Komplexität

Zeit O(steps * arms), zusätzlicher Speicher O(arms)

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.