⚡ electrical engineering

An Online Learning Approach for Two-Player Zero-Sum Linear Quadratic Games

यह शोध पत्र अज्ञात गतिकी (dynamics) वाले दो-खिलाड़ी शून्य-योग रैखिक द्विघाती खेलों (two-player zero-sum linear quadratic games) के लिए एक ऑनलाइन लर्निंग फ्रेमवर्क का प्रस्ताव करता है जो स्थिर समाधान सुनिश्चित करने और सिद्ध प्रतिफल सीमाएं (regret bounds) प्राप्त करने के लिए नियमित मॉडल अनुमान (regularized model estimation), विश्वास सेटों (confidence sets) और एक संकुचन-आधारित सरोगेट मॉडल चयन (shrinkage-based surrogate model selection) को एकीकृत करता है।

मूल लेखक: Shanting Wang, Weihao Sun, Andreas A. Malikopoulos

प्रकाशित 2026-04-06

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

CC0 1.0

मूल लेखक: Shanting Wang, Weihao Sun, Andreas A. Malikopoulos

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

कल्पना कीजिए कि दो ड्राइवर एक कार को मिलकर चलाने की कोशिश कर रहे हैं, लेकिन एक ट्विस्ट के साथ: एक ड्राइवर चाहता है कि यात्रा जितनी जल्दी हो सके पूरी हो जाए (न्यूनतम करने वाला या "Minimizer"), जबकि दूसरा चाहता है कि यात्रा जितनी हो सके उतनी धीमी और ऊबड़-खाबड़ हो (अधिकतम करने वाला या "Maximizer")। वे वाहन के अंदर रस्साकशी का एक उच्च-दांव वाला खेल खेल रहे हैं।

समस्या क्या है? उन्हें यह नहीं पता कि कार कैसे काम करती है। उन्हें नहीं पता कि इंजन कितना भारी है, टायर कितने फिसलन भरे हैं, या स्टीयरिंग कैसे प्रतिक्रिया देता है। वे केवल इतना जानते हैं कि जब वे पहिया घुमाते हैं या एक्सीलेटर दबाते हैं, तो कार उनके अनुमान से थोड़ा अलग तरह से चलती है।

यह पेपर इस बात पर चर्चा करता है कि ये दो ड्राइवर कार चलाते समय, बिना दुर्घटना किए, कार चलाना कैसे सीख सकते हैं।

यहाँ उनकी रणनीति का विवरण दिया गया है, जिसे सरल उपमाओं (analogies) का उपयोग करके समझाया गया है:

1. समस्या: आँखों पर पट्टी बांधकर गाड़ी चलाना

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

लेकिन एक पेच है: यदि आप गलत अनुमान लगाते हैं, तो कार नियंत्रण से बाहर होकर घूम सकती है। गणितीय शब्दों में, सिस्टम "अस्थिर" (unstable) हो जाता है। लक्ष्य खेल जीतने के लिए नियमों को पर्याप्त तेज़ी से सीखना है, लेकिन इतनी सावधानी से कि कभी दुर्घटना न हो।

2. समाधान: "सुरक्षित अनुमान" (Safe Guess) की रणनीति

लेखकों ने एक तीन-चरणीय लर्निंग लूप प्रस्तावित किया है जो बार-बार चलता रहता है:

चरण A: "नोटबुक" (डेटा संग्रह)

हर बार जब ड्राइवर कोई क्रिया करते हैं, तो वे जो कुछ भी होता है उसे एक नोटबुक में लिखते हैं।

उपमा: एक छात्र की कक्षा में नोट्स लेने की कल्पना करें। "मैंने एक्सीलेटर दबाया, और कार 5 मील प्रति घंटे की गति से चली।" "मैंने बाएँ मुड़ा, और हम दाईं ओर फिसल गए।"
वे अपने नोट्स को देखने के लिए रिज रिग्रेशन (Ridge Regression) नामक एक विधि का उपयोग करते हैं और कार के बारे में अपना सर्वश्रेष्ठ अनुमान लगाते हैं। यह उन्हें इंजन और स्टीयरिंग का एक "कच्चा अनुमान" (Raw Estimate) देता है।

चरण B: "सुरक्षा जाँच" (प्रमाणित सरोगेट - The Certified Surrogate)

