Optimal Rates for Feasible Payoff Set Estimation in Games

तकनीकी सारांश: खेलों में व्यवहार्य पे-ऑफ सेट (Feasible Payoff Set) के अनुमान के लिए इष्टतम दरें

समस्या का निरूपण
यह शोध पत्र इनवर्स गेम थ्योरी (Inverse Game Theory) की समस्या को संबोधित करता है, जो विशेष रूप से एक एकल बिंदु अनुमान के बजाय व्यवहार्य पे-ऑफ सेट (Feasible Payoff Set) के अनुमान पर केंद्रित है। इस परिवेश में, एक शिक्षार्थी (Learner) दो खिलाड़ियों के कार्यों का अवलोकन करता है जो एक अज्ञात बाईमैट्रिक्स गेम (या तो सामान्य-योग या शून्य-योग) में लगे हुए हैं, जहाँ खिलाड़ी एक नैश इक्विलिब्रियम (संभवतः सन्निकट/approximate) खेल रहे हैं। शिक्षार्थी को खिलाड़ियों के मिश्रित रणनीतियों (Mixed Strategies) $(x, y)$ के उत्पाद वितरण (Product Distribution) से प्राप्त i.i.d. नमूनों के क्रिया युग्मों $(X_t, Y_t)$ के नमूने मिलते हैं।

मुख्य चुनौती यह है कि व्यवहार से उपयोगिता कार्यों (Utility Functions) का निष्कर्ष निकालना स्वाभाविक रूप से अनिर्धारित (Underdetermined/Unidentifiable) है; कई पे-ऑफ मैट्रिसेस एक ही देखे गए इक्विलिब्रियम व्यवहार को तर्कसंगत बना सकते हैं। फलस्वरूप, इस शोध पत्र का लक्ष्य उन सभी पे-ऑफ मैट्रिसेस $(A', B')$ के सेट का अनुमान लगाना है जिनके लिए देखे गए रणनीतियाँ $(x, y)$ एक $\alpha$-नैश इक्विलिब्रियम बनाती हैं। इसका उद्देश्य इस सेट को उच्च प्रायिकता ($1-\delta$) और परिशुद्धता $\epsilon$ के साथ अनुमानित करना है, जिसे हाउसरडॉर्फ दूरी (Hausdorff Distance, $\mathcal{H}$) द्वारा मापा जाता है।

कार्यप्रणाली
लेखक एक सरल, गैर-पुनरावृत्ति (Non-iterative) शिक्षण एल्गोरिदम (प्रक्रिया 1) प्रस्तावित करते हैं और इसके सैंपल कॉम्प्लेक्सिटी (Sample Complexity) के कठोर सैद्धांतिक विश्लेषण के माध्यम से ऊपरी और निचली सीमाओं (Lower and Upper Bounds) को स्थापित करते हुए मिनिमैक्स इष्टतमता (Minimax Optimality) सिद्ध करते हैं।

1. एल्गोरिदम: शिक्षार्थी $m$ नमूनों को एकत्र करता है ताकि औसत रणनीतियों $\hat{x}$ और $\hat{y}$ की गणना की जा सके। एल्गोरिदम फिर उन सभी पे-ऑफ मैट्रिसेस के सेट को आउटपुट के रूप में देता है जिनके लिए $(\hat{x}, \hat{y})$ एक $\alpha$-नैश इक्विलिब्रियम है। यह सेट रैखिक असमानताओं (Linear Inequalities) द्वारा परिभाषित किया जाता है और इसे एक रैखिक व्यवहार्यता समस्या (Linear Feasibility Problem) के रूप में दर्शाया जा सकता है।
2. सटीक इक्विलिब्रियम ($\alpha = 0$) का विश्लेषण:
   • निचली सीमा (Lower Bound): लेखक यह प्रदर्शित करते हैं कि सटीक इक्विलिब्रियम से व्यवहार्य सेट को सीखना सामान्य मामले में अशिक्ष्य (Unlearnable) है, क्योंकि रणनीतियों और पे-ऑफ सेट्स के बीच संबंध में तीव्र विच्छिन्नता (Discontinuity) होती है। विशेष रूप से, यदि वास्तविक रणनीति प्रोफाइल में कुछ क्रियाओं की प्रायिकता लुप्त हो जाती है (Support बदल जाता है), तो रणनीतियाँ सांख्यिकीय रूप से अविभेद्य होने के बावजूद व्यवहार्य सेट्स के बीच हाउसरडॉर्फ दूरी बड़ी बनी रह सकती है। इस समस्या को सीखने योग्य बनाने के लिए, वे एक न्यूनतम प्रायिकता धारणा ($\pi_{\min}$) लागू करते हैं, जो यह सुनिश्चित करती है कि सपोर्ट में प्रत्येक क्रिया को शून्य से दूर एक निश्चित सीमा से ऊपर की प्रायिकता के साथ खेला जाए।
   • ऊपरी सीमा (Upper Bound): $\pi_{\min}$ धारणा के तहत, लेखक वास्तविक व्यवहार्य सेट $G(x, y)$ और अनुमानित सेट $G(\hat{x}, \hat{y})$ के बीच एक मैपिंग का निर्माण करते हैं। वे दिखाते हैं कि हाउसरडॉर्फ त्रुटि वास्तविक और अनुभवजन्य रणनीतियों के बीच $\ell_1$-दूरी ($\|x - \hat{x}\|_1 + \|y - \hat{y}\|_1$) के रैखिक रूप से स्केल करती है।
