กระบวนการตัดสินใจแบบมาร์คอฟ ( MDP )เป็นแบบจำลองทางคณิตศาสตร์สำหรับการตัดสินใจตามลำดับเมื่อผลลัพธ์ไม่แน่นอน^{[ 1 ]}เป็นกระบวนการตัดสินใจแบบสุ่มประเภทหนึ่ง^{[ 2 ]}และมักจะแก้ไขโดยใช้วิธีการของ การ เขียน โปรแกรมเชิงพลวัตแบบสุ่ม

MDPs ซึ่งมีต้นกำเนิดมาจากการวิจัยปฏิบัติการ ใน ช่วงทศวรรษ 1950 ^{[ 3 ] [ 4 ]}ได้รับการยอมรับในหลากหลายสาขา รวมถึงนิเวศวิทยาเศรษฐศาสตร์การดูแลสุขภาพโทรคมนาคมและการเรียนรู้แบบเสริมแรง [ ^{5 ] การ}เรียนรู้แบบเสริมแรงใช้กรอบงาน MDP เพื่อจำลองปฏิสัมพันธ์ระหว่างตัวแทนการเรียนรู้กับสภาพแวดล้อม ในกรอบงานนี้ ปฏิสัมพันธ์จะถูกกำหนดลักษณะด้วยสถานะ การกระทำ และรางวัล กรอบงาน MDP ได้รับการออกแบบมาเพื่อให้การแสดงภาพที่เรียบง่ายขององค์ประกอบสำคัญของ ความท้าทาย ด้านปัญญาประดิษฐ์กรอบงานการสร้างแบบจำลองนี้รวมถึงความเข้าใจในสาเหตุและผลกระทบการจัดการความไม่แน่นอนและการไม่แน่นอน และการแสวงหาเป้าหมายที่ชัดเจน^{[ 5 ]}

ชื่อนี้มาจากความเชื่อมโยงกับลูกโซ่มาร์คอฟ (Markov chains)ซึ่งเป็นแนวคิดที่พัฒนาโดยนักคณิตศาสตร์ชาวรัสเซียอันเดรย์ มาร์คอฟ (Andrey Markov ) คำว่า "มาร์คอฟ" ใน "กระบวนการตัดสินใจแบบมาร์คอฟ" (Markov decision process) หมายถึงโครงสร้างพื้นฐานของการเปลี่ยนสถานะที่ยังคงเป็นไปตามคุณสมบัติของมาร์คอฟกระบวนการนี้เรียกว่า "กระบวนการตัดสินใจ" เพราะเกี่ยวข้องกับการตัดสินใจที่ส่งผลต่อการเปลี่ยนสถานะเหล่านี้ ซึ่งเป็นการขยายแนวคิดของลูกโซ่มาร์คอฟไปสู่ขอบเขตของการตัดสินใจภายใต้ความไม่แน่นอน

กระบวนการตัดสินใจแบบมาร์คอฟเป็นทูเพิล 4 ตัว โดยที่: ${\displaystyle (S,A,P_{a},R_{a})}$

