論文の概要: Top Two Algorithms Revisited

• arxiv url: http://arxiv.org/abs/2206.05979v1
• Date: Mon, 13 Jun 2022 09:03:24 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-14 23:28:24.391566
• Title: Top Two Algorithms Revisited
• Title（参考訳）: トップ2のアルゴリズムが再検討
• Authors: Marc Jourdan, R\'emy Degenne, Dorian Baudry, Rianne de Heide and Emilie Kaufmann
• Abstract要約: トップ2のアルゴリズムは、トンプソンサンプリングの多腕バンディットモデルにおける最高の腕識別への適応として現れた。 本稿では,トップ2手法の一般解析を行い,リーダーの望ましい特性,挑戦者,および腕の(おそらくは非パラメトリックな)分布を同定する。 提案手法は,トンプソンサンプリングから受け継いだリーダの選択に使用されるサンプリングステップを,他の選択に置き換えることができることを示す。
• 参考スコア（独自算出の注目度）: 14.783452541904365
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Top Two algorithms arose as an adaptation of Thompson sampling to best arm identification in multi-armed bandit models (Russo, 2016), for parametric families of arms. They select the next arm to sample from by randomizing among two candidate arms, a leader and a challenger. Despite their good empirical performance, theoretical guarantees for fixed-confidence best arm identification have only been obtained when the arms are Gaussian with known variances. In this paper, we provide a general analysis of Top Two methods, which identifies desirable properties of the leader, the challenger, and the (possibly non-parametric) distributions of the arms. As a result, we obtain theoretically supported Top Two algorithms for best arm identification with bounded distributions. Our proof method demonstrates in particular that the sampling step used to select the leader inherited from Thompson sampling can be replaced by other choices, like selecting the empirical best arm.
• Abstract（参考訳）: トップ2のアルゴリズムは、トンプソンサンプリングを多腕バンディットモデル(Russo, 2016)の最も優れた腕識別に適応させたことで生まれた。 彼らは2つの候補の腕、リーダーと挑戦者のランダム化によって次の腕を選択します。 その優れた経験的性能にもかかわらず、固定信頼の最良の腕の識別に関する理論的保証は、既知のばらつきを持つガウス的腕のときのみ得られる。 本稿では, リーダー, 挑戦者, および(多分非パラメトリックな)アーム分布の望ましい特性を識別する, 上位2つの方法の一般解析を行う。 その結果,有界分布を持つ最適アーム識別のための理論的に支持されたトップ2アルゴリズムが得られた。 提案手法は,トンプソンサンプリングから受け継いだリーダの選択に使用されるサンプリングステップが,経験的ベストアームの選択など他の選択に置き換えられることを示す。

関連論文リスト

• Neural Dueling Bandits [58.90189511247936]
  ニューラルネットワークを用いて、予め選択した腕の好みフィードバックを用いて報酬関数を推定する。 次に、理論結果を二項フィードバックによる文脈的帯域幅問題に拡張し、それはそれ自体は自明な寄与ではない。
  論文  参考訳（メタデータ） (2024-07-24T09:23:22Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Eliciting Kemeny Rankings [6.971011179091351]
  ケメニーランキングの近似境界は、推定勝利確率に対する信頼区間に依存する。 我々は、ルックアヘッドを用いた複数の適応サンプリング手法を定式化し、どれだけの信頼区間を厳格化できるかを推定する。
  論文  参考訳（メタデータ） (2023-12-18T19:14:42Z)
• Worst-Case Optimal Multi-Armed Gaussian Best Arm Identification with a Fixed Budget [10.470114319701576]
  本研究は、腕を最も期待できる結果に識別する実験的な設計問題について検討する。 分散が知られているという仮定のもと、一般化ネマン割当(GNA)-経験的ベストアーム(EBA)戦略を提案する。 GNA-EBA戦略は、誤同定の確率が下界と一致するという意味で無限に最適であることを示す。
  論文  参考訳（メタデータ） (2023-10-30T17:52:46Z)
• Pure Exploration under Mediators' Feedback [63.56002444692792]
  マルチアームバンディット(Multi-armed bandits)は、各インタラクションステップにおいて、学習者が腕を選択し、報酬を観察する、シーケンシャルな意思決定フレームワークである。 本稿では,学習者が仲介者の集合にアクセスできるシナリオについて考察する。 本稿では,学習者には仲介者の方針が知られていると仮定して,最適な腕を発見するための逐次的意思決定戦略を提案する。
  論文  参考訳（メタデータ） (2023-08-29T18:18:21Z)
• Covariance Adaptive Best Arm Identification [0.0]
  ゴールは、腕のプル数を最小化しながら、最低でも1-$delta$の確率で腕を最も平均的な報酬で識別することである。 武器を頼りにでき、報酬を同時にサンプリングできる、より柔軟なシナリオを提案する。 この枠組みは、患者と薬物の類似性から根底にある相関関係が示唆される臨床試験など、様々な応用に関係している。
  論文  参考訳（メタデータ） (2023-06-05T06:57:09Z)
• 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)
• Quantile Bandits for Best Arms Identification [10.294977861990203]
  多腕バンディットにおける最適な腕識別タスクの変種について検討する。 リスクと逆の意思決定の問題によって動機づけられた当社の目標は、固定予算内で最高の$tau$-quantileの値を持つ、$m$の武器のセットを特定することです。
  論文  参考訳（メタデータ） (2020-10-22T09:58:54Z)
• Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
  サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。 既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
  論文  参考訳（メタデータ） (2020-06-29T14:25:51Z)

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

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