โจทย์
Multi-armed bandit คือแถวของตู้สล็อต (แขน) ที่ไม่รู้ว่าจ่ายเท่าไร Epsilon-greedy สร้างสมดุลระหว่างการสำรวจและการใช้ประโยชน์: ด้วยความน่าจะเป็น epsilon จะดึงแขนแบบสุ่ม มิฉะนั้นจะดึงแขนที่มีค่าประมาณสูงที่สุด
เพื่อให้ทดสอบได้ จึงกำหนดตัวเลขสุ่มมาให้ เริ่มด้วยค่าประมาณ Q = 0 และตัวนับ N = 0 สำหรับทุกแขน ในแต่ละก้าว t:
- ถ้า
random_values[t]< epsilon ให้สำรวจ: arm =random_arms[t]มิฉะนั้นใช้ประโยชน์: arm = แขนที่มี Q สูงที่สุด (index น้อยที่สุดถ้าเท่ากัน) - รับ reward =
rewards[t][arm] - N[arm] ← N[arm] + 1 และ Q[arm] ← Q[arm] + (reward - Q[arm]) / N[arm] ซึ่งคือค่าเฉลี่ยสะสม
จง implement epsilon_greedy(rewards, epsilon, random_values, random_arms)
อินพุต
rewards: หนึ่งแถวต่อก้าว เป็นรางวัลที่แต่ละแขนจะจ่ายในก้าวนั้น
epsilon: ความน่าจะเป็นของการสำรวจ
random_values: ตัวเลขสุ่มใน [0, 1) หนึ่งค่าต่อก้าว
random_arms: แขนที่จะดึงในแต่ละก้าวถ้าสำรวจ
เอาต์พุต
คืนค่าประมาณ Q สุดท้าย หนึ่งค่าต่อแขน
เงื่อนไข
1 ≤ จำนวนก้าว ≤ 10,000, 1 ≤ จำนวนแขน ≤ 100
0 ≤ epsilon ≤ 1, -100 ≤ แต่ละรางวัล ≤ 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};คำอธิบาย
ก้าว 0 ใช้ประโยชน์ Q ทั้งสองเป็น 0 จึงดึงแขน 0 ได้ Q = [1, 0] ก้าว 1 สำรวจ (0.05 < 0.1) และลองแขน 1: Q = [1, 3] ก้าว 2 และ 3 ใช้ประโยชน์จากแขน 1 ซึ่งดีกว่า ผลลัพธ์: [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};คำอธิบาย
เมื่อ epsilon = 0 เอเจนต์ไม่เคยสำรวจ มันดึงแขน 0 ไปเรื่อย ๆ ค่าเฉลี่ยเปลี่ยน 2 → 3 → 2 และไม่เคยรู้ว่าแขน 1 จ่าย 5 ผลลัพธ์: [2, 0]
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน