🤖 machine learning

Multi-User Dueling Bandits: A Fair Approach using Nash Social Welfare

यह शोध पत्र अल्पसंख्यक हाशिए पर जाने (minority marginalization) को रोकने के लिए एक नैश सोशल वेलफेयर (Nash Social Welfare) उद्देश्य को पेश करके, विषम प्राथमिकताओं (heterogeneous preferences) के लिए एक नवीन $O(T^{2/3})$ रिग्रेट लोअर बाउंड (regret lower bound) स्थापित करके और मिलान वाले अपर बाउंड्स (matching upper bounds) प्राप्त करने वाले एल्गोरिदम प्रस्तावित करके मल्टी-यूज़र ड्यूलिंग बैंडिट्स (multi-user dueling bandits) में निष्पक्षता को संबोधित करता है।

मूल लेखक: Maheed H. Ahmed, Mahsa Ghasemi

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

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

CC BY 4.0

मूल लेखक: Maheed H. Ahmed, Mahsa Ghasemi

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

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

अब, कल्पना कीजिए कि पार्टी को अलग-अलग समूहों में विभाजित किया गया है। कुछ को हेवी मेटल पसंद है, कुछ को जैज़, और कुछ को पॉप। यदि आप केवल "औसत" व्यक्ति को खुश करने की कोशिश करते हैं, तो आप अंततः गानों का एक ऐसा उबाऊ मिश्रण बजा सकते हैं जो कोई भी वास्तव में आनंद नहीं ले पाता, या इससे भी बुरा, आप जैज़ पसंद करने वाले छोटे समूह को पूरी तरह से अनदेखा कर सकते हैं क्योंकि मेटल चाहने वाले अधिक शोर मचा रहे हैं।

यह पेपर एक नया तरीका प्रस्तावित करता है जिससे आप एक ऐसे डीजे बन सकते हैं जो यह सुनिश्चित करता है कि हर किसी को अपनी पसंद का संगीत सुनने का उचित अवसर मिले, न कि केवल बहुमत को।

मुख्य समस्या: "औसत" का जाल

अधिकांश कंप्यूटर प्रणालियों में, लक्ष्य "कुल खुशी" (सभी के आनंद का योग) को अधिकतम करना होता है। यदि 90 लोग रॉक पसंद करते हैं और 10 लोग जैज़, तो सिस्टम केवल रॉक ही बजाएगा। 10 जैज़ प्रेमी शून्य खुशी प्राप्त करेंगे। यह अनुचित है। यह पेपर तर्क देता है कि एक ऐसा सिस्टम होना चाहिए जहाँ "जैज़ चाहने वाले" पीछे न छूट जाएं, भले ही वे अल्पसंख्यक हों।

समाधान: "समूह खुशी" का सूत्र

इसे हल करने के लिए, लेखक नैश सोशल वेलफेयर (Nash Social Welfare - NSW) नामक अवधारणा का उपयोग करते हैं।

इसे इस तरह सोचें:

पुराना तरीका (उपयोगितावादी/Utilitarian): आप हर किसी की खुशी को जोड़ देते हैं। $90 + 10 = 100$ । यदि आप रॉक बजाते हैं, तो 90 प्रशंसक खुश हैं, लेकिन 10 दुखी हैं। कुल स्कोर उच्च है, लेकिन यह अनुचित है।
नया तरीका (नैश सोशल वेलफेयर): जोड़ने के बजाय, आप हर किसी की खुशी को गुणा करते हैं।
- यदि 10 जैज़ प्रशंसकों की खुशी 0 है, तो कुल स्कोर 0 हो जाता है ( $90 \times 0 = 0$ )।
- उच्च स्कोर प्राप्त करने के लिए, हर किसी को कम से कम थोड़ी सी खुशी होनी चाहिए।

यह गणितीय युक्ति एल्गोरिदम को सबसे छोटे समूह की परवाह करने के लिए मजबूर करती है। यह एक श्रृंखला की तरह है: श्रृंखला उतनी ही मजबूत होती है जितनी उसकी सबसे कमजोर कड़ी।

एल्गोरिदम कैसे काम करता है

पेपर दो मुख्य रणनीतियाँ (एल्गोरिदम) पेश करता है जो गानों के सबसे अच्छे मिश्रण (या गणित की दुनिया में जिन्हें वे "आर्म्स" कहते हैं) को खोजने के लिए इस निष्पक्षता के नियम को पूरा करती हैं।

