Problema
La iteración de valores resuelve un proceso de decisión de Markov: encuentra V(s), la mejor recompensa total descontada que se puede obtener empezando en el estado s.
Aquí las transiciones son deterministas. En el estado s, la acción a da la recompensa rewards[s][a] y lleva al estado next_states[s][a], donde -1 significa que el episodio termina. Empieza con V(s) = 0 para cada estado y repite iterations veces, calculando cada valor nuevo a partir del barrido anterior:
V_new(s) = máximo sobre a de ( rewards[s][a] + gamma × V(next_states[s][a]) )
donde el término gamma × V es 0 cuando el siguiente estado es -1.
Implementa value_iteration(next_states, rewards, gamma, iterations).
Entrada
next_states: Para cada estado, el siguiente estado de cada una de sus acciones (-1 termina el episodio). Los estados pueden tener distinto número de acciones.
rewards: La recompensa de cada acción, con la misma forma que next_states.
gamma: El factor de descuento.
iterations: El número de barridos.
Salida
Devuelve V tras el último barrido, un valor por estado.
Restricciones
1 ≤ estados ≤ 200, 1 ≤ acciones por estado ≤ 10, 0 ≤ iterations ≤ 1.000
-100 ≤ cada recompensa ≤ 100, 0 ≤ gamma ≤ 1
Ejemplos
Entrada:
gamma = 0.9
rewards = [
[0.0, 0.0],
[0.0, 0.0],
[10.0]
]
iterations = 3
next_states = [
[0, 1],
[0, 2],
[-1]
]
Salida esperada:
expected = [8.1, 9.0, 10.0]Entrada:
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}
};
Salida esperada:
std::vector<double> expected = {8.1, 9.0, 10.0};Entrada:
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}
};
Salida esperada:
double[] expected = new double[] {8.1, 9.0, 10.0};Explicación
Barrido 1: solo el estado 2 puede obtener una recompensa, V = [0, 0, 10]. Barrido 2: el estado 1 va a la derecha hasta él, 0.9 × 10 = 9, V = [0, 9, 10]. Barrido 3: el estado 0 obtiene 0.9 × 9 = 8.1. Resultado: [8.1, 9, 10].
Entrada:
gamma = 0.0
rewards = [
[1.0, 2.0],
[3.0, 0.0]
]
iterations = 5
next_states = [
[1, 0],
[0, 1]
]
Salida esperada:
expected = [2.0, 3.0]Entrada:
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}
};
Salida esperada:
std::vector<double> expected = {2.0, 3.0};Entrada:
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}
};
Salida esperada:
double[] expected = new double[] {2.0, 3.0};Explicación
Con gamma = 0 el futuro no cuenta, así que el valor de cada estado es simplemente su mejor recompensa inmediata: [2, 3].
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Cada barrido usa solo los valores del barrido anterior, no las actualizaciones hechas antes en el mismo paso.
Pista 2
Para cada estado, compara todas las acciones combinando la recompensa inmediata con el valor descontado del siguiente estado.
Pista 3
Maneja con cuidado las acciones terminales: aportan solo su recompensa inmediata cuando falta el siguiente estado.
Complejidad esperada
O(iterations * total_actions) tiempo, O(states) espacio extra
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.