📊 statistics

Minimax PAC Bounds for Learning in Exogenous Contextual MDPs

यह शोध पत्र ज्ञात और पूर्णतः अज्ञात संक्रमण गतिकी (transition dynamics) दोनों के तहत पॉलिसी इवैल्यूएशन और बेस्ट-पॉलिसी एक्सट्रैक्शन के लिए वेरिएंस-रिड्यूस्ड एल्गोरिदम पेश करके, एक्सोजेनस कॉन्टेक्स्टुअल MDPs में PAC लर्निंग के लिए मिनिमैक्स ऑप्टिमल, कॉन्टेक्स्ट-स्पेस-साइज़-इंडिपेंडेंट सैंपल कॉम्प्लेक्सिटी बाउंड्स स्थापित करता है।

मूल लेखक: Corentin Pla, Hugo Richard, Marc Abeille, Vianney Perchet

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

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

CC BY 4.0

मूल लेखक: Corentin Pla, Hugo Richard, Marc Abeille, Vianney Perchet

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

कल्पना कीजिए कि आप एक जटिल बोर्ड गेम खेल रहे हैं, जैसे कि टेट्रिस का एक उच्च-दांव वाला संस्करण या कोई रणनीति वाला खेल। इस खेल में, आप एक पात्र (एजेंट) को नियंत्रित करते हैं जो एक मानचित्र (अवस्था/स्टेट) पर घूमता है। आप निर्णय (क्रियाएं/एक्शन) लेते हैं ताकि अंक (पुरस्कार/रिवॉर्ड्स) प्राप्त कर सकें।

आमतौर पर, इन खेलों में नियम तय होते हैं। यदि आप बाईं ओर जाते हैं, तो आप बाईं ओर जाते हैं। लेकिन इस शोध पत्र की दुनिया में, जिसका यह अध्ययन करता है, एक मोड़ है: बाहरी कारक (external factors) आपके चारों ओर खेल को बदलते रहते हैं, और आप उन्हें नियंत्रित नहीं कर सकते।

"मौसम" का रूपक (The "Weather" Analogy)

इन बाहरी कारकों को मौसम के रूप में सोचें।

अवस्था (The State): बोर्ड पर आपके पात्र की स्थिति।
क्रिया (The Action): आपका कूदने, दौड़ने या छिपने का निर्णय लेना।
संदर्भ (The Context - मौसम): अचानक आई बारिश, एक धूप वाला दिन, या एक धुंध भरी सुबह।

मौसम बहिर्जात (exogenous) है: यह आपके साथ होता है, आपके द्वारा नहीं। यह हर टर्न में यादृच्छिक रूप से (randomly) चुना जाता है।

यदि बारिश हो रही है, तो आपकी छलांग फिसलन भरी हो सकती है (जो परिवर्तन/ट्रांजिशन को बदल देती है)।
यदि धूप खिली है, तो आपको बोनस अंक मिल सकता है (जो पुरस्कार/रिवॉर्ड को बदल देता है)।

लक्ष्य एआई (AI) को इस खेल को जीतने के लिए सबसे अच्छी रणनीति सीखने के लिए प्रशिक्षित करना है, भले ही उसे मौसम के नियमों या मौसम खेल को कैसे प्रभावित करता है, इसके बारे में पता न हो। इसे एक "ओरेकल" (एक जादुई सहायक जो उत्तर जानता है) से प्रश्न पूछकर सीखना होगा।

दो बड़े प्रश्न

शोधकर्ताओं ने पूछा: एआई को मास्टर खिलाड़ी बनने के लिए ओरेकल से कितने प्रश्न पूछने की आवश्यकता है?

उन्होंने दो अलग-अलग परिदृश्यों को देखा:

परिदृश्य 1: एआई को नियम पता हैं, लेकिन मौसम नहीं

कल्पना कीजिए कि एआई के पास गेम मैनुअल है। वह जानता है कि सूखी जमीन पर कूदना कैसे काम करता है। लेकिन वह बारिश, धूप या कोहरे की संभावना के बारे में नहीं जानता। उसे बस "मौसम वितरण" (Weather Distribution) सीखना है।

