โจทย์
Q-learning เรียนรู้ว่าแต่ละการกระทำดีแค่ไหนในแต่ละสถานะ หรือ Q(s, a) จากประสบการณ์เพียงอย่างเดียว หลังจากทำการกระทำ a ในสถานะ s ได้รับ reward และไปถึงสถานะ s':
- target = reward ถ้า episode จบแล้ว (
done= 1) - target = reward + gamma × ค่าสูงสุดเหนือ a' ของ Q(s', a') ในกรณีอื่น
- Q(s, a) ← Q(s, a) + alpha × (target - Q(s, a))
เริ่มด้วยค่า Q ทุกตัวเป็น 0 แล้วใช้การเปลี่ยนสถานะตามลำดับ
จง implement q_learning(num_states, num_actions, transitions, alpha, gamma)
อินพุต
num_states, num_actions: ขนาดของตาราง
transitions: หนึ่งแถว [state, action, reward, next_state, done] ต่อหนึ่งก้าว
alpha: อัตราการเรียนรู้
gamma: ตัวประกอบส่วนลด
เอาต์พุต
คืนตาราง Q เป็นเมทริกซ์ที่มีหนึ่งแถวต่อสถานะและหนึ่งคอลัมน์ต่อการกระทำ
เงื่อนไข
1 ≤ num_states, num_actions ≤ 100, 0 ≤ จำนวนการเปลี่ยนสถานะ ≤ 10,000
-100 ≤ reward ≤ 100, done เป็น 0 หรือ 1
0 < alpha ≤ 1, 0 ≤ gamma ≤ 1
ตัวอย่าง
อินพุต:
alpha = 0.5
gamma = 0.9
num_states = 2
num_actions = 2
transitions = [
[0, 1, 0, 1, 0],
[1, 0, 10, 0, 1]
]
ผลลัพธ์ที่คาดหวัง:
expected = [
[0.0, 0.0],
[5.0, 0.0]
]อินพุต:
double alpha = 0.5;
double gamma = 0.9;
long long num_states = 2;
long long num_actions = 2;
std::vector<std::vector<long long>> transitions = {
{0, 1, 0, 1, 0},
{1, 0, 10, 0, 1}
};
ผลลัพธ์ที่คาดหวัง:
std::vector<std::vector<double>> expected = {
{0.0, 0.0},
{5.0, 0.0}
};อินพุต:
double alpha = 0.5;
double gamma = 0.9;
long num_states = 2;
long num_actions = 2;
long[][] transitions = new long[][] {
new long[] {0, 1, 0, 1, 0},
new long[] {1, 0, 10, 0, 1}
};
ผลลัพธ์ที่คาดหวัง:
double[][] expected = new double[][] {
new double[] {0.0, 0.0},
new double[] {5.0, 0.0}
};คำอธิบาย
ก้าวแรกยังไม่พบรางวัล: target = 0 + 0.9 × max(Q[1]) = 0 ดังนั้น Q[0][1] ยังเป็น 0 ก้าวที่สองจบ episode ด้วยรางวัล 10: Q[1][0] = 0 + 0.5 × (10 - 0) = 5
อินพุต:
alpha = 0.5
gamma = 0.9
num_states = 2
num_actions = 2
transitions = [
[1, 0, 10, 0, 1],
[0, 1, 0, 1, 0]
]
ผลลัพธ์ที่คาดหวัง:
expected = [
[0.0, 2.25],
[5.0, 0.0]
]อินพุต:
double alpha = 0.5;
double gamma = 0.9;
long long num_states = 2;
long long num_actions = 2;
std::vector<std::vector<long long>> transitions = {
{1, 0, 10, 0, 1},
{0, 1, 0, 1, 0}
};
ผลลัพธ์ที่คาดหวัง:
std::vector<std::vector<double>> expected = {
{0.0, 2.25},
{5.0, 0.0}
};อินพุต:
double alpha = 0.5;
double gamma = 0.9;
long num_states = 2;
long num_actions = 2;
long[][] transitions = new long[][] {
new long[] {1, 0, 10, 0, 1},
new long[] {0, 1, 0, 1, 0}
};
ผลลัพธ์ที่คาดหวัง:
double[][] expected = new double[][] {
new double[] {0.0, 2.25},
new double[] {5.0, 0.0}
};คำอธิบาย
ก้าวเดิมแต่สลับลำดับ Q[1][0] กลายเป็น 5 ก่อน ก้าวจากสถานะ 0 จึงเห็นค่านี้: target = 0 + 0.9 × 5 = 4.5 และ Q[0][1] = 0.5 × 4.5 = 2.25 รางวัลไหลย้อนกลับไปหนึ่งสถานะ
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
แต่ละ transition อัปเดต table entry เดียว โดยใช้แค่ค่าปัจจุบันกับ best estimate จาก state ถัดไป
คำใบ้ 2
ตั้งค่า Q table เริ่มต้นเป็นศูนย์ แล้วประมวลผล transitions ตามลำดับและอัปเดตทันทีหลังแต่ละครั้ง
คำใบ้ 3
ถ้า episode จบลง จะไม่มี future value ให้บวก และไม่ควรใช้ next-state maximum
ความซับซ้อนที่คาดหวัง
เวลา O(T * A), หน่วยความจำเพิ่ม O(S * A)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน