Problema
L'iterazione dei valori risolve un processo decisionale di Markov: trova V(s), la migliore ricompensa totale scontata che si può ottenere partendo dallo stato s.
Qui le transizioni sono deterministiche. Nello stato s, l'azione a dà la ricompensa rewards[s][a] e porta allo stato next_states[s][a], dove -1 significa che l'episodio termina. Parti da V(s) = 0 per ogni stato, poi ripeti iterations volte, calcolando ogni nuovo valore dalla passata precedente:
V_new(s) = massimo su a di ( rewards[s][a] + gamma × V(next_states[s][a]) )
dove il termine gamma × V vale 0 quando lo stato successivo è -1.
Implementa value_iteration(next_states, rewards, gamma, iterations).
Input
next_states: Per ogni stato, lo stato successivo di ciascuna delle sue azioni (-1 termina l'episodio). Gli stati possono avere un numero diverso di azioni.
rewards: La ricompensa di ogni azione, con la stessa forma di next_states.
gamma: Il fattore di sconto.
iterations: Il numero di passate.
Output
Restituisci V dopo l'ultima passata, un valore per stato.
Vincoli
1 ≤ stati ≤ 200, 1 ≤ azioni per stato ≤ 10, 0 ≤ iterations ≤ 1.000
-100 ≤ ogni ricompensa ≤ 100, 0 ≤ gamma ≤ 1
Esempi
Input:
gamma = 0.9
rewards = [
[0.0, 0.0],
[0.0, 0.0],
[10.0]
]
iterations = 3
next_states = [
[0, 1],
[0, 2],
[-1]
]
Output atteso:
expected = [8.1, 9.0, 10.0]Input:
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}
};
Output atteso:
std::vector<double> expected = {8.1, 9.0, 10.0};Input:
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}
};
Output atteso:
double[] expected = new double[] {8.1, 9.0, 10.0};Spiegazione
Passata 1: solo lo stato 2 può ottenere una ricompensa, V = [0, 0, 10]. Passata 2: lo stato 1 va a destra verso di esso, 0.9 × 10 = 9, V = [0, 9, 10]. Passata 3: lo stato 0 ottiene 0.9 × 9 = 8.1. Risultato: [8.1, 9, 10].
Input:
gamma = 0.0
rewards = [
[1.0, 2.0],
[3.0, 0.0]
]
iterations = 5
next_states = [
[1, 0],
[0, 1]
]
Output atteso:
expected = [2.0, 3.0]Input:
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}
};
Output atteso:
std::vector<double> expected = {2.0, 3.0};Input:
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}
};
Output atteso:
double[] expected = new double[] {2.0, 3.0};Spiegazione
Con gamma = 0 il futuro non conta, quindi il valore di ogni stato è semplicemente la sua migliore ricompensa immediata: [2, 3].
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Ogni sweep usa solo i valori dello sweep precedente, non gli aggiornamenti fatti prima nello stesso passaggio.
Suggerimento 2
Per ogni stato, confronta tutte le azioni combinando la ricompensa immediata con il valore scontato dello stato successivo.
Suggerimento 3
Gestisci con cura le azioni terminali: contribuiscono solo con la loro ricompensa immediata quando lo stato successivo manca.
Complessità attesa
tempo O(iterations * total_actions), spazio aggiuntivo O(states)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.