🤖 machine learning

Model-Based Reinforcement Learning with Double Oracle Efficiency in Policy Optimization and Offline Estimation

यह शोध पत्र एक नवीन मॉडल-आधारित सुदृढीकरण शिक्षण (reinforcement learning) एल्गोरिदम का प्रस्ताव करता है जो अवस्था और क्रिया स्थान के आकार से स्वतंत्र ऑरेकल जटिलता के साथ इष्टतम रिग्रेट बाउंड्स प्राप्त करता है, जो इसे अनंत अवस्था और क्रिया स्थानों वाले MDPs को हल करने में सक्षम प्रथम 'डबली ऑरेकल-एफिशिएंट' विधि बनाता है।

मूल लेखक: Haichen Hu, Jian Qian, David Simchi-Levi

प्रकाशित 2026-05-04

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

CC BY 4.0

मूल लेखक: Haichen Hu, Jian Qian, David Simchi-Levi

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

मुख्य विचार: "सुपर-प्लानर" (Super-Planner) की समस्या

कल्पना कीजिए कि आप एक रोबोट को एक विशाल, अनंत भूलभुलैया (maze) में खजाना खोजने के लिए प्रशिक्षित करने की कोशिश कर रहे हैं। यह रीइन्फोर्समेंट लर्निंग (RL) है: एक एजेंट जो प्रयास और त्रुटि (trial and error) से सीखता है।

इसे अच्छी तरह से करने के लिए, रोबोट को आमतौर पर दो चीजों की आवश्यकता होती है:

एक मानचित्र निर्माता (सांख्यिकीय ओरेकल - Statistical Oracle): इसे यह अनुमान लगाने के लिए अपने पिछले अनुभवों को देखने की आवश्यकता है कि भूलभुलैया कैसी दिखती है (दीवारें कहाँ हैं, फर्श कितना फिसलन भरा है)।
एक मार्ग योजनाकार (पॉलिसी ओरेकल - Policy Oracle): इसे उस मानचित्र को देखना चाहिए और खजाने तक पहुँचने का सबसे अच्छा रास्ता निकालना चाहिए।

समस्या: विशाल या जटिल भूलभुलैया में (जैसे वास्तविक दुनिया के वातावरण जिनमें अनंत संभावनाएं हैं), ऐसा करना एक दुःस्वप्न है।

यदि भूलभुलैया अनंत है, तो "मानचित्र निर्माता" को असंभव मात्रा में डेटा प्रोसेस करना पड़ेगा।
यदि भूलभुलैया बहुत बड़ी है, तो "मार्ग योजनाकार" को हर एक कदम पर अरबों संभावित रास्तों की जांच करनी होगी।
मौजूदा तरीके एक वाक्य लिखने के लिए लाइब्रेरी की हर किताब पढ़ने की कोशिश करने, या एक भी कदम उठाने से पहले मानचित्र पर हर संभव रास्ते की जांच करने के समान हैं। वे बहुत धीमे और गणनात्मक रूप से महंगे (computationally expensive) हैं।

समाधान: "डबल ओरेकल" दक्षता (Double Oracle Efficiency)

इस शोध पत्र के लेखक एक नया एल्गोरिदम प्रस्तावित करते हैं जिसे DOERL कहा जाता है। इसे एक "सुपर-प्लानर" के रूप में सोचें जो मानचित्र बनाने और मार्ग की योजना बनाने, दोनों में अविश्वसनीय रूप से कुशल है।

वे इसे "डबल ओरेकल दक्षता" कहते हैं। इसका अर्थ है कि एल्गोरिदम इतना स्मार्ट है कि:

वह मानचित्र निर्माता से मदद मांगने में बहुत कम बार (rarely) ही झिझकता है।
वह मार्ग योजनाकार से मदद मांगने में बहुत कम बार ही झिझकता है।

महत्वपूर्ण बात यह है कि यह मदद मांगने की संख्या इस बात पर निर्भर नहीं करती कि भूलभुलैया कितनी बड़ी है। चाहे भूलभुलैया में 10 कमरे हों या अनंत कमरे, "परामर्श" (consultations) की संख्या कम ही रहती है।

यह कैसे काम करता है: "ट्रस्टेड ज़ोन" और "लॉग-बैरियर"

इसे प्राप्त करने के लिए, लेखक दो चतुर युक्तियों का उपयोग करते हैं:

1. "ट्रस्टेड ज़ोन" (विश्वसनीय अधिभोग माप - Trusted Occupancy Measure)

कल्पना कीजिए कि आप एक नए शहर की खोज कर रहे हैं। हर गली के कोने का तुरंत मानचित्र बनाने के बजाय, आप केवल उन सड़कों पर भरोसा करते हैं जिन पर आपने हाल ही में पैदल यात्रा की है।

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

2. "लॉग-बैरियर" (सुरक्षा जाल - The Safety Net)

जब रोबोट अपने मार्ग की योजना बनाता है, तो उसके सामने एक विकल्प होता है: उस पथ पर टिके रहना जो वह सुरक्षित जानता है (Exploitation) या शॉर्टकट देखने के लिए एक नए, जोखिम भरे पथ को आज़माना (Exploration)।

लेखक एक गणितीय उपकरण का उपयोग करते हैं जिसे लॉग-बैरियर (Log-Barrier) कहा जाता है। इसे रोबोट के चारों ओर एक "सुरक्षा जाल" या "चुंबकीय क्षेत्र" के रूप में कल्पना करें।
जैसे-जैसे रोबोट अपने "ट्रस्टेड ज़ोन" के किनारे के करीब पहुँचता है, बैरियर मजबूत होता जाता है, जो उसे सहज होने से पहले नए क्षेत्रों की खोज करने के लिए धीरे से धकेलता है।
यह सुनिश्चित करता है कि रोबлот बिना हर एक संभावना को मैन्युअल रूप से जांचे, कुशलतापूर्वक पूरी भूलभुलैया की खोज करे।

दो प्रकार की भूलभुलैया जिन्हें उन्होंने हल किया

यह शोध पत्र दो विशिष्ट प्रकार की समस्याओं को संबोधित करता है:

1. सीमित भूलभुलैया (टेबुलर MDPs)

परिदृश्य: निश्चित और गणनीय (countable) कमरों और दरवाजों वाली भूलभुलैया।
उपलब्धि: नया एल्गोरिदम सर्वोत्तम संभव गति (regret bound) प्राप्त करता है जबकि यह मानचित्र निर्माता और मार्ग योजनाकार से बहुत कम बार मदद मांगता है (विशेष रूप से, कुल चरणों के सापेक्ष लघुगणकीय/logarithmic बार)।
क्यों महत्वपूर्ण है: पिछले तरीकों को भूलभुलैया में कमरों की संख्या के बराबर बार मदद मांगनी पड़ती थी। यह नया तरीका मदद मांगने की संख्या उतनी ही रखता है जो भूलभुलैया के आकार के बावजूद लगभग समान रहती है।

2. अनंत भूलभुलैया (लीनियर MDPs)

परिदृश्य: एक ऐसी भूलभुलैया जो प्रभावी रूप से अनंत है (जैसे एक निरंतर स्थान जहाँ आप किसी भी निर्देशांक/coordinate पर हो सकते हैं, न कि केवल विशिष्ट ग्रिड बिंदुओं पर)।
उपलब्धि: यह इस शोध पत्र की सबसे बड़ी सफलता है। उन्होंने अपनी विधि को अनंत स्थानों को संभालने के लिए विस्तारित किया है।
चाल (Trick): हर एक बिंदु की जांच करने के बजाय (जो असंभव है), वे लॉग-डिटरमिनेंट (Log-Determinant) तकनीक का उपयोग करते हैं। इसे रोबोट द्वारा खोजे गए क्षेत्र के "आयतन" (volume) या "फैलाव" (spread) की जांच करने के रूप में समझें, न कि रेत के हर एक कण को गिनने के रूप में। यह उन्हें कम संख्या में "परामर्शों" के साथ अनंत जटिलता को संभालने की अनुमति देता है।

निष्कर्ष (The Bottom Line)

इस शोध पत्र से पहले, यदि आप किसी जटिल रीइन्फोर्समेंट लर्निंग समस्या को कुशलतापूर्वक हल करना चाहते थे, तो आपको इन दोनों में से एक को चुनना पड़ता था:

या तो तेज़ होना लेकिन गलत (inaccurate)।
या सटीक होना लेकिन इतना धीमा कि कंप्यूटर पर चलाना असंभव हो।

यह शोध पत्र एक ऐसा तरीका पेश करता है जो तेज़ और सटीक दोनों है। यह निम्नलिखित द्वारा हल किया जाता है:

केवल कभी-कभी अपने "मानचित्र" और "योजना" को अपडेट करना (हर कदम पर नहीं)।
हर एक संभावना को जांचने की आवश्यकता के बिना अन्वेषण (exploration) को निर्देशित करने के लिए गणितीय "बैरियर्स" का उपयोग करना।
यह सिद्ध करना कि यह तब भी काम करता है जब वातावरण अनंत रूप से बड़ा हो।

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

यहाँ हु, कियान और सिमची-लेवी द्वारा लिखित शोध पत्र "Model-Based Reinforcement Learning with Double Oracle Efficiency" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण (Problem Statement)

बड़े पैमाने या निरंतर (continuous) वातावरण में सुदृढीकरण शिक्षण (Reinforcement Learning - RL) गंभीर कम्प्यूटेशनल बाधाओं का सामना करता है। पारंपरिक मॉडल-आधारित रिग्रेट मिनिमाइजेशन एल्गोरिदम को दो प्रकार के "ओरेकल" (oracles) के बार-बार कॉल्स की आवश्यकता होती है:

सांख्यिकीय अनुमान ओरेकल (Statistical Estimation Oracle): डेटा से पर्यावरण मॉडल (ट्रांज़िशन डायनेमिक्स और रिवार्ड्स) का अनुमान लगाने के लिए उपयोग किया जाता है।
नीति अनुकूलन (प्लानिंग) ओरेकल (Policy Optimization/Planning Oracle): अनुमानित मॉडल के आधार पर इष्टतम नीति (optimal policy) की गणना करने के लिए उपयोग किया जाता है।

मौजूदा दृष्टिकोणों में दो मुख्य सीमाएँ हैं:

उच्च ओरेकल कॉल आवृत्ति (High Oracle Call Frequency): अधिकांश एल्गोरिदम को इन ओरेकल के $O(T)$ कॉल्स की आवश्यकता होती है, जहाँ $T$ समय क्षितिज (time horizon) है, जो बड़े $T$ के लिए इन्हें कम्प्यूटेशनल रूप से निषेधात्मक बनाता है।
स्टेट/एक्शन स्पेस के आकार पर निर्भरता: प्लानिंग की जटिलता अक्सर स्टेट स्पेस ( $S$ ) और एक्शन स्पेस ( $A$ ) की कार्डिनैलिटी के साथ बढ़ती है। यह मौजूदा विधियों को उन वातावरणों के लिए अव्यवहार्य बना देता है जिनमें बड़े, अनंत या निरंतर स्टेट/एक्शन स्पेस होते हैं (जैसे कि अनंत स्टेट्स वाले लीनियर MDPs)।

जबकि हाल के कार्यों (जैसे, कियान एट अल., 2024) ने टेबुलर MDPs के लिए "ऑफलाइन ओरेकल दक्षता" (अनुमान ओरेकल के लिए कम कॉल्स) प्राप्त की, उनकी प्लानिंग ओरेकल जटिलता अभी भी $S$ और $A$ (विशेष रूप से $O(HSA \log \log T)$ ) के साथ स्केल करती थी। यह शोध पत्र इस खुले प्रश्न को संबोधित करता है: क्या हम एक ऐसा एल्गोरिदम डिज़ाइन कर सकते हैं जो अनुमान और प्लानिंग दोनों ओरेकल में कुशल हो, जिसकी जटिलता $S$ और $A$ से स्वतंत्र हो, और जो अनंत स्टेट/एक्शन स्पेस के लिए भी लागू हो सके?

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

लेखक DOERL (Doubly Oracle-Efficient Reinforcement Learning) प्रस्तावित करते हैं, जो log-barrier और log-determinant रेगुलाइजेशन पर आधारित एक नवीन एल्गोरिद्मिक ढांचा है। मुख्य नवाचार इस बात में निहित है कि एल्गोरिदम ओरेकल कॉल्स को कम करते हुए अन्वेषण (exploration) और दोहन (exploitation) के बीच संतुलन कैसे प्रबंधित करता है।

मुख्य तकनीकी घटक:

