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-প্রকার অ্যালগরিদম

মৌলিক তথ্য

  • পেপার আইডি: 2510.22654
  • শিরোনাম: UCB-প্রকার অ্যালগরিদম বাজেট-সীমাবদ্ধ বিশেষজ্ঞ শিক্ষার জন্য
  • লেখক: Ilgam Latypov, Alexandra Suvorikova, Alexey Kroshnin, Alexander Gasnikov, Yuriy Dorn
  • শ্রেণীবিভাগ: cs.LG (যন্ত্র শিক্ষা), cs.MA (বহু-এজেন্ট সিস্টেম)
  • প্রকাশনার সময়: ২৮ অক্টোবর, ২০২৫ (প্রাক-প্রকাশনা)
  • পেপার লিঙ্ক: 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: মিনিম্যাক্স সর্বোত্তম অনুশোচনা Õ(max{√(KT/M), √(T logK)})

উপসংহার এবং আলোচনা

প্রধান উপসংহার

  1. প্রতি-রাউন্ড বাজেট সীমাবদ্ধতার অধীনে একাধিক অভিযোজিত বিশেষজ্ঞের সমসাময়িক প্রশিক্ষণের জন্য প্রথম অনুশোচনা গ্যারান্টি প্রতিষ্ঠা করে
  2. M-LCB অ্যালগরিদম লগারিদমিক ফ্যাক্টরের মধ্যে মিনিম্যাক্স সর্বোত্তম অর্জন করে
  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

সামগ্রিক মূল্যায়ন: এটি একটি উচ্চ-মানের তাত্ত্বিক নিবন্ধ যা বাজেট সীমাবদ্ধতার অধীনে বিশেষজ্ঞ শিক্ষায় উল্লেখযোগ্য অবদান রাখে, যা এর আগে গবেষণা করা হয়েছে কিন্তু অপর্যাপ্ত। অ্যালগরিদম ডিজাইন চতুর, তাত্ত্বিক বিশ্লেষণ কঠোর এবং এই ক্ষেত্রের আরও উন্নয়নের জন্য একটি শক্তিশালী ভিত্তি স্থাপন করে।