📊 statistics

Asymptotic Optimality of Thompson Sampling for Risk-Averse Bandits with Sub-Gaussian Rewards

यह शोध पत्र सब-गॉसियन रिवॉर्ड्स वाले रिस्क-अवर्स मल्टी-आर्म्ड बैंडिट्स के लिए $\rho\text{-}\mathrm{NPTS}_{\mathrm{SG}}$ एल्गोरिदम की एसिम्प्टोटिक ऑप्टिमैलिटी को स्थापित करता है, यह सिद्ध करते हुए कि यह किसी भी निरंतर रिस्क फंक्शनल के लिए बिना किसी पैरामेट्रिक धारणा या लिप्सचिट्ज़ स्थितियों की आवश्यकता के, सैद्धांतिक निचली सीमा (लोअर बाउंड) से मेल खाने वाला इंस्टेंस-डिपेंडेंट रिग्रेट प्राप्त करता है।

मूल लेखक: Joel Q. L. Chang

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

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

CC BY 4.0

मूल लेखक: Joel Q. L. Chang

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

कल्पना कीजिए कि आप एक मैनेजर हैं जो उम्मीदवारों की एक टीम में से सबसे अच्छे कर्मचारी को चुनने की कोशिश कर रहे हैं। इस समस्या के क्लासिक संस्करण में, आप केवल इस बात की परवाह करते हैं कि कौन सबसे अधिक पैसा कमाता है। लेकिन वास्तविक दुनिया में, आप जोखिम (risk) की भी परवाह करते हैं।

क्या आप उस कर्मचारी को चाहते हैं जो बहुत सारा पैसा कमाता है लेकिन कल ही नौकरी छोड़ सकता है?
या वह जो एक स्थिर, विश्वसनीय राशि कमाता है?
शायद आप वह व्यक्ति चाहते हैं जो इस आधार पर सबसे अधिक पैसा कमाता है कि वह कितना तनाव पैदा करता है (जैसे वित्त में एक "शार्प रेशियो" (Sharpe ratio))।

यह रिस्क-अवेर्स बैंडिट्स (Risk-Averse Bandits) की दुनिया है। "बैंडिट" एक स्लॉट मशीन है जिसमें कई भुजाएं (उम्मीदवार) हैं। आप एक भुजा खींचते हैं ताकि इनाम देख सकें, लेकिन आप यह सीखना चाहते हैं कि कौन सा विकल्प सबसे अच्छा है बिना खराब विकल्पों पर बहुत अधिक बार हाथ आजमाए।

समस्या: "बढ़ती वर्णमाला" (Growing Alphabet) का उलझाव

वर्षों तक, वैज्ञानिकों के पास एक बेहतरीन उपकरण था जिसे थॉम्पसन सैंपलिंग (Thompson Sampling) कहा जाता था। यह इस प्रकार काम करता है:

आप इस आधार पर एक "विश्वास" (मानचित्र) रखते हैं कि आपने अब तक जो देखा है उसके आधार पर प्रत्येक भुजा कितनी अच्छी है।
आप उस मानचित्र से एक रैंडम परिदृश्य (scenario) चुनते हैं और उस भुजा को चुनते हैं जो उस विशिष्ट परिदृश्य में सबसे अच्छी दिखती है।
आप इसे दोहराते हैं।

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

गणितविद इसे "बढ़ती वर्णमाला" (growing alphabet) कहते हैं।

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

समाधान: "ग्रिड" (Grid) वाली तरकीब

लेखक, जोएल चांग (Joel Chang), इस उलझन को ठीक करने के लिए एक चतुर तरकीब पेश करते हैं। वे इसे डिस्क्रिटाइजेशन लेम्मा (Discretisation Lemma) कहते हैं।

कल्पना कीजिए कि आपका मानचित्र लाखों छोटे पिक्सेल (बढ़ती वर्णमाला) वाली एक हाई-रिज़ॉल्यूशन फोटो है। हर एक पिक्सेल का विश्लेषण करना असंभव है।

तरकीब: हर पिक्सेल को देखने के बजाय, आप फोटो के ऊपर एक निश्चित ग्रिड (ग्राफ पेपर की तरह) बिछा देते हैं। आपको केवल इस बात से मतलब है कि एक पिक्सेल ग्रिड के किस "वर्ग" (square) में आता है।
यह क्यों काम करता है: भले ही आप दस लाख कदम उठा लें, आपके पास ग्राफ पेपर पर वर्गों की एक निश्चित संख्या ही होगी। यह गणित को सरल और प्रबंधनीय रखता है। लेखक यह सिद्ध करते हैं कि यह "ग्रिड" सन्निकटन (approximation) वास्तविक चीज़ के इतने करीब है कि आप सटीकता नहीं खोते, लेकिन यह संख्याओं को विस्फोट होने से रोकता है।

उन्होंने क्या सिद्ध किया?

इस ग्रिड की तरकीब का उपयोग करके, पेपर दो मुख्य बातें सिद्ध करता है:

यह किसी भी "स्मूथ" (Smooth) जोखिम माप के लिए काम करता है: चाहे आप औसत इनाम की परवाह करें, सबसे खराब स्थिति (CVaR) की, या जोखिम-समायोजित रिटर्न (Sharpe ratio) की, यह एल्गोरिदम बिल्कुल उस गति से सीखता है जो सैद्धांतिक रूप से संभव है।
- उपमा: पहले, हम केवल "उच्चतम औसत चुनें" जैसे सरल नियमों के लिए इसे सिद्ध कर सकते थे। अब, हमने सिद्ध किया है कि यह "उच्चतम औसत को अस्थिरता (volatility) से विभाजित करने" जैसे जटिल नियमों के लिए भी काम करता है, बिना यह धारणा बनाए कि पुरस्कार एक विशिष्ट आकार (जैसे कि एक आदर्श बेल कर्व) का पालन करते हैं।
यह वास्तविक दुनिया के डेटा (Sub-Gaussian) के लिए काम करता है: लेखकों ने इसे ऐसे डेटा को संभालने के लिए विस्तारित किया है जो 0 और 1 के बीच सीमित नहीं है (जैसे $0 और$ 1 के बीच का पैसा)। उन्होंने सिद्ध किया कि यह ऐसे डेटा के लिए काम करता है जो कहीं भी जा सकता है लेकिन जिसके "पूंछ पतली" (thin tails) है (यानी चरम आउटलेयर्स बहुत दुर्लभ हैं, जैसे कि एक सामान्य वितरण में)।
- "एंकर-फ्री" (Anchor-Free) अपग्रेड: पुराने संस्करण को काम करने के लिए एक "सुरक्षा एंकर" (एक काल्पनिक शुरुआती बिंदु) की आवश्यकता थी। नया संस्करण, जिसे $\rho$ -NPTSSG कहा जाता है, को इस एंकर की आवश्यकता नहीं है। यह बस भुजाओं को खींचना शुरू करता है और शुद्ध अनुभव से सीखता है।

यह क्यों महत्वपूर्ण है (पेपर के अनुसार)

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

सारांश

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

तकनीकी सारांश: सब-गॉसियन रिवॉर्ड्स वाले रिस्क-अवर्स बैंडिट्स के लिए थॉम्पसन सैंपलिंग की एसिम्प्टोटिक ऑप्टिमैलिटी

समस्या विवरण
यह शोध पत्र रिस्क-अवर्स उद्देश्यों के तहत मल्टी-आर्म्ड बैंडिट (MAB) समस्या को संबोधित करता है। मानक MAB सेटिंग्स के विपरीत, जो अपेक्षित रिवॉर्ड (expected reward) को अधिकतम करने का लक्ष्य रखती हैं, रिस्क-अवर्स सेटिंग्स सामान्य रिस्क फंक्शनल्स $\rho$ (जैसे कि कंडीशनल वैल्यू-एट-रिस्क (CVaR), मीन-वेरिएंस, शार्प रेश्यो, या डिस्टॉर्शन रिस्क मेजर्स) को अनुकूलित करने का लक्ष्य रखती हैं। विशिष्ट चुनौती $\rho$ -NPTS (चांग और टैन [2022] द्वारा प्रस्तावित एक नॉनपैरामेट्रिक थॉम्पसन सैंपलिंग एल्गोरिदम) के सैद्धांतिक विश्लेषण की है। जबकि चांग और टैन ने एक पैरामेट्रिक साथी ( $\rho$ -MTS) के लिए इंस्टेंस-ऑप्टिमल रिग्रेट सिद्ध किया था, उन्होंने $\rho$ -NPTS की नॉनपैरामेट्रिक ऑप्टिमैलिटी को एक खुले प्रश्न के रूप में छोड़ दिया था।

मौलिक बाधा यह है कि $\rho$ -NPTS एक डिरिचलेट पोस्टीरियर (Dirichlet posterior) बनाता है जहाँ प्रभावी अल्फाबेट आकार अवलोकनों की संख्या ( $N_k$ ) के साथ बढ़ता है। मौजूदा टेल बाउंड्स (tail bounds) का प्रत्यक्ष अनुप्रयोग $(N_k)^{N_k/2}$ के सुपर-एक्सपोनेंशियल प्रीफैक्टर (prefactor) की ओर ले जाता है, जो लॉगरिदमिक रिग्रेट बाउंड्स के प्रमाण को रोकता है। इसके अलावा, पूर्व परिणामों के लिए अक्सर "डोमिनेंस" (dominance) जैसी मजबूत स्थितियों की आवश्यकता होती थी (पैरामेट्रिक विधियों के लिए) या UCB-प्रकार के एल्गोरिदम के लिए लिप्सचिट्ज़ निरंतरता (Lipschitz continuity) की आवश्यकता होती थी, जो शार्प रेश्यो जैसे महत्वपूर्ण नॉन-लिप्सचिट्ज़ फंक्शनल्स को बाहर करती है।

कार्यप्रणाली
लेखक $\rho$ -NPTSSG पेश करते हैं, जो बाउंडेड डेंसिटी और सब-गॉसियन टेल्स ( $P(B, \sigma)$ ) वाली डिस्ट्रीब्यूशंस के लिए डिज़ाइन किया गया एक अनकंस्ट्रक्टेड (anchor-free) वेरिएंट है। मुख्य तकनीकी नवाचार एक डिसक्रेटाइजेशन लेम्मा (और सब-गॉसियन टेल्स के लिए इसका ट्रंकेटेड एनालॉग) है जो बढ़ते-अल्फाबेट डिरिचलेट पोस्टीरियर को एक फिक्स्ड ग्रिड पर प्रोजेक्ट करता है।

