प्रतिस्पर्धी बहु-एजेंटों को 'सो लॉन्ग सकर' खेलने के लिए सुदृढ़ करना

मूल जानकारी

• पेपर ID: 2411.11057
• शीर्षक: प्रतिस्पर्धी बहु-एजेंटों को 'सो लॉन्ग सकर' खेलने के लिए सुदृढ़ करना
• लेखक: मेदांत शरण (किंग्स कॉलेज लंदन), चंद्रनाथ अदक (IIT पटना)
• वर्गीकरण: cs.AI
• प्रकाशन समय: नवंबर 2024 (arXiv प्रीप्रिंट)
• पेपर लिंक: https://arxiv.org/abs/2411.11057

सारांश

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

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या परिभाषा

मौजूदा बहु-एजेंट सुदृढ़ीकरण सीखने के बेंचमार्क मुख्य रूप से शुद्ध सहयोगी उद्देश्यों (जैसे समन्वय कार्य) या प्रतिकूल प्रतिस्पर्धा (जैसे दो-व्यक्ति शून्य-योग खेल) पर केंद्रित हैं, और गठबंधन निर्माण और विश्वासघात गतिशीलता दोनों को पकड़ने वाले मिश्रित वातावरण की कमी है। हालांकि Go, StarCraft II और Diplomacy जैसे क्षेत्रों में सफलताएं मिली हैं, लेकिन ये बेंचमार्क SLS के लिए अद्वितीय गठबंधन और विश्वासघात की मिश्रित गतिशीलता को पूरी तरह से प्रतिबिंबित नहीं करते हैं।

अनुसंधान का महत्व

SLS, जिसे Hausner, Nash, Shapley और Shubik द्वारा डिजाइन किया गया एक चार-व्यक्ति रणनीतिक खेल है, गठबंधन निर्माण, अस्थायी गठबंधन और अनिवार्य विश्वासघात के चारों ओर घूमता है। जीत न केवल कानूनी कार्यों पर निर्भर करती है, बल्कि राजनयिक और अवसरवादी कार्यों की भी आवश्यकता होती है, जिससे यह विश्वास, वार्ता और सामाजिक दुविधाओं का अध्ययन करने के लिए एक अद्वितीय परीक्षण मंच बन जाता है।

मौजूदा तरीकों की सीमाएं

1. अधिकांश MARL बेंचमार्क में गठबंधन और विश्वासघात की मिश्रित गतिशीलता की कमी है
2. सामाजिक रूप से समृद्ध सेटिंग्स पर पूर्व कार्य आमतौर पर स्पष्ट संचार चैनलों या हाथ से तैयार किए गए इंटरैक्शन नियमों पर निर्भर करते हैं
3. SLS को पहले कम्प्यूटेशनल बेंचमार्क के रूप में अध्ययन नहीं किया गया है

अनुसंधान प्रेरणा

SLS को एक पुनरुत्पादनीय अनुक्रमिक वेरिएंट के रूप में औपचारिक बनाकर और आधारभूत DRL एल्गोरिदम को बेंचमार्क करके, यह पेपर SLS को MARL अनुसंधान को आगे बढ़ाने के लिए एक गठबंधन और विश्वासघात-जागरूक परीक्षण मंच के रूप में स्थापित करता है।

मुख्य योगदान

1. पहला SLS कम्प्यूटेशनल ढांचा: सुदृढ़ीकरण सीखने के अनुसंधान के लिए विशेष रूप से डिजाइन किया गया पहला SLS कम्प्यूटेशनल ढांचा तैयार और जारी किया गया, जो GUI के साथ आता है
2. शास्त्रीय DRL एल्गोरिदम बेंचमार्किंग: SLS में शास्त्रीय DRL एल्गोरिदम (DQN, DDQN, Dueling DQN) को बेंचमार्क किया गया, कानूनी खेल कौशल प्राप्त करने और आंशिक रणनीति जागरूकता की क्षमता का विश्लेषण किया गया
3. गठबंधन और विश्वासघात-जागरूक बेंचमार्क: SLS को MARL के लिए एक गठबंधन और विश्वासघात-जागरूक बेंचमार्क के रूप में स्थापित किया, DRL और खेल सिद्धांत तर्क को जोड़ने वाली संकर विधियों के भविष्य के अनुसंधान को प्रेरित किया

विधि विवरण

कार्य परिभाषा

