Problema
El Q-learning aprende solo a partir de la experiencia lo buena que es cada acción en cada estado, Q(s, a). Tras realizar la acción a en el estado s, recibir reward y llegar al estado s':
- target = reward, si el episodio terminó (
done= 1) - target = reward + gamma × máximo sobre a' de Q(s', a'), en caso contrario
- Q(s, a) ← Q(s, a) + alpha × (target - Q(s, a))
Empieza con todos los valores Q en 0 y aplica las transiciones en orden.
Implementa q_learning(num_states, num_actions, transitions, alpha, gamma).
Entrada
num_states, num_actions: El tamaño de la tabla.
transitions: Una fila [state, action, reward, next_state, done] por paso.
alpha: La tasa de aprendizaje.
gamma: El factor de descuento.
Salida
Devuelve la tabla Q como una matriz con una fila por estado y una columna por acción.
Restricciones
1 ≤ num_states, num_actions ≤ 100, 0 ≤ número de transiciones ≤ 10.000
-100 ≤ reward ≤ 100, done es 0 o 1
0 < alpha ≤ 1, 0 ≤ gamma ≤ 1
Ejemplos
Entrada:
alpha = 0.5
gamma = 0.9
num_states = 2
num_actions = 2
transitions = [
[0, 1, 0, 1, 0],
[1, 0, 10, 0, 1]
]
Salida 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}
};
Salida 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}
};
Salida esperada:
double[][] expected = new double[][] {
new double[] {0.0, 0.0},
new double[] {5.0, 0.0}
};Explicación
El primer paso aún no encuentra recompensa: target = 0 + 0.9 × max(Q[1]) = 0, así que Q[0][1] sigue en 0. El segundo paso termina el episodio con 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]
]
Salida 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}
};
Salida 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}
};
Salida esperada:
double[][] expected = new double[][] {
new double[] {0.0, 2.25},
new double[] {5.0, 0.0}
};Explicación
Los mismos pasos en el orden inverso. Q[1][0] pasa primero a 5, así que el paso desde el estado 0 lo ve: target = 0 + 0.9 × 5 = 4.5 y Q[0][1] = 0.5 × 4.5 = 2.25. La recompensa ha fluido un estado hacia atrás.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Cada transición actualiza una entrada de la tabla usando solo su valor actual y la mejor estimación del siguiente estado.
Pista 2
Mantén la tabla Q inicializada en cero, luego procesa las transiciones en orden y actualiza inmediatamente después de cada una.
Pista 3
Si el episodio termina, no hay valor futuro que sumar, y no debe usarse el máximo del siguiente estado.
Complejidad esperada
O(T * A) tiempo, O(S * A) espacio extra
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.