2025-11-11T09:55:09.434704

UCB-type Algorithm for Budget-Constrained Expert Learning

Latypov, Suvorikova, Kroshnin et al.
In many modern applications, a system must dynamically choose between several adaptive learning algorithms that are trained online. Examples include model selection in streaming environments, switching between trading strategies in finance, and orchestrating multiple contextual bandit or reinforcement learning agents. At each round, a learner must select one predictor among $K$ adaptive experts to make a prediction, while being able to update at most $M \le K$ of them under a fixed training budget. We address this problem in the \emph{stochastic setting} and introduce \algname{M-LCB}, a computationally efficient UCB-style meta-algorithm that provides \emph{anytime regret guarantees}. Its confidence intervals are built directly from realized losses, require no additional optimization, and seamlessly reflect the convergence properties of the underlying experts. If each expert achieves internal regret $\tilde O(T^α)$, then \algname{M-LCB} ensures overall regret bounded by $\tilde O\!\Bigl(\sqrt{\tfrac{KT}{M}} \;+\; (K/M)^{1-α}\,T^α\Bigr)$. To our knowledge, this is the first result establishing regret guarantees when multiple adaptive experts are trained simultaneously under per-round budget constraints. We illustrate the framework with two representative cases: (i) parametric models trained online with stochastic losses, and (ii) experts that are themselves multi-armed bandit algorithms. These examples highlight how \algname{M-LCB} extends the classical bandit paradigm to the more realistic scenario of coordinating stateful, self-learning experts under limited resources.
academic

बजट-सीमित विशेषज्ञ शिक्षा के लिए UCB-प्रकार एल्गोरिदम

मूल जानकारी

  • पेपर ID: 2510.22654
  • शीर्षक: UCB-प्रकार एल्गोरिदम बजट-सीमित विशेषज्ञ शिक्षा के लिए
  • लेखक: Ilgam Latypov, Alexandra Suvorikova, Alexey Kroshnin, Alexander Gasnikov, Yuriy Dorn
  • वर्गीकरण: cs.LG (मशीन लर्निंग), cs.MA (बहु-एजेंट सिस्टम)
  • प्रकाशन समय: 28 अक्टूबर, 2025 (प्रीप्रिंट)
  • पेपर लिंक: https://arxiv.org/abs/2510.22654

सारांश

कई आधुनिक अनुप्रयोगों में, सिस्टम को कई ऑनलाइन प्रशिक्षित अनुकूली शिक्षण एल्गोरिदम के बीच गतिशील रूप से चयन करना चाहिए। उदाहरण के लिए स्ट्रीम वातावरण में मॉडल चयन, वित्त में व्यापार रणनीति स्विचिंग, और कई संदर्भ डाकू या सुदृढीकरण शिक्षण एजेंटों का समन्वय। प्रत्येक दौर में, शिक्षार्थी को K विशेषज्ञों में से एक भविष्यवक्ता चुनना चाहिए जबकि निश्चित प्रशिक्षण बजट के तहत अधिकतम M≤K विशेषज्ञों को अद्यतन कर सकता है।

यह पेपर स्टोकेस्टिक सेटिंग में इस समस्या को हल करता है, M-LCB एल्गोरिदम प्रस्तावित करता है—एक कम्प्यूटेशनल रूप से कुशल UCB शैली मेटा-एल्गोरिदम जो मनमाने समय के पश्चाताप गारंटी प्रदान करता है। इसके आत्मविश्वास अंतराल सीधे प्राप्त नुकसान से निर्मित होते हैं, अतिरिक्त अनुकूलन की आवश्यकता नहीं है, और अंतर्निहित विशेषज्ञों की अभिसरण विशेषताओं को निर्बाध रूप से प्रतिबिंबित करते हैं। यदि प्रत्येक विशेषज्ञ आंतरिक पश्चाताप Õ(T^α) प्राप्त करता है, तो M-LCB कुल पश्चाताप सीमा Õ(√(KT/M) + (K/M)^(1-α)T^α) सुनिश्चित करता है।

