論文の概要: Bandit Pareto Set Identification: the Fixed Budget Setting
- arxiv url: http://arxiv.org/abs/2311.03992v1
- Date: Tue, 7 Nov 2023 13:43:18 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-08 15:22:29.312922
- Title: Bandit Pareto Set Identification: the Fixed Budget Setting
- Title(参考訳): bandit pareto set identification: the fixed budget setting
- Authors: Cyrille Kone, Emilie Kaufmann, Laura Richert
- Abstract要約: マルチアームバンディットモデルにおける純粋探索問題について検討する。
目的は、平均値が他の分布よりも均一に悪くない分布を特定することである。
- 参考スコア(独自算出の注目度): 12.326452468513228
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: We study a multi-objective pure exploration problem in a multi-armed bandit
model. Each arm is associated to an unknown multi-variate distribution and the
goal is to identify the distributions whose mean is not uniformly worse than
that of another distribution: the Pareto optimal set. We propose and analyze
the first algorithms for the \emph{fixed budget} Pareto Set Identification
task. We propose Empirical Gap Elimination, a family of algorithms combining a
careful estimation of the ``hardness to classify'' each arm in or out of the
Pareto set with a generic elimination scheme. We prove that two particular
instances, EGE-SR and EGE-SH, have a probability of error that decays
exponentially fast with the budget, with an exponent supported by an
information theoretic lower-bound. We complement these findings with an
empirical study using real-world and synthetic datasets, which showcase the
good performance of our algorithms.
- Abstract(参考訳): マルチアームバンディットモデルにおける多目的純粋探索問題について検討する。
各アームは未知の多変量分布に関連付けられており、その目的は平均が他の分布よりも一様でない分布、すなわちパレート最適集合を特定することである。
我々は, \emph{fixed budget} pareto set identificationタスクのための最初のアルゴリズムを提案し,解析する。
本稿では,Pareto セットの内外における '`hardness to classification'' の各アームの注意深い推定と,汎用的な除去手法を組み合わせたアルゴリズムである Empirical Gap Elimination を提案する。
EGE-SR と EGE-SH の2つの特定の例は,情報理論的下界が支持する指数で,予算で指数関数的に高速に減衰する誤差の確率を持つことを示す。
これらの知見を実世界および合成データセットを用いた経験的研究で補完し,アルゴリズムの優れた性能を示す。
関連論文リスト
- Continuous K-Max Bandits [54.21533414838677]
我々は、連続的な結果分布と弱い値-インデックスフィードバックを持つ、$K$-Maxのマルチアームバンディット問題について検討する。
この設定は、レコメンデーションシステム、分散コンピューティング、サーバスケジューリングなどにおいて重要なアプリケーションをキャプチャします。
我々の重要な貢献は、適応的な離散化とバイアス補正された信頼境界を組み合わせた計算効率の良いアルゴリズムDCK-UCBである。
論文 参考訳(メタデータ) (2025-02-19T06:37:37Z) - Optimal Multi-Objective Best Arm Identification with Fixed Confidence [62.36929749450298]
我々は、各アームが選択時にM$Dのベクトル報酬を得られる多腕バンディット設定を考える。
最終的なゴールは、最も短い(予想される)時間において、エラーの確率の上限に従属する全ての目的の最良のアームを特定することである。
本稿では,各ステップでアームをサンプリングするために,エミュロゲート比例という新しいアイデアを用いたアルゴリズムを提案し,各ステップにおける最大最小最適化問題を解く必要をなくした。
論文 参考訳(メタデータ) (2025-01-23T12:28:09Z) - Representative Arm Identification: A fixed confidence approach to identify cluster representatives [7.459521930846415]
マルチアームバンディット(MAB)フレームワークにおける代表腕識別問題について検討する。
RAI問題は、最高の腕や、上位の$K$から$M$を識別するなど、いくつかのよく研究されたMAB問題としてカバーされている。
本稿では,信頼区間の概念に基づく2つのアルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-08-26T11:47:52Z) - Pure Exploration for Constrained Best Mixed Arm Identification with a Fixed Budget [6.22018632187078]
固定予算の制約付きベスト・ミックスアーム識別(CBMAI)問題を導入する。
目標は、与えられた学習予算$N$で、期待されるコストの制約によって期待される報酬を最大化する最高の混合アームを見つけることである。
我々は、(最良の混合アームの支持の)誤識別に関する理論上の上限を提供し、予算$N$で指数関数的に崩壊することを示す。
論文 参考訳(メタデータ) (2024-05-23T22:35:11Z) - Scalable Decentralized Algorithms for Online Personalized Mean Estimation [12.002609934938224]
本研究は,各エージェントが実数値分布からサンプルを収集し,その平均値を推定する,オーバーアーキシング問題の簡易版に焦点を当てた。
1つは信念の伝播からインスピレーションを得ており、もう1つはコンセンサスに基づくアプローチを採用している。
論文 参考訳(メタデータ) (2024-02-20T08:30:46Z) - Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳(メタデータ) (2023-12-19T13:17:43Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳(メタデータ) (2023-12-13T11:08:25Z) - A General Recipe for the Analysis of Randomized Multi-Armed Bandit Algorithms [14.33758865948252]
我々は2つの有名なバンディットアルゴリズム、Minimum Empirical Divergence (MED)とThompson Sampling (TS)を再検討する。
MEDがこれらのモデルすべてに最適であることを示すとともに、最適性がすでに知られているTSアルゴリズムの簡単な後悔解析も提供する。
論文 参考訳(メタデータ) (2023-03-10T16:43:48Z) - A Unified Framework for Multi-distribution Density Ratio Estimation [101.67420298343512]
バイナリ密度比推定(DRE)は多くの最先端の機械学習アルゴリズムの基礎を提供する。
ブレグマン最小化の発散の観点から一般的な枠組みを開発する。
我々のフレームワークはバイナリDREでそれらのフレームワークを厳格に一般化する手法に導かれることを示す。
論文 参考訳(メタデータ) (2021-12-07T01:23:20Z) - Mean-based Best Arm Identification in Stochastic Bandits under Reward
Contamination [80.53485617514707]
本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。
具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
論文 参考訳(メタデータ) (2021-11-14T21:49:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。