ट्रंकेटेड अपडेट के साथ एपोक-आधारित लर्निंग (Epoch-Based Learning with Truncated Updates):
- इंटरेक्शन प्रक्रिया को $N$ एपोक्स में विभाजित किया गया है। प्रत्येक एपोक के भीतर, एजेंट एक समय खंड (segment) के लिए एक निश्चित नीति का निष्पादन करता है।
- महत्वपूर्ण रूप से, ऑफलाइन अनुमान ओरेकल को केवल प्रत्येक एपोक (या खंड) के अंत में कॉल किया जाता है, जो मॉडल को अपडेट करने के लिए डेटा को एकत्रित करता है। यह अनुमान कॉल्स की संख्या को $O(N)$ तक कम कर देता है।
- प्लानिंग ओरेकल को भी केवल खंडों की शुरुआत में ही बुलाया जाता है, जिससे प्लानिंग की आवृत्ति काफी कम हो जाती है।
विश्वसनीय अधिभोग माप (Trusted Occupancy Measures):
- दुर्लभ या अविश्वसनीय स्टेट-एक्शन ट्रांज़िशन के अन्वेषण से बचने के लिए, एल्गोरिदम एक "विश्वसनीय ट्रांज़िशन सेट" $\mathcal{T}_m^h$ को परिभाषित करता है।
- ट्रांज़िशन को केवल तभी "विश्वसनीय" माना जाता है जब अनुमानित अधिभोग माप (occupancy measure) ट्रांज़िशन प्रोबेबिलिटी के साथ मिलकर $1/\zeta_m$ थ्रेसहोल्ड से अधिक होता है।
- कियान एट अल. (2024) से अनुकूलित यह अवधारणा, इसे पूरे पॉलिसी स्पेस पर पुनरावृत्ति किए बिना गणना योग्य बनाने के लिए संशोधित की गई है, जो दक्षता के लिए महत्वपूर्ण है।
अन्वेषण के लिए रेगुलाइजेशन (Regularization for Exploration):
- टेबुलर MDPs के लिए: एल्गोरिदम Log-Barrier Regularization का उपयोग करता है। पॉलिसी ऑप्टिमाइज़ेशन ऑब्जेक्टिव में $\sum \log(\text{trusted occupancy} + \beta)$ पद शामिल है। यह एजेंट को उन स्टेट-एक्शन पेयर्स को विज़िट करने के लिए प्रोत्साहित करता है जो "विश्वसनीय" हैं लेकिन जिनकी संभावना कम है, जिससे यह सुनिश्चित होता है कि सभी स्टेट्स को सूचीबद्ध किए बिना पर्याप्त अन्वेषण हो सके।
- लीनियर MDPs (अनंत स्पेस) के लिए: एल्गोरिदम Log-Determinant Regularization पेश करता है। डिस्क्रीट स्टेट्स पर योग करने के बजाय, यह विश्वसनीय अधिभोग माप द्वारा भारित फीचर कोवेरिएंस मैट्रिक्स के लॉग-डिटरमिनेंट को अधिकतम करता है: $\log \det(\mathbf{K} + \beta \mathbf{I})$ । यह फीचर स्पेस के अन्वेषण को बढ़ावा देता है, जिससे यह सुनिश्चित होता है कि एजेंट लीनियर कोएफिशिएंट्स का सटीक अनुमान लगाने के लिए विविध डेटा एकत्र करे।
एकत्रीकरण रणनीति (Aggregation Strategy):
- एल्गोरिदम अगले एपोक के लिए एक एकल ग्लोबल मॉडल में लेयर-वाइज अनुमानों (ट्रांज़िशन कर्नेल और रिवार्ड्स) को एकत्रित करता है, न कि प्रत्येक सिंगल स्टेप पर मॉडल को अपडेट करता है।

3. मुख्य योगदान (Key Contributions)