अनुसंधान पृष्ठभूमि और प्रेरणा

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

वास्तविक दुनिया के कई अनुप्रयोगों को कई स्व-शिक्षण विशेषज्ञों के बीच गतिशील चयन की आवश्यकता है:

  1. अनुशंसा प्रणालियाँ: कई भविष्यवक्ताओं को समानांतर में चलाना, उपयोगकर्ता प्रतिक्रिया के आधार पर अद्यतन करना
  2. वित्तीय मंच: बाजार तंत्र विकसित होने के साथ व्यापार रणनीतियों के बीच स्विच करना
  3. बड़े पैमाने पर ऑनलाइन सेवाएं: संदर्भ डाकू या सुदृढीकरण शिक्षण एल्गोरिदम के संयोजन का प्रबंधन करना

मूल चुनौतियाँ

पारंपरिक विधियों की सीमाएं:

  • शास्त्रीय बहु-भुजा डाकू (MAB): स्थिर या विरोधी पुरस्कार वितरण मानते हैं, भुजाओं की शिक्षण क्षमता पर विचार नहीं करते
  • विशेषज्ञ एल्गोरिदम: आमतौर पर पूर्ण प्रतिक्रिया की आवश्यकता होती है, विशेषज्ञों की शिक्षण दर पर विचार नहीं करते
  • मौजूदा विधियाँ: प्रत्येक दौर प्रशिक्षण बजट बाधा के तहत कई एक साथ शिक्षण विशेषज्ञों को प्रबंधित करने की चुनौती को पर्याप्त रूप से संबोधित नहीं करते

अनुसंधान प्रेरणा

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

मूल योगदान

  1. नवीन UCB-प्रकार मेटा-एल्गोरिदम (M-LCB): K स्व-शिक्षण विशेषज्ञों के पूल को प्रबंधित करने के लिए नया एल्गोरिदम प्रस्तावित करता है, सीमित प्रति-दौर शिक्षण बजट M(M≤K) पर विचार करते हुए
  2. कम्प्यूटेशनल दक्षता: प्राप्त नुकसान से सीधे आत्मविश्वास सीमाएं निर्मित करने की विधि प्रदान करता है, कम्प्यूटेशनल रूप से कुशल और महंगे सहायक अनुकूलन से बचता है
  3. सैद्धांतिक विश्लेषण: विशेषज्ञ व्यक्तिगत अभिसरण दर के आधार पर मेटा-एल्गोरिदम प्रदर्शन का अनुमान लगाता है, जब विशेषज्ञ पश्चाताप Õ(n^α) हो तो कुल पश्चाताप Õ(√(KT/M) + (K/M)^(1-α)T^α) है
  4. बहु-खेल डाकू विस्तार: साबित करता है कि M-LCB बहु-खेल डाकू सेटिंग तक विस्तारित हो सकता है

विधि विवरण

कार्य परिभाषा

  • निर्णय स्थान U: विशेषज्ञ सुझावों की स्थान
  • पर्यावरण स्थान E: स्टोकेस्टिक परिणाम स्थान
  • नुकसान फ़ंक्शन: ℓ : U×E → R₊
  • विशेषज्ञ विनिर्देश: प्रत्येक विशेषज्ञ k को टपल (Wₖ,Hₖ,Aₖ,gₖ,υₖ) द्वारा निर्दिष्ट किया जाता है
    • Wₖ: स्थिति/पैरामीटर स्थान
    • Hₖ: इतिहास स्थान
    • Aₖ: ऑनलाइन शिक्षण एल्गोरिदम
    • gₖ: स्थिति से सुझाव का मानचित्रण
    • υₖ: सुरक्षित सुझाव जनरेटर

प्रोटोकॉल प्रवाह

