अनुक्रमिक निर्णय लेना (MDPs)

अनुक्रमिक निर्णय लेना यह औपचारिक रूप देता है कि एक एजेंट को स्टोकेस्टिक वातावरण में समय के साथ कैसे कार्य करना चाहिए, जिसमें मार्कोव निर्णय प्रक्रियाओं का उपयोग किया जाता है, जिसमें क्रियाएं पुरस्कार देती हैं और संभाव्य रूप से स्थिति को बदलती हैं, ताकि दीर्घकालिक अपेक्षित पुरस्कार को अधिकतम करने वाली नीति की गणना की जा सके।

Definition

एक मार्कोव निर्णय प्रक्रिया को राज्यों, क्रियाओं, एक संक्रमण संभाव्यता फ़ंक्शन और एक पुरस्कार फ़ंक्शन द्वारा परिभाषित किया जाता है; अनुक्रमिक निर्णय लेना एक ऐसी नीति चाहता है जो राज्यों को उन क्रियाओं से मैप करती है जो मॉडल को देखते हुए अपेक्षित संचयी (आमतौर पर छूट वाले) पुरस्कार को अधिकतम करती हैं।

Scope

यह विषय समय के साथ निर्णय-सैद्धांतिक योजना को शामिल करता है: राज्यों, क्रियाओं, संक्रमण संभावनाओं, पुरस्कारों और छूट का मार्कोव निर्णय प्रक्रिया (MDP) मॉडल; नीतियां और मूल्य कार्य; इष्टतम व्यवहार को दर्शाने वाले बेलमैन समीकरण; और ज्ञात मॉडल को हल करने के लिए मूल्य पुनरावृति और नीति पुनरावृति के गतिशील-प्रोग्रामिंग एल्गोरिदम। यह आंशिक रूप से अवलोकन योग्य MDPs (POMDPs) और विश्वास-स्थिति योजना का भी परिचय देता है। ध्यान तब योजना बनाने पर है जब मॉडल दिया गया हो; ज्ञात मॉडल के बिना अनुभव से एक नीति सीखना सुदृढीकरण अधिगम है, जो मशीन-लर्निंग उपक्षेत्र से संबंधित है।

Core questions

• स्टोकेस्टिक संक्रमणों के तहत समय के साथ कार्य करने को राज्यों, क्रियाओं, संक्रमणों और पुरस्कारों के रूप में कैसे मॉडल किया जाता है?
• बेलमैन इष्टतमता समीकरण एक इष्टतम नीति के मूल्य के बारे में क्या कहता है?
• जब मॉडल ज्ञात हो तो मूल्य पुनरावृति और नीति पुनरावृति एक इष्टतम नीति की गणना कैसे करते हैं?
• आंशिक अवलोकनशीलता POMDPs और विश्वास राज्यों पर योजना बनाने की ओर कैसे ले जाती है?

Key concepts

• राज्य, क्रियाएं, संक्रमण, पुरस्कार
• नीति
• मूल्य कार्य
• छूट कारक
• बेलमैन समीकरण
• मूल्य पुनरावृति
• नीति पुनरावृति
• POMDP और विश्वास स्थिति

Key theories

बेलमैन इष्टतमता समीकरण

एक राज्य का इष्टतम मूल्य सर्वोत्तम तात्कालिक पुरस्कार और अगले राज्य के छूट वाले अपेक्षित इष्टतम मूल्य के बराबर होता है; यह पुनरावर्ती संबंध इष्टतम अनुक्रमिक व्यवहार को दर्शाता है और गतिशील-प्रोग्रामिंग समाधानों की नींव है।

मूल्य और नीति पुनरावृति

एक ज्ञात MDP के लिए, मूल्य पुनरावृति अभिसरण तक बेलमैन अपडेट को बार-बार लागू करती है, और नीति पुनरावृति नीति मूल्यांकन और सुधार को वैकल्पिक करती है; दोनों एक इष्टतम नीति खोजने की गारंटी देते हैं।

आंशिक रूप से अवलोकन योग्य MDPs

जब राज्य सीधे अवलोकन योग्य नहीं होता है, तो योजना एक विश्वास स्थिति (राज्यों पर एक वितरण) पर की जाती है जिसे अवलोकनों से अपडेट किया जाता है; ऐसे POMDPs को हल करना पूरी तरह से अवलोकन योग्य मामले की तुलना में कहीं अधिक कठिन है लेकिन यथार्थवादी संवेदन सीमाओं को पकड़ता है।

Clinical relevance

MDP- और POMDP-आधारित निर्णय लेना रोबोट नेविगेशन और नियंत्रण, स्वचालित संवाद प्रबंधन, रखरखाव और सूची निर्णयों और संसाधन आवंटन का आधार है, और निर्णय-सैद्धांतिक योजना नींव प्रदान करता है जिस पर सुदृढीकरण अधिगम तब निर्मित होता है जब पर्यावरण मॉडल को इसके बजाय सीखा जाना चाहिए।

History

अनुक्रमिक निर्णय लेना बेलमैन के गतिशील प्रोग्रामिंग (1957) और हॉवर्ड के नीति पुनरावृति (1960) से विकसित हुआ। पुटरमैन के 1994 के मोनोग्राफ ने मार्कोव निर्णय प्रक्रियाओं के सिद्धांत को समेकित किया, और केलबलिंग, लिटमैन और कैसेंड्रा (1998) ने अनिश्चित धारणा के तहत कार्य करने के लिए एक मॉडल के रूप में आंशिक रूप से अवलोकन योग्य MDPs को मुख्यधारा AI में लाया।

Key figures

• Richard Bellman
• Ronald A. Howard
• Martin L. Puterman
• Leslie P. Kaelbling
• Michael L. Littman

Seminal works

• bellman1957
• puterman1994
• kaelbling1998

Frequently asked questions

यह सुदृढीकरण अधिगम से कैसे भिन्न है?

MDPs के साथ अनुक्रमिक निर्णय लेना मानता है कि संक्रमण और पुरस्कार मॉडल ज्ञात है, इसलिए एक इष्टतम नीति को सीधे गतिशील प्रोग्रामिंग द्वारा गणना की जा सकती है। सुदृढीकरण अधिगम उस मामले को संबोधित करता है जहां मॉडल अज्ञात है और एजेंट को अनुभव से एक अच्छी नीति सीखनी चाहिए; यह MDP को अपने अंतर्निहित औपचारिकता के रूप में उपयोग करता है।

POMDP में विश्वास स्थिति क्या है?

एक आंशिक रूप से अवलोकन योग्य MDP में एजेंट वास्तविक स्थिति को नहीं देख सकता है, इसलिए यह एक विश्वास स्थिति, संभावित राज्यों पर एक संभाव्यता वितरण बनाए रखता है, जिसे क्रियाएं करने और अवलोकन प्राप्त करने पर अपडेट किया जाता है। योजना तब सीधे छिपी हुई स्थितियों के बजाय इन विश्वास स्थितियों पर होती है।