Problema
Il Q-learning impara solo dall'esperienza quanto è buona ogni azione in ogni stato, Q(s, a). Dopo aver eseguito l'azione a nello stato s, ricevuto reward ed essere arrivati nello stato s':
- target = reward, se l'episodio è terminato (
done= 1) - target = reward + gamma × massimo su a' di Q(s', a'), altrimenti
- Q(s, a) ← Q(s, a) + alpha × (target - Q(s, a))
Parti con tutti i valori Q a 0 e applica le transizioni in ordine.
Implementa q_learning(num_states, num_actions, transitions, alpha, gamma).
Input
num_states, num_actions: La dimensione della tabella.
transitions: Una riga [state, action, reward, next_state, done] per passo.
alpha: Il learning rate.
gamma: Il fattore di sconto.
Output
Restituisci la tabella Q come matrice con una riga per stato e una colonna per azione.
Vincoli
1 ≤ num_states, num_actions ≤ 100, 0 ≤ numero di transizioni ≤ 10.000
-100 ≤ reward ≤ 100, done è 0 o 1
0 < alpha ≤ 1, 0 ≤ gamma ≤ 1
Esempi
Input:
alpha = 0.5
gamma = 0.9
num_states = 2
num_actions = 2
transitions = [
[0, 1, 0, 1, 0],
[1, 0, 10, 0, 1]
]
Output atteso:
expected = [
[0.0, 0.0],
[5.0, 0.0]
]Input:
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}
};
Output atteso:
std::vector<std::vector<double>> expected = {
{0.0, 0.0},
{5.0, 0.0}
};Input:
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}
};
Output atteso:
double[][] expected = new double[][] {
new double[] {0.0, 0.0},
new double[] {5.0, 0.0}
};Spiegazione
Il primo passo non trova ancora ricompense: target = 0 + 0.9 × max(Q[1]) = 0, quindi Q[0][1] resta 0. Il secondo passo termina l'episodio con ricompensa 10: Q[1][0] = 0 + 0.5 × (10 - 0) = 5.
Input:
alpha = 0.5
gamma = 0.9
num_states = 2
num_actions = 2
transitions = [
[1, 0, 10, 0, 1],
[0, 1, 0, 1, 0]
]
Output atteso:
expected = [
[0.0, 2.25],
[5.0, 0.0]
]Input:
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}
};
Output atteso:
std::vector<std::vector<double>> expected = {
{0.0, 2.25},
{5.0, 0.0}
};Input:
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}
};
Output atteso:
double[][] expected = new double[][] {
new double[] {0.0, 2.25},
new double[] {5.0, 0.0}
};Spiegazione
Gli stessi passi in ordine inverso. Q[1][0] diventa prima 5, quindi il passo dallo stato 0 lo vede: target = 0 + 0.9 × 5 = 4.5 e Q[0][1] = 0.5 × 4.5 = 2.25. La ricompensa è risalita di uno stato.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Ogni transizione aggiorna una voce della tabella usando solo il suo valore corrente e la migliore stima dallo stato successivo.
Suggerimento 2
Tieni la tabella Q inizializzata a zero, poi processa le transizioni in ordine e aggiorna subito dopo ciascuna.
Suggerimento 3
Se l'episodio termina, non c'è alcun valore futuro da aggiungere, e il massimo sullo stato successivo non va usato.
Complessità attesa
tempo O(T * A), spazio aggiuntivo O(S * A)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.