Problème
Le Q-learning apprend, à partir de la seule expérience, à quel point chaque action est bonne dans chaque état, Q(s, a). Après avoir effectué l'action a dans l'état s, reçu reward et atterri dans l'état s' :
- target = reward, si l'épisode s'est terminé (
done= 1) - target = reward + gamma × max sur a' de Q(s', a'), sinon
- Q(s, a) ← Q(s, a) + alpha × (target - Q(s, a))
Partez de toutes les valeurs Q à 0 et appliquez les transitions dans l'ordre.
Implémentez q_learning(num_states, num_actions, transitions, alpha, gamma).
Entrée
num_states, num_actions : La taille de la table.
transitions : Une ligne [state, action, reward, next_state, done] par pas.
alpha : Le taux d'apprentissage.
gamma : Le facteur d'actualisation.
Sortie
Renvoyez la table Q sous forme de matrice avec une ligne par état et une colonne par action.
Contraintes
1 ≤ num_states, num_actions ≤ 100, 0 ≤ nombre de transitions ≤ 10 000
-100 ≤ reward ≤ 100, done vaut 0 ou 1
0 < alpha ≤ 1, 0 ≤ gamma ≤ 1
Exemples
Entrée :
alpha = 0.5
gamma = 0.9
num_states = 2
num_actions = 2
transitions = [
[0, 1, 0, 1, 0],
[1, 0, 10, 0, 1]
]
Sortie attendue :
expected = [
[0.0, 0.0],
[5.0, 0.0]
]Entrée :
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}
};
Sortie attendue :
std::vector<std::vector<double>> expected = {
{0.0, 0.0},
{5.0, 0.0}
};Entrée :
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}
};
Sortie attendue :
double[][] expected = new double[][] {
new double[] {0.0, 0.0},
new double[] {5.0, 0.0}
};Explication
Le premier pas ne trouve encore aucune récompense : target = 0 + 0.9 × max(Q[1]) = 0, donc Q[0][1] reste à 0. Le deuxième pas termine l'épisode avec une récompense de 10 : Q[1][0] = 0 + 0.5 × (10 - 0) = 5.
Entrée :
alpha = 0.5
gamma = 0.9
num_states = 2
num_actions = 2
transitions = [
[1, 0, 10, 0, 1],
[0, 1, 0, 1, 0]
]
Sortie attendue :
expected = [
[0.0, 2.25],
[5.0, 0.0]
]Entrée :
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}
};
Sortie attendue :
std::vector<std::vector<double>> expected = {
{0.0, 2.25},
{5.0, 0.0}
};Entrée :
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}
};
Sortie attendue :
double[][] expected = new double[][] {
new double[] {0.0, 2.25},
new double[] {5.0, 0.0}
};Explication
Les mêmes pas dans l'ordre inverse. Q[1][0] passe d'abord à 5, donc le pas depuis l'état 0 le voit : target = 0 + 0.9 × 5 = 4.5 et Q[0][1] = 0.5 × 4.5 = 2.25. La récompense a remonté d'un état.
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.