論文の概要: Locally Optimal Best Arm Identification with a Fixed Budget
- arxiv url: http://arxiv.org/abs/2310.19788v1
- Date: Mon, 30 Oct 2023 17:52:46 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-01 18:40:53.955105
- Title: Locally Optimal Best Arm Identification with a Fixed Budget
- Title（参考訳）: 予算を固定した局所最適最良腕識別法
- Authors: Masahiro Kato
- Abstract要約: 本研究は,最高の治療用アーム,最も期待される治療用アームを同定する問題について検討する。
我々は, 最適治療アームと準最適治療アームの差がゼロに近づく小ギャップ体制下で, 誤同定の確率の低い境界を開発する。
我々は、Neyman (1934) によって提案された Neyman 割り当ての拡張である Generalized-Neyman-Allocation (GNA)-empirical-best-arm (EBA) 戦略と Bubeck らによって提案された Uniform-EBA 戦略を設計する。
GNA-EBA戦略では、
- 参考スコア（独自算出の注目度）: 10.470114319701576
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This study investigates the problem of identifying the best treatment arm, a
treatment arm with the highest expected outcome. We aim to identify the best
treatment arm with a lower probability of misidentification, which has been
explored under various names across numerous research fields, including
\emph{best arm identification} (BAI) and ordinal optimization. In our
experiments, the number of treatment-allocation rounds is fixed. In each round,
a decision-maker allocates a treatment arm to an experimental unit and observes
a corresponding outcome, which follows a Gaussian distribution with a variance
different among treatment arms. At the end of the experiment, we recommend one
of the treatment arms as an estimate of the best treatment arm based on the
observations. The objective of the decision-maker is to design an experiment
that minimizes the probability of misidentifying the best treatment arm. With
this objective in mind, we develop lower bounds for the probability of
misidentification under the small-gap regime, where the gaps of the expected
outcomes between the best and suboptimal treatment arms approach zero. Then,
assuming that the variances are known, we design the
Generalized-Neyman-Allocation (GNA)-empirical-best-arm (EBA) strategy, which is
an extension of the Neyman allocation proposed by Neyman (1934) and the
Uniform-EBA strategy proposed by Bubeck et al. (2011). For the GNA-EBA
strategy, we show that the strategy is asymptotically optimal because its
probability of misidentification aligns with the lower bounds as the sample
size approaches infinity under the small-gap regime. We refer to such optimal
strategies as locally asymptotic optimal because their performance aligns with
the lower bounds within restricted situations characterized by the small-gap
regime.
- Abstract（参考訳）: 本研究は, 最良治療アーム, 期待結果の高い治療アームの同定に関する課題について検討する。
最良治療アームの同定と誤認の確率の低下を目標とし,様々な研究分野において,<emph{best arm identification} (bai) や順序最適化など様々な名称で検討してきた。
実験では,治療アロケーションラウンドの数を固定した。
各ラウンドにおいて、意思決定者は、処理アームを実験ユニットに割り当て、対応する結果を観察し、処理アーム間のばらつきが異なるガウス分布に従う。
実験の最後には、観察に基づいて最適な治療アームの見積もりとして、治療アームの1つを推奨する。
意思決定者の目標は、最良の治療アームを誤認する可能性を最小化する実験を設計することである。
この目的を念頭に、我々は、最善と準最適治療腕の期待結果のギャップがゼロに近づく小ギャップ体制の下で、誤同定の確率の低い境界を開発する。
そして、この分散が知られていると仮定して、我々は、Neyman (1934) が提案した Neyman 割り当ての拡張である Generalized-Neyman-Allocation (GNA)-empirical-best-arm (EBA) 戦略と Bubeck et al. (2011) が提案した Uniform-EBA 戦略を設計する。
GNA-EBA戦略は, サンプルサイズが小ギャップ体制下で無限に近づくにつれて, 誤同定の確率が下界と一致するため, 漸近的に最適であることを示す。
局所的な漸近的最適戦略は、その性能が小ギャップ体制によって特徴づけられる制限された状況の中で下界と一致しているためである。
関連論文リスト
- Optimal Multi-Objective Best Arm Identification with Fixed Confidence [62.36929749450298]
我々は、各アームが選択時にM$Dのベクトル報酬を得られる多腕バンディット設定を考える。
最終的なゴールは、最も短い(予想される)時間において、エラーの確率の上限に従属する全ての目的の最良のアームを特定することである。
本稿では,各ステップでアームをサンプリングするために,エミュロゲート比例という新しいアイデアを用いたアルゴリズムを提案し,各ステップにおける最大最小最適化問題を解く必要をなくした。
論文 参考訳（メタデータ） (2025-01-23T12:28:09Z) - Minimax Optimal Simple Regret in Two-Armed Best-Arm Identification [10.470114319701576]
簡単な後悔に対して、ネーマン割当の極小極小性を証明した。
局所正規度に局所性制限を課すことなく、最適性が達成できることが示される。
論文 参考訳（メタデータ） (2024-12-23T18:06:20Z) - Locally Optimal Fixed-Budget Best Arm Identification in Two-Armed Gaussian Bandits with Unknown Variances [10.470114319701576]
本稿では,適応実験における分散を推定し,推定標準偏差の比率でアームを描画する手法を提案する。
以上の結果から,小ギャップ体制を特徴とする最悪のシナリオでは,変動が未知であっても,推定分散を利用する戦略が最適であることが示唆された。
論文 参考訳（メタデータ） (2023-12-20T03:28:49Z) - Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳（メタデータ） (2023-12-19T13:17:43Z) - Optimal Best Arm Identification with Fixed Confidence in Restless Bandits [66.700654953613]
本研究は,有限個の腕を持つレスレス・マルチアーム・バンディット・セッティングにおけるベスト・アーム識別について検討する。
各アームによって生成された離散時間データは、共通の有限状態空間で値を取る同質マルコフ連鎖を形成する。
その結果,あるマルコフ決定過程の長期的挙動の追跡とその状態-行動的訪問比率が,逆および達成可能性境界を解析するための重要な要素であることが示唆された。
論文 参考訳（メタデータ） (2023-10-20T10:04:05Z) - Covariance Adaptive Best Arm Identification [0.0]
ゴールは、腕のプル数を最小化しながら、最低でも1-$delta$の確率で腕を最も平均的な報酬で識別することである。
武器を頼りにでき、報酬を同時にサンプリングできる、より柔軟なシナリオを提案する。
この枠組みは、患者と薬物の類似性から根底にある相関関係が示唆される臨床試験など、様々な応用に関係している。
論文 参考訳（メタデータ） (2023-06-05T06:57:09Z) - Asymptotically Optimal Fixed-Budget Best Arm Identification with
Variance-Dependent Bounds [10.915684166086026]
単純後悔を最小化するための固定予算ベストアーム識別(BAI)の問題点について検討する。
この決定は,最善腕と推奨腕の期待結果との違いである,期待された単純後悔に基づいて評価する。
我々は,HIR推定器(ヒラノら,2003年)を用いて最適な腕を推奨する2段階(TS-Hirano-Imbens-Ridder-HIR)戦略を提案する。
論文 参考訳（メタデータ） (2023-02-06T18:27:11Z) - Best Arm Identification in Restless Markov Multi-Armed Bandits [85.55466536537293]
マルチアームバンディット環境における最適な腕を特定することの問題点について検討する。
決定エンティティは、上限誤差確率を条件として、ベストアームのインデックスをできるだけ早く見つけることを希望する。
このポリシーは、$R$に依存する上限を達成し、$Rtoinfty$として単調に増加しないことを示す。
論文 参考訳（メタデータ） (2022-03-29T04:58:04Z) - Optimal Fixed-Budget Best Arm Identification using the Augmented Inverse
Probability Estimator in Two-Armed Gaussian Bandits with Unknown Variances [27.122181278234617]
両腕のガウスバンドにおける固定予算ベストアーム識別問題について検討する。
本稿では,アームドローの目標配置確率を推定し,ランダム化サンプリング(RS)を用いたサンプリングルールを含む戦略を提案する。
提案手法は,サンプルサイズが無限大になり,両腕間のギャップがゼロとなる場合に,不可視的に最適であることを示す。
論文 参考訳（メタデータ） (2022-01-12T13:38:33Z) - Mean-based Best Arm Identification in Stochastic Bandits under Reward
Contamination [80.53485617514707]
本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。
具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
論文 参考訳（メタデータ） (2021-11-14T21:49:58Z) - Towards Minimax Optimal Best Arm Identification in Linear Bandits [95.22854522340938]
固定予算設定における線形包帯における最適な腕識別の問題について検討する。
G-最適設計の特性を活用し、アーム割り当て規則に組み込むことにより、パラメータフリーなアルゴリズムを設計する。
OD-LinBAIの故障確率に関する理論的解析を行った。
論文 参考訳（メタデータ） (2021-05-27T09:19:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。