समस्या: संभावित मौसम स्थितियों की सूची (संदर्भ स्थान/Context Space) बहुत बड़ी हो सकती है। शायद मौसम के प्रकार 1,000 हों।
पुराना तरीका: आप सोच सकते हैं कि एआई को यह सीखना होगा कि प्रत्येक 1,000 मौसम प्रकार खेल को अलग-अलग कैसे प्रभावित करते हैं। इसमें बहुत समय लगेगा।
शोध पत्र की खोज: एआई को हर एक मौसम प्रकार को याद करने की आवश्यकता नहीं है! उसे केवल मौसम के औसत प्रभाव को सीखने की आवश्यकता है।
- रूपक: "हल्की बारिश," "भारी बारिश," "बूंदाबांदी" और "तूफान" में कूदना कैसा महसूस होता है, इसे याद रखने के बजाय, एआई बस दिन की "औसत बारिश" को सीख लेता है।
- परिणाम: पूछे गए प्रश्नों की संख्या इस बात पर निर्भर नहीं करती कि मौसम के कितने प्रकार हैं। चाहे मौसम के प्रकार 10 हों या 10 मिलियन, एआई उतनी ही तेजी से सीखता है। उसने एक "शॉर्टकट" ढूंढ लिया जो मौसम की सूची के आकार को अनदेखा करता है।

परिदृश्य 2: एआई कुछ भी नहीं जानता (न मैनुअल, न मौसम)

अब, कल्पना कीजिए कि एआई के पास कोई मैनुअल नहीं है। वह नहीं जानता कि कूदना कैसे काम करता है, और न ही वह मौसम को जानता है। उसे सब कुछ शून्य से सीखना है।

समस्या: यह बहुत कठिन है। एआई को यह सीखना होगा कि खेल के तंत्र (mechanics) कैसे काम करते हैं और मौसम उन्हें कैसे बदलता है।
शोध पत्र की खोज: इस अव्यवस्थपूर्ण, अज्ञात दुनिया में भी, एआई को अभी भी मौसम के प्रकारों की संख्या की चिंता करने की आवश्यकता नहीं है।
- रणनीति: एआई बोर्ड पर प्रत्येक स्थिति के लिए एक "औसत मूल्य" (Average Value) सीखता है (एक क्षण के लिए विशिष्ट मौसम को अनदेखा करते हुए)। फिर, जब उसे वास्तव में किसी विशिष्ट स्थिति में (जैसे, "मैं स्थिति X पर हूँ, और वर्तमान में बारिश हो रही है") कोई चाल चलनी होती है, तो वह विशिष्ट मौसम के लिए समायोजन करने हेतु ताज़ा नमूनों (samples) का उपयोग करके एक त्वरित, एक-चरणीय गणना करता है।
- परिणाम: सीखने की लागत बोर्ड के आकार और खेल की जटिलता पर निर्भर करती है, लेकिन अभी भी मौसम की सूची के आकार पर निर्भर नहीं करती।

"लुक-अहेड" बोनस (The "Look-Ahead" Bonus)

शोध पत्र में "परफेक्ट वन-स्टेप लुक-अहेड" नामक एक विशेष मामले का भी उल्लेख है।

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

"जादू" का सारांश

इस शोध पत्र का मुख्य निष्कर्ष एआई लर्निंग के लिए एक "नो-ब्रेनर" (सरल) परिणाम है:

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

संक्षेप में: आपको नौकायन सीखने के लिए हर संभावित तूफान को याद करने की आवश्यकता नहीं है; आपको बस औसत हवा को समझने की आवश्यकता है।

तकनीकी सारांश: बहिर्जात (Exogenous) कॉन्टेक्स्टुअल MDPs में सीखने के लिए मिनिमैक्स PAC बाउंड्स

1. समस्या सेटिंग

यह शोध पत्र बहिर्जात i.i.d. कॉन्टेक्स्ट्स वाले टैबुलर डिस्काउंटेड मार्कोव डिसीजन प्रोसेस (MDPs) में सीखने की सैंपल कॉम्प्लेक्सिटी (नमूना जटिलता) की जांच करता है। इस मॉडल को एक टुपल $\mathcal{M} = (\mathcal{X}, \mathcal{Z}, \mathcal{A}, P, r, \mu, \gamma)$ द्वारा परिभाषित किया गया है, जहाँ:

$\mathcal{X}$ एक परिमित नियंत्रित स्टेट स्पेस (controlled state space) है।
$\mathcal{A}$ एक परिमित एक्शन स्पेस है।
$\mathcal{Z}$ एक परिमित कॉन्टेक्स्ट स्पेस है।
$\gamma \in [0, 1)$ डिस्काउंट फैक्टर है।
$P: \mathcal{X} \times \mathcal{A} \times \mathcal{Z} \to \Delta(\mathcal{X})$ ट्रांजिशन कर्नेल है।
$r: \mathcal{X} \times \mathcal{A} \times \mathcal{Z} \to [0, 1]$ रिवॉर्ड फंक्शन है।
$\mu$ कॉन्टेक्स्ट्स पर अज्ञात वितरण (unknown distribution) है।

