Problema
Un bandito multi-braccio è una fila di slot machine (bracci) con vincite sconosciute. Epsilon-greedy bilancia esplorazione e sfruttamento: con probabilità epsilon tira un braccio a caso, altrimenti tira il braccio con il valore stimato più alto.
Per rendere l'esecuzione verificabile, i numeri casuali vengono forniti. Parti con una stima Q = 0 e un contatore N = 0 per ogni braccio. A ogni passo t:
- Se
random_values[t]< epsilon, esplora: arm =random_arms[t]. Altrimenti sfrutta: arm = il braccio con il Q più alto (l'indice minore in caso di parità). - Ricevi reward =
rewards[t][arm]. - N[arm] ← N[arm] + 1 e Q[arm] ← Q[arm] + (reward - Q[arm]) / N[arm], la media progressiva.
Implementa epsilon_greedy(rewards, epsilon, random_values, random_arms).
Input
rewards: Una riga per passo con la ricompensa che ogni braccio pagherebbe in quel passo.
epsilon: La probabilità di esplorazione.
random_values: Un numero casuale in [0, 1) per passo.
random_arms: Il braccio da tirare a ogni passo in caso di esplorazione.
Output
Restituisci le stime Q finali, una per braccio.
Vincoli
1 ≤ passi ≤ 10.000, 1 ≤ bracci ≤ 100
0 ≤ epsilon ≤ 1, -100 ≤ ogni ricompensa ≤ 100
Esempi
Input:
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]
Output atteso:
expected = [1.0, 3.0]Input:
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};
Output atteso:
std::vector<double> expected = {1.0, 3.0};Input:
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};
Output atteso:
double[] expected = new double[] {1.0, 3.0};Spiegazione
Il passo 0 sfrutta; entrambi i Q sono 0, quindi si tira il braccio 0 e Q = [1, 0]. Il passo 1 esplora (0.05 < 0.1) e prova il braccio 1: Q = [1, 3]. I passi 2 e 3 sfruttano il braccio migliore, l'1. Risultato: [1, 3].
Input:
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]
Output atteso:
expected = [2.0, 0.0]Input:
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};
Output atteso:
std::vector<double> expected = {2.0, 0.0};Input:
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};
Output atteso:
double[] expected = new double[] {2.0, 0.0};Spiegazione
Con epsilon = 0 l'agente non esplora mai. Continua a tirare il braccio 0, la cui media va 2 → 3 → 2, e non scopre mai che il braccio 1 paga 5. Risultato: [2, 0].
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
A ogni passo, scegli oppure il braccio casuale forzato oppure il braccio attualmente migliore stimato.
Suggerimento 2
Aggiorna il valore di ogni braccio con una media mobile, così i reward vecchi contano meno man mano che aumentano le estrazioni.
Suggerimento 3
Risolvi i pareggi scegliendo il braccio con indice più piccolo, e ricorda che ogni passo cambia solo il braccio scelto.
Complessità attesa
tempo O(steps * arms), spazio aggiuntivo O(arms)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.