📊 statistics

Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions

यह शोध पत्र वितरण रूप से सुदृढ़ (distributionally robust) औसत-पुरस्कार मार्कोव निर्णय प्रक्रियाओं में $\varepsilon$ -इष्टतम नीतियों को सीखने के लिए मिनिमैक्स-इष्टतम नमूना जटिलता (minimax-optimal sample complexity) स्थापित करता है, जो एक शासन-निर्भर (regime-dependent) जटिलता सीमा को प्रकट करता है जो विक्षोभ पैमाने (perturbation scale) $\sigma H_0$ के आधार पर नाममात्र (nominal) से सुदृढ़ व्यवहार में परिवर्तित होती है, और इन दरों को नवीन स्पैन-सूचित (span-informed) और स्पैन-अज्ञेय (span-agnostic) प्लग-इन रिडक्शन प्रक्रियाओं के माध्यम से प्राप्त करता है।

मूल लेखक: Yuepeng Yang, Yuxin Chen, Yuejie Chi

प्रकाशित 2026-08-10

📖 4 मिनट में पढ़ें☕ कॉफ़ी ब्रेक में पढ़ें

CC BY 4.0

मूल लेखक: Yuepeng Yang, Yuxin Chen, Yuejie Chi

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

कल्पना कीजिए कि आप एक रोबोट को भूलभुलैया (maze) में नेविगेट करने के लिए प्रशिक्षित कर रहे हैं। एक वीडियो गेम की आदर्श दुनिया में, दीवारें अपनी जगह पर टिकी रहती हैं, फर्श हमेशा सूखा रहता है, और रोबोट को पता होता है कि उसका हर कदम कहाँ लैंड करेगा। लेकिन वास्तविक दुनिया में, चीजें अव्यवस्थित होती हैं। फर्श फिसलन भरा हो सकता है, कोई दरवाजा थोड़ा अटका हुआ हो सकता है, या हवा का एक झोंका रोबोट को रास्ते से भटका सकता है। यदि आप अपने रोबोट को केवल "आदर्श" मानचित्र पर प्रशिक्षित करते हैं, तो वास्तविक दुनिया की थोड़ी सी भी अस्थिरता मिलते ही वह टकरा सकता है। यह रीइन्फोर्समेंट लर्निंग (Reinforcement Learning) नामक एक क्षेत्र का मूल है, जहाँ एजेंट परीक्षण और त्रुटि (trial and error) के माध्यम से सर्वोत्तम निर्णय लेना सीखते हैं।

आमतौर पर, ये एजेंट लंबे समय तक अपने कुल स्कोर को अधिकतम करने की कोशिश करते हैं, जैसे कि एक मैराथन धावक जो औसत गति को बेहतर बनाने का लक्ष्य रखता है। लेकिन यहाँ एक पेंच है: क्या होगा अगर जिस मानचित्र से उन्होंने सीखा है, वह वही मानचित्र नहीं है जिस पर वे दौड़ रहे हैं? यहीं पर डिस्ट्रीबशनल रूप से मजबूत (Distributionally Robust) सोच काम आती है। यह मानते हुए कि दुनिया बिल्कुल वैसी ही है जैसी वह दिखती है, एजेंट एक उचित त्रुटि सीमा के भीतर "सबसे खराब स्थिति" (worst-case scenario) के लिए तैयारी करता है। वह पूछता है, "क्या होगा अगर फर्श थोड़ा फिसलन भरा हो? क्या होगा अगर दरवाजा थोड़ा भारी हो?" वह एक ऐसी रणनीति सीखता है जो तब भी अच्छी तरह काम करती है जब चीजें थोड़ी गलत हो जाती हैं। वैज्ञानिक मुख्य सवाल यह पूछ रहे हैं कि: एक रोबोट को इस तरह की "सुरक्षित" रणनीति सीखने के लिए वास्तव में कितने अभ्यास (डेटा) की आवश्यकता होती है? क्या यह थोड़ा अतिरिक्त अभ्यास है, या वास्तव में मजबूत होने के लिए इसे भारी मात्रा में डेटा की आवश्यकता है?

यह शोध पत्र, जिसका शीर्षक "Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions" है, इसी प्रश्न की गहराई में जाता है। लेखक, जो येल और पेन से शोधकर्ता हैं, जासूसों की तरह यह पता लगाने की कोशिश कर रहे हैं कि सुरक्षा की सटीक "कीमत" क्या है। उन्होंने पाया कि आवश्यक डेटा दो मुख्य चीजों पर निर्भर करता है: वातावरण कितना "अनिश्चित" या अप्रत्याशित है (अनिश्चितता), और रोबोट का प्रदर्शन कहाँ से शुरू होने पर कितना भिन्न होता है (बायस स्पैन/bias span)।

