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:
- 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). - Erhalte reward =
rewards[t][arm]. - 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
Eingabe:
epsilon = 0.1
rewards = [
[1.0, 3.0],
[1.0, 3.0],
[1.0, 3.0],
[1.0, 3.0]
]
random_arms = [0, 1, 0, 0]
random_values = [0.5, 0.05, 0.7, 0.9]
Erwartete Ausgabe:
expected = [1.0, 3.0]Eingabe:
double epsilon = 0.1;
std::vector<std::vector<double>> rewards = {
{1.0, 3.0},
{1.0, 3.0},
{1.0, 3.0},
{1.0, 3.0}
};
std::vector<long long> random_arms = {0, 1, 0, 0};
std::vector<double> random_values = {0.5, 0.05, 0.7, 0.9};
Erwartete Ausgabe:
std::vector<double> expected = {1.0, 3.0};Eingabe:
double epsilon = 0.1;
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}
};
long[] random_arms = new long[] {0, 1, 0, 0};
double[] random_values = new double[] {0.5, 0.05, 0.7, 0.9};
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].
Eingabe:
epsilon = 0.0
rewards = [
[2.0, 5.0],
[4.0, 5.0],
[0.0, 5.0]
]
random_arms = [1, 1, 1]
random_values = [0.5, 0.5, 0.5]
Erwartete Ausgabe:
expected = [2.0, 0.0]Eingabe:
double epsilon = 0.0;
std::vector<std::vector<double>> rewards = {
{2.0, 5.0},
{4.0, 5.0},
{0.0, 5.0}
};
std::vector<long long> random_arms = {1, 1, 1};
std::vector<double> random_values = {0.5, 0.5, 0.5};
Erwartete Ausgabe:
std::vector<double> expected = {2.0, 0.0};Eingabe:
double epsilon = 0.0;
double[][] rewards = new double[][] {
new double[] {2.0, 5.0},
new double[] {4.0, 5.0},
new double[] {0.0, 5.0}
};
long[] random_arms = new long[] {1, 1, 1};
double[] random_values = new double[] {0.5, 0.5, 0.5};
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.