यहीं पर इस पेपर का बड़ा नवाचार है। "कच्चा अनुमान" डेटा के आधार पर गणितीय रूप से सटीक हो सकता है, लेकिन यह खतरनाक हो सकता है। यह ऐसा स्टीयरिंग एंगल सुझा सकता है जिससे कार पलट सकती है।

उपमा: कल्पना करें कि आपका सबसे अच्छा अनुमान कहता है, "यदि मैं पहिए को 90 डिग्री घुमाता हूँ, तो हम सीधे चलेंगे!" लेकिन आपकी अंतरात्मा कहती है, "यह दुर्घटना जैसा लग रहा है।"
इसलिए, एल्गोरिदम एक "श्रिंकेज स्टेप" (Shrinkage Step) करता है। यह उस जोखिम भरे, कच्चे अनुमान को लेता है और उसे एक "सुरक्षित क्षेत्र" की ओर वापस खींचता है। यह एक ऐसा मॉडल ढूंढता है जो कच्चे अनुमान के करीब है लेकिन यह गारंटी देता है कि कार स्थिर रहेगी।
वे इसे "प्रमाणित सरोगेट मॉडल" (Certified Surrogate Model) कहते हैं। यह सच्चाई का एक "सुरक्षित संस्करण" है जिस पर ड्राइवर अगले कुछ मिनटों के लिए भरोसा कर सकते हैं।

चरण C: "गेम प्लान" (पहेली सुलझाना)

एक बार जब उनके पास यह "सुरक्षित मॉडल" होता है, तो वे एक जटिल गणितीय पहेली (जिसे जनरलाइज्ड अल्जेब्रिक रिकाटी इक्वेशन या GARE कहा जाता है) को हल करते हैं।

उपमा: यह ऐसे है जैसे ड्राइवर अपने सुरक्षित मानचित्र के साथ बैठकर अपनी रणनीति की गणना कर रहे हों: "यदि मैं X करता हूँ, और दूसरा व्यक्ति Y करता है, तो हम यहाँ पहुँचेंगे।"
वे इस सुरक्षित मानचित्र के आधार पर नए स्टीयरिंग और एक्सीलेटर कमांड (फीडबैक गेन्स) की गणना करते हैं और उन्हें तब तक लागू करते हैं जब तक कि उनके पास नोटबुक को फिर से अपडेट करने के लिए पर्याप्त नया डेटा न हो जाए।

3. "रिग्रेट" (Regret) स्कोर: हमने कैसा प्रदर्शन किया?

इस क्षेत्र में, वे सफलता को "रिग्रेट" (Reget) नामक एक मीट्रिक से मापते हैं।

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

4. परिणाम: सिमुलेशन

लेखकों ने इसे एक 3D सिस्टम (जैसे ड्रोन या जटिल रोबोट) के कंप्यूटर सिमुलेशन पर परखा।

लर्निंग कर्व: उन्होंने दिखाया कि जैसे-जैसे समय बीता, उनका "सुरक्षित मॉडल" सिस्टम के वास्तविक भौतिकी के करीब आता गया।
सेफ्टी गैप: उन्होंने दिखाया कि "सुरक्षित मॉडल" अक्सर "कच्चे अनुमान" से अलग था, जिससे सिद्ध हुआ कि सुरक्षा जाँच वास्तव में अस्थिरता को रोकने का काम कर रही थी।
स्कोर: "रिग्रेट" कर्व स्थिर हो गया, जो यह साबित करता है कि एल्गोरिदम कुशलता से सीख रहा था और दुर्घटनाग्रस्त नहीं हुआ।

सारांश

इस पेपर को एक खतरनाक खेल खेलते समय सीखने के लिए एक सुरक्षा नियमावली के रूप में समझें।

सिस्टम कैसे काम करता है इसका अंधाधुंध अनुमान लगाने के बजाय, एल्गोरिदम:

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

यह एक कंप्यूटर को एक उच्च-दांव वाले शतरंज के खेल में एक प्रतिद्वंद्वी के खिलाफ सिखाने का एक तरीका है, भले ही कंप्यूटर को बोर्ड के नियम न पता हों, बिना कभी चेकमेट हुए।

यहाँ शोध पत्र "An Online Learning Approach for Two-Player Zero-Sum Linear Quadratic Games" का विस्तृत तकनीकी सारांश दिया गया है।

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

यह शोध पत्र दो-खिलाड़ी शून्य-योग लीनियर क्वाड्रेटिक (LQ) गेम्स को नियंत्रित करने की चुनौती को संबोधित करता है जहाँ सिस्टम डायनेमिक्स (system dynamics) अज्ञात होते हैं।

सिस्टम मॉडल: एक डिस्क्रीट-टाइम लीनियर सिस्टम $x_{t+1} = A x_t + B_1 u_t + B_2 v_t + w_t$ , जहाँ $u_t$ और $v_t$ क्रमशः प्लेयर 1 (मिनिमाइज़र) और प्लेयर 2 (मैक्सिमाइज़र) के लिए कंट्रोल इनपुट हैं। मैट्रिसेस $A, B_1, B_2$ अज्ञात हैं।
उद्देश्य: प्लेयर 1 का लक्ष्य अनंत-क्षितिज औसत लागत फलन (infinite-horizon average cost function) $J(u, v)$ को न्यूनतम करना है, और प्लेयर 2 का लक्ष्य इसे अधिकतम करना है।
संतुलन (Equilibrium): लक्ष्य नैश इक्विलिब्रियम (Nash Equilibrium - NE) रणनीतियों को खोजना है, जो जनरलाइज्ड अलब्राइक रिकोटी इक्वेशन (GARE) के समाधान से प्राप्त लीनियर फीडबैक पॉलिसीज़ ( $u_t = -K^* x_t, v_t = -L^* x_t$ ) हैं।
चुनौती: एकल-एजेंट लीनियर क्वाड्रेटिक रेगुलेटर (LQR) समस्याओं के विपरीत, ज़ीरो-सम गेम्स में युग्मित रणनीतियाँ (coupled strategies) और प्रतिकूल अंतःक्रियाएँ (adversarial interactions) शामिल होती हैं। मानक ऑनलाइन लर्निंग विधियाँ (जैसे सर्टेनिटी इक्विवेलेंस) अक्सर विफल हो जाती हैं क्योंकि अनुमानित मॉडल उस स्थिरता शर्तों को पूरा नहीं कर सकता जो GARE को हल करने के लिए आवश्यक हैं (अर्थात, अनुमानित मैट्रिसेस एक स्थिर सैडल-पॉइंट समाधान प्रदान करने में सक्षम नहीं हो सकते हैं)।
प्रदर्शन मीट्रिक: एल्गोरिदम के प्रदर्शन को रिग्रेट (Regret) द्वारा मापा जाता है, जिसे वास्तविक डायनेमिक्स के तहत होने वाली इष्टतम लागत और एल्गोरिदम द्वारा होने वाली संचयी लागत के अंतर के रूप में परिभाषित किया गया है। लक्ष्य सबलीनियर रिग्रेट ( $O(\sqrt{T})$ ) प्राप्त करना है।

2. कार्यप्रणाली (Methodology)

लेखक एक सर्टिफाइड ऑनलाइन लर्निंग एल्गोरिदम (एल्गोरिदम 1) प्रस्तावित करते हैं जो कठोर स्थिरता गारंटी के साथ सिस्टम आइडेंटिफिकेशन को एकीकृत करता है। कार्यप्रणाली के चार मुख्य चरण हैं:

A. कॉन्फिडेंस सेट्स के साथ पैरामीटर अनुमान (Parameter Estimation with Confidence Sets)

रिज रिग्रेशन (Ridge Regression): सिस्टम पैरामीटर्स $\Theta = [A, B_1, B_2]$ का अनुमान देखे गए स्टेट-इनपुट डेटा पर रेगुलराइज्ड लीस्ट स्क्वायर्स (रिज रिग्रेशन) का उपयोग करके लगाया जाता है।
कॉन्फिडेंस एलिप्सॉइड (Confidence Ellipsoid): अनुमान $\hat{\theta}_k$ के चारों ओर एक उच्च-संभाव्यता वाला कॉन्फिडेंस सेट $\mathcal{C}_k(\delta)$ बनाया जाता है। यह सेट $1-\delta$ प्रायिकता के साथ वास्तविक पैरामीटर $\theta^*$ को समाहित करता है।