प्रत्येक दौर t का निष्पादन प्रवाह:

  1. मेटा-प्रोग्राम सलाहकार iₜ∈K और प्रशिक्षण उपसमुच्चय Sₜ⊆K चुनता है, |Sₜ|≤M और iₜ∈Sₜ को संतुष्ट करते हुए
  2. विशेषज्ञ iₜ सुरक्षित सुझाव uₜ = υᵢₜ(Hᵢₜᵗ)∈U प्रदान करता है
  3. पर्यावरण ξᵗ～D नमूना लेता है, प्रोग्राम नुकसान ℓ(uₜ,ξᵗ) सहन करता है
  4. विशेषज्ञ k∈Sₜ इतिहास और आंतरिक स्थिति को अद्यतन करते हैं

M-LCB एल्गोरिदम कोर

आत्मविश्वास सीमा परिभाषा

विशेषज्ञ k के लिए, परिभाषित करें:

  • सामान्यीकृत चलने वाला नुकसान: LAₖ(t) = (1/nₖᵗ)∑_{τ∈Iₖ(t)} ℓₖᵗ(wₖᵗ)
  • निम्न आत्मविश्वास सीमा: LCBₖ(t,δ) = LAₖ(t) - Uₖ(nₖᵗ,δₐᵣₘ)/nₖᵗ - G(nₖᵗ,δₙᵗ)
  • ऊपरी आत्मविश्वास सीमा: UCBₖ(t,δ) = LAₖ(t) + H(nₖᵗ,δₙᵗ)

जहाँ:

  • δₐᵣₘ = δ/(2K), δₙ = δ/(7Kn²)
  • G(n,δ) = √(2log(1/δ)/n) + 2log(1/δ)/(3n)
  • H(n,δ) = √(2log(1/δ)/n)

चयन रणनीति

  • प्रशिक्षण सेट चयन: Sₜ := argmin_{S⊆K,|S|≤M} ∑_{k∈S} LCBₖ(t,δ)
  • सलाहकार चयन: iₜ := argmin_{k∈Sₜ} UCBₖ(t,δ)

तकनीकी नवाचार बिंदु

  1. प्रत्यक्ष आत्मविश्वास सीमा निर्माण: प्राप्त नुकसान से सीधे निर्मित, अतिरिक्त अनुकूलन की आवश्यकता नहीं
  2. अनुकूली विशेषज्ञ प्रबंधन: विशेषज्ञ चयन और प्रशिक्षण बजट आवंटन दोनों पर एक साथ विचार करता है
  3. मनमाने समय की गारंटी: सभी समय चरणों T के लिए पश्चाताप सीमा प्रदान करता है
  4. लचीली रूपरेखा: विभिन्न प्रकार के शिक्षण एल्गोरिदम को विशेषज्ञ के रूप में समर्थन करता है

प्रायोगिक सेटअप

डेटासेट

पेपर मुख्य रूप से सिंथेटिक प्रयोग आयोजित करता है:

सामान्यीकृत रैखिक मॉडल चयन

  • विशेषज्ञ संख्या: K=10 सामान्यीकृत रैखिक मॉडल
  • विशेषता आयाम: विशेषता वेक्टर इकाई गोले Sᵈ⁻¹ से समान रूप से नमूना लिए जाते हैं
  • चुनौतीपूर्ण सेटिंग: फ़ंक्शन f₇,f₈,f₉ डेटा-घने क्षेत्र में अत्यधिक समान हैं, अन्वेषण कठिनाई बढ़ाते हैं

मूल्यांकन मेट्रिक्स

  1. संचयी नुकसान: ∑ᵗ₌₁ᵀ ℓ(uᵗ,ξᵗ)
  2. भुजा चयन वितरण: अंतिम विभिन्न विशेषज्ञों को चुने जाने की आवृत्ति
  3. कम्प्यूटेशनल बजट आवंटन: विभिन्न विशेषज्ञों को प्राप्त प्रशिक्षण संख्या वितरण

तुलना विधियाँ

  1. ED2RB: सीखने योग्य भुजा गारंटी वाला एल्गोरिदम
  2. LimitedAdvice: प्रति-दौर बहु-भुजा अद्यतन को संभालने में सक्षम विशेषज्ञ एल्गोरिदम

