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
Eingabe:
alpha = 0.5
gamma = 0.9
num_states = 2
num_actions = 2
transitions = [
[0, 1, 0, 1, 0],
[1, 0, 10, 0, 1]
]
Erwartete Ausgabe:
expected = [
[0.0, 0.0],
[5.0, 0.0]
]Eingabe:
double alpha = 0.5;
double gamma = 0.9;
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}
};
Erwartete Ausgabe:
std::vector<std::vector<double>> expected = {
{0.0, 0.0},
{5.0, 0.0}
};Eingabe:
double alpha = 0.5;
double gamma = 0.9;
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}
};
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.
Eingabe:
alpha = 0.5
gamma = 0.9
num_states = 2
num_actions = 2
transitions = [
[1, 0, 10, 0, 1],
[0, 1, 0, 1, 0]
]
Erwartete Ausgabe:
expected = [
[0.0, 2.25],
[5.0, 0.0]
]Eingabe:
double alpha = 0.5;
double gamma = 0.9;
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}
};
Erwartete Ausgabe:
std::vector<std::vector<double>> expected = {
{0.0, 2.25},
{5.0, 0.0}
};Eingabe:
double alpha = 0.5;
double gamma = 0.9;
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}
};
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.