डबल ओरेकल दक्षता (Double Oracle Efficiency):
- यह पेपर पहला एल्गोरिदम प्रस्तुत करता है जो दोनों सांख्यिकीय अनुमान और नीति अनुकूलन ओरेकल दक्षता प्राप्त करता है।
- ओरेकल कॉल जटिलता: जब $T$ ज्ञात हो तो एल्गोरिदम दोनों ओरेकल के लिए केवल $O(H \log \log T)$ कॉल्स की आवश्यकता रखता है (और जब अज्ञात हो तो $O(H \log T)$ )।
- आयामों से स्वतंत्रता: महत्वपूर्ण रूप से, यह जटिलता स्टेट स्पेस के आकार ( $S$ ) और एक्शन स्पेस के आकार ( $A$ ) से पूरी तरह स्वतंत्र है।
अनंत स्थानों का विस्तार (Extension to Infinite Spaces):
- इस ढांचे को अनंत स्टेट स्पेस और अनिश्चित एक्शन स्पेस वाले Linear MDPs के लिए सामान्यीकृत किया गया है।
- यह वह पहला ऑफलाइन ओरेकल-कुशल एल्गोरिदम है जो इस सेटिंग में सब-लीनियर रिग्रेट प्राप्त करता है, जो "डायमेंशनलिटी के अभिशाप" (curse of dimensionality) को पार करता है जो टेबुलर विधियों को प्रभावित करता है।
इष्टतम रिग्रेट बाउंड्स (Optimal Regret Bounds):
- टेबुलर MDPs: $O(\sqrt{T})$ (इष्टतम) रिग्रेट प्राप्त करता है।
- लीनियर MDPs: $O(T^{4/5})$ (लॉगरिदमिक कारकों के साथ) का सब-लीनियर रिग्रेट प्राप्त करता है, जो दिए गए ओरेकल प्रतिबंधों के तहत अनंत-आयामी सेटिंग्स के लिए सार्थक है।

4. परिणाम (Results)

सीमित (टेबुलर) और अनंत (लीनियर) दोनों सेटिंग्स के लिए सैद्धांतिक गारंटी स्थापित की गई है:

टेबुलर MDPs:
- रिग्रेट: $O(\sqrt{T})$ (इष्टतम)।
- ओरेकल कॉल्स: दोनों अनुमान और प्लानिंग के लिए $O(H \log \log T)$ ।
- तुलना: कियान एट अल. (2024) में सुधार करता है, जिसे $O(HSA \log \log T)$ प्लानिंग कॉल्स की आवश्यकता थी।
लीनियर MDPs (अनंत स्टेट/एक्शन):
- रिग्रेट: $O(T^{4/5} \cdot \text{polylog}(T))$ ।
- ओरेकल कॉल्स: दोनों ओरेकल के लिए $O(H \log \log T)$ ।
- महत्व: इस कार्य से पहले, ऐसा कोई एल्गोरिदम मौजूद नहीं था जो इतने कम-आवृत्ति वाले ओरेकल कॉल्स के साथ सब-लीनियर रिग्रेट बनाए रखते हुए अनंत-स्टेट MDPs को हल कर सके।

5. महत्व और प्रभाव (Significance and Impact)

सिद्धांत और व्यवहार के बीच सेतु: स्टेट/एक्शन स्पेस के आकार से कम्प्यूटेशनल जटिलता को अलग करके, यह कार्य मॉडल-आधारित RL को रोबोटिक्स और स्वायत्त प्रणालियों जैसे जटिल, वास्तविक दुनिया के अनुप्रयोगों के लिए सैद्धांतिक रूप से व्यवहार्य बनाता है जहाँ $S$ और $A$ प्रभावी रूप से अनंत हैं।
बड़े पैमाने की प्रणालियों में दक्षता: ओरेकल कॉल्स को $O(T)$ या $O(SA) $से घटाकर$ O(\log \log T)$ करना कम्प्यूटेशनल ओवरहेड में भारी कमी है, जिससे RL लूप में महंगे ऑफलाइन एस्टिमेटर्स (जैसे डीप न्यूरल नेटवर्क) का उपयोग संभव होता है जहाँ वे पहले बहुत महंगे थे।
अन्वेषण के लिए नया प्रतिमान (New Paradigm for Exploration): "ट्रस्टेड" उपायों के साथ लॉग-बैरियर और लॉग-डिटरमिनेंट रेगुलाइजेशन का एकीकरण अन्वेषण के लिए एक मजबूत सैद्धांतिक तंत्र प्रदान करता है जो आयामीता (dimensionality) के साथ सहजता से स्केल करता है, जो उच्च-आयामी नियंत्रण के लिए भविष्य के एल्गोरिदम के लिए एक ब्लूप्रिंट पेश करता है।

संक्षेप में, यह शोध पत्र यह सिद्ध करके सुदृढ़ शिक्षण (Reinforcement Learning) की स्थिति को मौलिक रूप से आगे बढ़ाता है कि इष्टतम रिग्रेट को एपोक-आधारित लर्निंग, ट्रस्टेड मेजर्स और डिटरमिनेंट-आधारित रेगुलाइजेशन के एक नवीन संयोजन के माध्यम से न्यूनतम कम्प्यूटेशनल ओवरहेड (पर्यावरण के आकार से स्वतंत्र) के साथ प्राप्त किया जा सकता है।