โจทย์
A multi-armed bandit is a row of slot machines (arms) with unknown payouts. Epsilon-greedy balances exploring and exploiting: with probability epsilon it pulls a random arm, otherwise it pulls the arm with the highest estimated value.
To make the run testable, the random numbers are given. Start with an estimate Q = 0 and a count N = 0 for every arm. At each step t:
- If
random_values[t]< epsilon, explore: arm =random_arms[t]. Otherwise exploit: arm = the arm with the highest Q (the lowest index if several tie). - Receive reward =
rewards[t][arm]. - N[arm] ← N[arm] + 1 and Q[arm] ← Q[arm] + (reward - Q[arm]) / N[arm], the running average.
Implement epsilon_greedy(rewards, epsilon, random_values, random_arms).
Input
rewards: One row per step with the reward each arm would pay at that step.
epsilon: The exploration probability.
random_values: One random number in [0, 1) per step.
random_arms: The arm to pull at each step if exploring.
Output
Return the final Q estimates, one per arm.
เงื่อนไข
1 ≤ steps ≤ 10,000, 1 ≤ arms ≤ 100
0 ≤ epsilon ≤ 1, -100 ≤ each reward ≤ 100
ตัวอย่าง
อินพุต:
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]
ผลลัพธ์ที่คาดหวัง:
expected = [1.0, 3.0]อินพุต:
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};
ผลลัพธ์ที่คาดหวัง:
std::vector<double> expected = {1.0, 3.0};อินพุต:
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};
ผลลัพธ์ที่คาดหวัง:
double[] expected = new double[] {1.0, 3.0};คำอธิบาย
Step 0 exploits; both Q are 0, so arm 0 is pulled and Q = [1, 0]. Step 1 explores (0.05 < 0.1) and tries arm 1: Q = [1, 3]. Steps 2 and 3 exploit the better arm 1. Result: [1, 3].
อินพุต:
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]
ผลลัพธ์ที่คาดหวัง:
expected = [2.0, 0.0]อินพุต:
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};
ผลลัพธ์ที่คาดหวัง:
std::vector<double> expected = {2.0, 0.0};อินพุต:
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};
ผลลัพธ์ที่คาดหวัง:
double[] expected = new double[] {2.0, 0.0};คำอธิบาย
With epsilon = 0 the agent never explores. It keeps pulling arm 0, whose average goes 2 → 3 → 2, and never finds out arm 1 pays 5. Result: [2, 0].
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน