Minimax-Optimal Policy Regret in Partially Observable Markov Games

तकनीकी सारांश: आंशिक रूप से अवलोकन योग्य मार्कोव खेलों में मिनिमैक्स-इष्टतम नीति पछतावा (Minimax-Optimal Policy Regret)

समस्या का निरूपण
यह शोध पत्र रणनीतिक, अनुकूलनशील विरोधियों के विरुद्ध आंशिक रूप से अवलोकन योग्य वातावरणों (Partially Observable Markov Games - POMGs) में अनुक्रमिक निर्णय लेने की समस्या को संबोधित करता है। मुख्य चुनौती आंशिक अवलोकनों से गुप्त विश्व गतिकी (latent world dynamics) को सीखना है, जबकि एक ऐसा प्रतिपक्षी (adversary) मौजूद है जिसका व्यवहार शिक्षार्थी (learner) की रणनीति के अनुसार बदलता रहता है। इस परिवेश में मानक 'एक्सटर्नल रिग्रेट' (external regret) की अवधारणाएं अपर्याप्त हैं क्योंकि वातावरण की प्रतिक्रिया शिक्षार्थी के पिछले कार्यों पर निर्भर करती है, जिससे काउंटरफैक्चुअल निर्भरताएं (counterfactual dependencies) उत्पन्न होती हैं। फलस्वरूप, यह शोध पत्र प्रदर्शन मेट्रिक के रूप में पॉलिसी रिग्रेट (policy regret) को अपनाता है, जो शिक्षार्थी के संचयी पुरस्कार (cumulative reward) की तुलना सर्वोत्तम स्थिर नीति $\pi^*$ से करता है—यह मानते हुए कि यदि शिक्षार्थी शुरुआत से ही $\pi^*$ के प्रति प्रतिबद्ध होता, तो प्रतिपक्षी अंततः एक स्थिर प्रतिक्रिया $R_\infty(\pi^*)$ की ओर अभिसरित हो जाता।

इस परिवेश में दो खिलाड़ी शामिल हैं: एक शिक्षार्थी और एक प्रतिपक्षी, दोनों ही आंशिक अवलोकन के अधीन कार्य करते हैं। शिक्षार्थी संकेतों $o^A$ को देखता है और प्रतिपक्षी $o^B$ को देखता है, जबकि गुप्त अवस्था (latent state) दोनों खिलाड़ियों के कार्यों के आधार पर परिवर्तित होती है। यह माना गया है कि प्रतिपक्षी $m$-मेमोरी बाउंडेड (m-memory bounded) है, जिसका अर्थ है कि किसी भी एपिसोड में इसकी प्रतिक्रिया केवल पिछले $m$ एपिसोड के शिक्षार्थी की नीतियों पर निर्भर करती है।

कार्यप्रणाली और एल्गोरिदम ढांचा
लेखक पॉलिसी रिग्रेट को कम करने के लिए एक एपॉक-आधारित आशावादी मैक्सिमम लाइकलीहुड एस्टीमेशन (MLE) एल्गोरिदम (एल्गोरिदम 1) प्रस्तावित करते हैं। यह कार्यप्रणाली निम्नलिखित प्रमुख संरचनात्मक घटकों पर आधारित है:

1. कारण संबंधी अपघटन (Causal Decomposition): एक केंद्रीय सैद्धांतिक योगदान अवलोकन योग्य ऑपरेटर $J_{\xi,\pi}^h$ को दो अलग-अलग घटकों में विभाजित करना है:

   • एक वर्ल्ड चैनल (world channel) $W_h^\theta$, जो केवल विश्व गतिकी (ट्रांज़िशन और एमिशन कर्नेल) पर निर्भर करता है और प्रतिपक्षी के रिस्पॉन्स मॉडल से स्वतंत्र है।
   • एक एडवर्सरी एग्रीगेशन (adversary aggregation) ऑपरेटर $G_{\Phi,\pi}^h$, जो प्रतिपक्षी के रिस्पॉन्स फंक्शन और शिक्षार्थी की नीति पर निर्भर करता है, लेकिन विश्व पैरामीटर $\theta$ से स्वतंत्र है।
     यह गुणनखंड (factorization) एल्गोरिदम को विश्व गतिकी के अनुमान को प्रतिपक्षी की प्रतिक्रियाओं के नियंत्रण से अलग करने की अनुमति देता है।

2. संरचनात्मक धारणाएं (Structural Assumptions):

   • पोस्टीरियर-लिप्सचिट्ज़ एडवर्सरी (Posterior-Lipschitz Adversary): प्रतिपक्षी की प्रतिक्रिया शिक्षार्थी की नीति के साथ सुचारू रूप से बदलती है। महत्वपूर्ण रूप से, यह सुगमता एक निश्चित संदर्भ माप $\mu_{ref}$ (जो प्रतिपक्षी की वास्तविक रणनीति से स्वतंत्र है) के सापेक्ष परिभाषित है ताकि परिभाषा में चक्रीय निर्भरता (circular dependencies) से बचा जा सके।
   • मल्टी-स्टेप वीक रिवीलिंग (Multi-step Weak Revealing): अवलोकन $\kappa$ स्टेप्स की विंडो के दौरान गुप्त अवस्थाओं के बारे में पर्याप्त सूचनात्मक होते हैं, जिससे यह सुनिश्चित होता है कि विश्व गतिकी में विसंगतियों का पता लगाया जा सके।
   • एलुडर डायमेंशन (Eluder Dimension): संयुक्त विश्व-प्रतिपक्षी मॉडल क्लास की जटिलता को यूनिफॉर्म एग्रीगेट एलुडर डायमेंशन ($d_E$) द्वारा मापा जाता है।

3. एपॉक-आधारित निष्पादन (Epoch-Based Execution): एल्गोरिदम समय को ज्यामितीय रूप से बढ़ते एपॉक्स ($T_e = 2^e$) में विभाजित करता है। प्रत्येक एपॉक के भीतर:

   • एक एकल नीति $\pi_e$ को पिछले सभी डेटा से निर्मित संचयी विश्वास सेट (confidence set) से आशावादी रूप से चुना जाता है।
   • एक वार्म-अप चरण ($m-1$ एपिसोड) $m$-मेमोरी वाले प्रतिपक्षी को वर्तमान नीति के लिए अपनी स्थिर प्रतिक्रिया तक स्थिर होने की अनुमति देता है।
   • नीति को $T_e$ डेटा-संग्रह एपिसोड के लिए निष्पादित किया जाता है।
     यह संरचना सुनिश्चित करती है कि शिक्षार्थी $T$ एपिसोडों में केवल $O(\log T)$ विशिष्ट नीतियों को तैनात करता है, जो विभिन्न नीतियों के बीच प्रतिपक्षी प्रतिक्रियाओं की तुलना करने की लागत को नियंत्रित करने के लिए महत्वपूर्ण है।

प्रमुख परिणाम
शोध पत्र पॉलिसी रिग्रेट पर एक मिनिमैक्स-इष्टतम ऊपरी सीमा (upper bound) और एक मिलान निचली सीमा (lower bound) स्थापित करता है।

• ऊपरी सीमा (Upper Bound): घोषित धारणाओं के तहत, एल्गोरिदम निम्नलिखित पॉलिसी रिग्रेट प्राप्त करता है:
  $$PR(T) \leq C \left( H \sqrt{\bar{\beta}_T \cdot d_E \cdot T} + mH \log T \right)$$
  जहाँ $\bar{\beta}_T = H\beta_T + H^2 \log T$ है। पद $H^2 \log T$ $O(\log T)$ विशिष्ट नीतियों के बीच प्रतिपक्षी प्रतिक्रियाओं की तुलना करने के "ट्रांसपोर्ट कॉस्ट" (transport cost) का प्रतिनिधित्व करता है। $\sqrt{T}$ निर्भरता ज्यामितीय एपॉक संरचना द्वारा प्राप्त की जाती है; $O(\sqrt{T})$ नीतियां तैनात करने से (जैसा कि फ्लैट बैचिंग में होता है), ट्रांसपोर्ट कॉस्ट के संचय के कारण $T^{3/4}$ रिग्रेट दर प्राप्त होगी।