कार्यान्वयन विवरण

  • अद्यतन सीमा: M∈{1,2,3}
  • पुनरावृत्ति संख्या: औसत के लिए 30 स्वतंत्र चलन
  • आत्मविश्वास अंतराल: ±0.5 मानक विचलन दिखाता है
  • हाइपरपैरामीटर ट्यूनिंग: ED2RB अन्वेषण पैरामीटर c=0.1, M-FLCB सांद्रता पद स्केलिंग 0.3

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

मुख्य परिणाम

  1. अभिसरण प्रदर्शन: M-LCB उप-रैखिक पश्चाताप प्राप्त करता है, आधारभूत विधियों के साथ प्रतिस्पर्धी
  2. विशेषज्ञ पहचान: सर्वोत्तम विशेषज्ञ (k=9) की सफलतापूर्वक पहचान करता है
  3. बजट दक्षता: मुख्य रूप से अद्यतन को उच्च-प्रदर्शन विशेषज्ञों को आवंटित करता है, जबकि LimitedAdvice अधिक समान रूप से आवंटित करता है

सैद्धांतिक परिणाम

ऊपरी सीमा प्रमेय

प्रमेय 2: α,δ∈(0,1) सेट करें, मान लें कि प्रत्येक विशेषज्ञ k को Uₖ(t,δ)=O(t^α c(δ)) को संतुष्ट करता है, तो कम से कम 1-δ की संभावना के साथ, एल्गोरिदम 1 का पश्चाताप सभी T≥1 के लिए सीमित है:

Reg(T) = O(√(KT/M)log(KT/δ) + (K/M)^(1-α)T^α c(δ))

निम्न सीमा प्रमेय

प्रमेय 1: स्थिरांक c₁,c₂>0 मौजूद हैं, जैसे कि किसी भी शिक्षण एल्गोरिदम और मेटा-प्रोग्राम के लिए:

sup EReg(T) ≥ c₁√(KT/M) + c₂T^α(K/M)^(1-α)

यह दर्शाता है कि M-LCB लॉगरिदमिक कारकों के भीतर इष्टतम है।

संबंधित कार्य

स्व-शिक्षण विशेषज्ञ (भुजाएं)

  • 6: MAB सेटिंग में स्व-शिक्षण भुजाएं पेश करता है, प्रत्येक भुजा एक पैरामीट्रिक फ़ंक्शन है, पैरामीटर चुने जाने के बाद अद्यतन होते हैं

मेटा-स्तर मॉडल चयन

  • CORRAL8: महत्व भार प्रतिक्रिया के माध्यम से लॉग-बाधा ऑनलाइन दर्पण वंश का उपयोग करके डाकू एल्गोरिदम पूल प्रबंधित करता है
  • गतिशील संतुलन9: ज्ञात पश्चाताप दर अभिव्यक्तियों के आधार पर मेटा-एल्गोरिदम, प्रत्येक दौर में केवल एक शिक्षार्थी को अद्यतन करता है
  • 10: प्रत्येक शिक्षार्थी गुणांक ऑनलाइन अनुमान लगाता है, स्टोकेस्टिक डाकू के लिए उच्च-संभावना डेटा-निर्भर गारंटी प्राप्त करता है

बहु-भुजा अद्यतन के साथ MAB

  • सीमित सलाह12: अधिकतम M भुजाओं को क्वेरी करता है, Õ(√(KT logK/M)) पश्चाताप सीमा प्राप्त करता है
  • 13: minimax इष्टतम पश्चाताप Õ(max{√(KT/M), √(T logK)})

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

  1. प्रति-दौर बजट बाधा के तहत कई अनुकूली विशेषज्ञों को एक साथ प्रशिक्षित करने के लिए पहली बार पश्चाताप गारंटी स्थापित करता है
  2. M-LCB एल्गोरिदम लॉगरिदमिक कारकों के भीतर minimax इष्टतम है
  3. रूपरेखा ऑनलाइन अनुकूलन और स्टोकेस्टिक डाकू सेटिंग को एकीकृत करती है

सीमाएं

  1. ज्ञात आत्मविश्वास स्केलिंग: विश्लेषण मानता है कि आत्मविश्वास स्केलिंग फ़ंक्शन c(δ) ज्ञात है
  2. सीमित नुकसान धारणा: मुख्य रूप से सीमित नुकसान मामले पर केंद्रित है
  3. स्टोकेस्टिक सेटिंग: मुख्य रूप से स्टोकेस्टिक वातावरण में विश्लेषण, विरोधी सेटिंग को आगे के अनुसंधान की आवश्यकता है

भविष्य की दिशाएं

  1. अज्ञात c(δ) मामला: Pacchiano आदि11 की विधि जैसे हैंडलिंग
  2. अतिरिक्त अवलोकन विस्तार: सीमित सलाह और बहु-खेल डाकू तक विस्तार
  3. संदर्भ शासन: विशेषज्ञों के आधार पर अवलोकन विशेषताओं के विशेषज्ञता के मामले तक विस्तार

गहन मूल्यांकन

शक्तियाँ

  1. महत्वपूर्ण सैद्धांतिक योगदान: बजट बाधा के तहत बहु-विशेषज्ञ शिक्षा में पहली बार सैद्धांतिक गारंटी
  2. सुरुचिपूर्ण एल्गोरिदम डिजाइन: आत्मविश्वास सीमाएं सीधे नुकसान से निर्मित, कम्प्यूटेशनल रूप से कुशल
  3. मजबूत रूपरेखा सामान्यता: विभिन्न विशेषज्ञ प्रकारों (पैरामीट्रिक मॉडल, डाकू एल्गोरिदम आदि) के लिए लागू
  4. कठोर सैद्धांतिक विश्लेषण: मिलान ऊपरी और निचली सीमाएं प्रदान करता है, एल्गोरिदम इष्टतमता साबित करता है

कमियाँ

  1. सीमित प्रायोगिक सत्यापन: मुख्य रूप से सिंथेटिक प्रयोग, वास्तविक अनुप्रयोग परिदृश्य सत्यापन की कमी
  2. मजबूत धारणा शर्तें: विशेषज्ञ पश्चाताप सीमा रूप को जानने की आवश्यकता है
  3. स्थिरांक कारक विश्लेषण: सैद्धांतिक परिणामों में स्थिरांक बड़े हो सकते हैं, वास्तविक प्रदर्शन सत्यापन की आवश्यकता है

प्रभाव

  1. उच्च सैद्धांतिक मूल्य: बजट बाधा के तहत विशेषज्ञ शिक्षा के लिए सैद्धांतिक आधार प्रदान करता है
  2. बड़ी व्यावहारिक क्षमता: अनुशंसा प्रणाली, वित्तीय व्यापार आदि कई क्षेत्रों में लागू
  3. मजबूत विस्तारशीलता: रूपरेखा अधिक जटिल शिक्षण परिदृश्यों तक विस्तारित हो सकती है

लागू परिदृश्य

  1. ऑनलाइन मॉडल चयन: स्ट्रीम डेटा वातावरण में मॉडल गतिशील चयन
  2. बहु-रणनीति प्रणाली: वित्तीय व्यापार, विज्ञापन प्लेसमेंट आदि जहाँ रणनीति स्विचिंग की आवश्यकता है
  3. संसाधन-सीमित शिक्षा: कम्प्यूटेशनल संसाधन सीमित होने पर बहु-मॉडल समन्वय

संदर्भ

यह पेपर बहु-भुजा डाकू, ऑनलाइन शिक्षा, विशेषज्ञ एल्गोरिदम आदि क्षेत्रों के महत्वपूर्ण साहित्य का हवाला देता है, विशेष रूप से:

  • Auer आदि के शास्त्रीय UCB एल्गोरिदम1
  • Cesa-Bianchi और Lugosi का विशेषज्ञ एल्गोरिदम सिद्धांत4
  • Hazan का ऑनलाइन उत्तल अनुकूलन5
  • CORRAL आदि आधुनिक मेटा-शिक्षा एल्गोरिदम8

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