📊 statistics

Bilevel Optimization over Saddle Points of Zero-Sum Markov Games

यह शोध पत्र PANDA का प्रस्ताव करता है, जो एक पेनल्टी-आधारित फर्स्ट-ऑर्डर पॉलिसी-ग्रेडिएंट विधि है जो कुशलतापूर्वक उन बाइलेवल ऑप्टिमाइज़ेशन समस्याओं को हल करती है जहाँ लोअर लेवल एक ज़ीरो-सम मार्कोव गेम है, और बिना किसी सेकंड-ऑर्डर जानकारी या कॉनवेक्सिटी धारणाओं की आवश्यकता के, इष्टतम सैंपल कॉम्प्लेक्सिटी के साथ स्टेशनरी पॉइंट्स पर अभिसरण (कन्वर्जेंस) प्राप्त करता है।

मूल लेखक: Zihao Zheng, Irwin King, Songtao Lu

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

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

CC BY 4.0

मूल लेखक: Zihao Zheng, Irwin King, Songtao Lu

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

कल्पना कीजिए कि आप एक शहर के मेयर (ऊपरी स्तर) हैं, और आप एक नया ट्रैफिक सिस्टम डिजाइन करना चाहते हैं। हालाँकि, आप खुद कार नहीं चलाते। इसके बजाय, आप नियम तय करते हैं (जैसे गति सीमा या टोल की कीमतें), और फिर ड्राइवरों के दो प्रतिद्वंद्वी समूह—"स्पीडर्स" (तेज चलाने वाले) और "कॉशस ड्राइवर्स" (सावधान चालक)—आपके नियमों पर प्रतिक्रिया देते हैं।

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

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

समाधान: PANDA
लेखकों ने एक नया एल्गोरिदम बनाया है जिसे PANDA (पेनल्टी-ऑगमेंटेड निकाइडो-इसोडा डिसेंट-असेंट) कहा जाता है। यह इस प्रकार काम करता है, एक सरल उपमा का उपयोग करते हुए:

"पेनल्टी" (जुर्माना) वाली ट्रिक:
कल्पना कीजिए कि मेयर यह सुनिश्चित करना चाहती है कि वह अपने स्वयं के निर्णय को आंकने से पहले ड्राइवर वास्तव में एक निष्पक्ष गतिरोध तक पहुँच जाएँ। जटिल गणित (जो कि "क्या होगा अगर वे अपना मन बदल दें?") की गणना करने के बजाय (जिसके लिए महंगे सेकंड-ऑर्डर गणित की आवश्यकता होती है), PANDA एक पेनल्टी (जुर्माना) का उपयोग करता है।

यदि ड्राइवर एक निष्पक्ष गतिरोध पर नहीं हैं, तो PANDA मेयर के स्कोर में एक "जुर्माना" जोड़ देता है।
एल्गोरिदम फिर मेयर के स्कोर और इन जुर्मानों को कम करने (minimize) का प्रयास करता है।
ड्राइवरों को कम जुर्माना भरने के लिए प्रेरित करके, एल्गोरिदम स्वाभाविक रूप से उन्हें उस निष्पक्ष गतिरोध में धकेल देता है।

"डिसेंट-असेंट" (उतरना-चढ़ना) का नृत्य:
एल्गोरिदम के भीतर, एक निरंतर नृत्य होता है:

"स्पीडर" ड्राइवर अपनी लागत को कम करने (descend) का प्रयास करता है।
"कॉशस" ड्राइवर अपनी लागत को बढ़ाने (ascend) का प्रयास करता है (चूंकि वे ज़ीरो-सम गेम में "मैक्स" प्लेयर हैं)।
PANDA इस नृत्य को समन्वित करता है ताकि वे बिना सड़क की सटीक वक्रता (curvature) को जाने, अपने संतुलन बिंदु को जल्दी से खोज सकें, जिससे कंप्यूटिंग पावर की भारी बचत होती है।

यह क्यों विशेष है:

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

परिणाम:
लेखकों ने PANDA का परीक्षण दो परिदृश्यों में किया:

एक सिंथेटिक इंसेंटिव गेम: एक काल्पनिक दुनिया जहाँ एक डिज़ाइनर दो प्रतिस्पर्धी एजेंटों को सहयोग करने के लिए पुरस्कृत करने का प्रयास करता है। PANDA ने अन्य तरीकों की तुलना में डिज़ाइनर के लिए बेहतर पुरस्कार खोजे।
सेंटिनल बनाम इंट्रूडर (Sentinel vs. Intruder): एक ग्रिड-वर्ल्ड गेम जहाँ एक "सेंटिनल" (प्रहरी) एक "इंट्रूडर" (घुसपैठिये) को पकड़ने की कोशिश करता है। मेयर (ऊपरी स्तर) ऐसे नियम सेट करना चाहती है जिससे सेंटिनल खतरनाक "प्रतिबंधित क्षेत्रों" से बचते हुए भी घुसपैठिये को पकड़ने की कोशिश करे। PANDA ने सफलतापूर्वक सेंटिनल को खतरे वाले क्षेत्रों से बचने के लिए सिखाया, जबकि सेंटिनल और घुसपैठिया अपना प्रतिस्पर्धी खेल खेल रहे थे।

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

तकनीकी सारांश: सैडल पॉइंट्स ऑफ ज़ीरो-सम मार्कोव गेम्स पर बाइलेवल ऑप्टिमाइज़ेशन

1. समस्या का निरूपण (Problem Formulation)

यह कार्य बाइलेवल सुदृढीकरण शिक्षण (Bilevel Reinforcement Learning - BRL) को उन सेटिंग्स में संबोधित करता है जहाँ लोअर-लेवल (LL) समस्या एक मानक सिंगल-पॉलिसी मार्कोव डिसीजन प्रोसेस (MDP) नहीं है, बल्कि एक रेगुलराइज्ड मिन-मैक्स ज़ीरो-सम मार्कोव गेम (MMZSMG) है।

इस पदानुक्रमित ढांचे (hierarchical framework) में:

अपर-लेवल (UL): एक ऑप्टिमाइज़र पैरामीटर्स $x$ (जैसे, प्रोत्साहन संरचनाएं या रिवॉर्ड शेपिंग) का चयन करता है ताकि एक ऑब्जेक्टिव $f(x, \phi, \psi)$ को कम किया जा सके।
लोअर-लेवल (LL): दो विरोधी एजेंट (मिन-प्लेयर पॉलिसी $\pi_\phi$ के साथ और मैक्स-प्लेयर पॉलिसी $\pi_\psi$ के साथ) एक मार्कोव गेम में परस्पर क्रिया करते हैं जो $x$ द्वारा पैरामीटराइज्ड है। वे एक सैडल-पॉइंट इक्विलिब्रियम (नैश इक्विलिब्रियम) खोजने का प्रयास करते हैं जो निम्नलिखित को हल करता है:
$(\phi^*(x), \psi^*(x)) \in \arg\min_{\phi'} \max_{\psi'} J(x, \phi', \psi')$
जहाँ $J$ गेम का रेगुलराइज्ड वैल्यू फंक्शन है।
ऑब्जेक्टिव: UL ऑब्जेक्टिव का मूल्यांकन LL गेम द्वारा प्रेरित इक्विलिब्रियम पर किया जाता है:
$\min_x F(x) \equiv f(x, \phi^*(x), \psi^*(x))$

मुख्य चुनौती दोनों LL प्लेयर्स के बीच रणनीतिक जुड़ाव (strategic coupling) है। सिंगल-पॉलिसी MDPs के विपरीत, एक प्लेयर की इष्टतम प्रतिक्रिया दूसरे के व्यवहार पर निर्भर करती है, जिससे हाइपरग्रेडिएंट्स (x के सापेक्ष UL ऑब्जेक्टिव के डेरिवेटिव) की गणना कम्प्यूटेशनल रूप से महंगी और संरचनात्मक रूप से जटिल हो जाती है। मौजूदा BRL विधियाँ अक्सर सेकंड-ऑर्डर जानकारी (हेसियन इनवर्स) या सिंगल-पॉलिसी MDPs के विशिष्ट संरचनात्मक धारणाओं पर निर्भर करती हैं, जो MMZSMGs के जुड़े हुए मिन-मैक्स स्ट्रक्चर के अनुकूल नहीं होती हैं।

2. कार्यप्रणाली: PANDA

लेखक PANDA (पेनल्टी-अगमेंटेड निकैडो-इसोडा डिसेंट-अससेंट) प्रस्तावित करते हैं, जो एक फर्स्ट-ऑर्डर स्टोकेस्टिक पॉलिसी-ग्रेडिएंट एल्गोरिदम है जिसे बिना सेकंड-ऑर्डर डेरिवेटिव की आवश्यकता के 'बाइलेवल ऑप्टिमाइज़ेशन ओवर सैडल पॉइंट्स ऑफ मार्कोव गेम्स' (BOSMG) को हल करने के लिए डिज़ाइन किया गया है।

मुख्य घटक:

