Problème
L'itération sur les valeurs résout un processus de décision markovien : elle trouve V(s), la meilleure récompense totale actualisée que l'on peut obtenir en partant de l'état s.
Ici, les transitions sont déterministes. Dans l'état s, l'action a donne la récompense rewards[s][a] et mène à l'état next_states[s][a], où -1 signifie que l'épisode se termine. Partez de V(s) = 0 pour chaque état, puis répétez iterations fois, en calculant chaque nouvelle valeur à partir du balayage précédent :
V_new(s) = max sur a de ( rewards[s][a] + gamma × V(next_states[s][a]) )
où le terme gamma × V vaut 0 quand l'état suivant est -1.
Implémentez value_iteration(next_states, rewards, gamma, iterations).
Entrée
next_states : Pour chaque état, l'état suivant de chacune de ses actions (-1 termine l'épisode). Les états peuvent avoir des nombres d'actions différents.
rewards : La récompense de chaque action, de même forme que next_states.
gamma : Le facteur d'actualisation.
iterations : Le nombre de balayages.
Sortie
Renvoyez V après le dernier balayage, une valeur par état.
Contraintes
1 ≤ états ≤ 200, 1 ≤ actions par état ≤ 10, 0 ≤ iterations ≤ 1 000
-100 ≤ chaque récompense ≤ 100, 0 ≤ gamma ≤ 1
Exemples
Entrée :
gamma = 0.9
rewards = [
[0.0, 0.0],
[0.0, 0.0],
[10.0]
]
iterations = 3
next_states = [
[0, 1],
[0, 2],
[-1]
]
Sortie attendue :
expected = [8.1, 9.0, 10.0]Entrée :
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}
};
Sortie attendue :
std::vector<double> expected = {8.1, 9.0, 10.0};Entrée :
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}
};
Sortie attendue :
double[] expected = new double[] {8.1, 9.0, 10.0};Explication
Balayage 1 : seul l'état 2 peut obtenir une récompense, V = [0, 0, 10]. Balayage 2 : l'état 1 va à droite vers lui, 0.9 × 10 = 9, V = [0, 9, 10]. Balayage 3 : l'état 0 obtient 0.9 × 9 = 8.1. Résultat : [8.1, 9, 10].
Entrée :
gamma = 0.0
rewards = [
[1.0, 2.0],
[3.0, 0.0]
]
iterations = 5
next_states = [
[1, 0],
[0, 1]
]
Sortie attendue :
expected = [2.0, 3.0]Entrée :
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}
};
Sortie attendue :
std::vector<double> expected = {2.0, 3.0};Entrée :
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}
};
Sortie attendue :
double[] expected = new double[] {2.0, 3.0};Explication
Avec gamma = 0, le futur ne compte pas, donc la valeur de chaque état est simplement sa meilleure récompense immédiate : [2, 3].
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Chaque passe n’utilise que les valeurs de la passe précédente, pas les mises à jour faites plus tôt dans le même passage.
Indice 2
Pour chaque état, comparez toutes les actions en combinant la récompense immédiate avec la valeur actualisée de l’état suivant.
Indice 3
Traitez les actions terminales avec soin : elles ne contribuent que par leur récompense immédiate quand l’état suivant est absent.
Complexité attendue
temps O(iterations * total_actions), espace supplémentaire O(states)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.