論文の概要: Bayes Optimal Algorithm is Suboptimal in Frequentist Best Arm Identification

• arxiv url: http://arxiv.org/abs/2202.05193v1
• Date: Thu, 10 Feb 2022 17:50:26 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-11 15:15:28.771312
• Title: Bayes Optimal Algorithm is Suboptimal in Frequentist Best Arm Identification
• Title（参考訳）: ベイズ最適アルゴリズムは周波数的ベストアーム同定において最適である
• Authors: Junpei Komiyama
• Abstract要約: 頻繁な単純後悔は任意の固定パラメータに対して指数関数的に$T$に小さいことが知られているが、ベイズ的単純後悔は連続的な先行よりも$Theta(T-1)$である。 本稿では,ベイズ的単純後悔を最小限に抑えるベイズ最適アルゴリズムが,いくつかのパラメータに対して指数関数的単純後悔を伴わないことを示す。
• 参考スコア（独自算出の注目度）: 3.096615629099617
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the fixed-budget best arm identification problem with Normal rewards. In this problem, the forecaster is given $K$ arms (treatments) and $T$ time steps. The forecaster attempts to find the best arm in terms of the largest mean via an adaptive experiment conducted with an algorithm. The performance of the algorithm is measured by the simple regret, or the quality of the estimated best arm. It is known that the frequentist simple regret can be exponentially small to $T$ for any fixed parameters, whereas the Bayesian simple regret is $\Theta(T^{-1})$ over a continuous prior distribution. This paper shows that Bayes optimal algorithm, which minimizes the Bayesian simple regret, does not have an exponential simple regret for some parameters. This finding contrasts with the many results indicating the asymptotic equivalence of Bayesian and frequentist algorithms in fixed sampling regimes. While the Bayes optimal algorithm is described in terms of a recursive equation that is virtually impossible to compute exactly, we pave the way to an analysis by introducing a key quantity that we call the expected Bellman improvement.
• Abstract（参考訳）: 正規報酬を用いた固定予算ベストアーム識別問題を考察する。 この問題では、予測者は$k$ arms (treatments)と$t$ time stepを与えられる。 予測器はアルゴリズムを用いて行った適応実験により、最大の平均の観点で最適なアームを見つけようとする。 アルゴリズムの性能は、単純な後悔または推定されたベストアームの品質によって測定される。 頻繁な単純後悔は任意の固定パラメータに対して指数関数的に$T$に小さいことが知られているが、ベイズ的単純後悔は連続した事前分布に対して$\Theta(T^{-1})$である。 本稿では,ベイズ単純後悔を最小化するベイズ最適アルゴリズムが,いくつかのパラメータに対して指数関数的単純後悔を持たないことを示す。 この発見は、固定サンプリングレジームにおけるベイズアルゴリズムと頻繁アルゴリズムの漸近同値を示す多くの結果とは対照的である。 ベイズ最適アルゴリズムは、正確に計算することが事実上不可能な再帰方程式という観点から記述されるが、我々はベルマン改善と呼ばれる重要な量を導入することによって、分析への道を開く。

関連論文リスト

• Near-Optimal Algorithm for Non-Stationary Kernelized Bandits [6.379833644595456]
  時変ベイズ最適化(英語版)とも呼ばれる非定常カーネル化バンドイット問題(KB)について検討する。 我々は,2乗指数およびマタン核を持つ非定常KBに対して,アルゴリズムに依存しない最初のリフレッシュローバウンドを示す。 本稿では,ランダムな置換による位相除去を再開する手法を提案する。
  論文  参考訳（メタデータ） (2024-10-21T14:28:26Z)
• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• Optimal Multi-Fidelity Best-Arm Identification [65.23078799972188]
  バンディットのベストアーム識別において、アルゴリズムは、できるだけ早く特定の精度で、最高平均報酬の腕を見つけることを任務とする。 マルチフィデリティのベストアーム識別について検討し、低コストで低いフィデリティ(正確な平均推定値を持たない)で腕をサンプリングすることを選択できる。 この問題に対処するためのいくつかの方法が提案されているが、その最適性は、特に最適な腕を特定するのに必要な総コストのゆるやかな下限のため、未解決のままである。
  論文  参考訳（メタデータ） (2024-06-05T08:02:40Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Only Pay for What Is Uncertain: Variance-Adaptive Thompson Sampling [44.921905700729766]
  ほとんどのバンディットアルゴリズムは、報酬のばらつきまたはその上限が知られており、全ての腕について同じであると仮定する。 この動機付けは、強いインスタンス依存の後悔境界を持つ分散適応型頻繁性アルゴリズムに関する先行研究である。 我々は、過去の知識を取り入れたベイズ的設定の基礎を築いた。
  論文  参考訳（メタデータ） (2023-03-16T02:07:29Z)
• Rate-optimal Bayesian Simple Regret in Best Arm Identification [11.389780431092914]
  マルチアームバンディット問題における腕の識別について検討する。 本稿では,その先行項を定数係数まで下界にマッチングする,単純で容易に計算できるアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-11-18T18:59:35Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)
• Lenient Regret for Multi-Armed Bandits [72.56064196252498]
  エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。 アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。 我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
  論文  参考訳（メタデータ） (2020-08-10T08:30:52Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  強凸関数のゼロ次最適化問題について検討する。 予測勾配降下アルゴリズムのランダム化近似を考察する。 その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-14T10:42:23Z)
• Bandit algorithms to emulate human decision making using probabilistic distortions [20.422725678982726]
  報奨分布に歪んだ確率を持つ2つの多重武装バンディット問題を定式化する。 以上のような後悔の最小化の問題と、マルチアームバンディットのための最高の腕識別フレームワークについて考察する。
  論文  参考訳（メタデータ） (2016-11-30T17:37:51Z)

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

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