B. सर्टिफाइड सरोगेट मॉडल चयन (The Core Innovation)

समस्या: कच्चा अनुमान $\hat{\theta}_k$ उस क्षेत्र से बाहर हो सकता है जहाँ GARE एक स्थिर समाधान प्रदान करता है, जिससे अस्थिर कंट्रोलर बन सकते हैं।
समाधान: $\hat{\theta}_k$ का सीधे उपयोग करने के बजाय, एल्गोरिदम एक श्रिंकेज स्टेप (shrinkage step) करता है। यह पिछले सर्टिफाइड मॉडल $\tilde{\theta}_{k-1}$ और नए अनुमान $\hat{\theta}_k$ को जोड़ने वाले रेखा खंड (line segment) के अनुदिश खोज करता है।
चयन मानदंड: यह सबसे बड़े स्टेप साइज $\alpha$ $α$ का चयन करता है ताकि नया सरोगेट मॉडल $\tilde{\theta}_k = (1-\alpha)\tilde{\theta}_{k-1} + \alpha\hat{\theta}_k$ $\tilde{θ}_{k} = (1 - α) \tilde{θ}_{k - 1} + α \hat{θ}_{k}$ निम्नलिखित को संतुष्ट करे:
1. यह कॉन्फिडेंस सेट $\mathcal{C}_k(\delta)$ के भीतर रहे।
2. यह एक "रेगुलरिटी रीजन" $\theta_{reg}(\mu, \gamma)$ में स्थित हो जहाँ GARE हल करने योग्य है, समाधान धनात्मक निश्चित (positive definite) है, और क्लोज्ड-लूप सिस्टम विशिष्ट मार्जिन के साथ शूर स्टेबल (Schur stable) है।
परिणाम: यह सुनिश्चित करता है कि प्रत्येक पॉलिसी अपडेट व्यवहार्य (feasible) और स्थिर (stabilizing) है।

C. कंट्रोल अपडेट और एक्सप्लोरेशन (Control Update and Exploration)

सर्टेनिटी इक्विवेलेंस (Certainty Equivalence): एक बार सर्टिफाइड सरोगेट $\tilde{\theta}_k$ का चयन हो जाने के बाद, नए फीडबैक गेन्स $(K_k, L_k)$ प्राप्त करने के लिए GARE को हल किया जाता है।
एक्सप्लोरेशन (Exploration): निरंतर उत्तेजना (persistent excitation) सुनिश्चित करने के लिए (जो पैरामीटर अभिसरण के लिए आवश्यक है), कंट्रोल इनपुट्स में छोटा गाऊसी शोर (Gaussian noise) इंजेक्ट किया जाता है।
अपडेट फ्रीक्वेंसी: मॉडल को केवल तभी पुन: अनुमानित किया जाता है जब सूचना मैट्रिक्स पर्याप्त रूप से बढ़ता है (एक "डबलिंग ट्रिक" का उपयोग करके), जिससे अपडेट की संख्या को $O(\log T)$ तक सीमित किया जाता है।

D. लोकल परटर्बेशन एनालिसिस (Local Perturbation Analysis)

लेखक सिद्ध करते हैं कि मॉडल पैरामीटर्स में छोटे त्रुटियाँ, रिकोटी समाधान और फीडबैक गेन्स में आनुपातिक रूप से छोटी त्रुटियाँ उत्पन्न करती हैं। यह लिप्सचिट्ज़ निरंतरता (Lipschitz continuity) रिग्रेट को सीमित करने के लिए महत्वपूर्ण है।

3. प्रमुख योगदान (Key Contributions)