पेनल्टी-आधारित पुनर्रूपण (Penalty-Based Reformulation):
हाइपरग्रेडिएंट्स की सीधे गणना करने के बजाय, PANDA निकैडो-इसोडा (NI) फंक्शन, $g(x, \phi, \psi)$ का उपयोग करके बाधित बाइलेवल समस्या को पुनर्रूपित करता है, जो वर्तमान पॉलिसी पेयर और नैश इक्विलिब्रियम के बीच के अंतर को मापता है। बाधित समस्या को एक अनकन्स्ट्रेंड पेनलाइज्ड ऑब्जेक्टिव में बदल दिया जाता है:
$L_\lambda(x, \phi, \psi) = f(x, \phi, \psi) + \lambda g(x, \phi, \psi)$
जहाँ $\lambda$ एक पेनल्टी पैरामीटर है।
तीन-चरणीय पुनरावृत्ति एल्गोरिदम (Three-Step Iterative Algorithm):
एल्गोरिदम एक आउटर लूप (x को अपडेट करने के लिए) और एक इनर लूप (पॉलिसी $\phi, \psi$ को अपडेट करने के लिए) में कार्य करता है:
- स्टेप 1: बेस्ट-रिस्पॉन्स एप्रोक्सिमेशन: एल्गोरिदम वर्तमान पॉलिसियों के लिए बेस्ट-रिस्पॉन्स पॉलिसियों ( $\tilde{\phi}, \tilde{\psi}$ ) का अनुमान लगाने के लिए पॉलिसी-ग्रेडिएंट डिसेंट (मिन-प्लेयर के लिए) और अससेंट (मैक्स-प्लेयर के लिए) का उपयोग करता है। यह NI फंक्शन $g(x, \phi, \psi) \approx J(x, \phi, \tilde{\psi}) - J(x, \tilde{\phi}, \psi)$ के अनुमान की अनुमति देता है।
- स्टेप 2: पेनल्टी-सबप्रॉब्लम एप्रोक्सिमेशन: एल्गोरिदम पेनलाइज्ड सरोगेट ऑब्जेक्टिव $h(x, \phi, \psi) = \frac{1}{\lambda}f(x, \phi, \psi) + g(x, \phi, \psi)$ को मिनिमाइज करने के लिए स्टोकेस्टिक ग्रेडिएंट डिसेंट के माध्यम से पॉलिसी पैरामीटर्स $(\phi, \psi)$ को अपडेट करता है। यह स्टेप LL पॉलिसियों को सैडल पॉइंट की ओर ले जाता है।
- स्टेप 3: हाइपरग्रेडिएंट स्टेप: UL पैरामीटर $x$ को पेनलाइज्ड ऑब्जेक्टिव $L_\lambda$ के स्टोकेस्टिक ग्रेडिएंट अनुमान का उपयोग करके अपडेट किया जाता है। महत्वपूर्ण बात यह है कि यह ग्रेडिएंट सैंपल किए गए ट्राजेक्टरीज से प्राप्त फर्स्ट-ऑर्डर जानकारी का उपयोग करके कंप्यूट किया जाता है, जिससे LL हेसियन के इनवर्जन से बचा जा सकता है।
स्टोकेस्टिक एस्टीमेशन:
विधि वैल्यू फंक्शन्स और NI गैप के ग्रेडिएंट्स का अनुमान लगाने के लिए ट्रंकेटेड हॉरिज़न्स के साथ मोंटे कार्लो रोल-आउट्स पर निर्भर करती है, जो इसे बड़े पैमाने के, सैंपल-आधारित सेटिंग्स के लिए उपयुक्त बनाती है।

3. सैद्धांतिक योगदान (Theoretical Contributions)

यह पेपर मानक धारणाओं (बाउंडेड रिवार्ड्स, लिप्सचिट्ज़ निरंतरता, और पोलियाक-लोजासिएविक (PŁ) स्थितियों) के तहत PANDA के लिए कठोर अभिसरण गारंटी (convergence guarantees) स्थापित करता है।

स्टेशनरी पॉइंट्स की ओर अभिसरण: यह सिद्ध किया गया है कि PANDA बिना किसी कन्वेक्सिटी धारणा के मूल बाइलेवल समस्या के $\epsilon$ -स्टेशनरी पॉइंट की ओर अभिसरित होता है।
कॉम्प्लेक्सिटी बाउंड्स:
- इटरेशन कॉम्प्लेक्सिटी: $\tilde{O}(\epsilon^{-1})$ आउटर इटरेशन्स।
- सैंपल कॉम्प्लेक्सिटी: $\tilde{O}(\epsilon^{-3})$ ।
  इन दरों से पता चलता है कि यह जटिल युग्मित मिन-मैक्स गेम के बावजूद, सिंगल-पॉलिसी LL MDPs के लिए ज्ञात स्टेट-ऑफ-द-आर्ट बाउंड्स से मेल खाती है।