उन्होंने सीखने के दो अलग-अलग "क्षेत्रों" (zones) की खोज की। हाई-टॉलरेंस ज़ोन (High-Tolerance Zone) में, रोबोट को थोड़ा अपूर्ण होने की अनुमति है। यहाँ, आवश्यक डेटा अपेक्षाकृत कम है, जैसा कि आपको एक सामान्य, गैर-मजबूत रणनीति सीखने के लिए चाहिए होता है। यह एक शांत दिन पर साइकिल चलाना सीखने जैसा है; आपको हवा की बहुत चिंता करने की आवश्यकता नहीं है। हालाँकि, लो-टॉलरेंस ज़ोन (Low-Tolerance Zone) में, रोबोट को तब भी पूर्ण होना चाहिए जब हवा तेज़ चल रही हो। यहाँ, डेटा की आवश्यकता काफी बढ़ जाती है। लेखकों ने सिद्ध किया कि इतना सुरक्षित होने के लिए, रोबोट को अतिरिक्त डेटा की आवश्यकता होती है जो अनिश्चितता के वर्ग (square) के साथ बढ़ता है। पूर्ण सुरक्षा के लिए यह एक बड़ी कीमत है, लेकिन उन्होंने यह भी सिद्ध किया कि यह न्यूनतम आवश्यक लागत है—आप गणित को दरकिनार नहीं कर सकते।

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

संक्षेप में, यह शोध पत्र केवल अनुमान नहीं लगाता; यह गणितीय प्रमाण प्रदान करता है कि एक मजबूत नीति (robust policy) सीखने के लिए वास्तव में कितने नमूनों (samples) की आवश्यकता होती है। उन्होंने दिखाया कि पिछले तरीके या तो बहुत अधिक डेटा का उपयोग कर रहे थे या बहुत कम, और उन्होंने "गोल्डिलॉक्स" (Goldilocks) समाधान प्रदान किया: काम के लिए बिल्कुल सही मात्रा में डेटा, चाहे वातावरण शांत हो या अराजक। उनके निष्कर्षों का समर्थन कठोर गणितीय प्रमाणों और कंप्यूटर सिमुलेशन दोनों द्वारा किया गया था, जिन्होंने पुष्टि की कि उनके सिद्धांत व्यवहार में भी सही साबित होते हैं।

तकनीकी सारांश: रोबस्ट एवरेज-रिवॉर्ड मार्कोव डिसीजन प्रोसेस (MDPs)

समस्या का निरूपण
यह कार्य एक जनरेटिव मॉडल सेटिंग के तहत $\epsilon$ -इष्टतम नीति (policy) सीखने के लिए डिस्ट्रीशनली रोबस्ट एवरेज-रिवॉर्ड मार्कोव डिसीजन प्रोसेस (AMDPs) की सांख्यिकीय जटिलता की जांच करता है। एजेंट एक नाममात्र (nominal) वातावरण में कार्य करता है जो एक ट्रांजिशन कर्नेल $P^0$ और रिवॉर्ड फंक्शन $r$ द्वारा परिभाषित है। हालांकि, वास्तविक वातावरण की गति अनिश्चित है और $P^0$ पर केंद्रित एक निर्धारित अनिश्चितता सेट $\mathcal{P}$ के भीतर हो सकती है। विशेष रूप से, यह शोध पत्र $(s, a)$ -रेक्टेंगुलर टोटल-वेरिएशन (TV) अनिश्चितता सेट पर विचार करता है जिसका रेडियस (त्रिज्या) अधिकतम $\sigma$ है।

उद्देश्य रोबस्ट एवरेज रिवॉर्ड को अधिकतम करना है, जिसे $\mathcal{P}$ के सभी ट्रांजिशन कर्नेल के लिए सबसे खराब स्थिति वाले दीर्घकालिक औसत रिवॉर्ड के रूप में परिभाषित किया गया है:
$\rho^{\pi, \sigma} := \inf_{P \in \mathcal{P}} \lim_{T \to \infty} \mathbb{E}^\pi_P \left[ \frac{1}{T} \sum_{t=0}^{T-1} r(s_t, a_t) \right]$
सीखने का लक्ष्य $N$ सैंपल प्रति स्टेट-एक्शन पेयर का उपयोग करके एक ऐसी नीति $\hat{\pi}$ की गणना करना है कि $\rho^{\star, \sigma} - \rho^{\hat{\pi}, \sigma} \leq \epsilon$ हो, जहाँ $\rho^{\star, \sigma}$ इष्टतम रोबस्ट एवरेज रिवॉर्ड है।