• ${\displaystyle S}$คือเซตของสถานะที่เรียกว่าปริภูมิสถานะ ปริภูมิสถานะอาจเป็นแบบไม่ต่อเนื่องหรือแบบต่อเนื่อง เช่นเดียวกับเซตของจำนวนจริง
• ${\displaystyle A}$คือชุดของการกระทำที่เรียกว่าปริภูมิการกระทำ (หรืออีกนัยหนึ่งคือ ชุดของการกระทำที่มีให้เลือกจากสถานะ) สำหรับสถานะนั้น ชุดนี้อาจเป็นแบบไม่ต่อเนื่องหรือแบบต่อเนื่องก็ได้${\displaystyle A_{s}}$${\displaystyle s}$
• ${\displaystyle P_{a}(s,s')}$โดยพื้นฐานแล้ว อินทิกรัลคือความน่าจะเป็นที่การกระทำในสถานะณ เวลา t จะนำไปสู่สถานะณ เวลาt โดยทั่วไป ความน่าจะเป็นของการเปลี่ยนสถานะนี้ถูกกำหนดให้สอดคล้อง กับเงื่อนไข สำหรับทุกตัวแปรที่วัดได้ ในกรณีที่ปริภูมิสถานะเป็นแบบไม่ต่อเนื่อง อินทิกรัลจะพิจารณาจากมาตรวัดการนับ t ซึ่งทำให้มาตรวัดการนับง่ายขึ้นเป็น t = t(t) ในกรณีt(t) อินทิกรัลมักจะพิจารณาจากมาตรวัดเลเบส${\displaystyle a}$${\displaystyle s}$${\displaystyle t}$${\displaystyle s'}$${\displaystyle t+1}$${\displaystyle \Pr(s_{t+1}\in S'\mid s_{t}=s,a_{t}=a)=\int _{S'}P_{a}(s,s')ds',}$${\displaystyle S'\subseteq S}$${\displaystyle P_{a}(s,s')=\Pr(s_{t+1}=s'\mid s_{t}=s,a_{t}=a)}$${\displaystyle S\subseteq \mathbb {R} ^{d}}$
• ${\displaystyle R_{a}(s,s')}$คือรางวัลทันที (หรือรางวัลทันทีที่คาดว่าจะได้รับ) หลังจากดำเนินการเพื่อเปลี่ยนสถานะจากสถานะหนึ่งไปอีกสถานะหนึ่ง โดยทั่วไป แล้วรางวัลจะเป็นตัวแปรสุ่ม${\displaystyle a}$${\displaystyle s}$${\displaystyle s'}$

ฟังก์ชันนโยบายคือการแมป (ซึ่งอาจเป็นแบบความน่าจะเป็น) จากพื้นที่สถานะ ( ) ไปยังพื้นที่การกระทำ ( ) ${\displaystyle \pi }$${\displaystyle S}$${\displaystyle A}$

เป้าหมายในกระบวนการตัดสินใจแบบมาร์คอฟคือการค้นหา "นโยบาย" ที่ดีสำหรับผู้ตัดสินใจ: ฟังก์ชันที่ระบุการกระทำที่ผู้ตัดสินใจจะเลือกเมื่ออยู่ในสถานะหนึ่งเมื่อกระบวนการตัดสินใจแบบมาร์คอฟถูกรวมเข้ากับนโยบายในลักษณะนี้แล้ว การกระทำสำหรับแต่ละสถานะจะถูกกำหนดตายตัว และการรวมกันที่ได้จะทำงานเหมือนกับลูกโซ่มาร์คอฟ (เนื่องจากการกระทำที่เลือกในสถานะหนึ่งถูกกำหนดโดยนโยบายอย่างสมบูรณ์) ${\displaystyle \pi }$${\displaystyle \pi (s)}$${\displaystyle s}$${\displaystyle s}$${\displaystyle \pi (s)}$

เป้าหมายคือการเลือกนโยบายที่จะเพิ่มค่าฟังก์ชันสะสมของรางวัลแบบสุ่มให้สูงสุด ซึ่งโดยทั่วไปแล้วจะเป็นผลรวมส่วนลดที่คาดหวังในช่วงเวลาที่อาจไม่มีที่สิ้นสุด: ${\displaystyle \pi }$

${\displaystyle E\left[\sum _{t=0}^{\infty }{\gamma ^{t}R_{a_{t}}(s_{t},s_{t+1})}\right]}$(โดยที่เราเลือกเช่น การกระทำที่กำหนดโดยนโยบาย) และความคาดหวังจะถูกนำมาใช้${\displaystyle a_{t}=\pi (s_{t})}$${\displaystyle s_{t+1}\sim P_{a_{t}}(s_{t},s_{t+1})}$

ปัจจัยส่วนลดที่ตรงตามเงื่อนไขนั้นอยู่ที่ใดซึ่งโดยปกติจะใกล้เคียงกับ(ตัวอย่างเช่นสำหรับอัตราส่วนลดบางอัตรา) ปัจจัยส่วนลดที่ต่ำกว่าจะทำให้ผู้ตัดสินใจมองการณ์สั้นลง เนื่องจากมองข้ามผลกระทบที่การปฏิบัติตามนโยบายปัจจุบันอาจมีในอนาคตที่ไกลออกไป ${\displaystyle \ \gamma \ }$${\displaystyle 0\leq \ \gamma \ \leq \ 1}$${\displaystyle 1}$${\displaystyle \gamma =1/(1+r)}$${\displaystyle r}$

อีกหนึ่งเป้าหมายที่เป็นไปได้ แต่มีความเกี่ยวข้องอย่างเคร่งครัด และนิยมใช้กันคือ ผลตอบแทนตามขั้นตอน ในครั้งนี้ แทนที่จะใช้ปัจจัยส่วนลดตัวแทนจะสนใจเฉพาะขั้นตอนแรกของกระบวนการ โดยแต่ละรางวัลจะมีน้ำหนักเท่ากัน ${\displaystyle H-}$${\displaystyle \ \gamma \ }$${\displaystyle H}$

${\displaystyle E\left[\sum _{t=0}^{H-1}{R_{a_{t}}(s_{t},s_{t+1})}\right]}$(โดยที่เราเลือกเช่น การกระทำที่กำหนดโดยนโยบาย) และความคาดหวังจะถูกนำมาใช้${\displaystyle a_{t}=\pi (s_{t})}$${\displaystyle s_{t+1}\sim P_{a_{t}}(s_{t},s_{t+1})}$

ขอบเขตเวลาอยู่ที่ไหน เมื่อเปรียบเทียบกับวัตถุประสงค์ก่อนหน้านี้ วัตถุประสงค์หลังนี้ถูกนำมาใช้ใน ทฤษฎีการเรียนรู้มากกว่า ${\displaystyle \ H\ }$

นโยบายที่ทำให้ฟังก์ชันข้างต้นมีค่าสูงสุดเรียกว่านโยบายที่เหมาะสมที่สุดและโดยทั่วไปจะใช้สัญลักษณ์ แทนMDP หนึ่งๆ อาจมีนโยบายที่เหมาะสมที่สุดที่แตกต่างกันได้หลายแบบ เนื่องจากคุณสมบัติของมาร์คอฟจึงสามารถแสดงได้ว่านโยบายที่เหมาะสมที่สุดเป็นฟังก์ชันของสถานะปัจจุบัน ดังที่ได้สมมติไว้ข้างต้น เมื่อเป็นแบบกำหนดได้ จะมีนโยบายที่เหมาะสมที่สุดอยู่เสมอซึ่งเป็นแบบกำหนดได้เช่นกัน ${\displaystyle \pi ^{*}}$${\displaystyle R_{a}(s,s')}$${\displaystyle \pi ^{*}}$

ในหลายกรณี การแสดงการแจกแจงความน่าจะเป็นของการเปลี่ยนสถานะอย่างชัดเจนนั้นทำได้ยากในกรณีเช่นนี้ สามารถใช้โปรแกรมจำลองเพื่อจำลอง MDP โดยปริยายได้ โดยการสุ่มตัวอย่างจากการแจกแจงการเปลี่ยนสถานะ รูปแบบหนึ่งของแบบจำลอง MDP โดยปริยายที่พบได้ทั่วไปคือ โปรแกรมจำลองสภาพแวดล้อมแบบเป็นตอนๆ ซึ่งสามารถเริ่มต้นจากสถานะเริ่มต้นและให้ผลลัพธ์เป็นสถานะและรางวัลถัดไปทุกครั้งที่ได้รับอินพุตการกระทำ ด้วยวิธีนี้สามารถสร้าง วิถีของสถานะ การกระทำ และรางวัล ซึ่งมักเรียกว่า ตอนต่างๆ ได้${\displaystyle P_{a}(s,s')}$

อีกรูปแบบหนึ่งของโปรแกรมจำลองคือแบบจำลองเชิงกำเนิดซึ่งเป็นโปรแกรมจำลองแบบขั้นตอนเดียวที่สามารถสร้างตัวอย่างของสถานะและรางวัลถัดไปได้ โดยพิจารณาจากสถานะและการกระทำใดๆ^{[ 6 ]} (โปรดทราบว่านี่เป็นความหมายที่แตกต่างจากคำว่าแบบจำลองเชิงกำเนิดในบริบทของการจำแนกประเภททางสถิติ ) ในอัลกอริธึมที่แสดงโดยใช้รหัสเทียมมักใช้เพื่อแสดงถึงแบบจำลองเชิงกำเนิด ตัวอย่างเช่น นิพจน์อาจแสดงถึงการกระทำของการสุ่มตัวอย่างจากแบบจำลองเชิงกำเนิด โดยที่และคือสถานะและการกระทำปัจจุบัน และและคือสถานะและรางวัลใหม่ เมื่อเปรียบเทียบกับโปรแกรมจำลองแบบเป็นตอน แบบจำลองเชิงกำเนิดมีข้อได้เปรียบตรงที่สามารถสร้างข้อมูลจากสถานะใดๆ ก็ได้ ไม่ใช่เฉพาะสถานะที่พบในวิถีเท่านั้น ${\displaystyle G}$${\displaystyle s',r\gets G(s,a)}$${\displaystyle s}$${\displaystyle a}$${\displaystyle s'}$${\displaystyle r}$

คลาสของโมเดลเหล่านี้ก่อให้เกิดลำดับชั้นของเนื้อหาข้อมูล: โมเดลแบบชัดเจนจะสร้างโมเดลแบบสร้างขึ้นเองได้โดยง่ายผ่านการสุ่มตัวอย่างจากการกระจาย และการประยุกต์ใช้โมเดลแบบสร้างขึ้นเองซ้ำๆ จะสร้างตัวจำลองแบบเป็นตอนๆ ในทางตรงกันข้าม การเรียนรู้โมเดลโดยประมาณทำได้ผ่านการถดถอย เท่านั้น ประเภทของโมเดลที่มีให้สำหรับ MDP เฉพาะนั้นมีบทบาทสำคัญในการกำหนดว่าอัลกอริธึมการแก้ปัญหาใดเหมาะสม ตัวอย่างเช่น อัลก อริธึมการเขียนโปรแกรม เชิงพลวัตที่อธิบายไว้ในส่วนถัดไปต้องการโมเดลแบบชัดเจน และการค้นหาต้นไม้แบบมอนเตคาร์โลต้องการโมเดลแบบสร้างขึ้นเอง (หรือตัวจำลองแบบเป็นตอนๆ ที่สามารถคัดลอกได้ในทุกสถานะ) ในขณะที่ อัลกอริธึม การเรียนรู้แบบเสริมแรงส่วน ใหญ่ ต้องการเพียงตัวจำลองแบบเป็นตอนๆ เท่านั้น

ตัวอย่างหนึ่งของ MDP คือแบบจำลองการปรับสมดุลขั้ว ซึ่งมาจากทฤษฎีการควบคุมแบบคลาสสิก

ในตัวอย่างนี้ เรามี

• ${\displaystyle S}$คือเซตของทูเปิลเรียงลำดับที่กำหนดโดยมุมของเสา ความเร็วเชิงมุม ตำแหน่งของรถเข็น และความเร็วของรถเข็น${\displaystyle (\theta ,{\dot {\theta }},x,{\dot {x}})}$
• ${\displaystyle A}$คือซึ่งสอดคล้องกับการออกแรงทางด้านซ้าย (ขวา) บนรถเข็น${\displaystyle \{-1,1\}}$
• ${\displaystyle P_{a}(s,s')}$คือการเปลี่ยนแปลงของระบบ ซึ่งในกรณีนี้จะเป็นไปตามแบบแผนและขับเคลื่อนด้วยกฎของกลศาสตร์
• ${\displaystyle R_{a}(s,s')}$คือค่าของขั้วบวกหลังจากเปลี่ยนสถานะเป็นบวก และค่าของขั้วลบเป็นศูนย์ในกรณีอื่น ๆ ดังนั้น ฟังก์ชันนี้จึงขึ้นอยู่กับค่าของขั้วบวกในกรณีเฉพาะนี้ เท่านั้น${\displaystyle 1}$${\displaystyle s'}$

วิธีแก้ปัญหาสำหรับ MDP ที่มีสถานะและพื้นที่การกระทำจำกัดอาจพบได้ผ่านวิธีการต่างๆ เช่นการเขียนโปรแกรมแบบไดนามิก อัลกอริทึมในส่วนนี้ใช้กับ MDP ที่มีสถานะและพื้นที่การกระทำจำกัดและกำหนดความน่าจะเป็นการเปลี่ยนสถานะและฟังก์ชันรางวัลอย่างชัดเจน แต่แนวคิดพื้นฐานอาจขยายไปใช้กับปัญหาประเภทอื่นๆ ได้ เช่น การใช้การประมาณฟังก์ชันนอกจากนี้ กระบวนการบางอย่างที่มีสถานะและพื้นที่การกระทำที่นับได้ไม่จำกัดสามารถ ลดรูป ได้อย่างแม่นยำเป็นกระบวนการที่มีสถานะและพื้นที่การกระทำจำกัด^{[ 7 ]}

ชุดอัลกอริธึมมาตรฐานสำหรับการคำนวณนโยบายที่เหมาะสมที่สุดสำหรับ MDP ที่มีสถานะและการกระทำจำกัดนั้น ต้องการพื้นที่จัดเก็บข้อมูลสำหรับอาร์เรย์สองชุดที่จัดทำดัชนีตามสถานะ ได้แก่ อาร์เรย์ค่า (value ) ซึ่งมีค่าจริง และอาร์เรย์นโยบาย (policy ) ซึ่งมีค่าการกระทำ เมื่อสิ้นสุดอัลกอริธึม อาร์เรย์ค่าจะเก็บคำตอบ และอาร์เรย์นโยบายจะเก็บผลรวมส่วนลดของรางวัลที่จะได้รับ (โดยเฉลี่ย) โดยการปฏิบัติตามคำตอบนั้นจากสถานะ ${\displaystyle V}$${\displaystyle \pi }$${\displaystyle \pi }$${\displaystyle V(s)}$${\displaystyle s}$

อัลกอริทึมมีสองขั้นตอน (1) การอัปเดตค่า และ (2) การอัปเดตนโยบาย ซึ่งจะทำซ้ำตามลำดับบางอย่างสำหรับทุกสถานะจนกว่าจะไม่มีการเปลี่ยนแปลงเพิ่มเติมเกิดขึ้น ทั้งสองจะอัปเดตการประมาณค่าใหม่ของนโยบายและค่าสถานะที่เหมาะสมที่สุดโดยใช้การประมาณค่าเก่าของค่าเหล่านั้นแบบเรียกซ้ำ

${\displaystyle V(s):=\sum _{s'}P_{\pi (s)}(s,s')\left(R_{\pi (s)}(s,s')+\gamma V(s')\right)}$

${\displaystyle \pi (s):=\operatorname {argmax} _{a}\left\{\sum _{s'}P_{a}(s,s')\left(R_{a}(s,s')+\gamma V(s')\right)\right\}}$

ลำดับของขั้นตอนเหล่านี้ขึ้นอยู่กับรูปแบบของอัลกอริธึม นอกจากนี้ยังสามารถดำเนินการกับทุกสถานะพร้อมกันหรือทีละสถานะ และมักจะดำเนินการกับบางสถานะมากกว่าสถานะอื่น ตราบใดที่ไม่มีสถานะใดถูกยกเว้นอย่างถาวรจากขั้นตอนใดขั้นตอนหนึ่ง อัลกอริธึมก็จะสามารถหาคำตอบที่ถูกต้องได้ในที่สุด^{[ 8 ]}

ในการวนซ้ำค่า ( Bellman 1957 ) ซึ่งเรียกอีกอย่างว่าการเหนี่ยวนำย้อนกลับ จะไม่มีการใช้ ฟังก์ชัน แต่ จะคำนวณค่าของ ภายใน เมื่อใดก็ตามที่ต้องการ การแทนที่การคำนวณของลงในการคำนวณของจะได้ขั้นตอนรวม ${\displaystyle \pi }$${\displaystyle \pi (s)}$${\displaystyle V(s)}$${\displaystyle \pi (s)}$${\displaystyle V(s)}$

${\displaystyle V_{i+1}(s):=\max _{a}\left\{\sum _{s'}P_{a}(s,s')\left(R_{a}(s,s')+\gamma V_{i}(s')\right)\right\},}$

โดยที่คือหมายเลขการวนซ้ำ การวนซ้ำค่าเริ่มต้นที่และเป็นการคาดเดาฟังก์ชันค่าจากนั้นจะวนซ้ำ คำนวณซ้ำๆสำหรับทุกสถานะจนกระทั่งลู่เข้าโดยที่ด้านซ้ายมือเท่ากับด้านขวามือ (ซึ่งเป็น " สมการเบลล์แมน " สำหรับปัญหานี้) บทความของLloyd Shapley ในปี 1953 เกี่ยวกับ เกมสุ่มได้รวมวิธีการวนซ้ำค่าสำหรับ MDP ไว้เป็นกรณีพิเศษ^{[ 9 ]}แต่ได้รับการยอมรับในภายหลังเท่านั้น^{[ 10 ]}${\displaystyle i}$${\displaystyle i=0}$${\displaystyle V_{0}}$${\displaystyle V_{i+1}}$${\displaystyle s}$${\displaystyle V}$

การวนซ้ำค่ารับประกันว่าจะลู่เข้าตามทฤษฎีบทจุดตรึงของบานาค ${\displaystyle \gamma <1}$

ในการวนซ้ำนโยบาย^{[ 11 ]}ขั้นแรกจะทำการกำหนดค่าโดยการแก้หาค่าจากระบบเชิงเส้นที่อธิบายไว้ในขั้นตอนแรก จากนั้นจะทำการปรับปรุงนโยบายโดยการคำนวณตามขั้นตอนที่สอง จากนั้นทำซ้ำทั้งสองขั้นตอนจนกว่านโยบายจะบรรจบกัน (การวนซ้ำนโยบายถูกคิดค้นโดย Howard เพื่อเพิ่มประสิทธิภาพ การส่งจดหมายแคตตาล็อก ของ Searsซึ่งเขาได้เพิ่มประสิทธิภาพโดยใช้การวนซ้ำค่า^{[ 12 ]} ) ${\displaystyle V}$${\displaystyle \pi }$

เนื่องจากการวนซ้ำนโยบายเป็นการสลับปัญหาผกผัน เชิงเส้นกับการดำเนินการที่ไม่เป็นเชิงเส้นอย่างมีประสิทธิภาพ จึงอาจตีความได้ว่าเป็น วิธี การผ่อนคลายประเภทหนึ่ง

รูปแบบนี้มีข้อดีคือมีเงื่อนไขการหยุดที่แน่นอน เนื่องจากมีวิธีแก้ปัญหาที่ไม่ซ้ำกันสำหรับแต่ละนโยบายอัลกอริทึมจะเสร็จสมบูรณ์เมื่อการปรับปรุงนโยบายสร้างนโยบายเดียวกันสองครั้งติดต่อกัน ${\displaystyle V}$${\displaystyle \pi }$

แม้ว่าจะมีบางสถานการณ์ที่การวนซ้ำนโยบายอาจเร็วกว่าการวนซ้ำค่า (เช่น เมื่อพื้นที่การกระทำมีขนาดใหญ่กว่าพื้นที่สถานะอย่างมาก) แต่โดยทั่วไปแล้วการวนซ้ำนโยบายจะช้ากว่าการวนซ้ำค่าสำหรับจำนวนสถานะที่เป็นไปได้จำนวนมาก

ในการทำซ้ำนโยบายที่แก้ไขแล้ว ( van Nunen 1976 ; Puterman & Shin 1978 ) ขั้นตอนที่หนึ่งจะถูกทำซ้ำหลายครั้ง จากนั้นขั้นตอนที่สองจะถูกดำเนินการเพียงครั้งเดียว^{[ 13 ] [ 14 ]}จากนั้นขั้นตอนที่หนึ่งจะถูกทำซ้ำอีกหลายครั้งและต่อไปเรื่อยๆ

ในรูปแบบนี้ ขั้นตอนต่างๆ จะถูกนำไปใช้กับสถานะที่มีความสำคัญในบางแง่มุมเป็นหลัก ไม่ว่าจะเป็นไปตามอัลกอริทึม (มีการเปลี่ยนแปลงครั้งใหญ่ในหรือรอบๆ สถานะเหล่านั้นเมื่อเร็วๆ นี้) หรือไปตามการใช้งาน (สถานะเหล่านั้นอยู่ใกล้กับสถานะเริ่มต้น หรือเป็นที่น่าสนใจสำหรับบุคคลหรือโปรแกรมที่ใช้อัลกอริทึม) ${\displaystyle V}$${\displaystyle \pi }$

มีอัลกอริธึมสำหรับการค้นหานโยบายที่เหมาะสมที่สุดด้วย ความซับซ้อน ^ของเวลาที่เป็นพหุนามตามขนาดของการแสดงปัญหาสำหรับ MDP แบบจำกัด ดังนั้นปัญหาการตัดสินใจที่อิงตาม MDP จึงอยู่ในคลาสความซับซ้อน ในการคำนวณ P ^{[ 15} ] อย่างไรก็ตาม เนื่องจากคำสาปของมิติขนาดของการแสดงปัญหามักจะเป็นเลขชี้กำลังตามจำนวนตัวแปรสถานะและการกระทำ ซึ่งจำกัดเทคนิคการแก้ปัญหาที่แม่นยำไว้เฉพาะปัญหาที่มีการแสดงแบบกระชับ ในทางปฏิบัติ เทคนิคการวางแผนแบบออนไลน์ เช่นการค้นหาต้นไม้แบบมอนเตคาร์โลสามารถค้นหาวิธีแก้ปัญหาที่มีประโยชน์ในปัญหาขนาดใหญ่ได้ และในทางทฤษฎี เป็นไปได้ที่จะสร้างอัลกอริธึมการวางแผนแบบออนไลน์ที่สามารถค้นหานโยบายที่ใกล้เคียงกับค่าที่เหมาะสมที่สุดได้โดยไม่มีความซับซ้อนในการคำนวณขึ้นอยู่กับขนาดของพื้นที่สถานะ^{[ 16 ]}

กระบวนการตัดสินใจแบบมาร์คอฟเป็นเกมสุ่มที่มีผู้เล่นเพียงคนเดียว

วิธีแก้ปัญหาข้างต้นตั้งอยู่บนสมมติฐานว่าทราบสถานะเมื่อต้องดำเนินการ มิฉะนั้นจะไม่สามารถคำนวณได้ เมื่อสมมติฐานนี้ไม่เป็นจริง ปัญหาดังกล่าวเรียกว่ากระบวนการตัดสินใจแบบมาร์คอฟที่สังเกตได้บางส่วน หรือ POMDP ${\displaystyle s}$${\displaystyle \pi (s)}$

กระบวนการตัดสินใจแบบมาร์คอฟที่มีข้อจำกัด (CMDPS) เป็นส่วนขยายของกระบวนการตัดสินใจแบบมาร์คอฟ (MDPs) มีความแตกต่างพื้นฐานสามประการระหว่าง MDPs และ CMDPs ^{[ 17 ]}

• การดำเนินการหนึ่งอย่างแทนที่จะเป็นการดำเนินการเดียว ส่งผลให้เกิดค่าใช้จ่ายหลายอย่าง
• ปัญหา CMDP แก้ได้ด้วยโปรแกรมเชิงเส้นเท่านั้น และไม่สามารถใช้โปรแกรมเชิงพลวัต ได้
• นโยบายสุดท้ายขึ้นอยู่กับสถานะเริ่มต้น

วิธีการใช้ตัวคูณลากรางจ์สามารถนำไปใช้กับ CMDP ได้ มีการพัฒนาอัลกอริธึมที่ใช้ลากรางจ์เป็นพื้นฐานอยู่มากมาย

• วิธีการไล่ระดับนโยบายธรรมชาติแบบคู่หลัก^{[ 18 ]}

มีแอปพลิเคชันหลายอย่างสำหรับ CMDP โดยเพิ่งมีการนำไปใช้ใน สถานการณ์ การวางแผนการเคลื่อนที่ในหุ่นยนต์^{[ 19 ]}

ในกระบวนการตัดสินใจแบบมาร์คอฟแบบเวลาไม่ต่อเนื่อง การตัดสินใจจะเกิดขึ้นในช่วงเวลาที่ไม่ต่อเนื่องกัน แต่สำหรับกระบวนการตัดสินใจแบบมาร์คอฟแบบเวลาต่อเนื่อง การตัดสินใจสามารถเกิดขึ้นได้ทุกเมื่อที่ผู้ตัดสินใจเลือก เมื่อเปรียบเทียบกับกระบวนการตัดสินใจแบบมาร์คอฟแบบเวลาไม่ต่อเนื่อง กระบวนการตัดสินใจแบบมาร์คอฟแบบเวลาต่อเนื่องสามารถจำลองกระบวนการตัดสินใจสำหรับระบบที่มีพลวัตต่อเนื่อง ได้ดีกว่า กล่าวคือ พลวัตของระบบถูกกำหนดโดยสมการเชิงอนุพันธ์สามัญ (ODE) กรอบการสร้างแบบจำลองนี้สามารถนำไปใช้ในด้านต่างๆ เช่นระบบคิวกระบวนการระบาด และกระบวนการประชากร

เช่นเดียวกับกระบวนการตัดสินใจแบบมาร์คอฟในเวลาไม่ต่อเนื่อง ในกระบวนการตัดสินใจแบบมาร์คอฟในเวลาต่อเนื่อง ตัวแทนมีเป้าหมายที่จะค้นหานโยบาย ที่เหมาะสมที่สุด ซึ่งจะเพิ่มผลตอบแทนสะสมที่คาดหวังให้สูงสุด ความแตกต่างที่สำคัญกับกรณีมาตรฐานคือ เนื่องจากลักษณะต่อเนื่องของตัวแปรเวลา การหาผลรวมจึงถูกแทนที่ด้วยการหาปริพันธ์:

${\displaystyle \max \operatorname {E} _{\pi }\left[\left.\int _{0}^{\infty }\gamma ^{t}r(s(t),\pi (s(t)))\,dt\;\right|s_{0}\right]}$

ที่ไหน${\displaystyle 0\leq \gamma <1.}$

หากปริภูมิสถานะและปริภูมิการกระทำมีจำกัด เราสามารถใช้การเขียนโปรแกรมเชิงเส้นเพื่อค้นหานโยบายที่เหมาะสมที่สุด ซึ่งเป็นหนึ่งในแนวทางแรกๆ ที่นำมาใช้ ที่นี่เราพิจารณาเฉพาะแบบจำลองเออร์โกดิก ซึ่งหมายความว่า MDP แบบต่อเนื่องของเราจะกลายเป็นห่วงโซ่มาร์คอฟแบบต่อเนื่องเออร์โกดิก ภายใต้ นโยบาย คงที่ ภาย ใต้สมมติฐานนี้ แม้ว่าผู้ตัดสินใจจะสามารถตัดสินใจได้ตลอดเวลาในสถานะปัจจุบัน แต่ก็ไม่มีประโยชน์ในการดำเนินการหลายอย่าง การดำเนินการเฉพาะเมื่อระบบกำลังเปลี่ยนจากสถานะปัจจุบันไปยังสถานะอื่นจะดีกว่า ภายใต้เงื่อนไขบางประการ^{[ 20 ]}หากฟังก์ชันค่าที่เหมาะสมที่สุดของเราเป็นอิสระจากสถานะเราจะมีความไม่เท่าเทียมกันดังต่อไปนี้: ${\displaystyle V^{*}}$${\displaystyle i}$

${\displaystyle g\geq R(i,a)+\sum _{j\in S}q(j\mid i,a)h(j)\quad \forall i\in S{\text{ and }}a\in A(i)}$

ถ้ามีฟังก์ชัน อยู่จริงแล้วจะเป็นค่าที่เล็กที่สุดที่สอดคล้องกับสมการข้างต้น ในการหาค่าเราสามารถใช้แบบจำลองการเขียนโปรแกรมเชิงเส้นต่อไปนี้ได้: ${\displaystyle h}$${\displaystyle {\bar {V}}^{*}}$${\displaystyle g}$${\displaystyle {\bar {V}}^{*}}$

• โปรแกรมเชิงเส้นดั้งเดิม (P-LP)

${\displaystyle {\begin{aligned}{\text{Minimize}}\quad &g\\{\text{s.t}}\quad &g-\sum _{j\in S}q(j\mid i,a)h(j)\geq R(i,a)\,\,\forall i\in S,\,a\in A(i)\end{aligned}}}$

• โปรแกรมเชิงเส้นคู่ (D-LP)

${\displaystyle {\begin{aligned}{\text{Maximize}}&\sum _{i\in S}\sum _{a\in A(i)}R(i,a)y(i,a)\\{\text{s.t.}}&\sum _{i\in S}\sum _{a\in A(i)}q(j\mid i,a)y(i,a)=0\quad \forall j\in S,\\&\sum _{i\in S}\sum _{a\in A(i)}y(i,a)=1,\\&y(i,a)\geq 0\qquad \forall a\in A(i){\text{ and }}\forall i\in S\end{aligned}}}$

${\displaystyle y(i,a)}$คำตอบที่เป็นไปได้ของ D-LP คือคำตอบที่สอดคล้องกับเงื่อนไขในปัญหา D-LP คำตอบที่เป็นไปได้ของ D-LP จะเรียกว่าเป็นคำตอบที่เหมาะสมที่สุด ถ้า ${\displaystyle y(i,a)}$${\displaystyle y^{*}(i,a)}$

${\displaystyle {\begin{aligned}\sum _{i\in S}\sum _{a\in A(i)}R(i,a)y^{*}(i,a)\geq \sum _{i\in S}\sum _{a\in A(i)}R(i,a)y(i,a)\end{aligned}}}$

สำหรับคำตอบที่เป็นไปได้ทั้งหมดของ D-LP เมื่อเราพบคำตอบที่เหมาะสมที่สุดแล้ว เราสามารถใช้คำตอบนั้นเพื่อกำหนดนโยบายที่เหมาะสมที่สุดได้ ${\displaystyle y(i,a)}$${\displaystyle y^{*}(i,a)}$

ใน MDP แบบเวลาต่อเนื่อง หากปริภูมิสถานะและปริภูมิการกระทำเป็นแบบต่อเนื่อง เกณฑ์ที่เหมาะสมที่สุดสามารถหาได้โดยการแก้สมการเชิงอนุพันธ์ย่อยของ Hamilton–Jacobi–Bellman (HJB)เพื่อที่จะอธิบายสมการ HJB เราจำเป็นต้องกำหนดปัญหาของเราใหม่

${\displaystyle {\begin{aligned}V(s(0),0)={}&\max _{a(t)=\pi (s(t))}\int _{0}^{T}r(s(t),a(t))\,dt+D[s(T)]\\{\text{s.t.}}\quad &{\frac {ds(t)}{dt}}=f[t,s(t),a(t)]\end{aligned}}}$

${\displaystyle D(\cdot )}$คือฟังก์ชันรางวัลสุดท้ายคือเวกเตอร์สถานะของระบบคือเวกเตอร์ควบคุมระบบที่เราพยายามค้นหาแสดงให้เห็นว่าเวกเตอร์สถานะเปลี่ยนแปลงไปอย่างไรเมื่อเวลาผ่านไป สมการ Hamilton–Jacobi–Bellman มีดังนี้: ${\displaystyle s(t)}$${\displaystyle a(t)}$${\displaystyle f(\cdot )}$

${\displaystyle 0=\max _{a}(r(t,s,a)+{\frac {\partial V(t,s)}{\partial s}}f(t,s,a))}$

เราสามารถแก้สมการเพื่อหาฟังก์ชันค่า ที่เหมาะสมที่สุด ซึ่งจะนำไปสู่การควบคุมที่เหมาะสมที่สุดในแต่ละช่วงเวลาได้โดยผ่านทาง... ${\displaystyle V^{*}}$${\displaystyle t}$${\displaystyle a(t)}$${\displaystyle a(t)={\underset {a}{\text{argmax}}}(r(t,s,a)+{\frac {\partial V^{*}(t,s)}{\partial s}}f(t,s,a)).}$

การเรียนรู้แบบเสริมแรงเป็นสาขาสหวิทยาการของการเรียนรู้ของเครื่องและการควบคุมที่เหมาะสมที่สุดโดยมีวัตถุประสงค์หลักคือการค้นหานโยบายที่เหมาะสมที่สุดโดยประมาณสำหรับ MDP ซึ่งความน่าจะเป็นของการเปลี่ยนสถานะและรางวัลไม่เป็นที่รู้จัก^{[ 21 ]}

การเรียนรู้แบบเสริมแรงสามารถแก้ปัญหา Markov-Decision Process (MDP) ได้โดยไม่ต้องระบุความน่าจะเป็นของการเปลี่ยนสถานะอย่างชัดเจน ซึ่งจำเป็นต่อการทำซ้ำนโยบาย ในบริบทนี้ ความน่าจะเป็นของการเปลี่ยนสถานะและรางวัลจะต้องเรียนรู้จากประสบการณ์ กล่าวคือ โดยการปล่อยให้ตัวแทนโต้ตอบกับ MDP เป็นจำนวนขั้นตอนที่กำหนด ทั้งในระดับทฤษฎีและระดับปฏิบัติ มีความพยายามในการเพิ่มประสิทธิภาพของตัวอย่างให้สูงสุด กล่าวคือ ลดจำนวนตัวอย่างที่จำเป็นในการเรียนรู้นโยบายที่มีประสิทธิภาพใกล้เคียงกับนโยบายที่ดีที่สุดให้เหลือน้อยที่สุด (เนื่องจากลักษณะสุ่มของกระบวนการ การเรียนรู้นโยบายที่ดีที่สุดด้วยจำนวนตัวอย่างที่จำกัดนั้นโดยทั่วไปเป็นไปไม่ได้) ${\displaystyle \varepsilon -}$

เพื่อจุดประสงค์ของหัวข้อนี้ การกำหนดฟังก์ชันเพิ่มเติมซึ่งสอดคล้องกับการดำเนินการและดำเนินการต่ออย่างเหมาะสมที่สุด (หรือตามนโยบายใดก็ตามที่มีอยู่ในปัจจุบัน) จะเป็นประโยชน์: ${\displaystyle a}$

${\displaystyle \ Q(s,a)=\sum _{s'}P_{a}(s,s')(R_{a}(s,s')+\gamma V(s')).\ }$

แม้ว่าฟังก์ชันนี้จะยังไม่เป็นที่รู้จัก แต่ประสบการณ์ระหว่างการเรียนรู้จะอิงตามคู่ (รวมถึงผลลัพธ์ด้วย กล่าวคือ "ฉันอยู่ในสถานะหนึ่งและฉันลองทำบางอย่างและสิ่งนั้นก็เกิดขึ้น") ดังนั้น เราจึงมีอาร์เรย์และใช้ประสบการณ์เพื่ออัปเดตอาร์เรย์นั้นโดยตรง นี่คือสิ่งที่เรียกว่าQ- learning ${\displaystyle (s,a)}$${\displaystyle s'}$${\displaystyle s}$${\displaystyle a}$${\displaystyle s'}$${\displaystyle Q}$

การประยุกต์ใช้กระบวนการ MDP อีกอย่างหนึ่งใน ทฤษฎี การเรียนรู้ของเครื่องเรียกว่า ออโตมาตาการเรียนรู้ นี่เป็นการเรียนรู้แบบเสริมแรงประเภทหนึ่งเช่นกัน หากสภาพแวดล้อมเป็นแบบสุ่ม บทความเกี่ยวกับ ออโตมาตาการเรียนรู้ ฉบับแรก ได้รับการสำรวจโดยNarendraและ Thathachar (1974) ซึ่งเดิมทีได้อธิบายไว้อย่างชัดเจนว่าเป็น ออโต มาตาสถานะจำกัด^{[ 22 ]}เช่นเดียวกับการเรียนรู้แบบเสริมแรง อัลกอริทึมออโตมาตาการเรียนรู้ยังมีข้อดีในการแก้ปัญหาเมื่อไม่ทราบความน่าจะเป็นหรือรางวัล ความแตกต่างระหว่างออโตมาตาการเรียนรู้และ Q-learning คือเทคนิคแรกละเว้นหน่วยความจำของค่า Q แต่จะอัปเดตความน่าจะเป็นของการกระทำโดยตรงเพื่อค้นหาผลลัพธ์การเรียนรู้ ออโตมาตาการเรียนรู้เป็นแผนการเรียนรู้ที่มีการพิสูจน์การบรรจบกันอย่างเข้มงวด^{[ 23 ]}

ในทฤษฎีการเรียนรู้เกี่ยวกับออโตมาตา ออโตมาตาแบบสุ่มประกอบด้วย:

• เซตxของข้อมูลป้อนเข้าที่เป็นไปได้
• ชุด Φ = { Φ ₁ , ..., Φ _s } ของสถานะภายในที่เป็นไปได้
• เซต α = { α ₁ , ..., α _r } ของผลลัพธ์หรือการกระทำที่เป็นไปได้ โดยที่r ≤ s
• เวกเตอร์ความน่าจะเป็นสถานะเริ่มต้นp (0) = ≪ p ₁ (0), ..., p _s (0) ≫,
• ฟังก์ชันที่คำนวณได้Aซึ่งหลังจากแต่ละช่วงเวลาtจะสร้างp ( t +1) จากp ( t ) อินพุตปัจจุบัน และสถานะปัจจุบัน และ
• ฟังก์ชันG : Φ → α ซึ่งสร้างเอาต์พุตในแต่ละช่วงเวลา

สถานะของออโตมาตอนดังกล่าวสอดคล้องกับสถานะของ " กระบวนการมาร์คอฟ แบบสถานะไม่ต่อเนื่องและพารามิเตอร์ไม่ต่อเนื่อง " ^{[ 24 ]}ในแต่ละขั้นตอนเวลาt = 0,1,2,3,... ออโตมาตอนจะอ่านอินพุตจากสภาพแวดล้อม อัปเดต P( t ) เป็น P( t + 1) โดยAเลือกสถานะถัดไปแบบสุ่มตามความน่าจะเป็น P( t + 1) และส่งออกการกระทำที่สอดคล้องกัน ในทางกลับกัน สภาพแวดล้อมของออโตมาตอนจะอ่านการกระทำและส่งอินพุตถัดไปไปยังออโตมาตอน^{[ 23 ]}

นอกเหนือจากรางวัลแล้ว กระบวนการตัดสินใจแบบมาร์คอฟยังสามารถเข้าใจได้ในแง่ของทฤษฎีหมวดหมู่กล่าวคือ ให้แทนโมโนอิดอิสระที่มีเซตตัวสร้างAและ ให้Distแทนหมวดหมู่ไคลส์ลีของโมนาดกิรีจากนั้นฟังก์ชันเตอร์จะเข้ารหัสทั้งเซตSของสถานะและฟังก์ชันความน่าจะเป็นP${\displaystyle (S,A,P)}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {A}}\to \mathbf {Dist} }$

ด้วยวิธีนี้ กระบวนการตัดสินใจแบบมาร์คอฟสามารถขยายจากโมโนอิด (หมวดหมู่ที่มีวัตถุเดียว) ไปสู่หมวดหมู่ใดๆ ก็ได้ เราอาจเรียกผลลัพธ์นี้ว่ากระบวนการตัดสินใจแบบมาร์คอฟที่ขึ้นอยู่กับบริบทเพราะการเปลี่ยนจากวัตถุหนึ่งไปยังอีกวัตถุหนึ่งจะเปลี่ยนชุดของการกระทำที่มีอยู่และชุดของสถานะที่เป็นไปได้ ${\displaystyle ({\mathcal {C}},F:{\mathcal {C}}\to \mathbf {Dist} )}$${\displaystyle {\mathcal {C}}}$

คำศัพท์และสัญลักษณ์สำหรับ MDP ยังไม่เป็นที่ตกลงกันอย่างเด็ดขาด มีสองแนวทางหลัก — แนวทางหนึ่งเน้นปัญหาการหาค่าสูงสุดจากบริบทต่างๆ เช่น เศรษฐศาสตร์ โดยใช้คำว่า การกระทำ รางวัล คุณค่า และเรียกตัวประกอบส่วนลดว่าβหรือγในขณะที่อีกแนวทางหนึ่งเน้นปัญหาการหาค่าต่ำสุดจากวิศวกรรมและการนำทาง โดยใช้คำว่า การควบคุม ต้นทุน ต้นทุนที่ต้องเดินทาง และเรียกตัวประกอบส่วนลดว่าαนอกจากนี้ สัญลักษณ์สำหรับความน่าจะเป็นของการเปลี่ยนสถานะก็แตกต่างกันไป

ในบทความนี้	ทางเลือก	ความคิดเห็น
การกระทำก	ควบคุมคุณ
รางวัลR	ต้นทุนg	gคือค่าลบของR
ค่าV	ค่าใช้จ่ายต่อการเดินทางJ	Jคือค่าลบของV
นโยบายπ	นโยบายμ
ปัจจัยส่วนลดγ	ปัจจัยส่วนลดα
ความน่าจะเป็นของการเปลี่ยนสถานะ${\displaystyle P_{a}(s,s')}$	ความน่าจะเป็นของการเปลี่ยนสถานะ${\displaystyle p_{ss'}(a)}$

นอกจากนี้ บางครั้งความน่าจะเป็นของการเปลี่ยนสถานะจะเขียนเป็นหรือในบางกรณีที่พบได้น้อย จะเขียนว่า${\displaystyle \Pr(s,a,s')}$${\displaystyle \Pr(s'\mid s,a)}$${\displaystyle p_{s's}(a).}$

• เบลล์แมน, อาร์. (1957), การเขียนโปรแกรมเชิงพลวัต , สำนักพิมพ์มหาวิทยาลัยพรินซ์ตัน, ISBN 978-0-486-42809-3{{citation}}: ISBN / Date incompatibility (help)ฉบับปกอ่อนของสำนักพิมพ์ Dover (2003)

• Bellman., RE (2003) [1957]. การเขียนโปรแกรมเชิงพลวัต (ฉบับปกอ่อนของ Dover). Princeton, NJ: Princeton University Press. ISBN 978-0-486-42809-3.
• Bertsekas, D. (1995). การเขียนโปรแกรมเชิงพลวัตและการควบคุมที่เหมาะสมที่สุดเล่ม 2. MA: Athena.
• Derman, C. (1970). กระบวนการตัดสินใจแบบมาร์โคเวียนสถานะจำกัด . สำนักพิมพ์ Academic Press.
• Feinberg, EA; Shwartz, A., บรรณาธิการ (2002). คู่มือเกี่ยวกับกระบวนการตัดสินใจแบบมาร์คอฟ . บอสตัน, แมสซาชูเซตส์: Kluwer. ISBN 9781461508052.
• Guo, X.; Hernández-Lerma, O. (2009). กระบวนการตัดสินใจแบบมาร์คอฟในเวลาต่อเนื่องการสร้างแบบจำลองเชิงสุ่มและความน่าจะเป็นประยุกต์ Springer. ISBN 9783642025464.
• Meyn, SP (2007). เทคนิคการควบคุมสำหรับเครือข่ายที่ซับซ้อน . สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์. ISBN 978-0-521-88441-9เก็บถาวรจากต้นฉบับเมื่อวันที่ 19 มิถุนายน 2553ภาคผนวกประกอบด้วยบทสรุปย่อของ"Meyn & Tweedie"จัดเก็บจากต้นฉบับเมื่อวันที่ 18 ธันวาคม 2012
• Puterman., ML (1994). กระบวนการตัดสินใจแบบมาร์คอฟ . Wiley.
• Ross, SM (1983). บทนำสู่การเขียนโปรแกรมเชิงพลวัตแบบสุ่ม (PDF)สำนักพิมพ์ Academic press. เก็บถาวรจากต้นฉบับ(PDF)เมื่อ 2022-03-04 สืบค้นเมื่อ2019-01-19
• Sutton, RS; Barto, AG (2017). การเรียนรู้แบบเสริมแรง: บทนำ . เคมบริดจ์, แมสซาชูเซตส์: สำนักพิมพ์ MIT.
• Tijms., HC (2003). หลักสูตรเบื้องต้นเกี่ยวกับแบบจำลองสุ่ม . Wiley. ISBN 9780470864289.