प्रत्येक समय चरण $t$ पर, $\mu$ से स्वतंत्र रूप से एक कॉन्टेक्स्ट $Z_t$ खींचा जाता है और एजेंट को एक्शन चयन से पहले दिखाया जाता है। एजेंट $A_t$ चुनता है, रिवॉर्ड $r(X_t, A_t, Z_t)$ प्राप्त करता है, और $X_{t+1} \sim P(\cdot | X_t, A_t, Z_t)$ पर ट्रांजिशन करता है। महत्वपूर्ण रूप से, अगला कॉन्टेक्स्ट $Z_{t+1}$ एजेंट के कार्यों और वर्तमान अवस्था से स्वतंत्र होता है, जो केवल $\mu$ पर निर्भर करता है।

सीखने के उद्देश्य हैं: पॉलिसी इवैल्यूएशन (PE), बेस्ट-वैल्यू एस्टीमेशन (BVE), और बेस्ट-पॉलिसी एक्सट्रैक्शन (BPE)। सैंपल कॉम्प्लेक्सिटी को एक जोड़ी $(n_{\text{learn}}, m_{\text{query}})$ द्वारा मापा जाता है, जो क्रमशः ऑफलाइन लर्निंग चरण के दौरान किए गए ऑरेकल कॉल्स की संख्या और निर्णय-समय (query) चरण के दौरान किए गए कॉल्स की संख्या को दर्शाती है। पेपर दो व्यवस्थाओं (regimes) पर विचार करता है:

ज्ञात डायनेमिक्स (Known Dynamics): $P$ और $r$ ज्ञात हैं; केवल $\mu$ अज्ञात है।
पूर्णतः अज्ञात (Fully Unknown): $\mu$ और $P$ दोनों अज्ञात हैं।

2. कार्यप्रणाली (Methodology)

2.1 मुख्य अंतर्दृष्टि: औसत मान फलन (Averaged Value Functions)