सर्टिफाइड एल्गोरिदम: अज्ञात डायनेमिक्स वाले दो-खिलाड़ी शून्य-योग LQ गेम्स के लिए पहला ऑनलाइन लर्निंग एल्गोरिदम विकसित करना, जो सरोगेट चयन तंत्र के माध्यम से हर चरण में स्थिरता की गारंटी देता है।
रिग्रेट बाउंड: $O(\sqrt{T})$ का सबलीनियर रिग्रेट बाउंड स्थापित करना। यह रिग्रेट को ट्रांजिएंट कॉस्ट, एक्सप्लोरेशन कॉस्ट और पॉलिसी गैप कॉस्ट में विभाजित करके और प्रत्येक पद को अनुमान त्रुटि और GARE समाधान के लिप्सचिट्ज़ गुणों का उपयोग करके सीमित करके प्राप्त किया जाता है।
अभिसरण विश्लेषण (Convergence Analysis): यह कठोर प्रमाण कि अनुमानित पैरामीटर और फीडबैक गेन वास्तविक नैश इक्विलिब्रियम मानों की ओर अभिसरित होते हैं, बशर्ते कि सिस्टम एक पर्सिस्टेंट एक्साइटेशन स्थिति को पूरा करता हो।
सरोगेट चयन ढांचा (Surrogate Selection Framework): एक रचनात्मक श्रिंकेज प्रक्रिया का परिचय जो सांख्यिकीय अनुमान (कॉन्फिडेंस सेट्स) और कंट्रोल-थ्योरेटिक व्यवहार्यता (GARE सॉल्वेबिलिटी) के बीच के अंतर को पाटता है।

4. परिणाम (Results)

संख्यात्मक सिमुलेशन: शोध पत्र $T=50,000$ के क्षितिज (horizon) पर 3-स्टेट सिस्टम के साथ एक सिमुलेशन प्रस्तुत करता है।
पैरामीटर अभिसरण: अनुमान त्रुटि ( $\|\tilde{\theta}_k - \theta^*\|_2$ ) और फीडबैक गेन त्रुटियाँ ( $\|K_k - K^*\|_F$ ) समय के साथ कम होती हैं, जो पुष्टि करती है कि एल्गोरिदम वास्तविक डायनेमिक्स को सीख रहा है।
सरोगेट बनाम रॉ अनुमान: सिमुलेशन कच्चे रिज अनुमान त्रुटि और सर्टिफाइड सरोगेट त्रुटि के बीच एक स्पष्ट अंतर प्रदर्शित करता है। स्थिरता सुनिश्चित करने के लिए सरोगेट अधिक रूढ़िवादी (conservative) रहता है, जो श्रिंकेज स्टेप की आवश्यकता को प्रमाणित करता है।
रिग्रेट प्रदर्शन: सामान्यीकृत रिग्रेट ( $\text{Reg}(T)/\sqrt{T}$ ) सीमित रहता है और स्थिर होता है, जो अनुभवजन्य रूप से इसके सैद्धांतिक $O(\sqrt{T})$ बाउंड को सत्यापित करता है।

5. महत्व (Significance)

सिद्धांत और व्यवहार को जोड़ना: यह कार्य मल्टी-एजेंट कंट्रोल में एक महत्वपूर्ण अंतराल को हल करता है: सिस्टम मॉडल जाने बिना, प्रतिकूल सेटिंग्स में इष्टतम रणनीतियों को कैसे सीखा जाए, जबकि यह गारंटी दी जाए कि सिस्टम कभी भी अस्थिर न हो।
मजबूती (Robustness): रेगुलरिटी मार्जिन को लागू करके (श्रिंकेज स्टेप के माध्यम से), एल्गोरिदम मानक लर्निंग विधियों की "आशावाद" (optimism) को रोकने में सक्षम है जो विनाशकारी अस्थिरता का कारण बन सकती है, जो शून्य-योग खेलों में एक सामान्य विफलता मोड है।
भविष्य के कार्य के लिए आधार: यह ढांचा सर्टिफाइड चयन तंत्र को अनुकूलित करके, आंशिक रूप से प्रेक्षित खेलों (partially observed games), मल्टी-प्लेयर सेटिंग्स, या समय-परिवर्तनीय प्रणालियों जैसे अधिक जटिल परिदृश्यों में ऑनलाइन लर्निंग को विस्तारित करने के लिए एक ब्लूप्रिंट प्रदान करता है।

संक्षेप में, यह शोध पत्र अज्ञात प्रतिकूल वातावरणों में इष्टतम नियंत्रण रणनीतियों को सीखने के लिए एक गणितीय रूप से कठोर और व्यावहारिक रूप से व्यवहार्य दृष्टिकोण प्रस्तुत करता है, यह सुनिश्चित करते हुए कि सीखने की दक्षता सिस्टम की स्थिरता की कीमत पर न आए।