डिसक्रेटाइजेशन और एग्रीगेशन:
शोध पत्र आकार $M$ के एक फिक्स्ड ग्रिड $G_M$ को परिभाषित करता है। किसी भी देखे गए रिवॉर्ड सीक्वेंस के लिए, एम्पिरिकल मेजर को इस ग्रिड पर प्रोजेक्ट किया जाता है, जिसमें एक ही ग्रिड बिन के भीतर आने वाले अवलोकनों से संबंधित डिरिचलेट वेट्स को एग्रीगेट किया जाता है।
- मुख्य अंतर्दृष्टि: डिरिचलेट डिस्ट्रीब्यूशन के एग्रीगेशन गुण द्वारा, भरे हुए बिन्स पर प्रोजेक्टेड वेट्स एक डिरिचलेट डिस्ट्रीब्यूशन का पालन करते हैं जिसका आयाम (dimension) फिक्स्ड ( $M^+ \le M$ ) होता है, चाहे सैंपल साइज $N_k$ कुछ भी हो।
- परिणाम: यह प्रोजेक्शन टेल बाउंड्स में पॉलीनोमियल प्रीफैक्टर की डिग्री को $(M-1)/2$ पर सीमित कर देता है, जो $N_k$ से स्वतंत्र है। यह उस सुपर-एक्सपोनेंशियल बैरियर को तोड़ देता है जिसने पिछले प्रमाणों को बाधित किया था।
एल्गोरिदम वेरिएंट्स:
- $\rho$ -NPTS (बाउंडेड सपोर्ट): यह $[0, 1]$ के सपोर्ट और बाउंडेड डेंसिटी वाली डिस्ट्रीब्यूशंस पर कार्य करता है। यह एक फिक्स्ड एंकर (दायां एंडपॉइंट) और एक यूनिफॉर्म ग्रिड का उपयोग करता है।
- $\rho$ -NPTSSG (सब-गॉसियन): यह बाउंडेड डेंसिटी और सब-गॉसियन टेल्स वाली $\mathbb{R}$ पर डिस्ट्रीब्यूशंस पर कार्य करता है। यह फिक्स्ड एंकर को हटा देता है (राउंड-रॉबिन इनिशियलाइजेशन का उपयोग करके) और एक ट्रंकेटेड डिसक्रेटाइजेशन लेम्मा का उपयोग करता है। यह लेम्मा एम्पिरिकल मीन के केंद्र में एक ग्रिड का उपयोग करता जिसकी चौड़ाई सैंपल साइज बढ़ने के साथ कम होती जाती है, जबकि ओवरफ्लो प्रोबेबिलिटी को नियंत्रित करने के लिए टेल्स को ट्रंकेट करता है।
रिग्रेट विश्लेषण:
प्रमाण रिग्रेट के एक मानक अपघटन (decomposition) का अनुसरण करता है, जहाँ रिग्रेट को उन पदों में विभाजित किया जाता है जहाँ एल्गोरिदम एक "उच्च" थॉम्पसन स्कोर बनाम एक "निम्न" स्कोर वाले सब-ऑप्टिमल आर्म को खींचता है।
- अपर बाउंड (Upper Bound): फिक्स्ड-ग्रिड प्रोजेक्शन पर चांग और टैन [2022] के टेल बाउंड्स को लागू करने के लिए डिसक्रेटाइजेशन लेम्मा का उपयोग करता है। $\rho$ की निरंतरता (विशेष रूप से $D_\infty$ -निरंतरता) यह सुनिश्चित करती है कि प्रोजेक्टेड मेजर का रिस्क वास्तविक रिस्क का अनुमान लगाता है।
- लोअर बाउंड (Lower Bound): चांग और टैन [2022] द्वारा स्थापित इंस्टेंस-डिपेंडेंट लोअर बाउंड से मेल खाता है, जो कुलबैक-लीब्लर (KL) डाइवर्जेंस मिनिमाइजेशन समस्या $K^\rho_{\inf}$ पर निर्भर करता है।

मुख्य योगदान

खुले प्रश्न का समाधान: यह शोध पत्र सिद्ध करता है कि $\rho$ -NPTSSG बाउंडेड डेंसिटी और सब-गॉसियन टेल्स वाली डिस्ट्रीब्यूशंस के क्लास के लिए किसी भी निरंतर रिस्क फंक्शनल $\rho$ पर इंस्टेंस-ऑप्टिमल रिग्रेट $\sum_{k: \Delta^\rho_k > 0} \frac{\Delta^\rho_k \log n}{K^\rho_{\inf}(\nu_k, r^\rho_1)} + o(\log n)$ प्राप्त करता है।
कमजोर शर्तें: परिणाम के लिए केवल रिस्क फंक्शनल $\rho$ $ρ$ की निरंतरता (विशेष रूप से लेवी-प्रोकोरोव मेट्रिक के संबंध में) की आवश्यकता होती है। यह पैरामेट्रिक $\rho$ $ρ$ -MTS के लिए आवश्यक "डोमिनेंस" स्थिति से काफी कमजोर है:
- यह लिप्सचिट्ज़ शर्त से भी कमजोर है जो UCB-प्रकार के एल्गोरिदम के लिए आवश्यक है।
- यह शार्प रेश्यो जैसे नॉन-लिप्सचिट्ज़ फंक्शनल्स के लिए पहले इंस्टेंस-ऑप्टिमल गारंटी प्रदान करता है, बिना पैरामेट्रिक रिवॉर्ड डिस्ट्रीब्यूशंस की धारणा के।
डिसक्रेटाइजेशन लेम्मा: यह शोध पत्र एक तकनीकी लेम्मा पेश करता है जो एक फिक्स्ड रेजोल्यूशन पर बढ़ते-अल्फाबेट डिरिचलेट पोस्टीरियर को नियंत्रित करता है। यह लेम्मा बढ़ते सपोर्ट वाले डिरिचलेट प्रोसेस से जुड़े किसी भी समस्या के लिए स्वतंत्र रूप से उपयोगी हो सकता है।
सब-गॉसियन विस्तार: लेखक एक ट्रंकेटेड डिसक्रेटाइजेशन दृष्टिकोण के माध्यम से बाउंडेड-सपोर्ट परिणामों को व्यापक सब-गॉसियन डिस्ट्रीब्यूशंस (गाऊसी आर्म्स सहित) तक विस्तारित करते हैं, जिससे पूर्व-निर्धारित सपोर्ट इंटरवल की आवश्यकता समाप्त हो जाती है।

