Problème
Un bandit multi-bras est une rangée de machines à sous (bras) aux gains inconnus. Epsilon-greedy équilibre exploration et exploitation : avec la probabilité epsilon, il tire un bras au hasard, sinon il tire le bras à la plus haute valeur estimée.
Pour rendre l'exécution testable, les nombres aléatoires sont fournis. Partez d'une estimation Q = 0 et d'un compteur N = 0 pour chaque bras. À chaque pas t :
- Si
random_values[t]< epsilon, explorez : arm =random_arms[t]. Sinon exploitez : arm = le bras au Q le plus élevé (le plus petit indice en cas d'égalité). - Recevez reward =
rewards[t][arm]. - N[arm] ← N[arm] + 1 et Q[arm] ← Q[arm] + (reward - Q[arm]) / N[arm], la moyenne courante.
Implémentez epsilon_greedy(rewards, epsilon, random_values, random_arms).
Entrée
rewards : Une ligne par pas avec la récompense que chaque bras paierait à ce pas.
epsilon : La probabilité d'exploration.
random_values : Un nombre aléatoire dans [0, 1) par pas.
random_arms : Le bras à tirer à chaque pas en cas d'exploration.
Sortie
Renvoyez les estimations Q finales, une par bras.
Contraintes
1 ≤ pas ≤ 10 000, 1 ≤ bras ≤ 100
0 ≤ epsilon ≤ 1, -100 ≤ chaque récompense ≤ 100
Exemples
Entrée :
epsilon = 0.1
rewards = [
[1.0, 3.0],
[1.0, 3.0],
[1.0, 3.0],
[1.0, 3.0]
]
random_arms = [0, 1, 0, 0]
random_values = [0.5, 0.05, 0.7, 0.9]
Sortie attendue :
expected = [1.0, 3.0]Entrée :
double epsilon = 0.1;
std::vector<std::vector<double>> rewards = {
{1.0, 3.0},
{1.0, 3.0},
{1.0, 3.0},
{1.0, 3.0}
};
std::vector<long long> random_arms = {0, 1, 0, 0};
std::vector<double> random_values = {0.5, 0.05, 0.7, 0.9};
Sortie attendue :
std::vector<double> expected = {1.0, 3.0};Entrée :
double epsilon = 0.1;
double[][] rewards = new double[][] {
new double[] {1.0, 3.0},
new double[] {1.0, 3.0},
new double[] {1.0, 3.0},
new double[] {1.0, 3.0}
};
long[] random_arms = new long[] {0, 1, 0, 0};
double[] random_values = new double[] {0.5, 0.05, 0.7, 0.9};
Sortie attendue :
double[] expected = new double[] {1.0, 3.0};Explication
Le pas 0 exploite ; les deux Q valent 0, donc le bras 0 est tiré et Q = [1, 0]. Le pas 1 explore (0.05 < 0.1) et essaie le bras 1 : Q = [1, 3]. Les pas 2 et 3 exploitent le meilleur bras, le 1. Résultat : [1, 3].
Entrée :
epsilon = 0.0
rewards = [
[2.0, 5.0],
[4.0, 5.0],
[0.0, 5.0]
]
random_arms = [1, 1, 1]
random_values = [0.5, 0.5, 0.5]
Sortie attendue :
expected = [2.0, 0.0]Entrée :
double epsilon = 0.0;
std::vector<std::vector<double>> rewards = {
{2.0, 5.0},
{4.0, 5.0},
{0.0, 5.0}
};
std::vector<long long> random_arms = {1, 1, 1};
std::vector<double> random_values = {0.5, 0.5, 0.5};
Sortie attendue :
std::vector<double> expected = {2.0, 0.0};Entrée :
double epsilon = 0.0;
double[][] rewards = new double[][] {
new double[] {2.0, 5.0},
new double[] {4.0, 5.0},
new double[] {0.0, 5.0}
};
long[] random_arms = new long[] {1, 1, 1};
double[] random_values = new double[] {0.5, 0.5, 0.5};
Sortie attendue :
double[] expected = new double[] {2.0, 0.0};Explication
Avec epsilon = 0, l'agent n'explore jamais. Il tire sans cesse le bras 0, dont la moyenne passe de 2 → 3 → 2, et ne découvre jamais que le bras 1 paie 5. Résultat : [2, 0].
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.