Problema
Um bandido multibraço é uma fileira de caça-níqueis (braços) com pagamentos desconhecidos. O epsilon-greedy equilibra explorar e aproveitar: com probabilidade epsilon ele puxa um braço aleatório; caso contrário, puxa o braço com o maior valor estimado.
Para que a execução possa ser testada, os números aleatórios são fornecidos. Comece com uma estimativa Q = 0 e um contador N = 0 para cada braço. Em cada passo t:
- Se
random_values[t]< epsilon, explore: arm =random_arms[t]. Caso contrário, aproveite: arm = o braço com o maior Q (o menor índice em caso de empate). - Receba reward =
rewards[t][arm]. - N[arm] ← N[arm] + 1 e Q[arm] ← Q[arm] + (reward - Q[arm]) / N[arm], a média acumulada.
Implemente epsilon_greedy(rewards, epsilon, random_values, random_arms).
Entrada
rewards: Uma linha por passo com a recompensa que cada braço pagaria naquele passo.
epsilon: A probabilidade de exploração.
random_values: Um número aleatório em [0, 1) por passo.
random_arms: O braço a puxar em cada passo se for explorar.
Saída
Retorne as estimativas Q finais, uma por braço.
Restrições
1 ≤ passos ≤ 10.000, 1 ≤ braços ≤ 100
0 ≤ epsilon ≤ 1, -100 ≤ cada recompensa ≤ 100
Exemplos
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]
Saída 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};
Saída 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};
Saída esperada:
double[] expected = new double[] {1.0, 3.0};Explicação
O passo 0 aproveita; os dois Q são 0, então o braço 0 é puxado e Q = [1, 0]. O passo 1 explora (0.05 < 0.1) e testa o braço 1: Q = [1, 3]. Os passos 2 e 3 aproveitam o braço 1, que é melhor. 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]
Saída 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};
Saída 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};
Saída esperada:
double[] expected = new double[] {2.0, 0.0};Explicação
Com epsilon = 0 o agente nunca explora. Ele continua puxando o braço 0, cuja média vai 2 → 3 → 2, e nunca descobre que o braço 1 paga 5. Resultado: [2, 0].
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
A cada passo, escolha o braço aleatório forçado ou o braço atualmente estimado como melhor.
Dica 2
Atualize o valor de cada braço com uma média móvel, para que recompensas antigas valham menos conforme mais pulls se acumulam.
Dica 3
Quebre empates escolhendo o braço de menor índice, e lembre que só o braço escolhido muda em cada passo.
Complexidade esperada
tempo O(steps * arms), espaço extra O(arms)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.