Stochastic Dynamic Programming — การตัดสินใจตามลำดับภายใต้ความไม่แน่นอน
- ผู้เสนอ
- Bellman, R.; formalized for stochastic settings by Puterman, M. L.
- ปี
- 1957
- ประเภท
- Sequential optimization under uncertainty
- กลุ่มวิธี
- Simulation / optimization
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
Stochastic Dynamic Programming (SDP) หรือ การโปรแกรมพลวัตเชิงสุ่ม เป็นกรอบการหาค่าเหมาะที่สุดเชิงคณิตศาสตร์สำหรับปัญหาการตัดสินใจตามลำดับ ซึ่งผลลัพธ์มีความสุ่มบางส่วน โดยเป็นการขยายหลักการของ Bellman เกี่ยวกับความเหมาะสมที่สุดไปยังสภาพแวดล้อมที่มีความสุ่ม โดยแสดงปัญหาในรูปของกระบวนการตัดสินใจแบบมาร์คอฟ (Markov Decision Processes - MDPs) และคำนวณนโยบายที่เหมาะสมที่สุดโดยการแก้สมการค่าเวียนเกิด (recursive value equations) ผ่านสถานะและช่วงเวลา
แนวคิดเบื้องหลังวิธีการ
ลองนึกภาพการจัดการอ่างเก็บน้ำหลายเดือน โดยแต่ละเดือนคุณต้องตัดสินใจว่าจะปล่อยน้ำปริมาณเท่าใด แต่ปริมาณน้ำฝนนั้นไม่แน่นอน SDP จะแบ่งปัญหานี้ออกเป็นชุดของการตัดสินใจในแต่ละช่วงเวลา และตั้งคำถามว่า: เมื่อพิจารณาจากระดับน้ำปัจจุบันและอนาคตที่เป็นไปได้ทั้งหมด นโยบายการปล่อยน้ำแบบใดที่จะให้ผลประโยชน์รวมที่คาดหวังสูงสุด? โดยการทำงานย้อนกลับจากช่วงเวลาสุดท้าย (หรือการวนซ้ำจนได้ค่าคงที่) SDP จะค้นพบการกระทำที่เหมาะสมที่สุดในระดับสากลสำหรับทุกสถานะที่เป็นไปได้ แม้กระทั่งก่อนที่ความไม่แน่นอนจะคลี่คลาย ประเด็นสำคัญคือ มูลค่าในอนาคตของการอยู่ในสถานะหนึ่งๆ นั้นไม่ขึ้นอยู่กับว่าคุณมาถึงสถานะนั้นได้อย่างไร (คุณสมบัติมาร์คอฟ) ซึ่งทำให้การคำนวณแบบเวียนเกิดสามารถจัดการได้
ประวัติศาสตร์
Richard Bellman ได้นำเสนอ dynamic programming ในหนังสือปี 1957 ของเขา โดยได้วางรากฐานหลักการของความเหมาะสมที่สุด (principle of optimality) ซึ่งเป็นพื้นฐานของทั้ง DP แบบกำหนดและแบบสุ่ม รูปแบบกระบวนการตัดสินใจแบบมาร์คอฟที่มีความสุ่มได้รับการพัฒนาอย่างเป็นระบบในช่วงทศวรรษ 1960–1970 และได้รับการรวบรวมอย่างครอบคลุมโดย Martin Puterman ในตำราของเขาปี 1994 ซึ่งยังคงเป็นเอกสารอ้างอิงมาตรฐานสำหรับทฤษฎี SDP ทั้งแบบมีขอบเขตจำกัดและอนันต์
ควรใช้เมื่อใด
ใช้ SDP เมื่อการตัดสินใจเกิดขึ้นตามลำดับตามเวลาหรือขั้นตอน ผลลัพธ์ขึ้นอยู่กับการเปลี่ยนสถานะแบบสุ่มที่สอดคล้องกับคุณสมบัติมาร์คอฟ และมีแบบจำลองความน่าจะเป็นที่สมบูรณ์สำหรับการเปลี่ยนสถานะเหล่านั้น หรือสามารถประมาณค่าได้ ตัวอย่างทั่วไป: การจัดสรรทรัพยากรภายใต้ความไม่แน่นอนของอุปสงค์, การควบคุมสินค้าคงคลัง, การเปลี่ยนอุปกรณ์, การวางแผนการรักษาโดยคำนึงถึงการตอบสนองของผู้ป่วยที่ไม่แน่นอน, หรือการจัดส่งระบบพลังงาน **ห้ามใช้** เมื่อปริภูมิสถานะใหญ่เกินไปที่จะแจกแจงได้ทั้งหมด (คำสาปของมิติทำให้ SDP ที่แม่นยำไม่สามารถคำนวณได้หากไม่มีการประมาณค่า), เมื่อความน่าจะเป็นของการเปลี่ยนสถานะไม่ทราบและไม่สามารถสร้างแบบจำลองได้ (พิจารณาการเรียนรู้แบบเสริมกำลังแทน), เมื่อการตัดสินใจเป็นแบบครั้งเดียวโดยไม่มีโครงสร้างตามลำดับ (ใช้การหาค่าเหมาะที่สุดแบบสถิต), หรือเมื่อข้อสมมติฐานมาร์คอฟถูกละเมิดเนื่องจากมีการพึ่งพาประวัติที่แข็งแกร่ง
ข้อจำกัดและข้อควรพิจารณา
- ประสบปัญหาจากคำสาปของมิติ: ข้อกำหนดด้านการคำนวณและหน่วยความจำเพิ่มขึ้นแบบทวีคูณตามจำนวนตัวแปรสถานะ
- จำเป็นต้องระบุความน่าจะเป็นของการเปลี่ยนสถานะอย่างชัดเจน ซึ่งอาจไม่ทราบหรือไม่สามารถประมาณค่าได้โดยง่าย
- วิธีการที่แม่นยำจำกัดอยู่เฉพาะปริภูมิสถานะและการกระทำแบบไม่ต่อเนื่อง (หรือที่ถูกแบ่งเป็นช่วงๆ); ปริภูมิแบบต่อเนื่องต้องการการประมาณค่า
- ตั้งสมมติฐานคุณสมบัติมาร์คอฟ; ระบบที่มีหน่วยความจำยาวนานหรือการสังเกตบางส่วนต้องการการขยายที่ซับซ้อนกว่า (POMDPs)
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- รับประกันนโยบายที่เหมาะสมที่สุดในระดับสากลสำหรับ MDPs ที่มีขอบเขตจำกัดหรือมีขอบเขตอนันต์และมีการลดทอนค่าที่กำหนดไว้อย่างดี
- จัดการกับความไม่แน่นอนหลายขั้นตอนได้อย่างเป็นธรรมชาติ โดยการเข้ารหัสอนาคตที่เป็นไปได้ทั้งหมดในฟังก์ชันค่า
- โครงสร้างแบบมาร์คอฟช่วยลดปริภูมิการค้นหาได้อย่างมากเมื่อเทียบกับการมองไปข้างหน้าทั้งหมด
- อัลกอริทึม policy iteration และ value iteration เป็นที่เข้าใจกันดีพร้อมการรับประกันการลู่เข้าที่พิสูจน์แล้ว
- ขยายไปยังเกณฑ์ที่ไวต่อความเสี่ยง (CVaR, ความแปรปรวนของค่าเฉลี่ย) และ MDPs ที่มีข้อจำกัด โดยไม่ต้องเปลี่ยนแปลงกระบวนการพื้นฐาน
การประยุกต์ใช้
- การจัดการสินค้าคงคลัง: การหาปริมาณการสั่งซื้อที่ลดต้นทุนรวมที่คาดหวังภายใต้ความต้องการแบบสุ่มในช่วงหลายงวด
- การวางแผนทรัพยากรน้ำ: การจัดตารางการปล่อยน้ำจากอ่างเก็บน้ำภายใต้ปริมาณน้ำไหลเข้าที่ไม่แน่นอน เพื่อสร้างสมดุลระหว่างการผลิตไฟฟ้าพลังน้ำและความเสี่ยงน้ำท่วม
- การวางแผนการรักษาพยาบาล: การเลือกชุดการรักษาผู้ป่วยโดยพิจารณาจากความน่าจะเป็นของการดำเนินโรคที่ไม่แน่นอน
- ระบบพลังงาน: กลยุทธ์การจัดส่งและการชาร์จแบตเตอรี่ที่เหมาะสมที่สุดภายใต้การผลิตพลังงานหมุนเวียนและราคาไฟฟ้าที่ไม่แน่นอน
- การเงิน: การปรับสมดุลพอร์ตโฟลิโอและการกำหนดราคาออปชันภายใต้พลวัตราคาของสินทรัพย์แบบสุ่ม
- การจัดตารางการบำรุงรักษา: การกำหนดนโยบายการตรวจสอบและการเปลี่ยนเพื่อลดต้นทุนตลอดอายุการใช้งานที่คาดหวังของอุปกรณ์ภายใต้ความล้มเหลวแบบสุ่ม
วิธีการทำงาน
วิธีการทำงาน
กำหนด tuple ของ MDP (S, A, P, R, gamma): ปริภูมิสถานะ S ที่ครอบคลุมการกำหนดค่าระบบที่เกี่ยวข้องทั้งหมด, ปริภูมิการกระทำ A(s) ของการตัดสินใจที่อนุญาตในแต่ละสถานะ, ความน่าจะเป็นของการเปลี่ยนสถานะ P(s'|s,a) ที่อธิบายว่าระบบมีวิวัฒนาการแบบสุ่มภายใต้การกระทำ a อย่างไร, ฟังก์ชันรางวัล R(s,a) ที่วัดผลตอบแทนทันที, และตัวลดทอนค่า (discount factor) gamma ในช่วง [0,1] ที่ให้น้ำหนักระหว่างรางวัลในอนาคตกับปัจจุบัน
แสดงฟังก์ชันค่าที่เหมาะสมที่สุด V*(s) ผ่านสมการความเหมาะสมที่สุดของ Bellman: V*(s) = max เหนือการกระทำต่างๆ ของ [R(s,a) + gamma * ผลรวมเหนือ s' ของ P(s'|s,a)*V*(s')]. สมการเวียนเกิดนี้กล่าวว่า ค่าที่ดีที่สุดในสถานะ s เท่ากับรางวัลทันทีที่ดีที่สุด บวกกับค่าคาดหวังที่ลดทอนค่าของสถานะถัดไปภายใต้นโยบายที่เหมาะสมที่สุด
สูตร
V^*(s) = \max_{a \in A(s)} \left[ R(s,a) + \gamma \sum_{s'} P(s'|s,a)\, V^*(s') \right]แก้สมการหา V* แบบวนซ้ำ เริ่มต้นด้วย V_0 แบบสุ่ม (เช่น ค่าศูนย์ทั้งหมด) จากนั้นใช้ตัวดำเนินการ Bellman ซ้ำๆ: V_{k+1}(s) = max_a [R(s,a) + gamma * ผลรวม_{s'} P(s'|s,a) V_k(s')]. ภายใต้เงื่อนไขมาตรฐาน ลำดับนี้จะลู่เข้าสู่ V* แบบเรขาคณิต
สูตร
V_{k+1}(s) = \max_{a} \left[ R(s,a) + \gamma \sum_{s'} P(s'|s,a)\, V_k(s') \right]เมื่อการลู่เข้าเกิดขึ้นแล้ว ให้ดึงนโยบายที่เหมาะสมที่สุด pi*(s) ออกมา ซึ่งเป็นการกระทำที่ทำให้เกิดค่าสูงสุดในสมการ Bellman ณ แต่ละสถานะ นโยบายแบบละโมบ (greedy policy) นี้เทียบกับ V* ได้รับการพิสูจน์แล้วว่าเหมาะสมที่สุดสำหรับปัญหาที่มีขอบเขตอนันต์และมีการลดทอนค่า
สูตร
\pi^*(s) = \arg\max_{a} \left[ R(s,a) + \gamma \sum_{s'} P(s'|s,a)\, V^*(s') \right]สิ้นสุดการวนซ้ำค่า (value iteration) เมื่อระยะห่างในซุปนอร์ม (sup-norm distance) ระหว่างฟังก์ชันค่าที่ต่อเนื่องกันน้อยกว่าค่าคลาดเคลื่อนที่กำหนด epsilon: ||V_{k+1} - V_k||_inf < epsilon. นโยบาย pi* ที่ได้จะเป็นนโยบายที่เหมาะสมที่สุดแบบ epsilon/(1-gamma)
สูตร
\| V_{k+1} - V_k \|_\infty < \varepsilonข้อผิดพลาดที่พบบ่อย
- การแบ่งปริภูมิสถานะแบบต่อเนื่องอย่างหยาบเกินไปจะทำให้เกิดข้อผิดพลาดในการประมาณค่าจำนวนมากซึ่งจะแพร่กระจายผ่านฟังก์ชันค่า
- การเลือกตัวลดทอนค่า gamma ที่ใกล้เคียง 1 ทำให้การลู่เข้าช้าลงอย่างมาก; การตั้งค่าที่ใกล้เคียง 1 ต้องการเกณฑ์การสิ้นสุดที่รอบคอบ
- การละเลยเงื่อนไขขอบเขตสุดท้ายในปัญหาที่มีขอบเขตจำกัดนำไปสู่การประมาณค่าที่ผิดพลาดอย่างเป็นระบบในขั้นตอนสุดท้าย
- การปฏิบัติต่อแบบจำลองที่ระบุผิดว่าเป็นสิ่งเล็กน้อย: หากความน่าจะเป็นของการเปลี่ยนสถานะที่สมมติแตกต่างจากความเป็นจริงอย่างมีนัยสำคัญ นโยบายที่คำนวณได้อาจมีประสิทธิภาพต่ำในทางปฏิบัติ
- การสับสนระหว่างนโยบาย (การจับคู่จากสถานะไปสู่การกระทำ) กับฟังก์ชันค่า; การรายงานเฉพาะ V* โดยไม่ได้ดึง pi* ออกมา จะทำให้ปัญหาการตัดสินใจไม่ได้รับการแก้ไข
คำถามที่พบบ่อย
อะไรคือความแตกต่างระหว่าง deterministic dynamic programming และ stochastic dynamic programming?
ใน deterministic DP สถานะถัดไปจะถูกกำหนดอย่างสมบูรณ์โดยสถานะและการกระทำปัจจุบัน ดังนั้นจึงไม่มีความน่าจะเป็นเข้ามาเกี่ยวข้อง ใน SDP สถานะถัดไปจะถูกสุ่มจากฟังก์ชันความน่าจะเป็นแบบมีเงื่อนไข P(s'|s,a) ทำให้ผลลัพธ์มีความสุ่ม สมการ Bellman ใน SDP จะทำการหาค่าคาดหวังจากการเปลี่ยนสถานะเหล่านี้ ซึ่งเป็นความแตกต่างเชิงโครงสร้างที่สำคัญ
ฉันจะจัดการกับปริภูมิสถานะที่มีขนาดใหญ่เกินกว่าจะแจกแจงได้ทั้งหมดได้อย่างไร?
เมื่อ SDP ที่แม่นยำไม่สามารถคำนวณได้ ให้ใช้ approximate dynamic programming (ADP) หรือ reinforcement learning เทคนิคต่างๆ ได้แก่ การประมาณค่าฟังก์ชันด้วยฟังก์ชันเชิงเส้น (linear function approximation), ตัวประมาณค่าที่ใช้โครงข่ายประสาทเทียม (deep RL), และวิธีการที่ใช้การจำลอง เช่น approximate policy iteration ซึ่งทั้งหมดนี้จะแลกเปลี่ยนการรับประกันความเหมาะสมที่สุดกับความสามารถในการปรับขนาด
SDP เหมือนกับ Markov Decision Process หรือไม่?
MDP คือแบบจำลองทางคณิตศาสตร์ (tuple S, A, P, R, gamma) Stochastic Dynamic Programming หมายถึงกลุ่มของอัลกอริทึม — value iteration, policy iteration และรูปแบบต่างๆ — ที่ใช้ในการแก้ MDPs ในทางปฏิบัติ มักใช้คำเหล่านี้สลับกัน
เมื่อใดที่ฉันควรใช้ policy iteration แทน value iteration?
Policy iteration มักจะลู่เข้าในจำนวนรอบน้อยกว่า value iteration สำหรับหลายปัญหา แต่แต่ละรอบมีค่าใช้จ่ายสูงกว่าเนื่องจากต้องแก้ระบบสมการเชิงเส้น Value iteration นั้นง่ายต่อการนำไปใช้และเหมาะสำหรับปริภูมิสถานะขนาดใหญ่ สำหรับปัญหาขนาดเล็กถึงปานกลาง policy iteration มักจะเร็วกว่าโดยรวม
SDP สามารถจัดการกับวัตถุประสงค์ที่แข่งขันกันหลายอย่างได้หรือไม่?
ได้ ผ่าน MDPs ที่มีข้อจำกัด (constrained MDPs - CMDPs) ซึ่งต้นทุนสะสมที่คาดหวังรองต้องอยู่ภายใต้งบประมาณ หรือผ่าน MDPs แบบหลายวัตถุประสงค์ (multi-objective MDPs) ที่สร้างชุดนโยบายที่เหมาะสมที่สุดแบบพาเรโต (Pareto-optimal) อย่างไรก็ตาม รูปแบบมาตรฐานที่มีวัตถุประสงค์เดียวจะสมมติว่ามีรางวัลเป็นสเกลาร์ การแปลงวัตถุประสงค์หลายอย่างให้เป็นสเกลาร์ต้องอาศัยการระบุค่าน้ำหนักอย่างระมัดระวัง
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Bellman, R. (1957). Dynamic Programming. Princeton University Press, Princeton, NJ.
ISBN: 9780486428093คัดลอกแล้วPuterman, M. L. (1994). Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, New York.
ISBN: 9780471619772คัดลอกแล้ว