🤖 AI

Strongly Polynomial Time Complexity of Policy Iteration for $L_\infty$ Robust MDPs

यह शोध पत्र यह सिद्ध करके एक लंबे समय से खुले पड़े प्रश्न को हल करता है कि एक रोबस्ट पॉलिसी इटरेशन एल्गोरिदम एक निश्चित डिस्काउंट फैक्टर के साथ $(s, a)$ -रेक्टेंगुलर $L_\infty$ रोबस्ट मार्कोव डिसीजन प्रोसेस को स्ट्रॉन्गली पॉलीनोमियल समय में हल करता है।

मूल लेखक: Ali Asadi, Krishnendu Chatterjee, Ehsan Goharshady, Mehrdad Karrabi, Alipasha Montaseri, Carlo Pagano

प्रकाशित 2026-06-03

📖 5 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Ali Asadi, Krishnendu Chatterjee, Ehsan Goharshady, Mehrdad Karrabi, Alipasha Montaseri, Carlo Pagano

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप एक कोहरे से भरे समुद्र में एक जहाज के कप्तान हैं। आपका लक्ष्य कम से कम ईंधन खर्च करते हुए एक गंतव्य तक पहुँचना है।

एक आदर्श दुनिया में, आपके पास एक ऐसा मानचित्र होगा जो आपको ठीक-ठीक बताएगा कि हवा और धाराएँ आपको हर क्षण कैसे धकेलेंगी। कंप्यूटर वैज्ञानिक इसे मार्कोव डिसीजन प्रोसेस (MDP) कहते हैं। यह एक गणितीय तरीका है जिससे आप तब सबसे अच्छा रास्ता चुन सकते हैं जब आप जानते हों कि दुनिया कैसे काम करती है।

लेकिन वास्तविक दुनिया में, मानचित्र एकदम सटीक नहीं होता। हवा आपकी सोच से अधिक या कम तेज़ हो सकती है। यही वह अनिश्चितता है जिसे यह शोध पत्र संबोधित करता है। वे "कोहरे वाले मानचित्र" वाले मॉडल को रोबस्ट MDP (Robust MDP) कहते हैं। यहाँ आप किसी एक विशिष्ट हवा के पैटर्न को नहीं मानते, बल्कि आप यह मान लेते हैं कि हवा उस "कोहरे वाले क्षेत्र" (जिसे अनिश्चितता सेट/uncertainty set कहा जाता है) के भीतर कोई भी पैटर्न हो सकती है। आपका लक्ष्य बदल जाता है: आप केवल औसत मौसम के लिए सबसे अच्छा रास्ता नहीं चाहते; आप ऐसा रास्ता चाहते हैं जो यह गारंटी दे कि सबसे खराब मौसम में भी आपका ईंधन खत्म नहीं होगा।

समस्या: "परफेक्ट" रास्ता खोजना

इसे हल करने के लिए, आपको एक एल्गोरिदम (एक चरण-दर-चरण विधि) की आवश्यकता है ताकि सबसे अच्छी रणनीति खोजी जा सके।

पुराना तरीका: पिछले तरीके एक "काफी हद तक अच्छा" रास्ता जल्दी खोज सकते थे, लेकिन सटीक परफेक्ट रास्ता खोजना एक रहस्य बना हुआ था।
बड़ा सवाल: क्या हम एक "स्ट्रॉन्गली पॉलिनॉमियल" (strongly polynomial) समाधान पा सकते हैं, भले ही हमारे मानचित्र के अंक बहुत सटीक हों (जैसे कि दशमलव के कई स्थानों तक)? कंप्यूटर विज्ञान में, इसका अर्थ है कि इसे हल करने में लगने वाला समय केवल मानचित्र के आकार (कितने द्वीप और मार्ग हैं) पर निर्भर करता है, न कि मानचित्र पर लिखे नंबरों की जटिलता पर।

लंबे समय तक, कोई नहीं जानता था कि इन कोहरे वाले, रोबस्ट मानचित्रों के लिए "स्ट्रॉन्गली पॉलिनॉमियल" विधि मौजूद है या नहीं।

समाधान: एक स्मार्ट "पॉलिसी इटरेशन" रेसिपी

इस शोध पत्र के लेखक कहते हैं: "हाँ, हमने इसे खोज लिया है!"