मुख्य पैरामीटर और संरचनात्मक धारणाएं
विश्लेषण दो महत्वपूर्ण संरचनात्मक मापदंडों पर आधारित है:

नाममात्र इष्टतम बायस स्पैन ( $H_0$ ): उस बायस फंक्शन का स्पैन जो नाममात्र बेलमैन ऑप्टिमैलिटी इक्वेशन को संतुष्ट करता है।
रोबस्ट इष्टतम बायस स्पैन ( $H_\sigma$ ): उस बायस फंक्शन का स्पैन जो रोबस्ट बेलमैन ऑप्टिमैलिटी इक्वेशन को संतुष्ट करता है।

शोध पत्र स्थापित करता है कि $H_0$ और $H_\sigma$ आम तौर पर स्वतंत्र हैं; कोई भी दूसरे को नियंत्रित नहीं करता है। एक महत्वपूर्ण परटर्बेशन स्केल (perturbation scale) की पहचान की गई है जो $\sigma H_0$ है, जो सीखने की समस्या को दो अलग-अलग रेजिम (regimes) में विभाजित करता है:

हाई-टोलरेंस रेजिम ( $\epsilon \gtrsim \sigma H_0$ ): अनिश्चितता के कारण होने वाला परटर्बेशन लक्षित सटीकता के सापेक्ष छोटा है।
लो-टोलरेंस रेजिम ( $\epsilon \lesssim \sigma H_0$ ): परटर्बेशन महत्वपूर्ण है, और केवल नाममात्र अनुकूलन (nominal optimization) रोबस्ट इष्टतमता सुनिश्चित करने के लिए पर्याप्त नहीं है।

कार्यप्रणाली: रिडक्शन-आधारित प्लग-इन प्रक्रियाएं
मुख्य कार्यप्रणाली योगदान एक रिडक्शन फ्रेमवर्क है जो कठिन रोबस्ट एवरेज-रिवॉर्ड समस्या को अधिक सुलभ रोबस्ट डिस्काउंटेड MDP (DMDP) समस्या में बदल देता है। लेखक इस रिडक्शन पर आधारित दो एल्गोरिदम प्रस्तावित करते हैं:

स्पैन-इन्फॉर्म्ड प्रोसीजर (एल्गोरिदम 1): यह मानता है कि $H_0$ और $H_\sigma$ ज्ञात हैं। यह एक नाममात्र रिडक्शन (एम्पिरिकल कर्नेल के साथ एक मानक DMDP को हल करना) और एक रोबस्ट रिडक्शन (अनिश्चितता सेट पर एक DMDP को हल करना) के बीच अनुकूल रूप से चयन करता है। चुनाव $H_0$ और $H_\sigma$ के क्रम और टोलरेंस रेजिम पर निर्भर करता है। डिस्काउंट फैक्टर $\gamma$ को प्रासंगिक स्पैन पैरामीटर के आधार पर कैलिब्रेट किया जाता है (जैसे, $\gamma = 1 - \epsilon/(3H_\sigma)$ )।
स्पैन-एग्नोस्टिक प्रोसीजर (एल्गोरिदम 2): यह $H_0$ या $H_\sigma$ के ज्ञान के बिना कार्य करता है। यह डिस्काउंट फैक्टर्स के एक डायैडिक ग्रिड (dyadic grid) पर दोनों नाममात्र और रोबस्ट रिडक्शन से उम्मीदवार नीतियों का एक सेट बनाता है। इसके बाद यह एक अलग डेटा बैच से प्राप्त "एंकर सर्टिफिकेट" का उपयोग करके रोबस्ट एवरेज रिवॉर्ड पर लोअर-कॉन्फिडेंस बाउंड (LCB) के माध्यम से सर्वश्रेष्ठ नीति का चयन करता है। यह एल्गोरिदम को सही रिडक्शन और डिस्काउंट फैक्टर चुनने के लिए अनुकूल रूप से सक्षम बनाता है।

कठोर बाउंड प्राप्त करने के लिए विश्लेषण तीन प्रमुख तकनीकी सुधारों का लाभ उठाता है:

वेरिएंस टर्म्स को टाइट करने के लिए रोबस्ट डिस्काउंटेड समस्या की नाममात्र संदर्भ समाधान (एंकर) के साथ तुलना करना।
प्रभावी होराइजन के बजाय उनके स्पैन ( $H_\sigma$ ) के माध्यम से डिस्काउंटेड वैल्यू फंक्शन्स को नियंत्रित करना।
इन स्पैन द्वारा शासित लोकलाइज्ड कंसंट्रेशन बाउंड्स का उपयोग करना।

