🤖 machine learning

Nearly-Optimal Bandit Learning in Stackelberg Games with Side Information

यह शोध पत्र साइड इंफॉर्मेशन वाले ऑनलाइन स्टैकेलबर्ग गेम्स के लिए नवीन लर्निंग एल्गोरिदम प्रस्तुत करता है जो समस्या को लीनियर कॉन्टेक्स्टुअल बैंडिट्स में बदलकर बैंडिट फीडबैक के तहत लगभग-इष्टतम $O(T^{1/2})$ रिग्रेट प्राप्त करते हैं, जिससे पिछले $O(T^{2/3})$ दरों में सुधार होता है और नीलामी बोली (auction bidding) और बेयसियन पर्सुएशन (Bayesian persuasion) जैसे अनुप्रयोगों में प्रभावशीलता प्रदर्शित होती है।

मूल लेखक: Maria-Florina Balcan, Martino Bernasconi, Matteo Castiglioni, Andrea Celli, Keegan Harris, Zhiwei Steven Wu

प्रकाशित 2026-05-05

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

CC BY 4.0

मूल लेखक: Maria-Florina Balcan, Martino Bernasconi, Matteo Castiglioni, Andrea Celli, Keegan Harris, Zhiwei Steven Wu

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

एक उच्च-दांव वाले शतरंज के खेल की कल्पना करें, लेकिन एक ट्विस्ट के साथ: एक खिलाड़ी (लीडर/नेता) पहले चाल चलता है, और दूसरा खिलाड़ी (फॉलोअर/अनुगामी) उस चाल को देखता है और तुरंत सबसे अच्छा जवाबी कदम उठाता है। इसे स्टैकेलबर्ग गेम (Stackelberg Game) कहा जाता है।

वास्तविक दुनिया में, यह हर जगह होता है:

हवाई अड्डा सुरक्षा: TSA (लीडर) यह तय करता है कि वे कुत्तों और स्कैनरों को कहाँ रखेंगे। एक तस्कर (फॉलोअर) इसे देखता है और सबसे कमजोर जगह से घुसने की कोशिश करता है।
वन्यजीव संरक्षण: रेंजर (लीडर) तय करते हैं कि वे कहाँ गश्त करेंगे। शिकारी (फॉलोअर) देखते हैं और वहीं शिकार करते हैं जहाँ रेंजर नहीं हैं।

समस्या: अंधेरे में सीखना

आमतौर पर, लीडर को ठीक से पता होता है कि फॉलोअर कैसे सोचता है। लेकिन इस शोध पत्र में, लेखक एक ऐसी स्थिति की कल्पना करते हैं जहाँ लीडर फॉलोअर के विशिष्ट लक्ष्यों के प्रति अंधा (blind) है। लीडर को केवल एक "संकेत" (जिसे साइड इंफॉर्मेशन/पार्श्व सूचना कहा जाता है) मिलता है—जैसे कि यह जानना कि आज बारिश का दिन है, या हवाई अड्डा भीड़भाड़ वाला है।

खेल खेलने के बाद, लीडर को केवल एक स्कोर मिलता है (क्या मैंने तस्कर को पकड़ा? क्या मेरा पैसा नुकसान हुआ?)। उन्हें फॉलोअर के आंतरिक विचारों या उनकी सटीक रणनीति को देखने का मौका नहीं मिलता। इसे "बैंडिट फीडबैक" (Bandit Feedback) कहा जाता है। यह एक वीडियो गेम खेलने जैसा है जहाँ आप केवल अपनी हेल्थ बार को ऊपर या नीचे जाते देखते हैं, लेकिन आप दुश्मन की चाल या मैप को नहीं देख पाते।

पहले के सबसे अच्छे एल्गोरिदम इस "अंधेरे" में सीखने के लिए धीमे और अनाड़ी थे। उन्हें बेहतर होने के लिए बहुत अधिक अभ्यास राउंड की आवश्यकता थी, और उनकी गलतियों की दर लगभग $T^{2/3}$ की दर से बढ़ती थी (जहाँ $T$ राउंड की संख्या है)।

सफलता: द "यूटिलिटी ट्रांसलेटर" (उपयोगिता अनुवादक)

लेखकों ने एक नया एल्गोरिदम बनाया जो बहुत तेज़ी से सीखता है। उन्होंने गलती की दर में सुधार किया जो अब लगभग $T^{1/2}$ है। सरल शब्दों में कहें तो, इसका अर्थ है कि लीडर पहले की तुलना में दोगुनी तेज़ी से सीखता है।