संरचनात्मक गुण: लेखक रेगुलराइज्ड MMZSMGs के लिए नए संरचनात्मक परिणाम सिद्ध करते हैं, जिनमें शामिल हैं:
- सामान्य रेगुलराइजेशन के तहत इक्विलिब्रियम पॉलिसी पेयर की विशिष्टता (uniqueness)।
- पॉलिसी पैरामीटर्स के संबंध में NI फंक्शन का नॉन-यूनिफॉर्म PŁ गुण, जो अभिसरण विश्लेषण के लिए महत्वपूर्ण है।
- NI फंक्शन और हाइपर-ऑब्जेक्टिव के स्मूथनेस और लिप्सचिट्ज़ निरंतरता गुण।

4. प्रयोगात्मक परिणाम (Experimental Results)

लेखक दो सेटिंग्स में संख्यात्मक प्रयोगों के माध्यम से PANDA को सत्यापित करते हैं:

सिंथेटिक इंसेंटिव डिज़ाइन प्रॉब्लम:
- सेटअप: एक UL डिज़ाइनर दो प्रतिस्पर्धी एजेंटों को प्रभावित करने के लिए प्रोत्साहन (incentives) निर्धारित करता है।
- बेसलाइन्स: तुलना Meta-Gradient (ह्यूरिस्टिक), Differentiable Arbitrating (DA, सेकंड-ऑर्डर), और PBRL (पेनल्टी-आधारित सिंगल-पॉलिसी) के विरुद्ध की गई।
- परिणाम: PANDA उच्चतम UL इंसेंटिव रिवॉर्ड प्राप्त करता है और नैश इक्विलिब्रियम (NE) गैप को शून्य के करीब लाता है। यह "ओरेकल" बेसलाइन के तुलनीय प्रदर्शन करता है जो सटीक डायनेमिक प्रोग्रामिंग और सेकंड-ऑर्डर जानकारी का उपयोग करता है, और अन्य फर्स्ट-ऑर्डर बेसलाइन्स की तुलना में काफी बेहतर प्रदर्शन करता है।
सेंटिनल-इंट्रूडर गेम:
- सेटअप: एक ग्रिड-वर्ल्ड गेम जहाँ एक सेंटिनल घुसपैठिए (intruder) को पकड़ने की कोशिश करता है। UL ऑब्जेक्टिव प्रतिबंधित (खतरनाक) क्षेत्रों में सेंटिनल के दौरों को कम करना है जबकि प्रतिस्पर्धी खेल बनाए रखना है।
- स्केल: $5 \times 5$ और $20 \times 20$ ग्रिड पर परीक्षण किया गया।
- परिणाम: PANDA लगातार DA, PBRL और Meta-Gradient की तुलना में कम UL लॉस (कम प्रतिबंधित क्षेत्र दौरे) और छोटा NE गैप प्राप्त करता है, जो स्केलेबिलिटी और मजबूती (robustness) को प्रदर्शित करता है।

5. महत्व और दावे (Significance and Claims)

यह पेपर दावा करता है कि PANDA पहला स्टोकेस्टिक फर्स्ट-ऑर्डर एल्गोरिदम है जिसके पास उन बाइलेवल समस्याओं के लिए प्रमाणित अभिसरण गारंटी है जहाँ लोअर लेवल एक रेगुलराइज्ड MMZSMG है।

अंतराल को भरना: यह BRL साहित्य के एक महत्वपूर्ण अंतर को संबोधित करता है जहाँ मौजूदा विधियाँ लोअर लेवल पर प्रतिस्पर्धी मल्टी-एजेंट इंटरैक्शन को कुशलतापूर्वक संभालने में विफल रहती हैं।
दक्षता: सेकंड-ऑर्डर जानकारी (हेसियन इनवर्जन) से बचकर, PANDA सरल सिंगल-पॉलिसी सेटिंग्स के लिए ज्ञात सर्वोत्तम सैंपल कॉम्प्लेक्सिटी दरों ( $\tilde{O}(\epsilon^{-3})$ ) को प्राप्त करते हुए बड़े पैमाने की समस्याओं के लिए कम्प्यूटेशनल रूप से व्यवहार्य बना रहता है।
व्यावहारिक प्रयोज्यता: यह विधि सैंपल-आधारित सेटिंग्स के लिए डिज़ाइन की गई है, जिससे यह प्रोत्साहन डिजाइन, मैकेनिज्म डिजाइन और एडवरसेरियल ट्रेनिंग जैसे वास्तविक दुनिया के परिदृश्यों के लिए सीधे तौर पर लागू होने योग्य बन जाती है जहाँ प्रतिस्पर्धी इक्विलिब्रियम केंद्रीय होते हैं।

लेखक निष्कर्ष निकालते हैं कि हालांकि उनका वर्तमान कार्य रेगुलराइज्ड MMZSMGs पर केंद्रित है, यह ढांचा सामान्य मिन-मैक्स गेम्स और व्यापक मल्टी-एजेंट सेटिंग्स तक बाइलेवल ऑप्टिमाइज़ेशन को विस्तारित करने के लिए एक आशाजनक दिशा प्रदान करता है।