मुख्य पद्धतिगत योगदान समस्या को संवर्धित स्थान $\mathcal{X} \times \mathcal{Z}$ से नियंत्रित स्टेट स्पेस $\mathcal{X}$ में कम करना है। लेखक औसत मान फलन $\bar{V}(x) := \mathbb{E}_{Z \sim \mu}[V(x, Z)]$ को परिभाषित करते हैं।
चूंकि अगला कॉन्टेक्स्ट $\mu$ से स्वतंत्र रूप से खींचा जाता है, इसलिए औसत मान $\bar{V}^\star$ के लिए बेलमैन ऑप्टिमलिटी समीकरण केवल $\mu$ पर औसत किए गए ट्रांजिशन कर्नेल पर निर्भर करता है:
$\bar{V}^\star(x) = \mathbb{E}_{Z \sim \mu} \left[ \max_{a \in \mathcal{A}} \left( r(x, a, Z) + \gamma \sum_{x'} P(x' | x, a, Z) \bar{V}^\star(x') \right) \right]$
यह फॉर्मूलेशन लर्नर को कॉन्टेक्स्ट स्पेस के आकार $|\mathcal{Z}|$ से जटिलता को प्रभावी रूप से अलग करते हुए, $\mathbb{R}^{|\mathcal{X}|}$ में एक वेक्टर का अनुमान लगाने की अनुमति देता है।

2.2 एल्गोरिद्मिक फ्रेमवर्क: वेरिएन्स-रिड्यूस्ड हाल्विंग (Variance-Reduced Halving)

पेपर औसत मान फलनों का अनुमान लगाने के लिए एक वेरिएंस-रिड्यूस्ड वैल्यू इटरेशन योजना (Sidford et al., 2019 से अनुकूलित) का उपयोग करता है। एल्गोरिदम दो चरणों में कार्य करता है:

ऑफलाइन चरण (एंकर एस्टीमेशन): एल्गोरिदम एक प्रारंभिक मान अनुमान पर लागू बेलमैन ऑपरेटर के लिए एक उच्च-संभाव्यता निचला स्तर (anchor) कंप्यूट करता है। इसके लिए एम्पीरिकल मीन के वेरिएंस को नियंत्रित करने के लिए नमूनों के एक बड़े बैच की आवश्यकता होती है।
ऑनलाइन/इटरेटिव चरण (वेरिएंस-रिड्यूस्ड अपडेट्स): बाद के इटरेशन केवल वर्तमान बेलमैन बैकअप और एंकर के बीच के अंतर का अनुमान लगाते हैं। अंतर पद के लिए उन्हीं नमूनों का पुन: उपयोग करके, वेरिएंस काफी कम हो जाता है, जिससे प्रति इटरेशन छोटे सैंपल साइज की अनुमति मिलती है।

एल्गोरिदम एक "हाल्विंग" रणनीति का उपयोग करता है, जो बार-बार एक सबरूटीन (HALFERR) को कॉल करता है जो लक्ष्य सटीकता $\epsilon$ तक एरर बाउंड $u$ को आधा कर देता है।

2.3 अज्ञात डायनेमिक्स को संभालना

पूर्णतः अज्ञात व्यवस्था में, एल्गोरिदम एक सैंपल्ड कॉन्टेक्स्ट के साथ भी बेलमैन बैकअप को सटीक रूप से कंप्यूट नहीं कर सकता है। इसके बजाय, प्रत्येक सैंपल्ड कॉन्टेक्स्ट $Z$ के लिए, एल्गोरिदम एक अनबायस्ड एस्टीमेट बनाने के लिए एक ट्रांजिशन सैंपल $X' \sim P(\cdot | x, \pi(x, Z), Z)$ खींचता है। यह ट्रांजिशन कर्नेल से संबंधित एक अतिरिक्त वेरिएंस टर्म पेश करता है, जिसे कॉन्टेक्स्ट और ट्रांजिशन दोनों की रैंडमनेस को ध्यान में रखते हुए एक मार्टिंगेल डीकंपोजिशन का उपयोग करके कड़ाई से बाउंड किया गया है।

3. मुख्य परिणाम

3.1 ज्ञात डायनेमिक्स, अज्ञात कॉन्टेक्स्ट वितरण ( $P, r$ ज्ञात, $\mu$ अज्ञात)

जब ट्रांजिशन कर्नेल और रिवॉर्ड्स ज्ञात होते हैं, तो पेपर यह स्थापित करता है कि सैंपल कॉम्प्लेक्सिटी कॉन्टेक्स्ट स्पेस के आकार $|\mathcal{Z}|$ से स्वतंत्र है।

जटिलता: एल्गोरिदम उद्देश्यों को $(n_{\text{learn}}, m_{\text{query}}) = (\tilde{O}(\beta^3/\epsilon^2), 0)$ के साथ प्राप्त करता है, जहाँ $\beta = (1-\gamma)^{-1}$ है।
इष्टतमता (Optimality): एक $\Omega(\beta^3/\epsilon^2)$ का मिनिमैक्स लोअर बाउंड सिद्ध किया गया है, जो दिखाता है कि ऊपरी बाउंड लॉगरिदमिक फैक्टर्स तक टाइट है।
निहितार्थ: लर्नर को प्रत्येक $(x, z)$ जोड़े के लिए मानों का अनुमान लगाने की आवश्यकता नहीं है; $\bar{V}$ का अनुमान लगाना पर्याप्त है। क्वेरी चरण में किसी अतिरिक्त नमूनों की आवश्यकता नहीं होती है ( $m_{\text{query}}=0$ ) क्योंकि $\bar{V}$ से $V(x, z)$ तक का लिफ्ट ज्ञात $P$ और $r$ का उपयोग करके एक डिटर्मिनिस्टिक बेलमैन बैकअप है।

3.2 परफेक्ट वन-स्टेप लुकअहेड (Perfect One-Step Lookahead) पर अनुप्रयोग

इस फ्रेमवर्क को परफेक्ट वन-स्टेप ट्रांजिशन लुकअहेड सेटिंग पर लागू किया गया है (जहाँ एजेंट कार्य करने से पहले सभी संभावित अगले राज्यों को सभी क्रियाओं के लिए देख सकता है)।

इस सेटिंग को एक बहिर्जात कॉन्टेक्स्टुअल MDP के विशेष मामले के रूप में दिखाया गया है जहाँ कॉन्टेक्स्ट स्पेस सभी संभावित ट्रांजिशन टेंसरों का सेट है।
परिणाम $\tilde{O}(\beta^3/\epsilon^2)$ लुकअहेड सैंपल्स की सैंपल कॉम्प्लेक्सिटी प्रदान करता है।
व्यक्तिगत टैबुलर ट्रांजिशन्स के संदर्भ में, यह Lu et al. (2025) के पिछले बाउंड को $\beta$ के कारक से सुधारते हुए $\tilde{O}(\beta^3 |\mathcal{X}||\mathcal{A}|/\epsilon^2)$ के बराबर है।

3.3 पूर्णतः अज्ञात व्यवस्था ( $P$ और $\mu$ दोनों अज्ञात)

जब डायनेमिक्स और कॉन्टेक्स्ट वितरण दोनों अज्ञात होते हैं, तो पेपर पॉलिसी इवैल्यूएशन (PE) पर ध्यान केंद्रित करता है।

जटिलता: एल्गोरिदम $(n_{\text{learn}}, m_{\text{query}}) = (\tilde{O}(|\mathcal{X}|\beta^3/\epsilon^2), \tilde{O}(\beta^2/\epsilon^2))$ प्राप्त करता है।
ट्रेड-ऑफ: ऑफलाइन चरण औसत मान $\bar{V}^\pi$ को सीखता है (प्रति कॉन्टेक्स्ट सैंपल $|\mathcal{X}|$ ट्रांजिशन की लागत के साथ)। क्वेरी चरण, ताजे नमूनों का उपयोग करके वास्तविक $(x, z)$ पर एक-चरण ट्रांजिशन एक्सपेक्टेशन का अनुमान लगाता है।
लोअर बाउंड्स: पेपर मैचिंग लोअर बाउंड्स सिद्ध करता है, जो दर्शाता है कि:
- निर्णय-समय सटीकता के लिए $m_{\text{query}} = \Omega(\beta^2/\epsilon^2)$ आवश्यक है।
- ऑफलाइन लर्निंग के लिए $n_{\text{learn}} + |\mathcal{X}| m_{\text{query}} = \Omega(|\mathcal{X}|\beta^3/\epsilon^2)$ आवश्यक है।
महत्व: पूर्णतः अज्ञात व्यवस्था में भी, जटिलता कॉन्टेक्स्ट स्पेस $|\mathcal{Z}|$ से स्वतंत्र रहती है। अज्ञात डायनेमिक्स $\bar{V}$ से $V(x, z)$ के "लिफ्ट" के लिए स्टोकैस्टिसिटी (stochasticity) पेश करते हैं।

4. महत्व और दावे

पेपर का दावा है कि यह बहिर्जात कॉन्टेक्स्टुअल MDPs में सीखने के लिए पहले मिनिमैक्स-ऑप्टिमल PAC बाउंड्स प्रदान करता है। इसके प्राथमिक योगदान हैं:

कॉन्टेक्स्ट साइज से अलगाव (Decoupling from Context Size): यह प्रदर्शित करता है कि बड़े कॉन्टेक्स्ट स्पेस की सांख्यिकीय कीमत से बचा जा सकता है। सैंपल कॉम्प्लेक्सिटी नियंत्रित स्टेट स्पेस $|\mathcal{X}|$ पर निर्भर करती है, न कि कॉन्टेक्स्ट स्पेस $|\mathcal{Z}|$ पर।
इष्टतम दरें (Optimal Rates): प्राप्त दरें ( $\text{known dynamics}$ के लिए $\tilde{O}(\beta^3/\epsilon^2)$ और $\text{fully unknown}$ के लिए $\tilde{O}(|\mathcal{X}|\beta^3/\epsilon^2)$ ) लॉगरिदमिक फैक्टर्स तक मिनिमैक्स ऑप्टिमल हैं।
एकीकृत फ्रेमवर्क: यह फ्रेमवर्क परफेक्ट वन-स्टेप लुकअहेड के मौजूदा परिणामों को समाहित और बेहतर बनाता है और ऑफलाइन/ऑनलाइन सैंपल ट्रेड-ऑफ का कठोर विश्लेषण प्रदान करता है।

लेखक नोट करते हैं कि जबकि लोअर बाउंड शुद्ध रूप से ऑनलाइन पॉइंट ( $n_{\text{learn}}=0$ ) और रियूजेबल-ऑरेकल पॉइंट (उनका प्रस्तावित एल्गोरिदम) पर टाइट है, मध्यवर्ती ट्रेड-ऑफ के लिए बाउंड की टाइटनेस एक खुला प्रश्न है। इसके अतिरिक्त, ट्रांजिशन सैंपल्स से क्रियाओं के ऊपर मैक्सिमम का अनुमान लगाने में सिलेक्शन बायस (selection bias) को संभालने की कठिनाई के कारण, पूर्णतः अज्ञात व्यवस्था में बेस्ट-पॉलिसी एक्सट्रैक्शन (BPE) तक इन परिणामों का विस्तार करना भविष्य का कार्य है।