論文の概要: Functional multi-armed bandit and the best function identification problems

• arxiv url: http://arxiv.org/abs/2503.00509v1
• Date: Sat, 01 Mar 2025 14:28:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-05 19:26:42.547053
• Title: Functional multi-armed bandit and the best function identification problems
• Title（参考訳）: 機能的マルチアームバンディットと最適機能同定問題
• Authors: Yuriy Dorn, Aleksandr Katrutsa, Ilgam Latypov, Anastasiia Soboleva,
• Abstract要約: 本稿では,機能的マルチアームバンディット問題 (FMAB) と機能同定問題の2つの新しいクラスを提案する。 これらの問題クラスは、競争力のあるLLMトレーニングのような現実世界の問題をモデリングするのに驚くほど適しています。 本稿では, 既知収束率を持つ非線形最適化アルゴリズムに基づく, UCB型アルゴリズム, すなわちF-LCBアルゴリズムを構築するための新しい削減手法を提案する。
• 参考スコア（独自算出の注目度）: 42.50469483443937
• License:
• Abstract: Bandit optimization usually refers to the class of online optimization problems with limited feedback, namely, a decision maker uses only the objective value at the current point to make a new decision and does not have access to the gradient of the objective function. While this name accurately captures the limitation in feedback, it is somehow misleading since it does not have any connection with the multi-armed bandits (MAB) problem class. We propose two new classes of problems: the functional multi-armed bandit problem (FMAB) and the best function identification problem. They are modifications of a multi-armed bandit problem and the best arm identification problem, respectively, where each arm represents an unknown black-box function. These problem classes are a surprisingly good fit for modeling real-world problems such as competitive LLM training. To solve the problems from these classes, we propose a new reduction scheme to construct UCB-type algorithms, namely, the F-LCB algorithm, based on algorithms for nonlinear optimization with known convergence rates. We provide the regret upper bounds for this reduction scheme based on the base algorithms' convergence rates. We add numerical experiments that demonstrate the performance of the proposed scheme.
• Abstract（参考訳）: 帯域最適化(Bandit optimization)は通常、限られたフィードバックを持つオンライン最適化問題のクラスを指す。すなわち、意思決定者は現在の時点の目的値のみを使用して新しい決定を行い、目的関数の勾配にアクセスできない。 この名前はフィードバックの制限を正確に捉えているが、マルチアーム・バンディット(MAB)問題クラスとは無関係であるため、何らかの誤解を招く。 本稿では,機能的マルチアームバンディット問題 (FMAB) と機能同定問題の2つの新しいクラスを提案する。 これらは、各腕が未知のブラックボックス関数を表す、多腕バンディット問題と最高の腕識別問題の修正である。 これらの問題クラスは、競争力のあるLLMトレーニングのような現実世界の問題をモデリングするのに驚くほど適しています。 これらのクラスからの問題を解くため、既知の収束率を持つ非線形最適化アルゴリズムに基づいて、UCB型アルゴリズム、すなわちF-LCBアルゴリズムを構築するための新しい削減手法を提案する。 本稿では, 基本アルゴリズムの収束率に基づいて, この還元方式について, 後悔すべき上限を与える。 提案手法の性能を示す数値実験を加える。

関連論文リスト

• Fixed-Budget Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [65.268245109828]
  このアルゴリズムは,アクションクラスのサイズが指数関数的に大きい場合でも,最良のアクションを識別できる最初のアルゴリズムである。 CSAアルゴリズムの誤差確率の上限は指数の対数係数までの下界と一致することを示す。 提案手法を従来手法と実験的に比較し,アルゴリズムの性能が向上したことを示す。
  論文  参考訳（メタデータ） (2023-10-24T09:47:32Z)
• Online Clustering of Bandits with Misspecified User Models [42.56440072468658]
  コンテキスト線形バンディット(Contextual linear bandit)は、与えられた腕の特徴を学習エージェントが各ラウンドで選択し、長期の累積報酬を最大化するオンライン学習問題である。 バンディットのクラスタリング(CB)と呼ばれる一連の研究は、ユーザの好みに対する協調効果を利用しており、古典的な線形バンディットアルゴリズムよりも大幅に改善されている。 本稿では,不特定ユーザモデル (CBMUM) による盗賊のクラスタリングに関する重要な問題を初めて提示する。 モデル誤特定による不正確なユーザの選好推定と誤クラスタリングを両立できる頑健なCBアルゴリズムRCLUMBとRCLUMBを考案した。
  論文  参考訳（メタデータ） (2023-10-04T10:40:50Z)
• A Framework for Adapting Offline Algorithms to Solve Combinatorial Multi-Armed Bandit Problems with Bandit Feedback [27.192028744078282]
  離散オフライン近似アルゴリズムをサブ線形$alpha$-regretに適応するためのフレームワークを提供する。 提案手法は準モジュラー地平線における多種多様な応用に適用できる。
  論文  参考訳（メタデータ） (2023-01-30T23:18:06Z)
• Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability [59.81339109121384]
  我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。 提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
  論文  参考訳（メタデータ） (2021-11-24T07:14:57Z)
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
  この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。 我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。 標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
  論文  参考訳（メタデータ） (2021-07-09T16:04:24Z)
• Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback [51.21673420940346]
  コンビナーシャルバンディットはマルチアームバンディットを一般化し、エージェントが腕のセットを選択し、選択したセットに含まれる各腕の騒々しい報酬を観察します。 我々は, 最善の腕を一定の信頼度で識別する純粋爆発問題と, 応答集合の構造が動作集合の1つと異なるような, より一般的な設定に注目する。 有限多面体に対するプロジェクションフリーオンライン学習アルゴリズムに基づいて、凸的に最適であり、競争力のある経験的性能を持つ最初の計算効率の良いアルゴリズムである。
  論文  参考訳（メタデータ） (2021-01-21T10:35:09Z)
• Upper Confidence Bounds for Combining Stochastic Bandits [52.10197476419621]
  バンディットアルゴリズムを結合する簡単な手法を提案する。 私たちのアプローチは、個々のbanditアルゴリズムのそれぞれを、より高いレベルのn$-armed bandit問題のアームとして扱う"meta-ucb"手順に基づいています。
  論文  参考訳（メタデータ） (2020-12-24T05:36:29Z)
• Multi-armed Bandits with Cost Subsidy [1.6631602844999724]
  本稿では、インテリジェントSMSルーティング問題と広告オーディエンス最適化問題という2つのアプリケーションを提案する。 既存のMABアルゴリズムの素早い一般化は、この問題に対してうまく機能しないことを示す。 また,このアルゴリズムに対して,探索定理の簡単な変種を提示し,ほぼ最適な後悔境界を定めている。
  論文  参考訳（メタデータ） (2020-11-03T05:38:42Z)
• Bandit algorithms to emulate human decision making using probabilistic distortions [20.422725678982726]
  報奨分布に歪んだ確率を持つ2つの多重武装バンディット問題を定式化する。 以上のような後悔の最小化の問題と、マルチアームバンディットのための最高の腕識別フレームワークについて考察する。
  論文  参考訳（メタデータ） (2016-11-30T17:37:51Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。