उन्होंने यह कैसे किया? "मेन्यू" की उपमा।

कल्प la है कि लीडर एक शेफ है जो ग्राहक (फॉलोअर) को खुश करने की कोशिश कर रहा है।

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

लेखकों ने एक चतुर ट्रिक बनाई:

वे यह मान लेते हैं कि खेल रणनीति चुनने (जैसे गश्त का मार्ग) के बारे में नहीं है, बल्कि स्कोर के एक वेक्टर (संख्याओं की एक सूची) को चुनने के बारे में है (जो यह दर्शाता है कि विभिन्न प्रकार के फॉलोअर्स के खिलाफ लीडर कितना खुश होगा)।
वे एक सर्वश्रेष्ठ स्कोर-वेक्टर चुनने के लिए एक "ट्रांसलेटर" (एक लीनियर कॉन्टेक्स्टुअल बैंडिट एल्गोरिदम) का उपयोग करते हैं।
फिर, वे पीछे की ओर काम करते हैं ताकि वास्तविक रणनीति (गश्त का मार्ग) को खोजा जा सके जो वह स्कोर उत्पन्न करती है।

खेल को एक सरल "स्कोर प्रेडिक्शन" (स्कोर भविष्यवाणी) समस्या में बदलकर, वे बहुत तेज़ी से सीखने के लिए मौजूदा शक्तिशाली गणितीय उपकरणों का उपयोग कर सकते हैं।

दो परिदृश्य

यह पेपर इस "ट्रांसलेटर" का परीक्षण दो अलग-अलग दुनिया में करता है:

मौसम बदलता है, अपराधी रैंडम हैं: संदर्भ (मौसम, समय) एक चालाक विरोधी द्वारा चुना जाता है, लेकिन फॉलोअर्स के प्रकार (तस्कर, शिकारी) रैंडम रूप से आते हैं।
अपराधी बदलते हैं, मौसम रैंडम है: मौसम रैंडम है, लेकिन फॉलोअर्स के प्रकार एक चालाक विरोधी द्वारा चुने जाते हैं।

दोनों मामलों में, उनका नया एल्गोरिदम जीतता है, और $T^{1/2}$ की "लगभग-इष्टतम" गति प्राप्त करता है।

अन्य खेल जो उन्होंने खेले

लेखकों ने दिखाया कि यह "ट्रांसलेटर" ट्रिक केवल सुरक्षा खेलों के लिए नहीं है। यह निम्नलिखित के लिए भी काम करता है:

ऑनलाइन नीलामी: वस्तुओं पर बोली लगाना जहाँ मूल्य बाहरी समाचारों (जैसे फैशन ट्रेंड्स) पर निर्भर करता है।
बेयसियन पर्सुएशन (Bayesian Persuasion): एक प्रेषक (sender) जो आंशिक जानकारी प्रकट करके प्राप्तकर्ता (receiver) को कोई कार्रवाई करने के लिए मनाने की कोशिश करता है (जैसे एक सेल्सपर्सन जो ग्राहक के मूड के आधार पर उत्पाद बेचने की कोशिश करता है)।

अज्ञात उपयोगिता (Unknown Utilities) के बारे में क्या?

क्या होगा यदि लीडर को अपना स्वयं का स्कोरिंग सिस्टम भी पता न हो? (जैसे, "मुझे ठीक से नहीं पता कि एक शिकारी को पकड़ने बनाम ईंधन बचाने को मैं कितनी वैल्यू देता हूँ")।
लेखकों ने इसे भी संभालने के लिए अपने तरीके का विस्तार किया, यह मानते हुए कि लीडर का मूल्य संदर्भ का एक सरल लीनियर कॉम्बिनेशन है। यह अभी भी तेज़ी से काम करता है, हालांकि इसमें छिपे हुए मूल्यों को समझने के लिए थोड़ी अधिक कंप्यूटिंग शक्ति की आवश्यकता होती है।

निष्कर्ष

यह पेपर गेम थ्योरी की एक लंबे समय से चली आ रही पहेली को हल करता है: आप एक रणनीतिक खेल कैसे खेलते हैं जब आप अपने प्रतिद्वंद्वी के दिमाग को नहीं देख सकते, केवल उसकी प्रतिक्रिया को देख सकते हैं?

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

तकनीकी सारांश: साइड इंफॉर्मेशन के साथ स्टैकेलबर्ग गेम्स में लगभग-इष्टतम बैंडिट लर्निंग

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

