論文の概要: Constrained Pareto Set Identification with Bandit Feedback
- arxiv url: http://arxiv.org/abs/2506.08127v1
- Date: Mon, 09 Jun 2025 18:29:28 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-11 15:11:40.368635
- Title: Constrained Pareto Set Identification with Bandit Feedback
- Title（参考訳）: 帯域フィードバックを用いた制約付きパレートセット同定
- Authors: Cyrille Kone, Emilie Kaufmann, Laura Richert,
- Abstract要約: 意味不明の$Kの武器が与えられた場合、平均が他の腕よりも一様でない腕のセットを特定することが目的である。
我々は固定信頼度同定に重点を置いており、レースのようなアルゴリズムを著しく上回るアルゴリズムを導入している。
- 参考スコア（独自算出の注目度）: 10.967572582187014
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we address the problem of identifying the Pareto Set under feasibility constraints in a multivariate bandit setting. Specifically, given a $K$-armed bandit with unknown means $\mu_1, \dots, \mu_K \in \mathbb{R}^d$, the goal is to identify the set of arms whose mean is not uniformly worse than that of another arm (i.e., not smaller for all objectives), while satisfying some known set of linear constraints, expressing, for example, some minimal performance on each objective. Our focus lies in fixed-confidence identification, for which we introduce an algorithm that significantly outperforms racing-like algorithms and the intuitive two-stage approach that first identifies feasible arms and then their Pareto Set. We further prove an information-theoretic lower bound on the sample complexity of any algorithm for constrained Pareto Set identification, showing that the sample complexity of our approach is near-optimal. Our theoretical results are supported by an extensive empirical evaluation on a series of benchmarks.
- Abstract（参考訳）: 本稿では,多変量帯域設定における実現可能性制約の下でのパレート集合の同定の問題に対処する。
具体的には、未知の手段を持つ$K$武器の盗賊が$\mu_1, \dots, \mu_K \in \mathbb{R}^d$と与えられた場合、目標は、例えば各目的に対して最小限のパフォーマンスを満足しながら、他の目的よりも一様に劣る(すなわち、全ての目的に対して小さくない)腕の集合を特定することである。
そこでは、レースのようなアルゴリズムを著しく上回るアルゴリズムと、実現可能なアームとパレートセットを最初に識別する直感的な2段階アプローチを導入します。
さらに、制約されたパレート集合の同定のための任意のアルゴリズムのサンプル複雑性に対する情報理論的な下限を証明し、我々のアプローチのサンプル複雑性がほぼ最適であることを示す。
我々の理論結果は、一連のベンチマークにおける広範な経験的評価によって支持される。
関連論文リスト
- Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
本稿では,誤差確率の指数的減衰を保証し,最適な腕識別のための新しいアルゴリズムを提案する。
我々は,複雑性のレベルが異なる様々な問題インスタンスに対する包括的経験的評価を通じて,アルゴリズムの有効性を検証する。
論文 参考訳（メタデータ） (2025-06-03T02:56:26Z) - Best Arm Identification with Minimal Regret [55.831935724659175]
最高の腕識別問題 優雅にアマルガメートは、最小化とBAIを後悔している。
エージェントの目標は、所定の信頼度で最高の腕を特定することである。
二重KL-UCBアルゴリズムは、信頼度がゼロになる傾向があるため、最適性を達成する。
論文 参考訳（メタデータ） (2024-09-27T16:46:02Z) - Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳（メタデータ） (2023-12-19T13:17:43Z) - Bandit Pareto Set Identification: the Fixed Budget Setting [10.967572582187014]
マルチアームバンディットモデルにおける純粋探索問題について検討する。
目的は、平均値が他の分布よりも均一に悪くない分布を特定することである。
論文 参考訳（メタデータ） (2023-11-07T13:43:18Z) - Mean-based Best Arm Identification in Stochastic Bandits under Reward
Contamination [80.53485617514707]
本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。
具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
論文 参考訳（メタデータ） (2021-11-14T21:49:58Z) - An Empirical Process Approach to the Union Bound: Practical Algorithms
for Combinatorial and Linear Bandits [34.06611065493047]
本稿では、信頼度と予算設定の固定化において、純探索線形帯域問題に対する近似アルゴリズムを提案する。
サンプルの複雑性がインスタンスの幾何でスケールし、アームの数に縛られた明示的な結合を避けるアルゴリズムを提供する。
また,固定予算設定における線形帯域幅に対する最初のアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-21T00:56:33Z) - Quantile Multi-Armed Bandits: Optimal Best-Arm Identification and a
Differentially Private Scheme [16.1694012177079]
我々は,多腕バンディットにおける最高の武器識別問題,潜在的に私的な報酬について検討する。
ゴールは、固定された所定のレベルで、最も高い定量値を持つ腕を特定することである。
このアルゴリズムは$delta$-PACであり,サンプルの複雑さを特徴付ける。
論文 参考訳（メタデータ） (2020-06-11T20:23:43Z) - The Simulator: Understanding Adaptive Sampling in the
Moderate-Confidence Regime [52.38455827779212]
エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。
適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。
我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
論文 参考訳（メタデータ） (2017-02-16T23:42:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。