論文の概要: An $\varepsilon$-Best-Arm Identification Algorithm for Fixed-Confidence and Beyond

• arxiv url: http://arxiv.org/abs/2305.16041v1
• Date: Thu, 25 May 2023 13:19:11 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-26 14:58:11.714443
• Title: An $\varepsilon$-Best-Arm Identification Algorithm for Fixed-Confidence and Beyond
• Title（参考訳）: 固定信頼とそれ以上のための$\varepsilon$-best-arm識別アルゴリズム
• Authors: Marc Jourdan, R\'emy Degenne, Emilie Kaufmann
• Abstract要約: 本稿では,バンディットの腕識別のための新しいサンプリングルールであるEB-TC$varepsilon$を提案する。 EB-TC$varepsilon$に対して3種類の理論的保証を提供する。 EB-TC$varepsilon$が既存のアルゴリズムと比較して好適に動作することを示す。
• 参考スコア（独自算出の注目度）: 11.975934323118752
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: We propose EB-TC$\varepsilon$, a novel sampling rule for $\varepsilon$-best arm identification in stochastic bandits. It is the first instance of Top Two algorithm analyzed for approximate best arm identification. EB-TC$\varepsilon$ is an *anytime* sampling rule that can therefore be employed without modification for fixed confidence or fixed budget identification (without prior knowledge of the budget). We provide three types of theoretical guarantees for EB-TC$\varepsilon$. First, we prove bounds on its expected sample complexity in the fixed confidence setting, notably showing its asymptotic optimality in combination with an adaptive tuning of its exploration parameter. We complement these findings with upper bounds on its probability of error at any time and for any error parameter, which further yield upper bounds on its simple regret at any time. Finally, we show through numerical simulations that EB-TC$\varepsilon$ performs favorably compared to existing algorithms, in different settings.
• Abstract（参考訳）: 確率的バンドイットにおいて, eb-tc$-varepsilon$-best arm identificationのための新しいサンプリング規則であるeb-tc$-varepsilon$を提案する。 これは最良腕識別のために解析された上位2つのアルゴリズムの最初の例である。 EB-TC$\varepsilon$ は *anytime* サンプリングルールであり、固定された信頼度や固定された予算識別(予算の事前の知識なしで)の修正なしに使用できる。 eb-tc$\varepsilon$の3種類の理論保証を提供する。 まず, 一定の信頼度設定において, 推定されたサンプル複雑性の境界を証明し, その漸近的最適性と探索パラメータの適応チューニングを組み合わせる。 これらの結果は,任意の時間における誤差の確率と,任意の誤差パラメータの上限で補うことができ,任意の時間におけるその単純な後悔の上限をさらに高めることができる。 最後に,EB-TC$\varepsilon$が既存のアルゴリズムと比較して,異なる設定で良好に動作することを示す。

関連論文リスト

• Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits [55.957560311008926]
  そこで本研究では,各文脈の平均値によって腕の質を計測するPSLBモデルを提案する。 PS$varepsilon$BAI$+$は、$varepsilon$-optimal armを、確率$ge 1-delta$と最小限のサンプルで識別することが保証される。
  論文  参考訳（メタデータ） (2024-10-10T06:15:42Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Normalized/Clipped SGD with Perturbation for Differentially Private Non-Convex Optimization [94.06564567766475]
  DP-SGDとDP-NSGDは、センシティブなトレーニングデータを記憶する大規模モデルのリスクを軽減する。 DP-NSGD は DP-SGD よりも比較的チューニングが比較的容易であるのに対して,これらの2つのアルゴリズムは同様の精度を実現する。
  論文  参考訳（メタデータ） (2022-06-27T03:45:02Z)
• On the complexity of All $\varepsilon$-Best Arms Identification [2.1485350418225244]
  ガウスの報酬を持つ有限の多腕バンディットにおいて、$varepsilon$-optimal armsを全て識別する問題を考える。 我々は,$varepsilon$-good arms w.h.p の集合を同定し,期待されるサンプルの複雑さの観点から最適性($delta$が 0 になるとき)を享受するトラック・アンド・ストップアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-02-13T10:54:52Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)
• Misspecified Gaussian Process Bandit Optimization [59.30399661155574]
  カーネル化されたバンディットアルゴリズムは、この問題に対して強い経験的および理論的性能を示した。 本稿では、未知関数を$epsilon$-一様近似で近似できるエンフェミス特定カーネル化帯域設定を、ある再生カーネルヒルベルト空間(RKHS)において有界ノルムを持つ関数で導入する。 提案アルゴリズムは,不特定性に関する事前知識を伴わず,$epsilon$への最適依存を実現する。
  論文  参考訳（メタデータ） (2021-11-09T09:00:02Z)
• Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
  サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。 既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
  論文  参考訳（メタデータ） (2020-06-29T14:25:51Z)
• Regret and Belief Complexity Trade-off in Gaussian Process Bandits via Information Thresholding [42.669970064867556]
  GPバンディットアルゴリズムの残差境界と後部分布の複雑さのトレードオフを特徴付ける方法を示す。 大域的最適化に応用したGPバンディットアルゴリズムの精度と複雑性のトレードオフを観察する。
  論文  参考訳（メタデータ） (2020-03-23T21:05:15Z)

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

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