3. सन्निकट इक्विलिब्रियम ($\alpha > 0$) का विश्लेषण:
   • निचली सीमा: $\alpha$ की उपस्थिति विच्छिन्नता की समस्याओं को कम करती है जो सटीक मामले में पाई गई थीं, जिससे $\pi_{\min}$ धारणा के बिना भी यह समस्या सीखने योग्य बन जाती है। हालाँकि, लेखक सिद्ध करते हैं कि सैंपल कॉम्प्लेक्सिटी $\alpha$ के व्युत्क्रमानुपाती (Inversely proportional) है (विशेष रूप से $\alpha^{-1}$)। $\alpha$ के छोटे मान सीखने की दर को काफी खराब कर देते हैं क्योंकि जब प्रायिकताएँ $\alpha$ के आसपास होती हैं, तो रणनीतियों में छोटे परिवर्तन व्यवहार्य सेट की ज्यामिति में बड़े बदलाव ला सकते हैं।
   • ऊपरी सीमा: इस विश्लेषण में हाउसरडॉर्फ दूरी त्रुटि का एक नवीन अपघटन (Decomposition) शामिल है। लेखक त्रुटि नियंत्रण समस्या को एक फ्रैक्शनल नैपसैक समस्या (Fractional Knapsack Problem) में बदल देते हैं। व्यवहार्य सेट $G_\alpha(x, y)$ की ज्यामितीय संरचना का लाभ उठाते हुए, वे दिखाते हैं कि त्रुटि पद $(\hat{x} - x)^\top Ay$ का विचरण (Variance) छोटा है, जिससे मानक बाउंड्स की तुलना में तेज़ अभिसरण दर (Concentration Rates) प्राप्त होती है। वे "मिसिंग मास" (Missing Mass) समस्या (ऐसी क्रियाएं जिन्हें अनुभवजन्य वितरण में शून्य के रूप में देखा गया लेकिन वास्तविकता में गैर-शून्य हैं) को मिसिंग मास के लिए एकाग्रता असमानताओं (Concentration Inequalities) का उपयोग करके संभालते हैं।

प्रमुख योगदान और परिणाम
यह शोध पत्र सटीक और सन्निकट दोनों प्रकार के इक्विलिब्रियम के लिए, शून्य-योग और सामान्य-योग दोनों खेलों में व्यवहार्य पे-ऑफ सेट्स के अनुमान के लिए प्रथम मिनिमैक्स-इष्टतम सैंपल कॉम्प्लेक्सिटी दरें प्रदान करता है।

• सटीक इक्विलिब्रियम ($\alpha = 0$):
  • शर्त: $\pi_{\min} > 0$ (किसी भी क्रिया को खेलने की न्यूनतम प्रायिकता) की आवश्यकता है।
  • सैंपल कॉम्प्लेक्सिटी: $m = \tilde{O}\left( \frac{\log(1/\delta)}{\log(1/(1-\pi_{\min}))} + \frac{n + \log(1/\delta)}{\epsilon^2} \right)$।
  • पहला पद रणनीतियों के सपोर्ट को सीखने से संबंधित है; दूसरा भाग रणनीतियों को पर्याप्त सटीकता से अनुमानित करने से संबंधित है ताकि हाउसरडॉर्फ दूरी को सीमित किया जा सके।
