Problema
O Q-learning aprende apenas pela experiência o quão boa é cada ação em cada estado, Q(s, a). Depois de executar a ação a no estado s, receber reward e chegar ao estado s':
- target = reward, se o episódio terminou (
done= 1) - target = reward + gamma × máximo sobre a' de Q(s', a'), caso contrário
- Q(s, a) ← Q(s, a) + alpha × (target - Q(s, a))
Comece com todos os valores Q em 0 e aplique as transições em ordem.
Implemente q_learning(num_states, num_actions, transitions, alpha, gamma).
Entrada
num_states, num_actions: O tamanho da tabela.
transitions: Uma linha [state, action, reward, next_state, done] por passo.
alpha: A taxa de aprendizado.
gamma: O fator de desconto.
Saída
Retorne a tabela Q como uma matriz com uma linha por estado e uma coluna por ação.
Restrições
1 ≤ num_states, num_actions ≤ 100, 0 ≤ número de transições ≤ 10.000
-100 ≤ reward ≤ 100, done é 0 ou 1
0 < alpha ≤ 1, 0 ≤ gamma ≤ 1
Exemplos
Entrada:
alpha = 0.5
gamma = 0.9
num_states = 2
num_actions = 2
transitions = [
[0, 1, 0, 1, 0],
[1, 0, 10, 0, 1]
]
Saída esperada:
expected = [
[0.0, 0.0],
[5.0, 0.0]
]Entrada:
double alpha = 0.5;
double gamma = 0.9;
long long num_states = 2;
long long num_actions = 2;
std::vector<std::vector<long long>> transitions = {
{0, 1, 0, 1, 0},
{1, 0, 10, 0, 1}
};
Saída esperada:
std::vector<std::vector<double>> expected = {
{0.0, 0.0},
{5.0, 0.0}
};Entrada:
double alpha = 0.5;
double gamma = 0.9;
long num_states = 2;
long num_actions = 2;
long[][] transitions = new long[][] {
new long[] {0, 1, 0, 1, 0},
new long[] {1, 0, 10, 0, 1}
};
Saída esperada:
double[][] expected = new double[][] {
new double[] {0.0, 0.0},
new double[] {5.0, 0.0}
};Explicação
O primeiro passo ainda não encontra recompensa: target = 0 + 0.9 × max(Q[1]) = 0, então Q[0][1] continua 0. O segundo passo termina o episódio com recompensa 10: Q[1][0] = 0 + 0.5 × (10 - 0) = 5.
Entrada:
alpha = 0.5
gamma = 0.9
num_states = 2
num_actions = 2
transitions = [
[1, 0, 10, 0, 1],
[0, 1, 0, 1, 0]
]
Saída esperada:
expected = [
[0.0, 2.25],
[5.0, 0.0]
]Entrada:
double alpha = 0.5;
double gamma = 0.9;
long long num_states = 2;
long long num_actions = 2;
std::vector<std::vector<long long>> transitions = {
{1, 0, 10, 0, 1},
{0, 1, 0, 1, 0}
};
Saída esperada:
std::vector<std::vector<double>> expected = {
{0.0, 2.25},
{5.0, 0.0}
};Entrada:
double alpha = 0.5;
double gamma = 0.9;
long num_states = 2;
long num_actions = 2;
long[][] transitions = new long[][] {
new long[] {1, 0, 10, 0, 1},
new long[] {0, 1, 0, 1, 0}
};
Saída esperada:
double[][] expected = new double[][] {
new double[] {0.0, 2.25},
new double[] {5.0, 0.0}
};Explicação
Os mesmos passos na ordem inversa. Q[1][0] vira 5 primeiro, então o passo a partir do estado 0 o enxerga: target = 0 + 0.9 × 5 = 4.5 e Q[0][1] = 0.5 × 4.5 = 2.25. A recompensa voltou um estado.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Cada transição atualiza uma entrada da tabela usando só seu valor atual e a melhor estimativa do próximo estado.
Dica 2
Mantenha a tabela Q iniciada em zero, depois processe as transições em ordem e atualize imediatamente após cada uma.
Dica 3
Se o episódio termina, não há valor futuro a somar, e o máximo do próximo estado não deve ser usado.
Complexidade esperada
tempo O(T * A), espaço extra O(S * A)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.