मुख्य परिणाम: मिनिमैक्स सैंपल कॉम्प्लेक्सिटी
यह शोध पत्र लॉगरिदमिक कारकों तक, मिनिमैक्स सैंपल कॉम्प्लेक्सिटी $N_{SA}$ (प्रति स्टेट-एक्शन पेयर सैंपल) के लिए मिलान वाले अपर और लोअर बाउंड प्रदान करता है। जटिलता को $H_0$ और $H_\sigma$ के क्रम और टोलरेंस रेजिम के आधार पर चार-रेजिम सारांश द्वारा वर्णित किया गया है:

$N_{SA} \asymp \frac{SA}{\epsilon^2} \times \begin{cases} \min\{H_0, H_\sigma\} & \text{यदि } \epsilon \gtrsim \sigma H_0 \quad (\text{High Tolerance}) \\ \min\{H_0, H_\sigma\} + \sigma H_\sigma^2 & \text{यदि } \epsilon \lesssim \sigma H_0 \quad (\text{Low Tolerance}) \end{cases}$

हाई-टोलरेंस रेजिम: जटिलता रैखिक स्पैन टर्म $\min\{H_0, H_\sigma\}$ द्वारा हावी होती है। यदि $H_\sigma \leq H_0$ है, तो रोबस्ट रिडक्शन नाममात्र वाले से बेहतर (tight) बाउंड देता है।
लो-टोलरेंस रेजिम: एक अतिरिक्त "रोबस्टनेस-विशिष्ट" टर्म $\sigma H_\sigma^2$ दिखाई देता है, जो उच्च परिशुद्धता की आवश्यकता होने पर डिस्ट्रिब्यूशनल अनिश्चितता को संभालने की लागत का प्रतिनिधित्व करता है।
लोअर बाउंड: लेखक एक मिनिमैक्स लोअर बाउंड सिद्ध करते हैं जो अपर बाउंड से मेल खाता है, जिससे यह स्थापित होता है कि लो-टोलरेंस रेजिम में $\sigma H_\sigma^2$ टर्म मौलिक है और इसे टाला नहीं जा सकता। यह डिस्ट्रीशनली रोबस्ट AMDPs के सांख्यिकीय सीमाओं को चरित्रित करने वाला पहला लोअर बाउंड है।

महत्व और दावे
यह शोध पत्र दावा करता है कि यह डिस्ट्रीशनली रोबस्ट AMDPs के लिए मिनिमैक्स-ऑप्टिमल सैंपल कॉम्प्लेक्सिटी का पहला चरित्रण प्रदान करता है। मुख्य योगदान हैं:

सैंपल कॉम्प्लेक्सिटी गैप का समाधान: पिछले रोबस्ट अपर बाउंड्स (जैसे, Roch et al., 2025, 2026) हाई और लो टोलरेंस के बीच अंतर किए बिना रोबस्ट स्पैन पैरामीटर्स ( $H_{Roch}^2$ या $H_{RHI}^2$ ) पर द्विघात (quadratically) रूप से निर्भर थे। यह कार्य हाई-टोलरेंस रेजिम में $\min\{H_0, H_\sigma\}$ पर रिफाइनमेंट करता है और लो-टोलरेंस रेजिम में सटीक $\sigma H_\sigma^2$ लागत की पहचान करता है।
अनुकूली एल्गोरिदम (Adaptive Algorithms): प्रस्तावित स्पैन-एग्नोस्टिक प्रोसीजर (एल्गोरिदम 2) स्पैन पैरामीटर्स के पूर्व ज्ञान के बिना इन इष्टतम दरों को प्राप्त करता है, जो रेजिम और $H_0$ एवं $H_\sigma$ के सापेक्ष परिमाण के आधार पर स्वचालित रूप से अनुकूलित होता है।
व्यापकता (Generality): परिणाम तब भी मान्य रहते हैं जब केवल $H_\sigma$ को बाउंड माना जाता है, जिससे $\tilde{\Theta}(SA(H_\sigma + \sigma H_\sigma^2)\epsilon^{-2})$ की जटिलता प्राप्त होती है।

नियंत्रित सिमुलेशन पर प्रयोगात्मक परिणाम $\min\{H_0, H_\sigma\}$ पर रैखिक निर्भरता और लो-टोलरेंस रेजिम में $\sigma H_\sigma^2$ पर द्विघात निर्भरता के साथ-साथ स्पैन-एग्नोस्टिक एल्गोरिदम की अनुकूलता की पुष्टि करते हैं। लेखक नोट करते हैं कि भविष्य का कार्य युग्मित अनिश्चितता संरचनाओं (coupled uncertainty structures) और ऑनलाइन (रिग्रेट-आधारित) सेटिंग्स का पता लगा सकता है, लेकिन वर्तमान कार्य सख्ती से जनरेटिव मॉडल सेटिंग पर केंद्रित है।

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