"पहले सीखो, फिर खेलो" रणनीति (Fair-Explore-Then-Commit):
- चरण 1 (स्वाद परीक्षण): डीजे विभिन्न गानों के जोड़ों को बहुत समय तक बजाता है ताकि वह सटीक रूप से समझ सके कि प्रत्येक समूह क्या पसंद करता है। वे प्रत्येक समूह के लिए "कोंडोरसेट विजेता" (Condorcet Winner) की तलाश कर रहे हैं—यानी वह एक गाना जो उस विशिष्ट समूह के लिए अन्य सभी को हरा देता है।
- चरण 2 (सेटलिस्ट): एक बार जब उन्हें विश्वास हो जाता है कि वे जानते हैं कि हर कोई क्या पसंद करता है, तो वे अनुमान लगाना बंद कर देते हैं और बाकी पार्टी के लिए लोगों की खुशी को संतुलित करने वाला एकदम सही मिश्रण बजाते हैं।
"मिश्रण बनाए रखो" रणनीति (Fair- $\epsilon$ -Greedy):
- यह रणनीति अधिक लचीली है। यह ज्यादातर उस सर्वोत्तम मिश्रण को बजाती है जिसे यह अब तक जानता है, लेकिन समय-समय पर, यह अपनी धारणाओं की दोबारा जाँच करने के लिए जानबूझकर गानों के एक यादृच्छिक (random) जोड़े को बजाता है। यदि इसे एहसास होता है कि यह जैज़ चाहने वालों की पसंद के बारे में गलत था, तो यह तुरंत अपना मन बदल सकता है। यह एक ऐसे डीजे की तरह है जिसके पास बैक पॉकेट में कुछ सरप्राइज गाने रखे हैं, ताकि अगर भीड़ का मूड बदल जाए तो काम आ सकें।

बड़ी खोज: निष्पक्षता की एक कीमत होती है

लेखकों ने कुछ बहुत महत्वपूर्ण साबित किया है: निष्पक्ष होना, कुशल होने की तुलना में कठिन है।

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

उन्होंने गणना की कि यह कितना धीमा है। उन्होंने पाया कि "रिग्रेट" (वह खुशी जो डीजे के सही गाना न जानने के कारण कम हुई) एक विशिष्ट दर से बढ़ता है: लगभग समय के वर्ग (time squared) के समानुपाती, समूहों की संख्या के घनमूल (cube root) को विभाजित करके।

सरल अनुवाद: जितने अधिक अलग-अलग समूह होंगे, और आपके पास चुनने के लिए जितने अधिक विकल्प होंगे, बहुमत को खुश करने वाले सिस्टम की तुलना में एक ऐसा समाधान खोजने में उतना ही अधिक समय लगेगा जो सभी को खुश रखे।

परिणाम: क्या यह काम करता है?

लेखकों ने अपने विचारों का परीक्षण सिमुलेशन और वास्तविक डेटा (लोगों की सुशी प्राथमिकताओं के एक डेटासेट का उपयोग करके) के साथ किया।

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

सारांश

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

तकनीकी सारांश: मल्टी-यूज़र ड्यूलिंग बैंडिट्स: नैश सोशल वेलफेयर का उपयोग करते हुए एक निष्पक्ष दृष्टिकोण

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

यह शोध पत्र फेयर मल्टी-यूज़र ड्यूलिंग बैंडिट (Fair Multi-User Dueling Bandit) समस्या को संबोधित करता है, जो एक ऐसी स्थिति है जहाँ एक एजेंट $K$ भुजाओं (arms) के लिए $T$ समय क्षितिज (time horizon) के दौरान $D$ विशिष्ट उपयोगकर्ताओं द्वारा प्रदान किए गए युग्मवार वरीयता डेटा (pairwise preference data) से सीखता है। मानक ड्यूलिंग बैंडिट्स के विपरीत, जो एक एकल वरीयता मॉडल या एक एकल मैट्रिक्स में एकत्रित वरीयताओं को मानते हैं, यह कार्य एक ऐसे परिदृश्य पर विचार करता है जहाँ प्रत्येक उपयोगकर्ता $d$ के पास एक संभावित रूप से भिन्न वरीयता मैट्रिक्स $P_d$ हो सकता है।