• निचली सीमा (Lower Bound): लेखक किसी भी एल्गोरिदम के लिए $\Omega(\sqrt{d_E T})$ की निचली सीमा सिद्ध करते हैं, यहाँ तक कि मेमोरीलेस एडवर्सरी वाले पूर्ण रूप से रिवीलिंग (fully revealing) POMGs में भी। यह पुष्टि करता है कि ऊपरी सीमा में $\sqrt{T}$ और $d_E$ निर्भरता, समस्या-निर्भर और लॉगरिदमिक कारकों तक, इष्टतम है।

• विस्तार (Extensions): ढांचे को निम्नलिखित को संभालने के लिए विस्तारित किया गया है:

  • अज्ञात क्षितिज (Unknown Horizons): एल्गोरिदम बिना किसी संशोधन के अज्ञात $T$ के अनुकूल हो जाता है।
  • फेडिंग मेमोरी एडवर्सरीज (Fading Memory Adversaries): परिणाम ज्यामितीय रूप से घटने वाली मेमोरी वाले विरोधियों के लिए भी मान्य हैं, जहाँ वार्म-अप लागत $O(\frac{H \log^2 T}{1-\gamma})$ के रूप में स्केल होती है।
  • टेबुलर सेटिंग्स (Tabular Settings): स्टेट, एक्शन और ऑब्जर्वेशन स्पेस के आकार के संदर्भ में स्पष्ट सीमाएं प्राप्त की गई हैं।

महत्व और दावे
यह शोध पत्र दावा करता है कि यह अनुकूलनशील विरोधियों के विरुद्ध POMGs में पॉलिसी रिग्रेट न्यूनीकरण के लिए एक पूर्ण सैद्धांतिक उपचार प्रदान करता है। इसका प्राथमिक महत्व यह प्रदर्शित करने में है कि इस जटिल परिवेश में कुशल शिक्षण ($\sqrt{T}$ रिग्रेट के साथ) संभव है, बशर्ते कि प्रतिपक्षी की प्रतिक्रिया सुचारू (Posterior-Lipschitz) हो और अवलोकन कमजोर रूप से प्रकट करने वाले (weakly revealing) हों।

लेखक दो विशिष्ट तकनीकी नवाचारों को रेखांकित करते हैं जो इस परिणाम को सक्षम करते हैं:

1. गैर-चक्रीय सूत्रीकरण (Non-circular Formulation): एक निश्चित संदर्भ माप के सापेक्ष पोस्टीरियर-लिप्सचिट्ज़ स्थिति को परिभाषित करके, वे उन चक्रीयता समस्याओं से बचते हैं जो पूर्व प्रारूपों में मौजूद थीं जहाँ सुगमता मेट्रिक प्रतिपक्षी के बाधित होने पर निर्भर थी।
2. लॉगरिदमिक ट्रांसपोर्ट कॉस्ट (Logarithmic Transport Cost): एपॉक-आधारित संरचना के माध्यम से शिक्षार्थी को $O(\log T)$ विशिष्ट नीतियों तक सीमित करके, वे यह सुनिश्चित करते हैं कि एडवर्सरी-रिस्पॉन्स एरर को ट्रांसपोर्ट करने की लागत लॉगरिदमिक बनी रहे, जिससे इष्टतम $\sqrt{T}$ दर सुरक्षित रहती है। यह फ्लैट-बैचिंग दृष्टिकोणों के विपरीत है, जो लेखकों के अनुसार, ट्रांसपोर्ट कॉस्ट में बहुपद वृद्धि के कारण उप-इष्टतम $T^{3/4}$ दरों की ओर ले जाते हैं।

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