Problema
A iteração de valor resolve um processo de decisão de Markov: ela encontra V(s), a melhor recompensa total descontada que se pode obter começando no estado s.
Aqui as transições são determinísticas. No estado s, a ação a dá a recompensa rewards[s][a] e leva ao estado next_states[s][a], onde -1 significa que o episódio termina. Comece com V(s) = 0 para todo estado e repita iterations vezes, calculando cada novo valor a partir da varredura anterior:
V_new(s) = máximo sobre a de ( rewards[s][a] + gamma × V(next_states[s][a]) )
onde o termo gamma × V é 0 quando o próximo estado é -1.
Implemente value_iteration(next_states, rewards, gamma, iterations).
Entrada
next_states: Para cada estado, o próximo estado de cada uma de suas ações (-1 termina o episódio). Os estados podem ter números diferentes de ações.
rewards: A recompensa de cada ação, com o mesmo formato de next_states.
gamma: O fator de desconto.
iterations: O número de varreduras.
Saída
Retorne V após a última varredura, um valor por estado.
Restrições
1 ≤ estados ≤ 200, 1 ≤ ações por estado ≤ 10, 0 ≤ iterations ≤ 1.000
-100 ≤ cada recompensa ≤ 100, 0 ≤ gamma ≤ 1
Exemplos
Entrada:
gamma = 0.9
rewards = [
[0.0, 0.0],
[0.0, 0.0],
[10.0]
]
iterations = 3
next_states = [
[0, 1],
[0, 2],
[-1]
]
Saída 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}
};
Saída 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}
};
Saída esperada:
double[] expected = new double[] {8.1, 9.0, 10.0};Explicação
Varredura 1: só o estado 2 pode obter recompensa, V = [0, 0, 10]. Varredura 2: o estado 1 vai para a direita até ele, 0.9 × 10 = 9, V = [0, 9, 10]. Varredura 3: o estado 0 recebe 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]
]
Saída 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}
};
Saída 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}
};
Saída esperada:
double[] expected = new double[] {2.0, 3.0};Explicação
Com gamma = 0 o futuro não conta, então o valor de cada estado é simplesmente sua melhor recompensa imediata: [2, 3].
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Cada varredura usa só os valores da varredura anterior, não as atualizações feitas antes no mesmo passo.
Dica 2
Para cada estado, compare todas as ações combinando a recompensa imediata com o valor descontado do próximo estado.
Dica 3
Trate ações terminais com cuidado: elas contribuem só com a recompensa imediata quando o próximo estado não existe.
Complexidade esperada
tempo O(iterations * total_actions), espaço extra O(states)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.