論文の概要: Almost Optimal Variance-Constrained Best Arm Identification
- arxiv url: http://arxiv.org/abs/2201.10142v1
- Date: Tue, 25 Jan 2022 07:36:00 GMT
- ステータス: 処理完了
- システム内更新日: 2022-01-27 03:46:04.693250
- Title: Almost Optimal Variance-Constrained Best Arm Identification
- Title（参考訳）: ほぼ最適変数制約によるベストアーム同定
- Authors: Yunlong Hou, Vincent Y. F. Tan, Zixin Zhong
- Abstract要約: パラメータフリーなアルゴリズムであるVA-LUCBを用いて、固定信頼設定の下で最適なアームを識別する。
VA-LUCBは、リスクに制約された最高の腕識別問題に対して、最も低いサンプル複雑性を有する。
- 参考スコア（独自算出の注目度）: 81.60136088841948
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We design and analyze VA-LUCB, a parameter-free algorithm, for identifying
the best arm under the fixed-confidence setup and under a stringent constraint
that the variance of the chosen arm is strictly smaller than a given threshold.
An upper bound on VA-LUCB's sample complexity is shown to be characterized by a
fundamental variance-aware hardness quantity $H_{VA}$. By proving a lower
bound, we show that sample complexity of VA-LUCB is optimal up to a factor
logarithmic in $H_{VA}$. Extensive experiments corroborate the dependence of
the sample complexity on the various terms in $H_{VA}$. By comparing VA-LUCB's
empirical performance to a close competitor RiskAverse-UCB-BAI by David et al.
(2018), our experiments suggest that VA-LUCB has the lowest sample complexity
for this class of risk-constrained best arm identification problems, especially
for the riskiest instances.
- Abstract（参考訳）: パラメータフリーなアルゴリズムであるva-lucbを設計・解析し,固定信頼設定下で最良アームを同定し,選択したアームのばらつきが与えられたしきい値よりも厳密に小さいという厳密な制約の下で解析する。
VA-LUCBのサンプルの複雑さの上限は、基本分散を考慮したハードネス量$H_{VA}$によって特徴づけられる。
低境界を証明することにより、VA-LUCBのサンプル複雑性が$H_{VA}$の係数対数に最適であることを示す。
大規模な実験は、サンプル複雑性の様々な項への依存を$H_{VA}$で相関させる。
David et al. (2018) によるVA-LUCBの実証的な性能と近い競合である RiskAverse-UCB-BAI (2018) を比較することで、VA-LUCBはリスクに制約された最高の腕の識別問題、特に最もリスクの高い症例において、最も低いサンプルの複雑さを持つことが示唆された。
関連論文リスト
- Representative Arm Identification: A fixed confidence approach to identify cluster representatives [7.459521930846415]
マルチアームバンディット(MAB)フレームワークにおける代表腕識別問題について検討する。
RAI問題は、最高の腕や、上位の$K$から$M$を識別するなど、いくつかのよく研究されたMAB問題としてカバーされている。
本稿では,信頼区間の概念に基づく2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-08-26T11:47:52Z) - 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) - Optimal Multi-Distribution Learning [88.3008613028333]
マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。
本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-12-08T16:06:29Z) - Fixed-Budget Best-Arm Identification with Heterogeneous Reward Variances [12.00630538470713]
不均一な報酬分散を伴う固定予算設定におけるベストアーム識別(BAI)の問題について検討する。
本稿では, 既知報酬分散に対するSHVarと未知報酬分散に対するSHAdaVarの2つの分散適応型BAIアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-06-13T05:41:38Z) - Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。
トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
論文 参考訳（メタデータ） (2023-03-30T02:51:00Z) - Private Mean Estimation of Heavy-Tailed Distributions [10.176795938619417]
差分的にプライベートな分布の平均推定におけるミニマックスサンプルの複雑さについて, 新たな上限値と下限値を与える。
$n = Thetaleft(frac1alpha2 + frac1alphafrack-1varepsilonright)$サンプルは必要で、$varepsilon$-differential privacyの下で$alpha$-accuracyと見積もるのに十分である。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z) - The Simulator: Understanding Adaptive Sampling in the
Moderate-Confidence Regime [52.38455827779212]
エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。
適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。
我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
論文 参考訳（メタデータ） (2017-02-16T23:42:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。