Prior Diffusiveness and Regret in the Linear-Gaussian Bandit

समस्या विवरण
यह शोध पत्र लीनियर-गौसियन बैंडिट (linear-Gaussian bandit) समस्या को संबोधित करता है, जो एक अनुक्रमिक निर्णय लेने वाली सेटिंग है जहाँ एक खिलाड़ी संचयी पुरस्कार (cumulative rewards) को अधिकतम करने के लिए क्रियाएं $A_t \in \mathcal{A} \subset \mathbb{R}^d$ चुनता है। समय $t$ पर पुरस्कार $R_{t+1} = \theta_\star^\top A_t + W_{t+1}$ द्वारा उत्पन्न होता है, जहाँ $\theta_\star$ एक अज्ञात पैरामीटर वेक्टर है और $W_{t+1}$ $\sigma^2$ विचरण (variance) वाला i.i.d. गौसियन शोर (noise) है। इसका उद्देश्य एक पूर्व वितरण (prior distribution) $\rho$ के तहत $\theta_\star$ पर कुल क्षति (cumulative regret) को कम करना है, जिसे क्षेतिज $T$ के ऊपर इष्टतम क्रिया और चुनी गई क्रिया के अपेक्षित अंतर के रूप में परिभाषित किया गया है। विशेष रूप से, लेखक $r$ त्रिज्या वाले स्केल्ड $\ell_2$-बॉल के मामले पर ध्यान केंद्रित करते हैं।

कार्यप्रणाली
लेखक थॉम्पसन सैंपलिंग (Thompson sampling) का विश्लेषण करते हैं, जो एक पोस्टीरियर सैंपलिंग एल्गोरिदम है जो इतिहास $H_t$ के आधार पर पोस्टीरियर वितरण से एक पैरामीटर अनुमान $\hat{\theta}_t$ प्राप्त करता है और $\hat{\theta}_t$ के तहत अपेक्षित पुरस्कार को अधिकतम करने वाली क्रिया का चयन करता है।

रेग्रेट बाउंड्स (regret bounds) प्राप्त करने के लिए, लेखक तात्कालिक क्षति (instantaneous regret) को दो पदों में विभाजित करते हैं:

1. पद (I): वह क्षति जो तब होती है जब सैंपल्ड पैरामीटर $\hat{\theta}_t$ वास्तविक पैरामीटर $\theta_\star$ के करीब होता है (पोस्टीरियर प्रिसिजन मैट्रिक्स द्वारा परिभाषित एक उच्च-संभाव्यता घटना के भीतर)।
2. पद (II): वह क्षति जो तब होती है जब सैंपल्ड पैरामीटर वास्तविक पैरामीटर से दूर होता है।

मुख्य तकनीकी नवाचार पद (I) के विश्लेषण में निहित है। लेखक एक सामान्यीकृत दीर्घवृत्तीय क्षमता लेम्मा (generalized elliptical potential lemma) (लेम्मा 3) पेश करते हैं। लीनियर बैंडिट साहित्य (जैसे, एबेल और लाज़ारिक, 2017; डेनी एट अल., 2008) में उपयोग किए जाने वाले मानक दीर्घवृत्तीय क्षमता लेम्मा के विपरीत, जिन्हें आमतौर पर प्रारंभिक प्रिसिजन मैट्रिक्स को शून्य से दूर (जैसे, $V_0 \succeq I$) होने की आवश्यकता होती है और जो द्विघात त्रुटियों (quadratic errors) को बांधते हैं, यह नया लेम्मा:

• प्रारंभिक प्रिसिजन मैट्रिक्स $V_0$ को मनमाने ढंग से छोटा (या सीमा में शून्य भी) होने की अनुमति देता है, जो विसरित प्रायर (diffuse priors) को समायोजित करता है।
• नॉर्म्स के योग में एक लचीला घातांक $p \in [0, 1]$ पेश करता है।
• स्पष्ट रूप से बाउंड को एक लॉगरिदमिक डिटरमिनेंट टर्म (जो दीर्घकालिक सूचना लाभ को कैप्चर करता है) और प्रारंभिक प्रिसिजन मैट्रिक्स से जुड़े एक ट्रेस टर्म (जो प्रारंभिक "बर्न-इन" लागत को कैप्चर करता है) में अलग करता है।

पद (II) का विश्लेषण गौसियन वितरणों के लिए मानक एकाग्रता असमानताओं (concentration inequalities) पर निर्भर करता है ताकि $\hat{\theta}_t$ और $\theta_\star$ के बीच बड़े विचलन की संभावना को सीमित किया जा सके।

प्रमुख योगदान और परिणाम
प्राथमिक योगदान लीनियर-गौसियन सेटिंग में थॉम्पसन सैंपलिंग के लिए एक नया बेयसियन रेग्रेट बाउंड है जो प्रायर-निर्भर "बर्न-इन" पद को मिनिमैक्स रेट से अलग करता है।

1. सुधारित रेग्रेट बाउंड: लेखक सिद्ध करते हैं कि थॉम्पसन सैंपलिंग निम्नलिखित रेग्रेट प्राप्त करता है:
   $$\text{Reg}(T) = \tilde{O}\left( \sigma d \sqrt{T} + d r \sqrt{\text{Tr}(\Sigma_0)} \right)$$
   यहाँ, $\sigma d \sqrt{T}$ एसिम्प्टोटिक मिनिमैक्स दर का प्रतिनिधित्व करता है, जबकि $d r \sqrt{\text{Tr}(\Sigma_0)}$ प्रायर स्केल से शोर स्केल तक अनिश्चितता को कम करने की प्रारंभिक लागत है।

2. पदों का पृथक्करण (Decoupling of Terms): पिछले बाउंड्स (जैसे, कलकनली और ओज़गुर, 2020) में एक गुणात्मक निर्भरता प्रदर्शित होती थी, जैसे कि $\tilde{O}(d \sqrt{T(\sigma^2 + r^2 \text{Tr}(\Sigma_0))})$, जहाँ प्रायर डिफ्यूसिवनेस $\sqrt{\text{Tr}(\Sigma_0)}$ संपूर्ण मिनिमैक्स रेट को स्केल करती थी। नया परिणाम दिखाता है कि, लॉगरिदमिक कारकों तक, प्रायर डिफ्यूसिवनेस केवल एक योगात्मक स्थिरांक (additive constant) जोड़ती है, जो समय क्षेतिज $T$ से स्वतंत्र है।

3. लोअर बाउंड्स (Lower Bounds): यह शोध पत्र इस सेटिंग में किसी भी नीति के लिए एक लोअर बाउंड स्थापित करता है, यह प्रदर्शित करते हुए कि गौसियन प्रायर के लिए बर्न-इन पद $d r \sqrt{\text{Tr}(\Sigma_0)}$ अपरिहार्य है। यह पुष्टि करता है कि ऊपरी बाउंड की योगात्मक संरचना (लॉगरिदमिक कारकों तक) टाइट है और प्रायर डिफ्यूसिवनेस को पूरी तरह से हटाया नहीं जा सकता है।

4. सामान्यीकरण: लेखक उल्लेख करते हैं कि उनके परिणामों को केवल गौसियन मामले तक सीमित न रहकर, स्ट्रॉन्गली लॉग-कॉन्केव प्रायर और शोर वितरणों तक विस्तारित किया जा सकता है।

महत्व
यह शोध पत्र दावा करता है कि इसके परिणाम थॉम्पसन सैंपलिंग के लिए मौजूदा रेग्रेट बाउंड्स की ढीलेपन (looseness) को हल करते हैं। यह सिद्ध करके कि प्रायर-निर्भर पद गुणात्मक होने के बजाय योगात्मक है, यह कार्य प्रायर डिफ्यूसिवनेस की भूमिका को स्पष्ट करता है: यह एक बार की "बर्न-इन" लागत के रूप में कार्य करता है जो अनिश्चितता को अवलोकन शोर के स्तर तक कम करने के लिए आवश्यक है, जिसके बाद एल्गोरिदम का प्रदर्शन केवल शोर विचरण $\sigma$ और आयाम $d$ द्वारा नियंत्रित होता है। यह एल्गोरिदम की दक्षता का अधिक सटीक लक्षण वर्णन प्रदान करता है, विशेष रूप से उन व्यवस्थाओं में जहाँ प्रायर अत्यधिक विसरित (large $\text{Tr}(\Sigma_0)$) है, यह दिखाते हुए कि ऐसी डिफ्यूसिवनेस एसिम्प्टोटिक अभिसरण दर को स्थायी रूप से खराब नहीं करती है। पेश किया गया सामान्यीकृत दीर्घवृत्तीय क्षमता लेम्मा एक ऐसे उपकरण के रूप में प्रस्तुत किया गया है जो स्टोकेस्टिक ऑप्टिमाइज़ेशन समस्याओं के अधिक लचीले विश्लेषण को सक्षम बनाता है जहाँ प्रारंभिक अनिश्चितता अनबाउंडेड हो सकती है।