SLS को MARL वातावरण में परिवर्तित किया गया है, Hofstra संस्करण के शून्य-योग वेरिएंट को अपनाया गया। चार खिलाड़ियों को प्रत्येक को एक अद्वितीय रंग सौंपा गया है, प्रत्येक 5 समान-रंग की चिप्स से शुरू करते हैं, अधिकतम 6 सक्रिय ढेर के साथ एक बोर्ड पर खेल खेलते हैं। जीत की शर्त अंतिम जीवित खिलाड़ी बनना है।

सुदृढ़ीकरण सीखने का औपचारिकीकरण

SLS को मार्कोव निर्णय प्रक्रिया (MDP) के रूप में मॉडल किया गया है:

• अवस्था स्थान S: सभी संभावित खेल अवस्थाओं का सेट
• कार्य स्थान A: एजेंट के लिए उपलब्ध सभी कार्यों का सेट (असतत वैध चाल)
• संक्रमण फ़ंक्शन: p(s'|s,a) अवस्था s में कार्य a निष्पादित करने के बाद s' में संक्रमण की संभावना को दर्शाता है
• पुरस्कार फ़ंक्शन: r(s,a,s') प्रत्येक संक्रमण के लिए एक अदिश मान निर्दिष्ट करता है
• नीति: π(a|s) दी गई अवस्था s में एजेंट द्वारा कार्य a चुनने की नीति है

लक्ष्य अपेक्षित छूट प्राप्त को अधिकतम करने के लिए सर्वोत्तम नीति π* खोजना है: $R_t = \sum_{k=0}^{\infty} \gamma^k r_{t+k+1}$

अवस्था प्रतिनिधित्व

अवस्था st खेल के वातावरण का वर्णन करने के लिए आवश्यक सभी जानकारी को एन्कोड करता है: $s_t = (Board\ Configuration, Player\ Chips, Eliminated\ Chips, Current\ Player, Game\ Phase, Step\ Count)$

अवलोकन स्थान का आकार है: $obs\_size = (n_{rows} \times n_{players} \times n_{max\_pile}) + n_{players}^2 + (2 \times n_{players}) + 4 + 1$

कार्य स्थान

असतत कार्य स्थान A = {A₀, A₁, ..., A₉}, जिसमें शामिल हैं:

• A₀-A₅: ढेर चयन कार्य (ढेर चयन चरण में वैध)
• A₆-A₉: खिलाड़ी/रंग निर्णय कार्य (चिप चयन, अगले खिलाड़ी चयन, चिप उन्मूलन चरण में वैध)

पुरस्कार डिजाइन

समय चरण t पर पुरस्कार संकेत को परिभाषित किया गया है: $r_t = \min\left(\wp, \frac{\wp}{(\alpha/n_c) \cdot t}\right)$

जहां α ∈ (0,1] क्षय दर को नियंत्रित करने वाला हाइपरपैरामीटर है, ℘ पुरस्कार परिमाण है। अवैध कार्यों को निश्चित नकारात्मक पुरस्कार (-℘) से दंडित किया जाता है, कानूनी कार्यों को +℘ तक सकारात्मक पुरस्कार मिलते हैं, यह मान दक्षता को बढ़ावा देने के लिए चरणों के साथ क्षय होता है।

प्रायोगिक सेटअप

खेल कॉन्फ़िगरेशन

• खिलाड़ियों की संख्या: 4 खिलाड़ी
• प्रारंभिक चिप्स: प्रत्येक खिलाड़ी के लिए 5 समान-रंग की चिप्स
• अधिकतम ढेर संख्या: 6 सक्रिय ढेर
• जीत की शर्त: शून्य-योग खेल, पुरस्कार संरचना {0,0,0,ù}, ù ∈ N⁺

प्रशिक्षण कॉन्फ़िगरेशन

केंद्रीकृत संचयी सीखने की सेटिंग अपनाई गई, सभी चार खिलाड़ी एजेंट एक सामान्य सीखने वाले नेटवर्क और रीप्ले बफर साझा करते हैं। नेटवर्क आर्किटेक्चर दो 64-न्यूरॉन पूरी तरह से जुड़ी हुई छिपी परतें (ReLU सक्रियण) है, जिसके बाद एक रैखिक आउटपुट परत है।

हाइपरपैरामीटर सेटिंग्स

• छूट कारक γ = 0.95
• प्रारंभिक अन्वेषण दर ε₀ = 1.0
• अन्वेषण क्षय दर ε_decay = 0.995
• न्यूनतम अन्वेषण दर ε_min = 0.01
• सीखने की दर = 0.001
• बैच आकार = 64
• प्रशिक्षण एपोक = 10,000 खेल

मूल्यांकन मेट्रिक्स

• संचयी पुरस्कार माध्य और मानक विचलन
• प्रति खेल औसत चरण
• पुरस्कार रेंज न्यूनतम, अधिकतम
• चरण रेंज न्यूनतम, अधिकतम

तुलनात्मक विधियां

• DQN (Deep Q-Network)
• DDQN (Double DQN)
• Dueling DQN
• Random baseline (यादृच्छिक आधारभूत)

प्रायोगिक परिणाम

मुख्य परिणाम

मुख्य निष्कर्ष

1. प्रदर्शन: सभी DRL एजेंट लगातार यादृच्छिक आधारभूत से बेहतर प्रदर्शन करते हैं, सैद्धांतिक अधिकतम पुरस्कार (≈200) का लगभग आधा हिस्सा प्राप्त करते हैं
2. अभिसरण विशेषताएं: DDQN सबसे स्थिर अभिसरण और उच्चतम औसत पुरस्कार प्राप्त करता है, दोहरे अनुमान के लाभों को दीर्घकालीन खेल Q-मान अधिमूल्यांकन को कम करने में सत्यापित करता है
3. सीखने की गतिशीलता: प्रारंभिक प्रशिक्षण चरण (<500 खेल) में एजेंट उच्च पुरस्कार विचरण प्रदर्शित करते हैं, लगभग 2000 खेलों के बाद सभी DRL एजेंट अधिक सुचारु अभिसरण दिखाते हैं

सीखने वक्र विश्लेषण

प्रशिक्षण प्रक्रिया तीन चरणों में विभाजित है:

• अन्वेषण चरण (0-500 खेल): उच्च विचरण, बार-बार अवैध कार्य
• सीखने का चरण (500-2000 खेल): नियमों में क्रमिक महारत, पुरस्कार में स्थिर वृद्धि
• अभिसरण चरण (>2000 खेल): पुरस्कार 100-120 रेंज में स्थिर, कभी-कभी अन्वेषणात्मक गिरावट

संबंधित कार्य

MARL बेंचमार्क विकास

• पारंपरिक बेंचमार्क: Go, StarCraft II मुख्य रूप से शुद्ध प्रतिस्पर्धा या सहयोग पर केंद्रित
• सामाजिक खेल: Diplomacy आदि वार्ता में शामिल लेकिन स्पष्ट संचार पर निर्भर
• खेल सिद्धांत अनुप्रयोग: बहु-एजेंट प्रणालियों में नैश संतुलन समाधान

गहन सुदृढ़ीकरण सीखने का खेलों में अनुप्रयोग

• AlphaGo श्रृंखला: पूर्ण जानकारी खेलों में सफलता
• बहु-एजेंट सीखना: स्व-खेल प्रशिक्षण और रणनीति विविधता
• मूल्य फ़ंक्शन विधियां: असतत कार्य स्थान में DQN और इसके वेरिएंट

SLS संबंधित अनुसंधान

यह पेपर पहली बार SLS को कम्प्यूटेशनल बेंचमार्क के रूप में प्रस्तुत करता है, गठबंधन निर्माण और विश्वासघात गतिशीलता अनुसंधान में अंतराल को भरता है।

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

1. शास्त्रीय मूल्य-आधारित विधियां SLS के मुख्य नियमों और आंशिक रणनीति सीख सकती हैं, स्थिर लेकिन उप-इष्टतम प्रदर्शन प्राप्त करती हैं
2. पुरस्कार का उच्च विचरण प्रारंभिकीकरण और अन्वेषण के प्रति संवेदनशीलता को दर्शाता है
3. संदर्भ-निर्भर कार्य अल्पकालीन मूल्य अनुमान की सीमाओं को उजागर करते हैं
4. SLS वार्ता-जागरूक MARL बेंचमार्क के रूप में सफलतापूर्वक स्थापित हुआ

सीमाएं

1. रणनीति सीमाएं: एजेंट अक्सर प्रतिक्रियाशील के बजाय रणनीतिक व्यवहार अपनाते हैं
2. नियम पालन: गतिशील कार्य मास्किंग के बावजूद, अभी भी कभी-कभी अवैध कार्य निष्पादित करते हैं
3. दीर्घकालीन तर्क: संयोजन कार्य स्थान और विलंबित पुरस्कार निर्भरता में कठिनाई
4. गठबंधन गतिशीलता: जटिल गठबंधन निर्माण और विश्वासघात रणनीतियों को पूरी तरह से पकड़ने में विफल

भविष्य की दिशाएं

1. आर्किटेक्चर सुधार: actor-critic और गठबंधन-जागरूक ढांचे को एकीकृत करना
2. रणनीति वृद्धि: दीर्घकालीन तर्क और नियम पालन को मजबूत करना
3. सामाजिक गतिशीलता: वार्ता/गठबंधन/धोखाधड़ी क्षमता विकसित करना
4. सैद्धांतिक विश्लेषण: खेल सिद्धांत तर्क को गहन सीखने के साथ जोड़ना

गहन मूल्यांकन

शक्तियां

1. नवीन बेंचमार्क: पहली बार SLS को MARL में प्रस्तुत किया, गठबंधन और विश्वासघात गतिशीलता अनुसंधान में महत्वपूर्ण अंतराल को भरा
2. संपूर्ण ढांचा: GUI के साथ संपूर्ण कम्प्यूटेशनल ढांचा प्रदान किया, पुनरुत्पादनीय अनुसंधान को बढ़ावा दिया
3. व्यवस्थित मूल्यांकन: कई शास्त्रीय DRL विधियों का व्यापक बेंचमार्किंग किया
4. सैद्धांतिक योगदान: शून्य-योग वेरिएंट नियमों को स्पष्ट किया, मूल औपचारिकीकरण की अधूरापन को हल किया

कमियां

1. विधि सीमाएं: केवल शास्त्रीय मूल्य-आधारित विधियों का परीक्षण किया, अधिक उन्नत MARL एल्गोरिदम की खोज नहीं की
2. सरलीकृत सेटिंग: स्पष्ट वार्ता तंत्र को हटाया गया, संभवतः SLS की मुख्य विशेषताओं को खो दिया
3. प्रदर्शन बाधा: एजेंट अभी भी अवैध कार्य निष्पादित करते हैं, बुनियादी विधियों की अपर्याप्तता को उजागर करते हैं
4. सैद्धांतिक विश्लेषण की कमी: SLS के खेल सिद्धांत गुणों का गहन विश्लेषण नहीं

प्रभाव

1. शैक्षणिक मूल्य: MARL समुदाय को नई अनुसंधान दिशा और बेंचमार्क प्रदान किया
2. व्यावहारिक महत्व: ढांचे की ओपन-सोर्स रिलीज भविष्य के अनुसंधान को बढ़ावा देगी
3. पद्धति योगदान: जटिल रणनीतिक खेलों को ML-अनुकूल वातावरण में कैसे परिवर्तित करें यह प्रदर्शित किया
4. सीमा प्रेरणा: जटिल सामाजिक खेलों में शास्त्रीय RL की अपर्याप्तता को उजागर किया, भविष्य के अनुसंधान को निर्देशित किया

प्रयोज्य परिदृश्य

1. MARL अनुसंधान: गठबंधन निर्माण और विश्वासघात गतिशीलता के लिए एल्गोरिदम विकास
2. खेल सिद्धांत अनुप्रयोग: बहु-पक्षीय वार्ता और रणनीति तर्क के कम्प्यूटेशनल मॉडल
3. सामाजिक AI: विश्वास, धोखाधड़ी और सहयोग व्यवहार का मॉडलिंग
4. शैक्षणिक उपकरण: खेल सिद्धांत और बहु-एजेंट प्रणालियों की शिक्षण प्रदर्शनी

संदर्भ

1. Hausner, M., Nash, J., Shapley, L., & Shubik, M. (1964). So Long Sucker- A Four-Person Game
2. Vinyals, O. et al. (2019). Grandmaster level in StarCraft II using multi-agent reinforcement learning. Nature
3. FAIR Team et al. (2022). Human-level play in the game of diplomacy by combining language models with strategic reasoning. Science
4. Mnih, V. et al. (2015). Human-level control through deep reinforcement learning. Nature

यह पेपर SLS को MARL के नए बेंचमार्क के रूप में प्रस्तुत करके, गठबंधन निर्माण और रणनीतिक धोखाधड़ी के अनुसंधान के लिए एक मूल्यवान मंच प्रदान करता है। हालांकि वर्तमान परिणाम शास्त्रीय विधियों की सीमाओं को दर्शाते हैं, लेकिन यह इस बेंचमार्क की चुनौतीपूर्ण प्रकृति और अनुसंधान मूल्य को उजागर करता है, जो अधिक उन्नत बहु-एजेंट सीखने के एल्गोरिदम विकसित करने के लिए भविष्य के अनुसंधान को निर्देशित करता है।