उन्होंने पॉलिसी इटरेशन (Policy Iteration) नामक एक विधि का उपयोग किया। इसे सबसे अच्छे रास्ते को खोजने के लिए "हॉट एंड कोल्ड" (पास या दूर) के खेल की तरह समझें:

शुरुआत: आप एक यादृच्छिक (random) मार्ग चुनते हैं (एक "पॉलिसी")।
परीक्षण: आप गणना करते हैं कि इस मार्ग में सबसे खराब मौसम में कितना ईंधन लगेगा।
सुधार: आप अपने वर्तमान मार्ग को देखते हैं और पूछते हैं, "यदि मैं इस विशिष्ट द्वीप पर अपना मोड़ बदल दूँ, तो क्या मैं एक और भी खराब तूफान से बच सकूँगा?" यदि हाँ, तो आप मार्ग बदल देते हैं।
दोहराव: आप तब तक परीक्षण और सुधार करते रहते हैं जब तक कि आपको कोई बेहतर मार्ग न मिल जाए।

"रोबस्ट" मानचित्र में पेचीदा हिस्सा यह है कि "सबसे खराब मौसम" केवल एक चीज़ नहीं है; यह संभावनाओं का एक पूरा बादल है। लेखकों को इस सबसे खराब स्थिति की गणना करने के लिए एक विशेष, तेज़ तरीका विकसित करना पड़ा (जिसे होमोटॉपी एल्गोरिदम/Homotopy Algorithm कहा जाता है, जो एक स्मार्ट स्लाइडिंग तंत्र की तरह है जो संभावनाओं को कुशलतापूर्वक समायोजित करता है)।

जादू का नुस्खा: "पोटेंशियल फंक्शन"

सबसे कठिन हिस्सा यह साबित करना था कि यह "हॉट एंड कोल्ड" का खेल अनंत लूप में नहीं फँसेगा या बहुत अधिक समय नहीं लेगा।

इसे सिद्ध करने के लिए, लेखकों ने एक पोटेंशियल फंक्शन (Potential Function) नामक गणितीय उपकरण का आविष्कार किया।

उपमा: कल्पना कीजिए कि आपके मार्ग का एक "स्कोर" है जो इस बात पर आधारित है कि वह परफेक्ट रूट से कितना दूर है। हर बार जब आप अपने मार्ग में सुधार करते हैं, तो यह स्कोर कम हो जाता है।
खोज: लेखकों ने सिद्ध किया कि यह स्कोर केवल थोड़ा सा कम नहीं होता; यह एक बहुत ही अनुमानित, "चंकी" (chunk) तरीके से गिरता है। उन्होंने दिखाया कि परफेक्ट समाधान तक की "दूरी" शामिल संख्याओं के सबसे महत्वपूर्ण "बिट्स" (bits) द्वारा निर्धारित होती है।
परिणाम: क्योंकि इन "महत्वपूर्ण बिट्स" को बदलने की संख्या सीमित है, इसलिए एल्गोरिदम को एक निश्चित, प्रबंधनीय संख्या के चरणों के बाद रुकने के लिए मजबूर किया जाता है। यह अनंत काल तक इधर-उधर डोल नहीं सकता।

मुख्य निष्कर्ष

यह शोध पत्र सिद्ध करता है कि एक विशिष्ट प्रकार के अनिश्चित मानचित्र के लिए (जहाँ अनिश्चितता एक अनुमान के चारों ओर एक सरल "त्रिज्या" द्वारा परिभाषित होती है, जिसे $L_\infty$ अनिश्चितता कहा जाता है), यह "हॉट एंड कोल्ड" सुधार रेसिपी हमेशा एक ऐसे समय में समाप्त होती है जो मानचित्र के आकार के सीधे आनुपातिक है।

इससे कोई फर्क नहीं पड़ता कि आपके मानचित्र के नंबर सरल (1.5) हैं या अविश्वसनीय रूप से जटिल (1.5000000001)। सबसे खराब स्थिति के लिए योजना बनाने में लगने वाला समय केवल आपके पास कितने द्वीप और मार्ग हैं उस पर निर्भर करता है, न कि डेटा की सटीकता पर।

