Mittel 0 gelöst 0% Erfolgsquote

Value Iteration

Compute how valuable each state of a Markov decision process is by repeatedly applying the Bellman optimality update.

Das lernst du

  • Apply the Bellman optimality update
  • Compute state values sweep by sweep
  • Model decisions as states, actions and rewards

Problem

Übersetzung anzeigen

Value iteration solves a Markov decision process: it finds V(s), the best total discounted reward you can collect starting from state s.

Here the transitions are deterministic. In state s, action a gives reward rewards[s][a] and moves to state next_states[s][a], where -1 means the episode ends. Start with V(s) = 0 for every state, then repeat iterations times, computing every new value from the previous sweep:

V_new(s) = max over a of ( rewards[s][a] + gamma × V(next_states[s][a]) )

where the gamma × V term is 0 when the next state is -1.

Implement value_iteration(next_states, rewards, gamma, iterations).

Input

next_states: For each state, the next state of each of its actions (-1 ends the episode). States may have different numbers of actions.

rewards: The reward of each action, with the same shape as next_states.

gamma: The discount factor.

iterations: The number of sweeps.

Output

Return V after the last sweep, one value per state.

Einschränkungen

1 ≤ states ≤ 200, 1 ≤ actions per state ≤ 10, 0 ≤ iterations ≤ 1,000

-100 ≤ each reward ≤ 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

Sweep 1: only state 2 can collect a reward, V = [0, 0, 10]. Sweep 2: state 1 moves right to it, 0.9 × 10 = 9, V = [0, 9, 10]. Sweep 3: state 0 gets 0.9 × 9 = 8.1. Result: [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

With gamma = 0 the future does not count, so each state's value is just its best immediate reward: [2, 3].

So gehst du vor

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

Hinweis 1

Every sweep uses only the values from the previous sweep, not updates made earlier in the same pass.

Hinweis 2

For each state, compare all actions by combining immediate reward with the discounted value of the next state.

Hinweis 3

Handle terminal actions carefully: they contribute only their immediate reward when the next state is missing.

Erwartete Komplexität

O(iterations * total_actions) time, O(states) 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.