โจทย์
Value iteration แก้กระบวนการตัดสินใจแบบมาร์คอฟ: มันหา V(s) ซึ่งคือผลรวมรางวัลแบบมีส่วนลดที่ดีที่สุดที่เก็บได้เมื่อเริ่มจากสถานะ s
ในที่นี้การเปลี่ยนสถานะเป็นแบบกำหนดได้ ในสถานะ s การกระทำ a ให้รางวัล rewards[s][a] และย้ายไปสถานะ next_states[s][a] โดย -1 หมายถึง episode จบ เริ่มด้วย V(s) = 0 สำหรับทุกสถานะ แล้วทำซ้ำ iterations ครั้ง โดยคำนวณค่าใหม่ทุกค่าจากรอบกวาดก่อนหน้า:
V_new(s) = ค่าสูงสุดเหนือ a ของ ( rewards[s][a] + gamma × V(next_states[s][a]) )
โดยพจน์ gamma × V เป็น 0 เมื่อสถานะถัดไปคือ -1
จง implement value_iteration(next_states, rewards, gamma, iterations)
อินพุต
next_states: สำหรับแต่ละสถานะ คือสถานะถัดไปของแต่ละการกระทำ (-1 จบ episode) แต่ละสถานะอาจมีจำนวนการกระทำไม่เท่ากัน
rewards: รางวัลของแต่ละการกระทำ มีรูปร่างเดียวกับ next_states
gamma: ตัวประกอบส่วนลด
iterations: จำนวนรอบกวาด
เอาต์พุต
คืน V หลังรอบกวาดสุดท้าย หนึ่งค่าต่อสถานะ
เงื่อนไข
1 ≤ จำนวนสถานะ ≤ 200, 1 ≤ จำนวนการกระทำต่อสถานะ ≤ 10, 0 ≤ iterations ≤ 1,000
-100 ≤ แต่ละรางวัล ≤ 100, 0 ≤ gamma ≤ 1
ตัวอย่าง
อินพุต:
gamma = 0.9
rewards = [
[0.0, 0.0],
[0.0, 0.0],
[10.0]
]
iterations = 3
next_states = [
[0, 1],
[0, 2],
[-1]
]
ผลลัพธ์ที่คาดหวัง:
expected = [8.1, 9.0, 10.0]อินพุต:
double gamma = 0.9;
std::vector<std::vector<double>> rewards = {
{0.0, 0.0},
{0.0, 0.0},
{10.0}
};
long long iterations = 3;
std::vector<std::vector<long long>> next_states = {
{0, 1},
{0, 2},
{-1}
};
ผลลัพธ์ที่คาดหวัง:
std::vector<double> expected = {8.1, 9.0, 10.0};อินพุต:
double gamma = 0.9;
double[][] rewards = new double[][] {
new double[] {0.0, 0.0},
new double[] {0.0, 0.0},
new double[] {10.0}
};
long iterations = 3;
long[][] next_states = new long[][] {
new long[] {0, 1},
new long[] {0, 2},
new long[] {-1}
};
ผลลัพธ์ที่คาดหวัง:
double[] expected = new double[] {8.1, 9.0, 10.0};คำอธิบาย
รอบ 1: มีแค่สถานะ 2 ที่ได้รางวัล V = [0, 0, 10] รอบ 2: สถานะ 1 เดินขวาไปหามัน 0.9 × 10 = 9, V = [0, 9, 10] รอบ 3: สถานะ 0 ได้ 0.9 × 9 = 8.1 ผลลัพธ์: [8.1, 9, 10]
อินพุต:
gamma = 0.0
rewards = [
[1.0, 2.0],
[3.0, 0.0]
]
iterations = 5
next_states = [
[1, 0],
[0, 1]
]
ผลลัพธ์ที่คาดหวัง:
expected = [2.0, 3.0]อินพุต:
double gamma = 0.0;
std::vector<std::vector<double>> rewards = {
{1.0, 2.0},
{3.0, 0.0}
};
long long iterations = 5;
std::vector<std::vector<long long>> next_states = {
{1, 0},
{0, 1}
};
ผลลัพธ์ที่คาดหวัง:
std::vector<double> expected = {2.0, 3.0};อินพุต:
double gamma = 0.0;
double[][] rewards = new double[][] {
new double[] {1.0, 2.0},
new double[] {3.0, 0.0}
};
long iterations = 5;
long[][] next_states = new long[][] {
new long[] {1, 0},
new long[] {0, 1}
};
ผลลัพธ์ที่คาดหวัง:
double[] expected = new double[] {2.0, 3.0};คำอธิบาย
เมื่อ gamma = 0 อนาคตไม่ถูกนับ ค่าของแต่ละสถานะจึงเป็นแค่รางวัลทันทีที่ดีที่สุดของมัน: [2, 3]
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
แต่ละ sweep ใช้เฉพาะค่าจาก sweep ก่อนหน้า ไม่ใช่ค่าที่อัปเดตไปแล้วในรอบเดียวกัน
คำใบ้ 2
สำหรับแต่ละ state ให้เปรียบเทียบทุก action โดยรวม immediate reward กับ discounted value ของ next state
คำใบ้ 3
จัดการ terminal actions ให้ดี: ถ้า next state ไม่มี ให้คิดแค่ immediate reward
ความซับซ้อนที่คาดหวัง
เวลา O(iterations * total_actions), หน่วยความจำเพิ่ม O(states)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน