Mittel 0 gelöst 0% Erfolgsquote

Wertiteration

Berechne, wie wertvoll jeder Zustand eines Markov-Entscheidungsprozesses ist, indem du wiederholt das Bellman-Optimalitäts-Update anwendest.

Das lernst du

  • Das Bellman-Optimalitäts-Update anwenden
  • Zustandswerte Durchlauf für Durchlauf berechnen
  • Entscheidungen als Zustände, Aktionen und Belohnungen modellieren

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

Beispiel 1
Eingabe:
next_states = [
    [0, 1],
    [0, 2],
    [-1]
]
rewards = [
    [0.0, 0.0],
    [0.0, 0.0],
    [10.0]
]
gamma = 0.9
iterations = 3

Erwartete Ausgabe:
expected = [8.1, 9.0, 10.0]
Eingabe:
std::vector<std::vector<long long>> next_states = {
    {0, 1},
    {0, 2},
    {-1}
};
std::vector<std::vector<double>> rewards = {
    {0.0, 0.0},
    {0.0, 0.0},
    {10.0}
};
double gamma = 0.9;
long long iterations = 3;

Erwartete Ausgabe:
std::vector<double> expected = {8.1, 9.0, 10.0};
Eingabe:
long[][] next_states = new long[][] {
    new long[] {0, 1},
    new long[] {0, 2},
    new long[] {-1}
};
double[][] rewards = new double[][] {
    new double[] {0.0, 0.0},
    new double[] {0.0, 0.0},
    new double[] {10.0}
};
double gamma = 0.9;
long iterations = 3;

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].

Beispiel 2
Eingabe:
next_states = [
    [1, 0],
    [0, 1]
]
rewards = [
    [1.0, 2.0],
    [3.0, 0.0]
]
gamma = 0.0
iterations = 5

Erwartete Ausgabe:
expected = [2.0, 3.0]
Eingabe:
std::vector<std::vector<long long>> next_states = {
    {1, 0},
    {0, 1}
};
std::vector<std::vector<double>> rewards = {
    {1.0, 2.0},
    {3.0, 0.0}
};
double gamma = 0.0;
long long iterations = 5;

Erwartete Ausgabe:
std::vector<double> expected = {2.0, 3.0};
Eingabe:
long[][] next_states = new long[][] {
    new long[] {1, 0},
    new long[] {0, 1}
};
double[][] rewards = new double[][] {
    new double[] {1.0, 2.0},
    new double[] {3.0, 0.0}
};
double gamma = 0.0;
long iterations = 5;

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.

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.