論文の概要: Locally Optimal Fixed-Budget Best Arm Identification in Two-Armed
Gaussian Bandits with Unknown Variances
- arxiv url: http://arxiv.org/abs/2312.12741v1
- Date: Wed, 20 Dec 2023 03:28:49 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-21 16:48:55.560729
- Title: Locally Optimal Fixed-Budget Best Arm Identification in Two-Armed
Gaussian Bandits with Unknown Variances
- Title（参考訳）: 変種不明の2アーマドガウスバンドにおける局所的最適固定ベストアーム同定
- Authors: Masahiro Kato
- Abstract要約: 本稿では,適応実験における分散を推定し,推定標準偏差の比率でアームを描画する手法を提案する。
以上の結果から,小ギャップ体制を特徴とする最悪のシナリオでは,変動が未知であっても,推定分散を利用する戦略が最適であることが示唆された。
- 参考スコア（独自算出の注目度）: 10.470114319701576
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We address the problem of best arm identification (BAI) with a fixed budget
for two-armed Gaussian bandits. In BAI, given multiple arms, we aim to find the
best arm, an arm with the highest expected reward, through an adaptive
experiment. Kaufmann et al. (2016) develops a lower bound for the probability
of misidentifying the best arm. They also propose a strategy, assuming that the
variances of rewards are known, and show that it is asymptotically optimal in
the sense that its probability of misidentification matches the lower bound as
the budget approaches infinity. However, an asymptotically optimal strategy is
unknown when the variances are unknown. For this open issue, we propose a
strategy that estimates variances during an adaptive experiment and draws arms
with a ratio of the estimated standard deviations. We refer to this strategy as
the Neyman Allocation (NA)-Augmented Inverse Probability weighting (AIPW)
strategy. We then demonstrate that this strategy is asymptotically optimal by
showing that its probability of misidentification matches the lower bound when
the budget approaches infinity, and the gap between the expected rewards of two
arms approaches zero (small-gap regime). Our results suggest that under the
worst-case scenario characterized by the small-gap regime, our strategy, which
employs estimated variance, is asymptotically optimal even when the variances
are unknown.
- Abstract（参考訳）: 両腕のガウスバンドの固定予算によるベストアーム識別(BAI)の問題に対処する。
複数の腕が与えられたBAIでは、適応的な実験を通じて、最高の腕、最も期待される報酬を持つ腕を見つけることを目指している。
Kaufmann et al. (2016) は、最良の腕を誤識別する確率の低い境界を開発する。
また、報酬の分散が知られていると仮定して戦略を提案し、予算が無限に近づくと、その誤認の確率が下限と一致するという意味で漸近的に最適であることを示す。
しかし、漸近的最適戦略は、分散が未知であるときに未知である。
本稿では,適応実験中にばらつきを推定し,推定された標準偏差の比率で腕を引く戦略を提案する。
この戦略をニーマン割当(na)による逆確率重み付け(aipw)戦略と呼ぶ。
次に,この戦略が漸近的最適であることを示すために,予算が無限大に近づくと誤認の確率が下限に一致し,両腕の期待報酬の差がゼロに近づくことを示す。
以上の結果から,小ギャップ体制を特徴とする最悪のシナリオでは,予測分散を用いた我々の戦略は,変動が未知であっても漸近的に最適であることが示唆された。
関連論文リスト
- Adaptive Generalized Neyman Allocation: Local Asymptotic Minimax Optimal Best Arm Identification [10.470114319701576]
本研究は、固定予算ベストアーム識別(BAI)のための局所的ミニマックス最適戦略について検討する。
最強の腕を誤識別する確率の最悪の上限は、小ギャップ体制下での最悪の下限と一致していることを示す。
論文 参考訳（メタデータ） (2024-05-29T17:43:13Z) - Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳（メタデータ） (2023-12-19T13:17:43Z) - Worst-Case Optimal Multi-Armed Gaussian Best Arm Identification with a
Fixed Budget [10.470114319701576]
本研究は、腕を最も期待できる結果に識別する実験的な設計問題について検討する。
分散が知られているという仮定のもと、一般化ネマン割当(GNA)-経験的ベストアーム(EBA)戦略を提案する。
GNA-EBA戦略は、誤同定の確率が下界と一致するという意味で無限に最適であることを示す。
論文 参考訳（メタデータ） (2023-10-30T17:52:46Z) - Optimal Best Arm Identification with Fixed Confidence in Restless Bandits [66.700654953613]
本研究は,有限個の腕を持つレスレス・マルチアーム・バンディット・セッティングにおけるベスト・アーム識別について検討する。
各アームによって生成された離散時間データは、共通の有限状態空間で値を取る同質マルコフ連鎖を形成する。
その結果,あるマルコフ決定過程の長期的挙動の追跡とその状態-行動的訪問比率が,逆および達成可能性境界を解析するための重要な要素であることが示唆された。
論文 参考訳（メタデータ） (2023-10-20T10:04:05Z) - Thompson Exploration with Best Challenger Rule in Best Arm
Identification [66.33448474838342]
本稿では,バンドイットフレームワークにおける固定信頼度最良腕識別問題について検討する。
我々は、トンプソンサンプリングと、ベストチャレンジャールールとして知られる計算効率の良いアプローチを組み合わせた新しいポリシーを提案する。
論文 参考訳（メタデータ） (2023-10-01T01:37:02Z) - Fixed-Budget Best-Arm Identification with Heterogeneous Reward Variances [12.00630538470713]
不均一な報酬分散を伴う固定予算設定におけるベストアーム識別(BAI)の問題について検討する。
本稿では, 既知報酬分散に対するSHVarと未知報酬分散に対するSHAdaVarの2つの分散適応型BAIアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-06-13T05:41:38Z) - 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) - Algorithms for Adaptive Experiments that Trade-off Statistical Analysis
with Reward: Combining Uniform Random Assignment and Reward Maximization [50.725191156128645]
トンプソンサンプリングのようなマルチアームバンディットアルゴリズムは適応的な実験を行うのに利用できる。
統計的解析のための一様ランダム化の利点を組み合わせた2つのアルゴリズムを探索する2つのアーム実験のシミュレーションを提案する。
論文 参考訳（メタデータ） (2021-12-15T22:11:58Z) - Mean-based Best Arm Identification in Stochastic Bandits under Reward
Contamination [80.53485617514707]
本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。
具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
論文 参考訳（メタデータ） (2021-11-14T21:49:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。