Mittel 0 gelöst 0% Erfolgsquote

Q-Learning Updates

Apply the Q-learning update to a stream of experiences and watch rewards flow back to earlier states.

Das lernst du

  • Update action values from experience
  • Use discount factors and terminal states
  • Watch rewards flow back to earlier states

Problem

Übersetzung anzeigen

Q-learning learns how good each action is in each state, Q(s, a), from experience alone. After taking action a in state s, receiving reward and landing in state s':

  • target = reward, if the episode ended (done = 1)
  • target = reward + gamma × max over a' of Q(s', a'), otherwise
  • Q(s, a) ← Q(s, a) + alpha × (target - Q(s, a))

Start with every Q value at 0 and apply the transitions in order.

Implement q_learning(num_states, num_actions, transitions, alpha, gamma).

Input

num_states, num_actions: The table size.

transitions: One row [state, action, reward, next_state, done] per step.

alpha: The learning rate.

gamma: The discount factor.

Output

Return the Q table as a matrix with one row per state and one column per action.

Einschränkungen

1 ≤ num_states, num_actions ≤ 100, 0 ≤ number of transitions ≤ 10,000

-100 ≤ reward ≤ 100, done is 0 or 1

0 < alpha ≤ 1, 0 ≤ gamma ≤ 1

Beispiele

Beispiel 1
Eingabe:
num_states = 2
num_actions = 2
transitions = [
    [0, 1, 0, 1, 0],
    [1, 0, 10, 0, 1]
]
alpha = 0.5
gamma = 0.9

Erwartete Ausgabe:
expected = [
    [0.0, 0.0],
    [5.0, 0.0]
]
Eingabe:
long long num_states = 2;
long long num_actions = 2;
std::vector<std::vector<long long>> transitions = {
    {0, 1, 0, 1, 0},
    {1, 0, 10, 0, 1}
};
double alpha = 0.5;
double gamma = 0.9;

Erwartete Ausgabe:
std::vector<std::vector<double>> expected = {
    {0.0, 0.0},
    {5.0, 0.0}
};
Eingabe:
long num_states = 2;
long num_actions = 2;
long[][] transitions = new long[][] {
    new long[] {0, 1, 0, 1, 0},
    new long[] {1, 0, 10, 0, 1}
};
double alpha = 0.5;
double gamma = 0.9;

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

Erläuterung

The first step finds no reward yet: target = 0 + 0.9 × max(Q[1]) = 0, so Q[0][1] stays 0. The second step ends the episode with reward 10: Q[1][0] = 0 + 0.5 × (10 - 0) = 5.

Beispiel 2
Eingabe:
num_states = 2
num_actions = 2
transitions = [
    [1, 0, 10, 0, 1],
    [0, 1, 0, 1, 0]
]
alpha = 0.5
gamma = 0.9

Erwartete Ausgabe:
expected = [
    [0.0, 2.25],
    [5.0, 0.0]
]
Eingabe:
long long num_states = 2;
long long num_actions = 2;
std::vector<std::vector<long long>> transitions = {
    {1, 0, 10, 0, 1},
    {0, 1, 0, 1, 0}
};
double alpha = 0.5;
double gamma = 0.9;

Erwartete Ausgabe:
std::vector<std::vector<double>> expected = {
    {0.0, 2.25},
    {5.0, 0.0}
};
Eingabe:
long num_states = 2;
long num_actions = 2;
long[][] transitions = new long[][] {
    new long[] {1, 0, 10, 0, 1},
    new long[] {0, 1, 0, 1, 0}
};
double alpha = 0.5;
double gamma = 0.9;

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

Erläuterung

Same steps in the other order. Q[1][0] becomes 5 first, so the step from state 0 now sees it: target = 0 + 0.9 × 5 = 4.5 and Q[0][1] = 0.5 × 4.5 = 2.25. The reward has flowed back one state.

So gehst du vor

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

Hinweis 1

Each transition updates one table entry using only its current value and the best estimate from the next state.

Hinweis 2

Keep the Q table initialized to zero, then process transitions in order and update immediately after each one.

Hinweis 3

If the episode ends, there is no future value to add, and the next-state maximum should not be used.

Erwartete Komplexität

O(T * A) time, O(S * A) 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.