संक्षेप में: लेखकों ने एक गणितीय गारंटी खोजी है कि अनिश्चितता के तहत निर्णय लेने के क्षेत्र में एक विशिष्ट, स्मार्ट योजना बनाने का तरीका न केवल तेज़ है, बल्कि यह गणितीय रूप से गारंटीकृत है कि वह तेज़ होगा, चाहे आपके डेटा की सटीकता कितनी भी अधिक क्यों न हो। यह उस बड़े पहेली को हल करता है जो वर्षों से अनिश्चितता के तहत निर्णय लेने के क्षेत्र में खुली पड़ी थी।

तकनीकी सारांश: $L_\infty$ रोबस्ट MDPs के लिए पॉलिसी इटरेशन की स्ट्रॉन्गली पॉलिनोमियल टाइम कॉम्प्लेक्सिटी

समस्या विवरण
यह शोध पत्र अनिश्चितता के तहत अनुक्रमिक निर्णय लेने (sequential decision-making) के एक मौलिक खुले प्रश्न को संबोधित करता है: एक निश्चित डिस्काउंट फैक्टर वाले $L_\infty$ अनिश्चितता सेट्स (uncertainty sets) वाले रोबस्ट मार्कोव डिसीजन प्रोसेस (RMDPs) के लिए स्ट्रॉन्गली पॉलिनोमियल-टाइम एल्गोरिदम का अस्तित्व। जबकि शास्त्रीय MDPs के लिए सटीक मान गणना (exact value computation) हेतु स्ट्रॉन्गली पॉलिनोमियल एल्गोरिदम मौजूद हैं (ये, 2011), और LP के माध्यम से RMDPs के लिए पॉलिनोमियल-टाइम एल्गोरिदम उपलब्ध हैं, यह प्रश्न कि क्या RMDPs में स्ट्रॉन्गली पॉलिनोमियल एल्गोरिदम उपलब्ध हैं (जहाँ अंकगणितीय ऑपरेशन्स की संख्या इनपुट गुणांकों के बिट-लेंथ से स्वतंत्र होती है), अनसुलझा रहा। विशेष रूप से, $L_\infty$ अनिश्चितता पॉलीटोप्स (polytopes) को दर्शाने के लिए आवश्यक क्रियाओं (actions) की घातांकीय संख्या के कारण, टर्न-बेस्ड स्टोकेस्टिक गेम्स में $(s, a)$ -रेक्टेंगुलर RMDPs को कम करने के पिछले प्रयास पॉलिनोमियल-टाइम रिडक्शन देने में विफल रहे।

मॉडल और परिभाषाएँ
लेखक $(s, a)$ -रेक्टेंगुलर RMDPs पर ध्यान केंद्रित करते हैं जिनमें $L_\infty$ अनिश्चितता सेट्स होते हैं।

$(s, a)$ -रेक्टेंगुलरिटी: वातावरण प्रत्येक स्टेट-एक्शन पेयर $(s, a)$ के लिए स्वतंत्र रूप से ट्रांजिशन प्रोबेबिलिटी चुनता है, जिससे डायनेमिक प्रोग्रामिंग संरचना बनी रहती है।
$L_\infty$ अनिश्चितता: प्रत्येक स्टेट-एक्शन पेयर $(s, a)$ के लिए, वास्तविक ट्रांजिशन वेक्टर एक नाममात्र अनुमान $\hat{P}_{s,a}$ के चारों ओर $\delta_{s,a}$ त्रिज्या वाले $L_\infty$ बॉल के भीतर स्थित होता है।
उद्देश्य: एजेंट एक प्रतिकूल वातावरण नीति $\tau$ के विरुद्ध सबसे खराब स्थिति (worst-case) के अपेक्षित डिस्काउंटेड कॉस्ट को कम करने के लिए एक नीति $\sigma$ खोजता है।
स्ट्रॉन्गली पॉलिनोमियल टाइम: एक एल्गोरिदम स्ट्रॉन्गली पॉलिनोमियल है यदि अंकगणितीय ऑपरेशन्स की संख्या वेरिएबल्स और बाधाओं (constraints) के पॉलिनोमियल में सीमित है, और गणना के दौरान संख्याओं का आकार इनपुट गुणांकों के मानों से स्वतंत्र है।

