Problem
Wertiteration löst einen Markov-Entscheidungsprozess: Sie findet V(s), die beste gesamte diskontierte Belohnung, die man ab Zustand s sammeln kann.
Hier sind die Übergänge deterministisch. In Zustand s bringt Aktion a die Belohnung rewards[s][a] und führt in Zustand next_states[s][a], wobei -1 bedeutet, dass die Episode endet. Beginne mit V(s) = 0 für jeden Zustand und wiederhole dann iterations-mal, wobei jeder neue Wert aus dem vorherigen Durchlauf berechnet wird:
V_new(s) = Maximum über a von ( rewards[s][a] + gamma × V(next_states[s][a]) )
wobei der Term gamma × V gleich 0 ist, wenn der nächste Zustand -1 ist.
Implementiere value_iteration(next_states, rewards, gamma, iterations).
Eingabe
next_states: Für jeden Zustand der nächste Zustand jeder seiner Aktionen (-1 beendet die Episode). Zustände können unterschiedlich viele Aktionen haben.
rewards: Die Belohnung jeder Aktion, in derselben Form wie next_states.
gamma: Der Diskontfaktor.
iterations: Die Anzahl der Durchläufe.
Ausgabe
Gib V nach dem letzten Durchlauf zurück, ein Wert pro Zustand.
Einschränkungen
1 ≤ Zustände ≤ 200, 1 ≤ Aktionen pro Zustand ≤ 10, 0 ≤ iterations ≤ 1.000
-100 ≤ jede Belohnung ≤ 100, 0 ≤ gamma ≤ 1
Beispiele
Eingabe:
gamma = 0.9
rewards = [
[0.0, 0.0],
[0.0, 0.0],
[10.0]
]
iterations = 3
next_states = [
[0, 1],
[0, 2],
[-1]
]
Erwartete Ausgabe:
expected = [8.1, 9.0, 10.0]Eingabe:
double gamma = 0.9;
std::vector<std::vector<double>> rewards = {
{0.0, 0.0},
{0.0, 0.0},
{10.0}
};
long long iterations = 3;
std::vector<std::vector<long long>> next_states = {
{0, 1},
{0, 2},
{-1}
};
Erwartete Ausgabe:
std::vector<double> expected = {8.1, 9.0, 10.0};Eingabe:
double gamma = 0.9;
double[][] rewards = new double[][] {
new double[] {0.0, 0.0},
new double[] {0.0, 0.0},
new double[] {10.0}
};
long iterations = 3;
long[][] next_states = new long[][] {
new long[] {0, 1},
new long[] {0, 2},
new long[] {-1}
};
Erwartete Ausgabe:
double[] expected = new double[] {8.1, 9.0, 10.0};Erläuterung
Durchlauf 1: Nur Zustand 2 kann eine Belohnung einsammeln, V = [0, 0, 10]. Durchlauf 2: Zustand 1 geht nach rechts dorthin, 0.9 × 10 = 9, V = [0, 9, 10]. Durchlauf 3: Zustand 0 bekommt 0.9 × 9 = 8.1. Ergebnis: [8.1, 9, 10].
Eingabe:
gamma = 0.0
rewards = [
[1.0, 2.0],
[3.0, 0.0]
]
iterations = 5
next_states = [
[1, 0],
[0, 1]
]
Erwartete Ausgabe:
expected = [2.0, 3.0]Eingabe:
double gamma = 0.0;
std::vector<std::vector<double>> rewards = {
{1.0, 2.0},
{3.0, 0.0}
};
long long iterations = 5;
std::vector<std::vector<long long>> next_states = {
{1, 0},
{0, 1}
};
Erwartete Ausgabe:
std::vector<double> expected = {2.0, 3.0};Eingabe:
double gamma = 0.0;
double[][] rewards = new double[][] {
new double[] {1.0, 2.0},
new double[] {3.0, 0.0}
};
long iterations = 5;
long[][] next_states = new long[][] {
new long[] {1, 0},
new long[] {0, 1}
};
Erwartete Ausgabe:
double[] expected = new double[] {2.0, 3.0};Erläuterung
Mit gamma = 0 zählt die Zukunft nicht, also ist der Wert jedes Zustands einfach seine beste sofortige Belohnung: [2, 3].
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Jeder Durchlauf verwendet nur die Werte aus dem vorherigen Sweep, nicht die Änderungen, die schon in diesem Pass gemacht wurden.
Hinweis 2
Vergleiche für jeden Zustand alle Aktionen, indem du die unmittelbare Belohnung mit dem diskontierten Wert des Folgezustands kombinierst.
Hinweis 3
Behandle terminale Aktionen sorgfältig: Sie tragen nur ihre unmittelbare Belohnung bei, wenn der Folgezustand fehlt.
Erwartete Komplexität
Zeit O(iterations * total_actions), zusätzlicher Speicher O(states)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.