論文の概要: UCB-type Algorithm for Budget-Constrained Expert Learning
- arxiv url: http://arxiv.org/abs/2510.22654v1
- Date: Sun, 26 Oct 2025 12:36:17 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-28 17:41:21.980336
- Title: UCB-type Algorithm for Budget-Constrained Expert Learning
- Title（参考訳）: 予算制約付きエキスパート学習のためのUPB型アルゴリズム
- Authors: Ilgam Latypov, Alexandra Suvorikova, Alexey Kroshnin, Alexander Gasnikov, Yuriy Dorn,
- Abstract要約: algnameM-LCBはUCBスタイルのメタアルゴリズムであり、幻想的後悔の保証を提供する
我々は、AlgnameM-LCBが、限られたリソースの下で、ステートフルで自己学習の専門家をコーディネートする、より現実的なシナリオまで、古典的な帯域幅パラダイムをどのように拡張しているかを示す。
- 参考スコア（独自算出の注目度）: 71.67657715154034
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: 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^\alpha)$, then \algname{M-LCB} ensures overall regret bounded by $\tilde O\!\Bigl(\sqrt{\tfrac{KT}{M}} \;+\; (K/M)^{1-\alpha}\,T^\alpha\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.
- Abstract（参考訳）: 現代の多くのアプリケーションにおいて、システムはオンラインで訓練された適応学習アルゴリズムを動的に選択する必要がある。
例えば、ストリーミング環境でのモデル選択、金融におけるトレーディング戦略の切り替え、複数のコンテキスト的バンディットや強化学習エージェントのオーケストレーションなどだ。
各ラウンドでは、学習者は予測を行うために、適応的な専門家のうち1人の予測者を選ばなければならない。
本稿では,この問題をemph{stochastic setting} で解決し,計算効率のよい UCB 形式のメタアルゴリズムである \algname{M-LCB} を導入する。
その信頼区間は、実現された損失から直接構築され、追加の最適化を必要とせず、基礎となる専門家の収束特性をシームレスに反映する。
各専門家が内部後悔$\tilde O(T^\alpha)$を達成すれば、 \algname{M-LCB} は全体の後悔を$\tilde O\!
\Bigl(\sqrt{\tfrac{KT}{M}} \;+\; (K/M)^{1-\alpha}\,T^\alpha\Bigr)$
我々の知る限り、これは、複数の適応的専門家が全体予算の制約の下で同時に訓練されるときに、後悔の保証を確立する最初の結果です。
フレームワークを2つの代表的なケースで説明します。
一 確率的損失を伴うオンラインで訓練されたパラメトリックモデル、及び
(二)多武装の盗賊アルゴリズムを自称する専門家。
これらの例は、‘algname{M-LCB} が古典的バンディットパラダイムを、限られたリソースの下でステートフルで自己学習の専門家をコーディネートするより現実的なシナリオにどのように拡張するかを強調している。
関連論文リスト
- Effective Policy Learning for Multi-Agent Online Coordination Beyond Submodular Objectives [64.16056378603875]
マルチエージェントオンライン協調問題に対する2つのポリシー学習アルゴリズムを提案する。
1つめの textttMA-SPL は MA-OC 問題に対して最適な$(fracce)$-approximation を達成することができる。
第2のオンラインアルゴリズムである textttMA-MPL は同じ近似比を同時に維持できる。
論文 参考訳（メタデータ） (2025-09-26T17:16:34Z) - Why Ask One When You Can Ask $k$? Learning-to-Defer to the Top-$k$ Experts [6.792743621449621]
我々は、Top-k$ Learning-to-Deferの最初のフレームワークを紹介します。
クエリを$k$のコスト効率の高いエンティティに割り当てる。
また、クエリ毎に最適な専門家数を学ぶ適応型変種であるTop-$k(x)$ Learning-to-Deferを提案する。
論文 参考訳（メタデータ） (2025-04-17T14:50:40Z) - Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
本稿では,Banditを用いたオンライン最適化に適したフェデレーション学習フレームワークを提案する。
この設定では、エージェントのアームサブセットは、個々のアーム情報にアクセスせずにこれらのサブセットに対するノイズの多い報酬を観察し、特定の間隔で協力して情報を共有することができる。
論文 参考訳（メタデータ） (2024-05-09T17:40:09Z) - No-Regret Online Prediction with Strategic Experts [16.54912614895861]
オンラインバイナリ予測の一般化をエキスパートアドバイスフレームワークを用いて研究し、各ラウンドで、学習者は、Kドルの専門家のプールからmgeq 1ドルの専門家を選ぶことができる。
我々は、専門家が戦略的に行動し、彼らの信念を誤報することでアルゴリズムの予測への影響を最大化することを目的とした設定に焦点を当てる。
目標は,次の2つの要件を満たすアルゴリズムを設計することです。 1) $textitIncentive-compatible$: 専門家に信念を真実に報告させるインセンティブ,2) $textitNo-regret$: Achieve。
論文 参考訳（メタデータ） (2023-05-24T16:43:21Z) - Private Online Prediction from Experts: Separations and Faster Rates [74.52487417350221]
専門家によるオンライン予測は機械学習の基本的な問題であり、いくつかの研究がプライバシーの制約の下でこの問題を研究している。
本研究では,非適応的敵に対する最良な既存アルゴリズムの残差を克服する新たなアルゴリズムを提案し,解析する。
論文 参考訳（メタデータ） (2022-10-24T18:40:19Z) - When are Local Queries Useful for Robust Learning? [25.832511407411637]
本研究では,学習者が局所的なクエリを用いてより多くのパワーを与えられる学習モデルについて検討する。
我々は、ロバストな経験的リスク最小化を行う最初の分布自由アルゴリズムを与える。
我々は、0,1n$でハーフスペースに対してロバストな学習アルゴリズムを与え、その後、精度に縛られた敵に対して$mathbbRn$でハーフスペースに対してロバスト性を保証する。
論文 参考訳（メタデータ） (2022-10-12T11:04:22Z) - Trading Off Resource Budgets for Improved Regret Bounds [6.85316573653194]
対戦型オンライン学習問題に対するFPML(Follow the Perturbed Multiple Leaders)と呼ばれるアルゴリズムを提案する。
また, FPML は, 所要時間で $mathcalO(Tfrac1B+1ln(N)fracBB+1)$ となることを示す。
我々はFPMLがより強力なオラクルを必要とする線形プログラミングの新しいアルゴリズムにどのように導くかを示す。
論文 参考訳（メタデータ） (2022-10-11T21:13:48Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。