यह शोध पत्र साइड इंफॉर्मेशन (संदर्भ/context) के साथ स्टैकेलबर्ग गेम्स में ऑनलाइन लर्निंग की समस्या को संबोधित करता है। यह सेटिंग $T$ राउंड में एक लीडर (नेता) और अनुक्रमिक फॉलोअर्स (अनुयायियों) के बीच निरंतर अंतःक्रिया (interaction) को दर्शाती है। प्रत्येक दौर $t$ में:

दोनों खिलाड़ी एक संदर्भ $z_t \in \mathcal{Z} \subseteq \mathbb{R}^d$ देखते हैं (साइड इंफॉर्मेशन, जैसे मौसम, ट्रैफ़िक, या इंटेलिजेंस रिपोर्ट)।
लीडर एक मिश्रित रणनीति (mixed strategy) $x_t \in \Delta(\mathcal{A}_l)$ निर्धारित करता है।
एक फॉलोअर $f_t$ (जो $K$ संभावित प्रकारों में से एक है) संदर्भ और लीडर की रणनीति को देखता है, और फिर एक बेस्ट-रिस्पॉन्स एक्शन $a_{f,t}$ खेलता है।
लीडर को अपने यूटिलिटी फंक्शन $u(z_t, a_{l,t}, a_{f,t})$ के आधार पर रिवॉर्ड प्राप्त होता है, जबकि फॉलोअर को अपने स्वयं के फंक्शन के आधार पर यूटिलिटी मिलती है।

लर्निंग वातावरण बैंडिट फीडबैक द्वारा विशेषता प्राप्त करता है: लीडर केवल अपना वास्तविक प्राप्त यूटिलिटी और फॉलोअर का एक्शन देखता है, लेकिन वह फॉलोअर के प्रकार की पहचान या फॉलोअर के यूटिलिटी फंक्शन को कभी नहीं देख पाता। यह शोध पत्र दो प्राथमिक एडवरसैरियल/स्टोकेस्टिक (adversarial/stochastic) व्यवस्थाओं पर विचार करता है:

एडवरसैरियल कॉन्टेक्स्ट, स्टोकेस्टिक फॉलोअर्स: संदर्भों का अनुक्रम एक एडवरसरी (विरोधी) द्वारा चुना जाता है, जबकि फॉलोअर के प्रकार एक अज्ञात स्थिर वितरण (stationary distribution) से लिए जाते हैं।
स्टोकेस्टिक कॉन्टेक्स्ट, एडवरसैरियल फॉलोअर्स: संदर्भों का अनुक्रम एक अज्ञात वितरण से लिया जाता है, जबकि फॉलोअर के प्रकार एक एडवरसरी द्वारा चुने जाते हैं।

लक्ष्य कॉन्टेक्स्टुअल स्टैकेलबर्ग रिग्रेट (Contextual Stackelberg Regret) को कम करना है, जिसे इष्टतम हिंडसाइट पॉलिसी (जो संदर्भ और फॉलोअर अनुक्रम को जानती है) की संचयी यूटिलिटी और लीडर की संचयी यूटिलिटी के बीच के अंतर के रूप में परिभाषित किया गया है।

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

मुख्य योगदान लीडर के यूटिलिटी स्पेस में लीनियर कॉन्टेक्स्टुअल बैंडिट्स में एक रिडक्शन (reduction) है। हालांकि लीडर की यूटिलिटी अपने मिश्रित रणनीति $x_t$ के संबंध में नॉन-लीनियर (गैर-रेखीय) है (फॉलोअर के बेस्ट-रिस्पॉन्स फंक्शन के कारण), लेखक समस्या को लीनियर करने के लिए फॉलोअर प्रकारों की सीमित संख्या ( $K$ ) का लाभ उठाते हैं।

द रिडक्शन (The Reduction)