मुख्य चुनौती एक ऐसी नीति (policy) सीखने की है जो विषम (heterogeneous) उपयोगकर्ताओं के हितों को संतुलित करे बिना अल्पसंख्यक समूहों को हाशिए पर डाले। मानक दृष्टिकोण जो औसत (उपयोगितावादी/utilitarian) कल्याण के लिए अनुकूलन करते हैं, वे अक्सर सांख्यिकीय बहुमत का पक्ष लेते हैं, जिससे भिन्न वरीयताओं वाले उपयोगकर्ताओं के लिए अनुचित परिणाम निकलते हैं। इस समस्या के समाधान के लिए, लेखक अपने उद्देश्य को नैश सोशल वेलफेयर (Nash Social Welfare - NSW) का उपयोग करके परिभाषित करते हैं, जो उपयोगकर्ताओं के उपयोगिता गुणनफल (product of user utilities) को अधिकतम करता है। यह उद्देश्य स्वाभाविक रूप से असमानता को दंडित करता है, यह सुनिश्चित करता है कि किसी भी एकल उपयोगकर्ता की उपयोगिता शून्य न हो जाए।

इस सेटिंग में एक महत्वपूर्ण तकनीकी बाधा पूर्ण पुरस्कारों (absolute rewards) का अभाव है; फीडबैक पूरी तरह से सापेक्ष (relative) है (दो भुजाओं के बीच कौन सी बेहतर है, यह दर्शाने वाले बाइनरी परिणाम)। इस सापेक्ष सेटिंग में उपयोगिता को परिभाषित करने के लिए, लेखक प्रत्येक उपयोगकर्ता के लिए एक कॉोंडोरसेट विजेता (Condorcet winner) के अस्तित्व की धारणा बनाते हैं (एक ऐसी भुजा जो अन्य सभी भुजाओं को $>0.5$ प्रायिकता के साथ हरा देती है)। उपयोगकर्ता की उपयोगिता को उस उपयोगकर्ता के विशिष्ट कॉोंडोरसेट विजेता के विरुद्ध एक भुजा के जीतने की प्रायिकता से प्राप्त स्कोर के रूप में परिभाषित किया जाता है।

कार्यप्रणाली

सैद्धांतिक ढांचा (Theoretical Framework)

लेखक एक स्कोरिंग फ़ंक्शन $s_d(i) = 2P_{d, i, a^*_d}$ को परिभाषित करके समस्या को औपचारिक रूप देते हैं, जहाँ $a^*_d$ उपयोगकर्ता $d$ का कॉोंडोरसेट विजेता है। एक नीति $\pi$ के लिए उपयोगकर्ता $d$ की उपयोगिता अपेक्षित स्कोर $u_d(\pi) = \mathbb{E}_{a \sim \pi}[s_d(a)]$ है। वैश्विक उद्देश्य नैश सोशल वेलफेयर है:
$f(\pi, s) = \prod_{d=1}^D u_d(\pi)$
लक्ष्य इष्टतम नीति $\pi^*$ के सापेक्ष अपेक्षित संचयी पछतावा (expected cumulative regret) को कम करना है, जो इस गुणनफल को अधिकतम करती है।

कठिनाई विश्लेषण (Hardness Analysis)

यह शोध पत्र एक मौलिक रिग्रेट लोअर बाउंड (regret lower bound) $\Omega(T^{2/3} \min(K, D)^{1/3})$ स्थापित करता है। यह परिणाम दर्शाता है कि परस्पर विरोधी कॉोंडोरसेट विजेताओं वाले उपयोगकर्ताओं के बीच NSW को अधिकतम करने की आवश्यकता मानक ड्यूलिंग बैंडिट्स (जो आमतौर पर $O(\log T)$ रिग्रेट प्राप्त करते हैं) की तुलना में महत्वपूर्ण कठिनाई पेश करती है। कठिनाई इसलिए उत्पन्न होती है क्योंकि एल्गोरिदम को "बुरे" कॉोंडोरसेट विजेताओं को खेलना पड़ता है (जो एक उपयोगकर्ता के लिए इष्टतम हैं लेकिन अन्य उपयोगकर्ताओं के लिए लगभग शून्य उपयोगिता देते हैं) ताकि उन्हें "अच्छे" विजेताओं से अलग पहचाना जा सके, जिससे अन्वेषण लागत (exploration costs) और तात्कालिक पछतावे (instantaneous regret) के बीच एक ट्रेड-ऑफ पैदा होता है।

एल्गोरिदम (Algorithms)

इस उद्देश्य को प्राप्त करने के लिए दो एल्गोरिदम प्रस्तावित किए गए हैं, जिनमें दोनों में कॉोंडोरसेट विजेता पहचान चरण (Condorcet winner identification phase) शामिल है:

फेयर-एक्सप्लोर-देन-कमिट (Fair-ETC):
- चरण 1 (पहचान): सभी $D$ उपयोगकर्ताओं के लिए कॉोंडोरसेट विजेताओं के सेट $\hat{A}^*$ की पहचान करने के लिए एक संशोधित ड्वोरेट्स्की-कीफर-वोल्फविट्ज़ टूर्नामेंट (DKWT) एल्गोरिदम का उपयोग करता है। यह चरण सभी उपयोगकर्ताओं के लिए एम्पिरिकल मार्जिन को एक साथ अपडेट करने के लिए साझा इंटरैक्शन का लाभ उठाता है।
- चरण 2 (अन्वेषण): पहचाने गए कॉोंडोरसेट विजेताओं के सापेक्ष सभी भुजाओं के स्कोर का अनुमान लगाता है।
- चरण 3 (प्रतिबद्धता): वह नीति $\hat{\pi}$ की गणना करता है जो एम्पिरिकल NSW को अधिकतम करती है और शेष क्षितिज के लिए उसी के प्रति प्रतिबद्ध हो जाता है।
फेयर- $\epsilon$ -ग्रीडी (Fair- $\epsilon$ -Greedy):
- यह एल्गोरिदम पूरे क्षितिज के दौरान अन्वेषण और दोहन (exploration and exploitation) को आपस में जोड़ता है।
- यह उसी कॉोंडोरसेट विजेता पहचान चरण के साथ शुरू होता है।
- प्रत्येक चरण $t$ पर, $\epsilon_t$ प्रायिकता के साथ, यह अनुमानित कॉोंडोरसेट विजेताओं को शामिल करने वाली जोड़ियों को खेलकर अन्वेषण करता है (राउंड-रॉबिन शेड्यूलिंग का उपयोग करते हुए) ताकि स्कोर अनुमानों को परिष्कृत किया जा सके।
- $1-\epsilon_t$ प्रायिकता के साथ, यह वर्तमान एम्पिरिकल NSW को अधिकतम करने वाली नीति को खेलकर दोहन करता है।
- अभिसरण (convergence) सुनिश्चित करने के लिए अन्वेषण दर $\epsilon_t$ समय के साथ घटती जाती है।

दोनों एल्गोरिदम को $\tilde{O}(T^{2/3})$ का रिग्रेट अपर बाउंड प्राप्त करने के लिए सिद्ध किया गया है, जो लॉगरिदमिक कारकों तक $T$ के संबंध में लोअर बाउंड से मेल खाता है।

मुख्य योगदान

समस्या का निरूपण: फेयर मल्टी-यूज़र ड्यूलिंग बैंडिट का पहला औपचारिक निरूपण, जो व्यक्तिगत कॉोंडोरसेट विजेters के आधार पर विशिष्ट उपयोगकर्ता उपयोगिताओं को मॉडल करता है और NSW को निष्पक्षता उद्देश्य के रूप में अपनाता है।
रिग्रेट लोअर बाउंड: $\Omega(T^{2/3} \min(K, D)^{1/3})$ का एक रिग्रेट लोअर बाउंड प्राप्त करना, जिसे लेखक विषम वरीयताओं वाले ड्यूलिंग बैंडिट्स में निष्पक्षता की लागत को मापने वाला पहला परिणाम बताते हैं।
एल्गोरिदम समाधान: Fair-ETC और Fair- $\epsilon$ -Greedy एल्गोरिदम का प्रस्ताव, जो लोअर बाउंड के $T$ के संबंध को मैच करने वाले सैद्धांतिक रिग्रेट अपर बाउंड के साथ आते हैं।
अनुभवजन्य सत्यापन (Empirical Validation): व्यापक सिमुलेशन जो यह प्रदर्शित करते हैं कि प्रस्तावित एल्गोरिदम निष्पक्षता मेट्रिक्स (गिनी गुणांक, न्यूनतम उपयोगकर्ता कल्याण) में उपयोगितावादी बेसलाइन से बेहतर प्रदर्शन करते हुए प्रतिस्पर्धी संचयी रिग्रेट बनाए रखते हैं।

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