कार्यप्रणाली (Methodology)
यह शोध पत्र रोबस्ट पॉलिसी इटरेशन (PI) एल्गोरिदम का विश्लेषण करता है, जो पॉलिसी इवैल्यूएशन और पॉलिसी इम्प्रूवमेंट के बीच बारी-बारी से कार्य करता है।

रोबस्ट मार्कोव चेन्स (RMCs): लेखक पहले सरल मामले का विश्लेषण करते हैं जहाँ एजेंट के पास प्रत्येक स्टेट के लिए एक ही एक्शन होता है (RMC-PI)।
- पॉलिसी इम्प्रूवमेंट: बिट प्रिसिजन पर निर्भर करने वाले लीनियर प्रोग्राम (LP) को हल करने के बजाय, लेखक एक होमोटॉपी एल्गोरिदम (Behzadian et al., 2021) का उपयोग करते हैं ताकि इष्टतम वातावरण प्रतिक्रिया (optimal environment response) की गणना की जा सके। यह एल्गोरिदम $O(n \log n)$ में चलता है और ऐसी नीतियों का उत्पादन करता है जिनमें एक विशिष्ट संरचनात्मक गुण होता है: ट्रांजिशन प्रोबेबिलिटीज को तब तक समायोजित किया जाता है जब तक कि सीमाओं (0, 1, या अनिश्चितता त्रिज्या) को हिट न किया जाए, जिसमें मास (mass) को "डोनर" स्टेट्स से "रिसीवर" स्टेट्स की ओर स्थानांतरित किया जाता है।
- पोटेंशियल फंक्शन: मास ट्रांसफर को ट्रैक करने के लिए एक नया पोटेंशियल फंक्शन $f_\tau(s, s', s'')$ पेश किया गया है। यह फंक्शन कम इष्टतम वैल्यू वाले स्टेट से अधिक इष्टतम वैल्यू वाले स्टेट की ओर मास शिफ्ट करने से होने वाले संभावित सुधार को मापता है।
- कॉम्बिनेटोरियल बाउंड्स: लेखक सिद्ध करते हैं कि वर्तमान नीति की ट्रांजिशन प्रोबेबिलिटीज और इष्टतम वाली के बीच का "डिस्क्रिपेंसी" (discrepancy) ज्यामितीय रूप से घटता है। महत्वपूर्ण रूप से, वे वास्तविक संख्याओं के साइन्ड सबसेट सम (signed subset sums) में अलग-अलग मोस्ट सिग्निफिकेंट बिट्स (MSBs) की संख्या के संबंध में एक कॉम्बिनेटोरियल लेम्मा (लेम्मा 8) स्थापित करते हैं। यह लेम्मा, जो एक अधिक सामान्य प्रमेय (थ्योरम 20/21) से प्राप्त हुआ है, MSBs की संख्या को $O(|X| \log |X|)$ द्वारा सीमित करता है।
- कन्वर्जेंस तर्क: वैल्यू एरर के ज्यामितिक संकुचन (geometric contraction) और डिस्प्रिपेंसी के संभावित MSBs की सीमित संख्या (लेम्मा 8) को जोड़कर, लेखक दिखाते हैं कि एल्गोरिदम अनिश्चित काल तक मनमाने ढंग से छोटे अपडेट नहीं कर सकता। डिस्प्रिपेंसी का MSB एक पॉलिनोमियल संख्या में ही बदल सकता है।
रोबस्ट MDPs (RMDPs): विश्लेषण को सामान्य RMDP केस (RMDP-PI) के लिए विस्तारित किया गया है।
- एल्गोरिदम वर्तमान एजेंट नीति के लिए वर्तमान RMC सब-प्रॉब्लम को हल करता है ताकि सबसे खराब स्थिति वाली वातावरण प्रतिक्रिया पाई जा सके, फिर एजेंट नीति को परिणामी लागत को कम करने के लिए अपडेट करता है।
- एक समान पोटेंशियल फंक्शन क्रियाओं (actions) के लिए परिभाषित किया गया है, जो इष्टतम एजेंट एक्शन से विचलित होने की लागत को ट्रैक करता है।
- समान तर्क लागू होता है: अधिकतम पोटेंशियल वाला एक्शन एक लॉगरिदमिक संख्या से अधिक इटरेशन तक बना नहीं रह सकता है, इससे पहले कि वैल्यू एरर संकुचन बदलाव को मजबूर करे।

प्रमुख योगदान और परिणाम

स्ट्रॉन्गली पॉलिनोमियल RMC-PI: लेखक सिद्ध करते हैं कि $n$ स्टेट्स और एक स्थिर डिस्काउंट फैक्टर $\gamma$ वाले RMCs के लिए रोबस्ट पॉलिसी इटरेशन $O(n^4 \log n \cdot \frac{\log((1-\gamma)/n^2)}{\log \gamma})$ इटरेशन्स में समाप्त होता है। चूंकि प्रत्येक इटरेशन में पॉलिनोमियल-टाइम ऑपरेशन्स (मैट्रिक्स इन्वर्जन और होमोटॉपी स्टेप्स) शामिल हैं, इसलिए कुल रनटाइम स्ट्रॉन्गली पॉलिनोमियल है।
स्ट्रॉन्गली पॉलिनोमियल RMDP-PI: परिणाम को $n$ स्टेट्स और $m$ एक्शन्स वाले सामान्य RMDPs के लिए सामान्यीकृत किया गया है। एल्गोरिदम $O(n \cdot m \cdot \frac{\log(1-\gamma)}{\log \gamma})$ इटरेशन्स में समाप्त होता है, यह स्थापित करता है कि RMDP-PI भी स्ट्रॉन्गली पॉलिनोमियल है।
कॉम्बिनेटोरियल लेम्मा: पेपर लेम्मा 8 पेश करता है, जो साइन्ड सबसेट सम्स में अलग-अलग MSBs को सीमित करने वाला एक नवीन कॉम्बिनेटोरियल परिणाम है, जो जटिलता प्रमाण के लिए केंद्रीय है। लेखक नोट करते हैं कि इस थ्योरम का एक अधिक मजबूत संस्करण स्वतंत्र रूप से एक AI रिसर्च एजेंट (Aletheia) द्वारा निकाला गया था, जो गणित में AI के योगदान को रेखांकित करता है।

महत्व और दावे
यह पेपर रोबस्ट ऑप्टिमाइज़ेशन के सिद्धांत में एक प्रमुख खुले प्रश्न को हल करने का दावा करता है। यह प्रदर्शित करके कि एक रोबस्ट पॉलिसी इटरेशन एल्गोरिदम $(s, a)$ -रेक्टेंगुलर $L_\infty$ RMDPs के लिए स्ट्रॉन्गली पॉलिनोमियल समय में समाप्त होता है, लेखक शास्त्रीय MDPs के लिए ये (Ye, 2011) के मौलिक परिणाम को रोबस्ट सेटिंग में सामान्यीकृत करते हैं। यह परिणाम महत्वपूर्ण है क्योंकि:

यह इनपुट पैरामीटर्स के बिट-लेंथ पर निर्भर किए बिना RMDPs के लिए सटीक मानों (अनुमान के बजाय) की गणना करने के लिए सैद्धांतिक गारंटी प्रदान करता है।
यह उन पिछले रिडक्शन तकनीकों की सीमाओं को दूर करता है जो क्रियाओं की घातांकीय वृद्धि के कारण विफल रहे थे।
यह स्थापित करता है कि अनंत अनिश्चितता सेट के बावजूद, रोबस्ट बेलमैन ऑपरेटर को होमोटॉपी एल्गोरिदम के कॉम्बिनेटोरियल गुणों का उपयोग करके कुशलतापूर्वक नेविगेट किया जा सकता है।

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

समस्या: "परफेक्ट" रास्ता खोजना

समाधान: एक स्मार्ट "पॉलिसी इटरेशन" रेसिपी

जादू का नुस्खा: "पोटेंशियल फंक्शन"

मुख्य निष्कर्ष

तकनीकी सारांश: L∞L_\inftyL∞​ रोबस्ट MDPs के लिए पॉलिसी इटरेशन की स्ट्रॉन्गली पॉलिनोमियल टाइम कॉम्प्लेक्सिटी

इसी तरह के और पेपर

तकनीकी सारांश: $L_\infty$ रोबस्ट MDPs के लिए पॉलिसी इटरेशन की स्ट्रॉन्गली पॉलिनोमियल टाइम कॉम्प्लेक्सिटी