論文の概要: SPRT-based Efficient Best Arm Identification in Stochastic Bandits

• arxiv url: http://arxiv.org/abs/2207.11158v1
• Date: Fri, 22 Jul 2022 15:54:53 GMT
• ステータス: 処理完了
• システム内更新日: 2022-07-25 12:37:16.900875
• Title: SPRT-based Efficient Best Arm Identification in Stochastic Bandits
• Title（参考訳）: 確率帯域におけるSPRTに基づく効率的なベストアーム同定
• Authors: Arpan Mukherjee and Ali Tajer
• Abstract要約: 本稿では,固定信頼度設定におけるマルチアームバンディットの腕識別問題について検討する。 バンドイットの指数族に対する最先端のアルゴリズムは、計算上の課題に直面している。 BAI問題を逐次仮説テストとみなす新しい枠組みが提案されている。
• 参考スコア（独自算出の注目度）: 31.359578768463752
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper investigates the best arm identification (BAI) problem in stochastic multi-armed bandits in the fixed confidence setting. The general class of the exponential family of bandits is considered. The state-of-the-art algorithms for the exponential family of bandits face computational challenges. To mitigate these challenges, a novel framework is proposed, which views the BAI problem as sequential hypothesis testing, and is amenable to tractable analysis for the exponential family of bandits. Based on this framework, a BAI algorithm is designed that leverages the canonical sequential probability ratio tests. This algorithm has three features for both settings: (1) its sample complexity is asymptotically optimal, (2) it is guaranteed to be $\delta-$PAC, and (3) it addresses the computational challenge of the state-of-the-art approaches. Specifically, these approaches, which are focused only on the Gaussian setting, require Thompson sampling from the arm that is deemed the best and a challenger arm. This paper analytically shows that identifying the challenger is computationally expensive and that the proposed algorithm circumvents it. Finally, numerical experiments are provided to support the analysis.
• Abstract（参考訳）: 本稿では,確率的マルチアームバンディットにおける最適腕識別(BAI)問題について検討する。 指数的ブレイディット族(英語版)の一般類を考える。 指数関数的なバンディット群に対する最先端のアルゴリズムは計算の課題に直面している。 これらの課題を緩和するために, bai 問題を逐次仮説検定と捉えた新しい枠組みが提案されている。 この枠組みに基づき、標準的な逐次確率比テストを利用するbaiアルゴリズムが設計されている。 このアルゴリズムは,(1)サンプルの複雑さが漸近的に最適であること,(2)$\delta-$PACであること,(3)最先端アプローチの計算課題に対処すること,の3つの特徴を有する。 具体的には、ガウス的な設定にのみ焦点をあてたこれらのアプローチは、ベストかつ挑戦的な腕と見なされる腕からのトンプソンサンプリングを必要とする。 本稿では,挑戦者の同定が計算コストが高く,提案アルゴリズムが回避できることを解析的に示す。 最後に,解析を支援する数値実験を行った。

関連論文リスト

• Pure Exploration for Constrained Best Mixed Arm Identification with a Fixed Budget [6.22018632187078]
  固定予算の制約付きベスト・ミックスアーム識別(CBMAI)問題を導入する。 目標は、与えられた学習予算$N$で、期待されるコストの制約によって期待される報酬を最大化する最高の混合アームを見つけることである。 我々は、(最良の混合アームの支持の)誤識別に関する理論上の上限を提供し、予算$N$で指数関数的に崩壊することを示す。
  論文  参考訳（メタデータ） (2024-05-23T22:35:11Z)
• 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)
• Thompson Exploration with Best Challenger Rule in Best Arm Identification [66.33448474838342]
  本稿では,バンドイットフレームワークにおける固定信頼度最良腕識別問題について検討する。 我々は、トンプソンサンプリングと、ベストチャレンジャールールとして知られる計算効率の良いアプローチを組み合わせた新しいポリシーを提案する。
  論文  参考訳（メタデータ） (2023-10-01T01:37:02Z)
• Best Arm Identification in Stochastic Bandits: Beyond $\beta-$optimality [31.359578768463752]
  本稿では,固定信頼設定における多腕バンディットにおけるベストアーム識別(BAI)の非装飾的側面について検討する。 帯域幅アルゴリズムを評価するための2つの重要な指標は、計算効率と性能最適性である。 本稿では,BAIのためのフレームワークとアルゴリズムを導入し,計算効率のよい決定ルールセットを用いて最適性能を実現する。
  論文  参考訳（メタデータ） (2023-01-10T05:02:49Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。 これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。 合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
  論文  参考訳（メタデータ） (2022-02-09T06:05:05Z)
• From Optimality to Robustness: Dirichlet Sampling Strategies in Stochastic Bandits [0.0]
  本研究では、腕の観察を再サンプリングした経験的指標のペア比較に基づいて、ジェネリックディリクレサンプリング(DS)アルゴリズムについて検討する。 この戦略の異なる変種は、分布が有界であるときに証明可能な最適後悔保証と、半有界分布に対して軽度量子状態の対数後悔を実現することを示す。
  論文  参考訳（メタデータ） (2021-11-18T14:34:21Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)
• Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
  サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。 既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
  論文  参考訳（メタデータ） (2020-06-29T14:25:51Z)

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

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