यूटिलिटी स्पेस रिप्रेजेंटेशन: दिए गए संदर्भ $z$ और रणनीति $x$ के लिए, प्रत्येक फॉलोअर प्रकार $i \in [K]$ के विरुद्ध लीडर की यूटिलिटी की गणना की जा सकती है। ये यूटिलिटीज एक वेक्टर $u(z, x) \in \mathbb{R}^K$ बनाती हैं।
लीनियराइजेशन (Linearization): फॉलोअर प्रकार $f_t$ के विरुद्ध प्राप्त वास्तविक यूटिलिटी को $\langle u(z_t, x_t), \mathbf{1}_{f_t} \rangle$ के इनर प्रोडक्ट (inner product) के रूप में व्यक्त किया जा सकता है, जहाँ $\mathbf{1}_{f_t}$ फॉलोअर प्रकार को दर्शाने वाला एक वन-हॉट वेक्टर है।
डिस्क्रीटाइजेशन (Discretization): हालांकि रणनीति स्पेस $\Delta(\mathcal{A}_l)$ अनंत है, यह शोध पत्र लीडर को कॉन्टेक्स्टुअल बेस्ट-रिस्पॉन्स क्षेत्रों के $\delta$ -एप्रोक्सिमेट एक्सट्रीम पॉइंट्स ( $E_t$ ) के एक परिमित सेट तक सीमित करता है। यह डिस्क्रीटाइजेशन नगण्य रिग्रेट ( $O(1)$ ) का बोझ डालता है, जबकि यह सुनिश्चित करता है कि संभावित यूटिलिटी वेक्टर्स $U_t = \{u(z_t, x) : x \in E_t\}$ परिमित हैं।
एल्गोरिदम 1: प्रस्तावित एल्गोरिदम इस प्रकार कार्य करता है:
- संदर्भ $z_t$ देखें और व्यवहार्य यूटिलिटी वेक्टर्स का सेट $U_t$ कंप्यूट करें।
- एक लीनियर कॉन्टेक्स्टुअल बैंडिट एल्गोरिदम $\mathcal{R}$ को एक वेक्टर $v_t \in U_t$ की सिफारिश करने के लिए क्वेरी करें।
- $v_t$ को प्रेरित करने वाली मिश्रित रणनीति $x_t$ खोजने के लिए मैपिंग को उल्टा (invert) करें।
- $x_t$ खेलें, रिवॉर्ड देखें, और वास्तविक यूटिलिटी को $\mathcal{R}$ को वापस फीड करें।

इंस्टेंशिएशन्स (Instantiations)

यह शोध पत्र अलग-अलग सेटिंग्स के आधार पर विशिष्ट बैंडिट एल्गोरिदम के साथ एल्गोरिदम 1 को लागू करता है:

OFUL (Optimism in the Face of Uncertainty for Linear models): जब फॉलोअर प्रकार स्टोकेस्टिक होते हैं, तो इसका उपयोग किया जाता है। यह फॉलोअर प्रकारों पर अज्ञात वितरण $p^*$ को सीखता है।
logdet-FTRL (Follow-The-Regularized-Leader with log-determinant barrier): जब फॉलोअर एडवरसैरियल होते हैं, तो इसका उपयोग किया जाता है। यह वेरिएंट लीनियर कॉन्टेक्स्टुअल बैंडिट्स में एडवरसैरियल लॉस को संभालता है।

अज्ञात यूटिलिटीज तक विस्तार

इस ढांचे को उन सेटिंग्स तक विस्तारित किया गया है जहाँ लीडर का यूटिलिटी फंक्शन $u$ अज्ञात है। एक लीनियरिटी धारणा (Assumption 3.3) के तहत, जहाँ $u(z, a_l, a_f) = \langle z, U(a_l, a_f) \rangle$ है, समस्या को उच्च-आयामी लीनियर कॉन्टेक्स्टुअल बैंडिट समस्या में बदल दिया जाता है। फीचर वेक्टर को संदर्भ, लीडर एक्शन और फॉलोअर एक्शन के बीच की अंतःक्रिया को शामिल करने के लिए विस्तारित किया जाता है, जिससे एल्गोरिदम को अज्ञात पैरामीटर्स $\theta$ को सीखने की अनुमति मिलती है।

मुख्य योगदान और परिणाम

1. बेहतर रिग्रेट बाउंड्स (Improved Regret Bounds)

यह शोध पत्र इस सेटिंग में बैंडिट फीडबैक के लिए ज्ञात ऊपरी और निचली सीमाओं के बीच के अंतर को समाप्त करता है:

स्टोकेस्टिक फॉलोअर्स / एडवरसैरियल कॉन्टेक्ट्स: $\tilde{O}(\sqrt{T})$ रिग्रेट प्राप्त करता है (विशेष रूप से $O(K\sqrt{T}\log T)$ )। यह Harris et al. (2024) के $\tilde{O}(T^{2/3})$ के पिछले सर्वश्रेष्ठ परिणाम से बेहतर है।
एडवरसैरियल फॉलोअर्स / स्टोकेस्टिक कॉन्टेक्ट्स: $\tilde{O}(\sqrt{T})$ रिग्रेट प्राप्त करता है (विशेष रूप से $O(K^{2.5}\sqrt{T}\log T)$ )।
ये दरें लॉगरिदमिक कारकों तक ज्ञात लोअर बाउंड्स से मेल खाती हैं, जो लगभग-इष्टतमता स्थापित करती हैं।