परिणाम

थ्योरम 1 (बाउंडेड सपोर्ट): केवल निरंतरता के तहत $P(B)$ पर $\rho$ -NPTS के लिए एसिम्प्टोटिक ऑप्टिमैलिटी स्थापित करता है।
थ्योरम 2 (सब-गॉसियन): $P(B, \sigma)$ पर $\rho$ -NPTSSG के लिए एसिम्प्टोटिक ऑप्टिमैलिटी स्थापित करता है।
प्रायोगिक सत्यापन: शोध पत्र सिद्धांत को मान्य करने के लिए चार प्रयोग प्रस्तुत करता है:
1. $\rho$ -NPTS बीटा आर्म्स पर CVaR के लिए इंस्टेंस-ऑप्टिमल लोअर बाउंड को ट्रैक करता है, जो रिस्क-LCB बेसलाइन (जिसमें $\log^2 n$ गारंटी है) से बेहतर प्रदर्शन करता है।
2. $\rho$ -NPTS ट्रंकेटेड-नॉर्मल आर्म्स पर शार्प रेश्यो के लिए $O(\log n)$ रिग्रेट प्राप्त करता है, जो एक ऐसा मामला है जहाँ नॉन-लिप्सचिट्ज़नेस के कारण पहले कोई भी एल्गोरिदम गारंटी नहीं दे सका था।
3. एल्गोरिदम बिना किसी संशोधन के कंपोजिट फंक्शनल्स (जैसे $0.5 \text{CVaR} + 0.5 \text{Sharpe}$ ) को संभालता है।
4. $\rho$ -NPTSSG गाऊसी आर्म्स के लिए इंस्टेंस-ऑप्टिमल लोअर बाउंड की ओर अभिसरित (converge) होता है, जो बिना पैरामेट्रिक धारणाओं के स्पेशलाइज्ड नॉर्मल-गामा थॉम्पसन सैंपलिंग एल्गोरिदम (शाह एट अल. [2025]) के प्रदर्शन से मेल खाता है।

महत्व और दावे
यह शोध पत्र दावा करता है कि यह रिस्क-अवर्स बैंडिट्स के लिए नॉनपैरामेट्रिक थॉम्पसन सैंपलिंग की सैद्धांतिक स्थिति को सुलझाता है। यह प्रदर्शित करता है कि ये एल्गोरिदम केवल अनुभवजन्य ह्यूरिस्टिक्स (empirical heuristics) नहीं हैं बल्कि प्रमाणित रूप से एसिम्प्टोटिक रूप से ऑप्टिमल हैं।

इनका महत्व धारणाओं के सरलीकरण में निहित है:

अभ्यासकर्ता (practitioners) बिना किसी पूर्व-निर्धारित रिवॉर्ड ग्रिड या अल्फाबेट आकार को ट्यून किए कच्चे अवलोकनों का उपयोग कर सकते हैं।
विधि पिछले अनुकूलतम तरीकों की तुलना में एक व्यापक वर्ग के रिस्क फंक्शनल्स (शार्प रेश्यो सहित) और डिस्ट्रीब्यूशन क्लासेज (सब-गॉसियन) पर लागू होती है।
यह परिणाम शाह एट अल. [2025] के समवर्ती कार्य को कंजुगेट प्रायर्स या पैरामेट्रिक धारणाओं की आवश्यकता के बिना शार्प रेश्यो के लिए एक शार्पर, इंस्टेंस-ऑप्टिमल कॉन्स्टेंट प्रदान करके समाहित (subsume) करता है।

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

समस्या: "बढ़ती वर्णमाला" (Growing Alphabet) का उलझाव

समाधान: "ग्रिड" (Grid) वाली तरकीब

उन्होंने क्या सिद्ध किया?

यह क्यों महत्वपूर्ण है (पेपर के अनुसार)

सारांश

इसी तरह के और पेपर