Beyond Bayesian Nash: Learning Minimax-Regret Equilibria for Adversarial Team Games under Asymmetric Information
यह शोध पत्र प्रोबेबिलिस्टिकली रोबस्ट मिनिमैक्स-रिग्रेट इक्विलिब्रियम (PR-MRE) को प्रस्तुत करता है, जो विषम सूचना के तहत प्रतिकूल टीम खेलों के लिए एक नवीन समाधान अवधारणा है जो रणनीतिक धोखे को कम करने के लिए वितरण-मुक्त मजबूती (distribution-free robustness) को संभाव्य अंतर्दृष्टि के साथ जोड़ती है, और इन रणनीतियों को डीप रिइन्फोर्समेंट लर्निंग का उपयोग करके कुशलतापूर्वक गणना करने के लिए PRMRE-PSRO एल्गोरिदम का प्रस्ताव करता है।
मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें
कल्पना कीजिए कि आप एक विशाल, जटिल मानचित्र पर एक हाई-स्टेक्स 'कैप्चर द फ्लैग' (झंडा पकड़ो) का खेल खेल रहे हैं। आप ब्लू टीम में हैं, और आपका काम रेड टीम का छिपा हुआ झंडा ढूंढना और उसे हासिल करना है। यहाँ एक ट्विस्ट है: आपको ठीक-ठीक नहीं पता कि झंडा कहाँ है। आपके पास पिछले खेलों के आधार पर एक "सबसे अच्छा अनुमान" है—शायद आपको लगता है कि इसकी 70% संभावना बाईं सुरंग में है और 30% संभावना दाईं सुरंग में है। लेकिन रेड टीम? उन्हें सटीक स्थान पता है। वे झंडे को देख सकते हैं, और वे आपको जाल में फंसाने के लिए गलत जगह होने का नाटक करके आपको गुमराह भी कर सकते हैं।
यह एडवर्सरियल टीम गेम्स विद एसिमेट्रिक इंफॉर्मेशन (विषम सूचना वाले प्रतिकूल टीम खेल) की दुनिया है। नमन अग्रवाल और जोनाथन पी. हाउ का शोध पत्र एक बड़ी समस्या पर चर्चा करता है: आप तब कैसे खेलें जब आपका "सबसे अच्छा अनुमान" एक झूठ हो सकता है, या जब खेल के नियम उस तरह से बदल जाएं जिसकी आपने उम्मीद नहीं की थी?
"संभावनाओं के साथ खेलने" की समस्या
आमतौर पर, स्मार्ट खिलाड़ी एक रणनीति का उपयोग करते हैं जिसे बेयसियन नैश इक्विलिब्रियम (BNE) कहा जाता है। इसे एक मौसम विज्ञानी की तरह समझें जिसे केवल औसत की परवाह होती है। यदि पूर्वानुमान कहता है कि "बारिश की 70% संभावना है," तो वे 70% बार छाता पैक करते हैं और 30% बार बिना छाते के घर रहते हैं। खेल में, ब्लू टीम अपनी पूरी ऊर्जा बाईं सुरंग पर केंद्रित कर देगी क्योंकि वहीं झंडा होने की सबसे अधिक संभावना है।
लेकिन यहाँ एक पेंच है: रेड टीम चालाक है। यदि वे जानते हैं कि आप बाईं सुरंग के प्रति जुनूनी हैं, तो वे झंडे को दाईं सुरंग में स्थानांतरित कर सकते हैं। अचानक, आपकी "70% संभावना" वाली रणनीति बुरी तरह विफल हो जाती है। शोध पत्र तर्क देता है कि एक एकल "सबसे अच्छे अनुमान" (नोमिनल डिस्ट्रीब्यूशन) पर भरोसा करना खतरनाक है क्योंकि प्रतिद्वंद्वी स्थिति में हेरफेर कर सकता है। यह अपने जीवन की सारी जमा पूंजी एक ऐसे घोड़े पर लगाने जैसा है जिसके जीतने की संभावना अधिक है, केवल यह पता चलने के लिए कि जॉकी वास्तव में भेष बदलकर खड़ा आपका प्रतिद्वंद्वी है।
"सबसे खराब स्थिति" का जाल
कुछ खिलाड़ी अत्यधिक सुरक्षित होने की कोशिश करते हैं ताकि वे बिल्कुल सबसे खराब स्थिति के लिए तैयार रह सकें। वे मान लेते हैं कि झंडा कहीं भी हो सकता है, यहाँ तक कि ऐसी जगह भी जहाँ वह पहले कभी नहीं देखा गया। वे शायद मानचित्र के हर कोने में एक स्काउट भेज सकते हैं, बस सावधानी के तौर पर।
शोध पत्र सुझाव देता है कि यह दृष्टिकोण बहुत अधिक शंकालु (पैरानॉयड) है। यह एक धूल के सूक्ष्म कण की 0.01% संभावना के कारण फुल हज़मैट सूट पहनने जैसा है। हालांकि यह आपको सबसे बुरे से बचाता है, लेकिन यह आपको धीमा और अनाड़ी बना देता है, और आप खेल हार जाते हैं क्योंकि आप हिलने-डुलने से भी डर रहे होते हैं। शोध पत्र स्पष्ट रूप से इस "पूर्णतः सबसे खराब स्थिति" (fully worst-case) वाले दृष्टिकोण को वास्तविक दुनिया के खेलों के लिए बहुत अधिक रूढ़िवादी बताते हुए खारिज करता है, जहाँ कुछ परिणाम इतने दुर्लभ होते हैं कि उन पर चिंता करने की आवश्यकता नहीं होती।
नया नायक: PR-MRE
यहाँ समाधान के रूप में आता है: प्रोबेबिलिस्टिकली रोबस्ट मिनिमैक्स-रिग्रेट इक्विलिब्रियम (PR-MRE)।
PR-MRE को एक "स्मार्ट स्काउट" रणनीति के रूप में सोचें। केवल सबसे संभावित स्थान पर दांव लगाने (BNE की तरह) या जमीन के हर छेद की जांच करने (पैरानॉयड दृष्टिकोण की तरह) के बजाय, PR-MRE एक चतुर सवाल पूछता है: "यदि मैं गलती करता हूँ, तो मुझे कितना पछतावा होगा, और उस गलती के होने की कितनी संभावना है?"
यह एक विशेष नियम का उपयोग करता है जिसे "टिपिकैलिटी-प्रिजर्विंग थ्रेट मॉडल" कहा जाता है। कल्पना करें कि आपके पास "संदिग्ध" स्थानों की एक सूची है। आप जानते हैं कि कुछ स्थान इतने अजीब या असंभव (जैसे आसमान में झंडा होना) हैं कि आप उन्हें सुरक्षित रूप से अनदेखा कर सकते हैं। लेकिन उन स्थानों के लिए जो संभावित हैं (भले ही वे सबसे लोकप्रिय न हों), आप एक बैकअप योजना तैयार करते हैं।
PR-MRE कहता है: "मैं अत्यंत दुर्लभ, असंभव परिदृश्यों को अनदेखा कर दूँगा। लेकिन उन परिदृश्यों के लिए जो संभव हैं लेकिन कम सामान्य हैं, मैं यह सुनिश्चित करूँगा कि मुझे धोखा न दिया जाए।" यह "क्या आमतौर पर होता है" के गणित और "क्या गलत हो सकता है" के बीच संतुलन बनाता है।
उन्होंने इसका परीक्षण कैसे किया
लेखकों ने केवल इसे कागज पर नहीं लिखा; उन्होंने इसे टेस्ट करने के लिए एक कंप्यूटर सिमुलेशन बनाया। उन्होंने ग्राफ (पथों और नोड्स का एक नेटवर्क) पर कैप्चर द फ्लैग गेम का एक डिजिटल संस्करण बनाया।
अपने प्रयोगों में, उन्होंने नए PR-MRE को पुराने BNE के खिलाफ लड़ा।
- सेटअप: उन्होंने ब्लू टीम को एक "नोमिनल" विश्वास दिया कि झंडा 80% संभावना के साथ बाईं ओर और 20% संभावना के साथ दाईं ओर था।
- परीक्षण: इसके बाद उन्होंने सिस्टम को चकमा देने के लिए झंडे के वास्तविक स्थान को दाईं ओर (20% संभावना वाले स्थान पर) बदलकर या संभावनाओं को इधर-उधर करके परीक्षण किया।
- परिणाम: BNE टीम, जिसने बाईं ओर सब कुछ दांव पर लगा दिया था, दाईं ओर झंडा मिलने पर बुरी तरह हार गई। वे बहुमत पर बहुत अधिक केंद्रित थे।
- PR-MRE टीम: इन खिलाड़ियों ने अलग तरह से व्यवहार किया। सीधे बाईं ओर भागने के बजाय, उन्होंने पहले दोनों तरफ स्काउट भेजकर जांच की। वे पूरी तरह से एक पथ के प्रति प्रतिबद्ध होने से पहले सुनिश्चित होने का इंतजार करते रहे।
शोध पत्र दिखाता है कि इन सिमुलेशन में, PR-MRE टीम ने अप्रत्याशित रूप से झंडे का स्थान बदलने पर बहुत अधिक जीत दर बनाए रखी। वे केवल अधिक बार जीते ही नहीं; उन्हें धोखा देना बहुत कठिन था। शोध पत्र स्पष्ट रूप से बताता है कि जबकि BNE तब बहुत अच्छा काम करता है जब खेल बिल्कुल वैसा ही रहता है जैसा भविष्यवाणी की गई थी, PR-MRE वह है जो तब जीवित रहता है जब प्रतिद्वंद्वी आपको धोखा देने की कोशिश करता है।
जादू के पीछे का गणित
इसे काम करने के लिए, लेखकों को कुछ बहुत ही जटिल गणितीय समस्याओं को हल करना पड़ा। उन्होंने इस खेल को एक "रोबस्ट बायलिनियर प्रोग्राम" में बदल दिया। इस भारी-भरकम नाम से न डरें; इसे एक जटिल पहेली के रूप में समझें जहाँ आपको अपना सर्वश्रेष्ठ कदम ढूंढना होता है, यह मानते हुए कि प्रतिद्वंद्वी आपके विशिष्ट प्लान को बिगाड़ने की कोशिश कर रहा है।
उन्होंने PRMRE-PSRO नामक एक नया एल्गोरिदम बनाया। यह एक ट्रेनिंग कैंप की तरह है जहाँ AI एजेंट एक-दूसरे के खिलाफ हजारों बार खेलते हैं। "ब्लू" एजेंट "रिग्रेट-मिनिमाइजिंग" (पछतावा कम करने वाले) बनने के लिए सीखते हैं, जिसका अर्थ है कि वे उन चालों से बचना सीखते हैं जो उन्हें बाद में पछतावा कराएंगी यदि झंडा कहीं और निकला। "रेड" एजेंट किसी भी कमजोरी का फायदा उठाने के लिए सीखते हैं। इस उतार-चढ़ाव के माध्यम से, ब्लू टीम एक ऐसी रणनीति सीखती है जो धोखे के प्रति मजबूत (robust) है।
निष्कर्ष
यह शोध पत्र सुझाव देता है कि जिन खेलों में एक पक्ष के पास दूसरे की तुलना में अधिक जानकारी होती है, वहां आपको केवल भीड़ का अनुसरण (सबसे संभावित परिणाम) नहीं करना चाहिए या हर एक संभावना के बारे में घबराना नहीं चाहिए। इसके बजाय, आपको PR-MRE का उपयोग करना चाहिए: एक ऐसी रणनीति जो "सामान्य" संभावनाओं का सम्मान करती है लेकिन "संभावित लेकिन कम सामान्य" परिदृश्यों के लिए एक सुरक्षा जाल रखती है।
इन सिमुलेशन में, यह दृष्टिकोण ब्लू टीमों को "ओवर-कमिट" (एक अनुमान पर सब कुछ दांव पर लगाना) करने के बजाय "स्कौटिंग" (कई विकल्पों की जांच करना) करने में बेहतर बनाता है। इसने उन्हें तब धोखा देना बहुत कठिन बना दिया जब रेड टीम ने खेल की वास्तविकता को बदलने की कोशिश की। लेखक निष्कर्ष निकालते हैं कि यह विधि तब प्रदर्शन की एक मजबूत गारंटी प्रदान करती है जब प्रतिद्वंद्वी इतना स्मार्ट हो कि वह चलते-फिरते नियमों को बदल सके।
अपने क्षेत्र के पेपरों की भीड़ में उलझे हुए हैं?
आपके रिसर्च कीवर्ड से मेल खाने वाले सबसे नए और अलग सोच वाले पेपरों का रोज़ाना Digest पाएँ—तकनीकी सारांश के साथ, आपकी भाषा में।