論文の概要: On Universally Optimal Algorithms for A/B Testing

• arxiv url: http://arxiv.org/abs/2308.12000v4
• Date: Tue, 4 Jun 2024 12:14:46 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-06 14:16:48.419650
• Title: On Universally Optimal Algorithms for A/B Testing
• Title（参考訳）: A/Bテストのための普遍的最適アルゴリズムについて
• Authors: Po-An Wang, Kaito Ariu, Alexandre Proutiere,
• Abstract要約: ベルヌーイ報奨を伴う多腕バンディットにおける固定予算によるベストアーム識別の問題について検討する。 A/Bテスト問題としても知られる2つのアームの問題に対して,各アームを等しくサンプリングするアルゴリズムが存在しないことを証明した。
• 参考スコア（独自算出の注目度）: 49.429419538826444
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of best-arm identification with fixed budget in stochastic multi-armed bandits with Bernoulli rewards. For the problem with two arms, also known as the A/B testing problem, we prove that there is no algorithm that (i) performs as well as the algorithm sampling each arm equally (referred to as the {\it uniform sampling} algorithm) in all instances, and that (ii) strictly outperforms uniform sampling on at least one instance. In short, there is no algorithm better than the uniform sampling algorithm. To establish this result, we first introduce the natural class of {\it consistent} and {\it stable} algorithms, and show that any algorithm that performs as well as the uniform sampling algorithm in all instances belongs to this class. The proof then proceeds by deriving a lower bound on the error rate satisfied by any consistent and stable algorithm, and by showing that the uniform sampling algorithm matches this lower bound. Our results provide a solution to the two open problems presented in \citep{qin2022open}. For the general problem with more than two arms, we provide a first set of results. We characterize the asymptotic error rate of the celebrated Successive Rejects (SR) algorithm \citep{audibert2010best} and show that, surprisingly, the uniform sampling algorithm outperforms the SR algorithm in some instances.
• Abstract（参考訳）: ベルヌーイ報奨を伴う確率的マルチアームバンディットにおける固定予算によるベストアーム識別の問題について検討する。 A/Bテスト問題としても知られる2つのアームの問題に対して、アルゴリズムが存在しないことが証明される。 i)全ての事例において、各アームを等しくサンプリングするアルゴリズム(「一様サンプリングアルゴリズム」と呼ぶ)と同様に、そのアルゴリズムを実行する。 (ii)少なくとも1つのインスタンスで一様サンプリングを厳格に上回る。 要するに、一様サンプリングアルゴリズムに勝るアルゴリズムはない。 この結果を確立するために、まず自然クラス {\it consistent} と {\it stable} アルゴリズムを導入し、全てのインスタンスにおける一様サンプリングアルゴリズムと同様に動作する任意のアルゴリズムがこのクラスに属することを示す。 証明は、任意の一貫した安定なアルゴリズムで満たされた誤差率の低い境界を導出し、一様サンプリングアルゴリズムがこの下限と一致することを示す。 この結果から,2つの開問題に対する解が得られる。 2つ以上の腕を持つ一般的な問題に対して、最初の一連の結果を提供する。 本稿では,SR アルゴリズムの漸近誤差率を特徴付けるとともに,一様サンプリングアルゴリズムが SR アルゴリズムより優れていることを示す。

関連論文リスト

• Online Uniform Sampling: Randomized Learning-Augmented Approximation Algorithms with Application to Digital Health [3.534690532561709]
  オンライン一様サンプリング(OUS)の新たな課題として,未知の意思決定時間に一様にサンプリング予算を分散させることが目的である。 OUS問題では、アルゴリズムは予算$b$とタイムホライズ$T$を与えられ、敵は[b,T]$の値$tau*を選択し、それをオンラインに公開する。 この問題に対して設計された最初のランダム化アルゴリズムを提示し、その後、学習拡張を組み込むように拡張する。
  論文  参考訳（メタデータ） (2024-02-03T02:36:59Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Fixed-Budget Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [65.268245109828]
  このアルゴリズムは,アクションクラスのサイズが指数関数的に大きい場合でも,最良のアクションを識別できる最初のアルゴリズムである。 CSAアルゴリズムの誤差確率の上限は指数の対数係数までの下界と一致することを示す。 提案手法を従来手法と実験的に比較し,アルゴリズムの性能が向上したことを示す。
  論文  参考訳（メタデータ） (2023-10-24T09:47:32Z)
• Non-Asymptotic Analysis of a UCB-based Top Two Algorithm [4.18804572788063]
  バンディット識別のためのトップ2サンプリングルールは、2つの候補アームの中から次のアームを選択する方法である。 提案するUCBベースのトップ2は,非漸近的保証と競合経験性能を同時に享受する。
  論文  参考訳（メタデータ） (2022-10-11T13:21:59Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)
• A Systematic Characterization of Sampling Algorithms for Open-ended Language Generation [71.31905141672529]
  本稿では,自己回帰型言語モデルに広く採用されている祖先サンプリングアルゴリズムについて検討する。 エントロピー低減, 秩序保存, 斜面保全の3つの重要な特性を同定した。 これらの特性を満たすサンプリングアルゴリズムのセットが,既存のサンプリングアルゴリズムと同等に動作することがわかった。
  論文  参考訳（メタデータ） (2020-09-15T17:28:42Z)
• An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits [34.06611065493047]
  本稿では、信頼度と予算設定の固定化において、純探索線形帯域問題に対する近似アルゴリズムを提案する。 サンプルの複雑性がインスタンスの幾何でスケールし、アームの数に縛られた明示的な結合を避けるアルゴリズムを提供する。 また,固定予算設定における線形帯域幅に対する最初のアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-21T00:56:33Z)
• Corralling Stochastic Bandit Algorithms [54.10645564702416]
  相関アルゴリズムの後悔は、最も報酬の高い腕を含む最高のアルゴリズムの後悔よりも悪くはないことを示す。 最高報酬と他の報酬の差は、最高報酬と他の報酬の差に依存することを示す。
  論文  参考訳（メタデータ） (2020-06-16T15:33:12Z)

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

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