लेखकों ने अपने एल्गोरिदम का मूल्यांकन यादृच्छिक रूप से उत्पन्न वरीयताओं और वास्तविक दुनिया के डेटा (सुशी डेटासेट, जिसे मैक्रोस्कोपिक उपयोगकर्ताओं में क्लस्टर किया गया है) दोनों पर किया।

यादृच्छिक वरीयताएँ (Random Preferences): उपयोगकर्ताओं ( $D$ ) और भुजाओं ( $K$ ) के विभिन्न विन्यासों में, Fair-ETC और Fair- $\epsilon$ -Greedy दोनों ने उप-रैखिक (sublinear) रिग्रेट प्रदर्शित किया, और लगातार उपयोगितावादी बेसलाइन और 'यूनिफॉर्म-ओवर-यूजर्स' बेसलाइन से बेहतर प्रदर्शन किया।
निष्पक्षता मेट्रिक्स (Fairness Metrics): प्रस्तावित एल्गोरिदम ने उच्चतम नैश सोशल वेलफेयर और उपयोगितावादी दृष्टिकोणों की तुलना में काफी कम गिनी गुणांक प्राप्त किया। उन्होंने उच्च न्यूनतम उपयोगकर्ता कल्याण भी बनाए रखा, जो अल्पसंख्यक वरीयताओं के बेहतर संरक्षण को दर्शाता है।
क्लस्टर्ड वरीयताएँ (Clustered Preferences): स्पष्ट बहुमत और अल्पसंख्यक क्लस्टरों (ध्रुवीकृत वरीयताओं का अनुकरण करते हुए) वाले परिदृश्यों में, उपयोगितावादी एल्गोरिदम ने बहुमत का पक्ष लिया, जिससे उच्च असमानता हुई। प्रस्तावित निष्पक्ष एल्गोरिदम ने हितों को सफलतापूर्वक संतुलित किया, कम गिनी गुणांक और उच्च न्यूनतम कल्याण बनाए रखा।
सुशी डेटासेट (Sushi Dataset): वास्तविक दुनिया के डेटा पर, प्रस्तावित तरीकों ने $D=5$ और $D=10$ क्लस्टर सेटिंग्स में सबसे कम संचयी रिग्रेट प्राप्त किया। हालांकि एक यूनिफॉर्म बेसलाइन ने अत्यधिक खंडित $D=10$ मामले में थोड़ा बेहतर निष्पक्षता दिखाई, लेकिन उसका रिग्रेट बहुत खराब था।

महत्व और दावे

यह शोध पत्र दावा करता है कि यह विषम वरीयताओं वाले ड्यूलिंग बैंडिट्स में निष्पक्षता की लागत को मापने वाला पहला कार्य है, जो $\Omega(T^{2/3})$ का एक मौलिक रिग्रेट लोअर बाउंड स्थापित करता है। लेखक अपने कार्य को मानव-केंद्रित मशीन लर्निंग की दिशा में एक आवश्यक कदम के रूप में देखते हैं, जहाँ औसत वरीयता के लिए अनुकूलन करना अपर्याप्त है और संभावित रूप से अल्पसंख्यक समूहों के लिए हानिकारक है।

ड्यूलिंग बैंडिट ढांचे में नैश सोशल वेलफेर उद्देश्य को एकीकृत करके, यह कार्य उन नीतियों को सीखने के लिए एक सैद्धांतिक और एल्गोरिदम आधार प्रदान करता है जो दक्षता और निष्पक्षता के बीच संतुलन बनाती हैं। लेखक नोट करते हैं कि उनका दृष्टिकोण पूर्व मल्टी-एजेंट बैंडिट कार्यों (जैसे Hossian et al., 2021; Jones et al., 2023) से अलग है क्योंकि यह पूर्ण पुरस्कारों के बजाय एक सापेक्ष वरीयता सेटिंग में काम करता है, जिसके लिए मौलिक रूप से भिन्न उपयोगिता अनुमान तकनीकों की आवश्यकता होती है।

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