論文の概要: Best Arm Identification in Stochastic Bandits: Beyond $\beta-$optimality
- arxiv url: http://arxiv.org/abs/2301.03785v1
- Date: Tue, 10 Jan 2023 05:02:49 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-11 16:26:05.297476
- Title: Best Arm Identification in Stochastic Bandits: Beyond $\beta-$optimality
- Title(参考訳): 確率帯域における最高の腕識別:$\beta-$optimalityを超える
- Authors: Arpan Mukherjee and Ali Tajer
- Abstract要約: 本稿では,固定信頼度,パラメトリック設定におけるマルチアームバンディット(MAB)のベストアーム識別(BAI)に焦点を当てた。
サンプリング戦略の精度は、アーム間のサンプリング資源の逐次割り当てに批判的に掛かる。
- 参考スコア(独自算出の注目度): 31.359578768463752
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper focuses on best arm identification (BAI) in stochastic multi-armed
bandits (MABs) in the fixed-confidence, parametric setting. In such pure
exploration problems, the accuracy of the sampling strategy critically hinges
on the sequential allocation of the sampling resources among the arms. The
existing approaches to BAI address the following question: what is an optimal
sampling strategy when we spend a $\beta$ fraction of the samples on the best
arm? These approaches treat $\beta$ as a tunable parameter and offer efficient
algorithms that ensure optimality up to selecting $\beta$, hence
$\beta-$optimality. However, the BAI decisions and performance can be highly
sensitive to the choice of $\beta$. This paper provides a BAI algorithm that is
agnostic to $\beta$, dispensing with the need for tuning $\beta$, and specifies
an optimal allocation strategy, including the optimal value of $\beta$.
Furthermore, the existing relevant literature focuses on the family of
exponential distributions. This paper considers a more general setting of any
arbitrary family of distributions parameterized by their mean values (under
mild regularity conditions).
- Abstract(参考訳): 本稿では,固定信頼パラメトリック設定における確率的多腕バンディット(mabs)における最良腕識別(bai)に着目した。
このような純粋な探索問題において、サンプリング戦略の精度は、アーム間のサンプリング資源の逐次配置に決定的に影響を及ぼす。
BAIの既存のアプローチは次のような問題に対処している。 ベストアームのサンプルの$\beta$分を費やすとき、最適なサンプリング戦略は何ですか?
これらのアプローチは$\beta$を調整可能なパラメータとして扱い、$\beta$を選択するまでの最適性を保証する効率的なアルゴリズムを提供する。
しかし、BAIの決定とパフォーマンスは$\beta$の選択に非常に敏感である。
本稿では、$\beta$に非依存なBAIアルゴリズムを提供し、$\beta$をチューニングする必要がなく、$\beta$の最適値を含む最適なアロケーション戦略を指定する。
さらに、既存の関連文献は指数分布の族に焦点をあてている。
本稿では, 平均値によってパラメータ化された任意の分布列のより一般的な設定について考察する。
関連論文リスト
- Stochastic Bayesian Optimization with Unknown Continuous Context
Distribution via Kernel Density Estimation [28.413085548038932]
本稿では,カーネル密度推定を用いて連続文脈変数の確率密度関数(PDF)をオンラインで学習する2つのアルゴリズムを提案する。
理論的結果は、両方のアルゴリズムが期待する目的に対して準線形ベイズ累積後悔を持つことを示している。
論文 参考訳(メタデータ) (2023-12-16T11:32:28Z) - Efficient Convex Algorithms for Universal Kernel Learning [50.877957471649395]
カーネルの理想的な集合: 線形パラメータ化(トラクタビリティ)を認める; すべてのカーネルの集合に密着する(正確性)。
従来のカーネル最適化アルゴリズムは分類に限られており、計算に複雑なセミデフィニティプログラミング(SDP)アルゴリズムに依存していた。
本稿では,従来のSDP手法と比較して計算量を大幅に削減するSVD-QCQPQPアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-04-15T04:57:37Z) - Mean-based Best Arm Identification in Stochastic Bandits under Reward
Contamination [80.53485617514707]
本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。
具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
論文 参考訳(メタデータ) (2021-11-14T21:49:58Z) - Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
空間的制約が存在する場合の高次元統計量と非破壊的最適化の関連について検討する。
これらの問題に対する新規で簡単な最適化法を開発した。
結論として、効率よくステーションに収束する一階法は、これらのタスクに対して効率的なアルゴリズムを導出する。
論文 参考訳(メタデータ) (2021-09-23T17:38:24Z) - Near-Optimal High Probability Complexity Bounds for Non-Smooth
Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。
クリッピングを用いた2つの勾配法に対して, 新たなステップサイズルールを提案する。
論文 参考訳(メタデータ) (2021-06-10T17:54:21Z) - Benchmarking Simulation-Based Inference [5.3898004059026325]
確率的モデリングの最近の進歩は、確率の数値的評価を必要としないシミュレーションに基づく推論アルゴリズムを多数もたらした。
推論タスクと適切なパフォーマンス指標を備えたベンチマークを,アルゴリズムの初期選択とともに提供する。
性能指標の選択は重要であり、最先端のアルゴリズムでさえ改善の余地があり、逐次推定によりサンプリング効率が向上することがわかった。
論文 参考訳(メタデータ) (2021-01-12T18:31:22Z) - Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
バイレベル最適化は多くの機械学習問題に対するツールである。
Stoc-BiO という新しい確率効率勾配推定器を提案する。
論文 参考訳(メタデータ) (2020-10-15T18:09:48Z) - Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
我々のアルゴリズムは、トレーニングセットのサイズとパラメータの数によらず、多くの評価勾配を必要とすることを証明している。
MNIST と ImageNet の実験により,本手法の 9-36 倍の効率性を持つアルゴリズムの理論的スケーリングが確認された。
論文 参考訳(メタデータ) (2020-10-12T17:41:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。