Problema
Un bandido multibrazo es una fila de máquinas tragaperras (brazos) con pagos desconocidos. Epsilon-greedy equilibra explorar y explotar: con probabilidad epsilon tira de un brazo al azar y, si no, tira del brazo con el valor estimado más alto.
Para que la ejecución se pueda probar, los números aleatorios se proporcionan. Empieza con una estimación Q = 0 y un contador N = 0 para cada brazo. En cada paso t:
- Si
random_values[t]< epsilon, explora: arm =random_arms[t]. Si no, explota: arm = el brazo con el Q más alto (el índice menor si hay empate). - Recibe reward =
rewards[t][arm]. - N[arm] ← N[arm] + 1 y Q[arm] ← Q[arm] + (reward - Q[arm]) / N[arm], la media acumulada.
Implementa epsilon_greedy(rewards, epsilon, random_values, random_arms).
Entrada
rewards: Una fila por paso con la recompensa que pagaría cada brazo en ese paso.
epsilon: La probabilidad de exploración.
random_values: Un número aleatorio en [0, 1) por paso.
random_arms: El brazo del que tirar en cada paso si se explora.
Salida
Devuelve las estimaciones Q finales, una por brazo.
Restricciones
1 ≤ pasos ≤ 10.000, 1 ≤ brazos ≤ 100
0 ≤ epsilon ≤ 1, -100 ≤ cada recompensa ≤ 100
Ejemplos
Entrada:
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]
Salida esperada:
expected = [1.0, 3.0]Entrada:
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};
Salida esperada:
std::vector<double> expected = {1.0, 3.0};Entrada:
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};
Salida esperada:
double[] expected = new double[] {1.0, 3.0};Explicación
El paso 0 explota; ambos Q son 0, así que se tira del brazo 0 y Q = [1, 0]. El paso 1 explora (0.05 < 0.1) y prueba el brazo 1: Q = [1, 3]. Los pasos 2 y 3 explotan el brazo 1, que es mejor. Resultado: [1, 3].
Entrada:
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]
Salida esperada:
expected = [2.0, 0.0]Entrada:
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};
Salida esperada:
std::vector<double> expected = {2.0, 0.0};Entrada:
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};
Salida esperada:
double[] expected = new double[] {2.0, 0.0};Explicación
Con epsilon = 0 el agente nunca explora. Sigue tirando del brazo 0, cuya media va 2 → 3 → 2, y nunca descubre que el brazo 1 paga 5. Resultado: [2, 0].
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
En cada paso, elige entre el brazo aleatorio forzado o el brazo actualmente mejor estimado.
Pista 2
Actualiza el valor de cada brazo con un promedio acumulado para que las recompensas antiguas pesen menos a medida que se acumulan más tiradas.
Pista 3
Desempata eligiendo el brazo de menor índice, y recuerda que solo cambia el brazo elegido en cada paso.
Complejidad esperada
O(steps * arms) tiempo, O(arms) espacio extra
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.