Alle Herausforderungen
Einfach 0 gelöst 0% Erfolgsquote

Epsilon-Greedy Multi-Armed Bandit

Balance exploration and exploitation on a multi-armed bandit with epsilon-greedy action selection.

Das lernst du

  • Balance exploring and exploiting
  • Update running averages incrementally
  • See why pure greedy agents get stuck

Problem

Übersetzung anzeigen

A multi-armed bandit is a row of slot machines (arms) with unknown payouts. Epsilon-greedy balances exploring and exploiting: with probability epsilon it pulls a random arm, otherwise it pulls the arm with the highest estimated value.

To make the run testable, the random numbers are given. Start with an estimate Q = 0 and a count N = 0 for every arm. At each step t:

  1. If random_values[t] < epsilon, explore: arm = random_arms[t]. Otherwise exploit: arm = the arm with the highest Q (the lowest index if several tie).
  2. Receive reward = rewards[t][arm].
  3. N[arm] ← N[arm] + 1 and Q[arm] ← Q[arm] + (reward - Q[arm]) / N[arm], the running average.

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

Input

rewards: One row per step with the reward each arm would pay at that step.

epsilon: The exploration probability.

random_values: One random number in [0, 1) per step.

random_arms: The arm to pull at each step if exploring.

Output

Return the final Q estimates, one per arm.

Einschränkungen

1 ≤ steps ≤ 10,000, 1 ≤ arms ≤ 100

0 ≤ epsilon ≤ 1, -100 ≤ each reward ≤ 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

Step 0 exploits; both Q are 0, so arm 0 is pulled and Q = [1, 0]. Step 1 explores (0.05 < 0.1) and tries arm 1: Q = [1, 3]. Steps 2 and 3 exploit the better arm 1. Result: [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

With epsilon = 0 the agent never explores. It keeps pulling arm 0, whose average goes 2 → 3 → 2, and never finds out arm 1 pays 5. Result: [2, 0].

So gehst du vor

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

Hinweis 1

At each step, choose either the forced random arm or the currently best estimated arm.

Hinweis 2

Update each arm’s value with a running average so old rewards matter less as more pulls accumulate.

Hinweis 3

Break ties by choosing the smallest-index arm, and remember that only the chosen arm changes each step.

Erwartete Komplexität

O(steps * arms) time, O(arms) extra space

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.