• सन्निकट इक्विलिब्रियम ($\alpha > 0$):
  • शर्त: न्यूनतम प्रायिकता धारणा की आवश्यकता नहीं है।
  • सैंपल कॉम्प्लेक्सिटी: $m = O\left( \frac{n + \log(1/\delta)}{\epsilon^2 \alpha} + \frac{\sqrt{n}\log(1/\delta)}{\epsilon \alpha} \right)$।
  • परिणाम $\alpha^{-1}$ पर अनिवार्य निर्भरता को प्रकट करते हैं। छोटे $\epsilon$ के लिए $\frac{n}{\epsilon^2 \alpha}$ वाला पद प्रभावी होता है, जबकि बड़े $\epsilon$ के लिए $\frac{\sqrt{n}}{\epsilon \alpha}$ प्रासंगिक हो जाता है।
• शून्य-योग बनाम सामान्य-योग: लेखक इन्हें अलग-अलग समस्याओं के रूप में देखते हैं। यद्यपि शून्य-योग गेम सामान्य-योग गेम का एक उपसमुच्चय है, लेखक नोट करते हैं कि केवल सामान्य-योग अनुमान को शून्य-योग बाधा ($A = -B$) को संतुष्ट करने के लिए काटने से हाउसरडॉर्फ दूरी की दिशात्मकता (Directionality) के मुद्दों के कारण शून्य-योग सेट के लिए इष्टतम अनुमान स्वतः प्राप्त नहीं होता है। वे दोनों परिवेशों के लिए विशिष्ट निर्माण (Constructions) प्रदान करते हैं।

महत्व और दावे
यह शोध पत्र मल्टी-एजेंट वातावरण में सेट-वैल्यूड पे-ऑफ इन्फरेंस (Set-valued payoff inference) के लिए लर्निंग-थ्योरेटिक आधार प्रदान करने का दावा करता है। अतिरिक्त मॉडलिंग धारणाओं (जैसे पैरामीट्रिक परिवार) या पूर्व-निर्धारित चयन सिद्धांतों (जैसे मैक्सिमम एंट्रॉपी) को थोपे बिना, प्रस्तावित दृष्टिकोण:

1. अंतर्निहित अस्पष्टता को कैप्चर करता है: यह सभी संगत पे-ऑफ्स के सेट को स्पष्ट रूप से दर्शाता है, जिससे विशिष्ट संरचनात्मक बाधाओं या चयन मानदंडों को लागू करने के लिए डाउनस्ट्रीम अनुप्रयोगों (जैसे मैकेनिज्म डिज़ाइन, काउंटरफैक्टुअल विश्लेषण) पर निर्णय को टाल दिया जाता है।
2. मौलिक सीमाओं को स्थापित करता है: मिलान करने वाली निचली और ऊपरी सीमाएं समस्या की सांख्यिकीय कठिनाई को स्पष्ट करती हैं, जो $\alpha$ पैरामीटर और रणनीतियों के सपोर्ट स्ट्रक्चर की महत्वपूर्ण भूमिका को रेखांकित करती हैं।
3. मॉड्यूलरिटी: सेट-वैल्यूड परिप्रेक्ष्य संरचनात्मक अर्थशास्त्र (Structural Econometrics) में मानक है लेकिन गेम लर्निंग में सैद्धांतिक रूप से कम समझा गया है; यह कार्य उस अंतर को पाटता है।

लेखक स्पष्ट रूप से कहते हैं कि उनका विश्लेषण इंस्टेंस-इंडिपेंडेंट (Instance-independent) है और भविष्य के कार्य इंस्टेंस-डिपेंडेंट बाउंड्स या अनंत एक्शन स्पेस और विकसित होती रणनीति प्रोफाइल्स (जैसे रिग्रेट मिनिमाइजेशन) के विस्तार की खोज कर सकते हैं। वे स्थापित सैद्धांतिक ढांचे के परे किसी विशिष्ट प्रयोगात्मक सत्यापन या नए अनुप्रयोगों का प्रस्ताव नहीं करते हैं।