Mittel 0 gelöst 0% Erfolgsquote

Q-Learning-Updates

Wende das Q-Learning-Update auf einen Strom von Erfahrungen an und sieh zu, wie Belohnungen zu früheren Zuständen zurückfließen.

Das lernst du

  • Aktionswerte aus Erfahrung aktualisieren
  • Diskontfaktoren und Endzustände verwenden
  • Zusehen, wie Belohnungen zu früheren Zuständen zurückfließen

Problem

Q-Learning lernt allein aus Erfahrung, wie gut jede Aktion in jedem Zustand ist, Q(s, a). Nachdem in Zustand s die Aktion a ausgeführt, reward erhalten und Zustand s' erreicht wurde:

  • target = reward, wenn die Episode endete (done = 1)
  • target = reward + gamma × Maximum über a' von Q(s', a'), sonst
  • Q(s, a) ← Q(s, a) + alpha × (target - Q(s, a))

Beginne mit allen Q-Werten bei 0 und wende die Übergänge der Reihe nach an.

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

Eingabe

num_states, num_actions: Die Größe der Tabelle.

transitions: Eine Zeile [state, action, reward, next_state, done] pro Schritt.

alpha: Die Lernrate.

gamma: Der Diskontfaktor.

Ausgabe

Gib die Q-Tabelle als Matrix mit einer Zeile pro Zustand und einer Spalte pro Aktion zurück.

Einschränkungen

1 ≤ num_states, num_actions ≤ 100, 0 ≤ Anzahl der Übergänge ≤ 10.000

-100 ≤ reward ≤ 100, done ist 0 oder 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

Der erste Schritt findet noch keine Belohnung: target = 0 + 0.9 × max(Q[1]) = 0, also bleibt Q[0][1] bei 0. Der zweite Schritt beendet die Episode mit Belohnung 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

Dieselben Schritte in umgekehrter Reihenfolge. Q[1][0] wird zuerst 5, also sieht der Schritt aus Zustand 0 diesen Wert: target = 0 + 0.9 × 5 = 4.5 und Q[0][1] = 0.5 × 4.5 = 2.25. Die Belohnung ist einen Zustand zurückgeflossen.

So gehst du vor

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

Hinweis 1

Jeder Übergang aktualisiert genau einen Tabelleneintrag, nur mit seinem aktuellen Wert und der besten Schätzung aus dem Folgezustand.

Hinweis 2

Initialisiere die Q-Tabelle mit null und verarbeite Übergänge in Reihenfolge; aktualisiere sofort nach jedem einzelnen.

Hinweis 3

Wenn die Episode endet, gibt es keinen Zukunftswert mehr hinzuzufügen, und das Maximum des Folgezustands darf nicht verwendet werden.

Erwartete Komplexität

Zeit O(T * A), zusätzlicher Speicher O(S * A)

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.