2. अज्ञात यूटिलिटी विस्तार

लेखक दिखाते हैं कि यदि लीडर का यूटिलिटी फंक्शन अज्ञात है लेकिन संदर्भ में लीनियर है, तो $\tilde{O}(\sqrt{T})$ रिग्रेट दर बनी रहती है, हालांकि संदर्भ के आयाम ( $d$ ) और एक्शन स्पेस के आकार ( $A_l, A_f$ ) पर एक बहुपद (polynomial) निर्भरता होती है। रिग्रेट $\tilde{O}(\text{poly}(d, K, A_l, A_f)\sqrt{T})$ के रूप में स्केल करता है।

3. अन्य डोमेन में अनुप्रयोग

रिडक्शन तकनीक को दो अन्य सेटिंग्स पर लागू किया गया है जहाँ साइड इंफॉर्मेशन प्रचुर मात्रा में है लेकिन इस विशिष्ट बैंडिट संदर्भ में पहले अध्ययन नहीं की गई थी:

सेकंड-प्राइस ऑक्शन्स (Second-Price Auctions): साइड इंफॉर्मेशन के साथ कॉम्बिनेटोरियल सेकंड-प्राइस ऑक्शन्स में बोली लगाने को सीखना। यह पेपर बैंडिट फीडबैक के साथ इस सेटिंग के लिए पहले नो-रिग्रेट एल्गोरिदम प्रदान करता है।
ऑनलाइन बेयसियन पर्सुएशन (Online Bayesian Persuasion): पब्लिक और प्राइवेट स्टेट्स के साथ बेयसियन पर्सुएशन गेम्स में सिग्नलिंग पॉलिसी को सीखना। परिणाम साइड इंफॉर्मेशन वाले सेटिंग्स तक विस्तारित होते हैं, जो $\tilde{O}(\sqrt{T})$ रिग्रेट प्राप्त करते हैं।

4. अनुभवजन्य सत्यापन (Empirical Validation)

सिंथेटिक स्टैकेलबर्ग गेम्स पर संख्यात्मक सिमुलेशन दर्शाते हैं कि प्रस्तावित एल्गोरिदम (Algorithm 1-OFUL) संचयी यूटिलिटी और रिग्रेट के मामले में पिछले बेसलाइन्स (विशेष रूप से Harris et al., 2024 के एल्गोरिदम 3) से काफी बेहतर प्रदर्शन करता है, यहाँ तक कि उन मामलों में भी जहाँ फॉलोअर यूटिलिटी साइड इंफॉर्मेशन पर निर्भर करती है (एक ऐसा परिदृश्य जहाँ पिछले एल्गोरिदम लागू नहीं थे)।

महत्व और दावे (Significance and Claims)

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

इसका महत्व निम्नलिखित में निहित है:

सैद्धांतिक सटीकता (Theoretical Tightness): इस श्रेणी की समस्याओं के लिए लोअर बाउंड्स से मेल खाना, जो पिछले $T^{2/3}$ परिणामों द्वारा छोड़े गए अंतर को हल करता है।
व्यापकता (Generality): रिडक्शन मॉड्यूलर है, जो कोर स्टैकेलबर्ग लर्निंग लॉजिक को फिर से डिजाइन किए बिना विभिन्न एडवरसैरियल/स्टोकेस्टिक धारणाओं के लिए अलग-अलग बैंडिट एल्गोरिदम को लागू करने की अनुमति देता है।
व्यापक प्रयोज्यता (Broad Applicability): यह प्रदर्शित करना कि समान संरचनात्मक रिडक्शन ऑक्शन्स और बेयसियन पर्सुएशन पर भी लागू होता है, जो साइड इंफॉर्मेशन वाले रणनीतिक वातावरण में सीखने के लिए एक एकीकृत दृष्टिकोण का सुझाव देता है।

लेखक नोट करते हैं कि हालांकि डिस्क्रीटाइज्ड स्ट्रैटेजी सेट के आकार के कारण वर्स्ट-केस रनटाइम एक्सपोनेंशियल है (जो ऑफलाइन स्टैकेलबर्ग गणना से NP-hardness को विरासत में लेता है), यह दृष्टिकोण प्रभावी फॉलोअर प्रकारों या डोमिनेटेड एक्शन्स की कम संख्या वाले सेटिंग्स के लिए व्यावहारिक है और अनुभवजन्य परिणाम मजबूत प्रदर्शन दिखाते हैं।