論文の概要: Robust Outlier Arm Identification

• arxiv url: http://arxiv.org/abs/2009.09988v1
• Date: Mon, 21 Sep 2020 16:13:01 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-16 04:25:18.375476
• Title: Robust Outlier Arm Identification
• Title（参考訳）: ロバストな外れ値アームの識別
• Authors: Yinglun Zhu, Sumeet Katariya and Robert Nowak
• Abstract要約: ロバスト・アウトリー・アーム識別(ROAI)の問題点について検討する。 目標は、期待される報酬が多数派から大きく逸脱した武器を特定することである。 我々は、期待される報酬の中央値と中央値の絶対偏差を用いて、外れ値のしきい値を算出する。
• 参考スコア（独自算出の注目度）: 16.21284542559277
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of Robust Outlier Arm Identification (ROAI), where the goal is to identify arms whose expected rewards deviate substantially from the majority, by adaptively sampling from their reward distributions. We compute the outlier threshold using the median and median absolute deviation of the expected rewards. This is a robust choice for the threshold compared to using the mean and standard deviation, since it can identify outlier arms even in the presence of extreme outlier values. Our setting is different from existing pure exploration problems where the threshold is pre-specified as a given value or rank. This is useful in applications where the goal is to identify the set of promising items but the cardinality of this set is unknown, such as finding promising drugs for a new disease or identifying items favored by a population. We propose two $\delta$-PAC algorithms for ROAI, which includes the first UCB-style algorithm for outlier detection, and derive upper bounds on their sample complexity. We also prove a matching, up to logarithmic factors, worst case lower bound for the problem, indicating that our upper bounds are generally unimprovable. Experimental results show that our algorithms are both robust and about $5$x sample efficient compared to state-of-the-art.
• Abstract（参考訳）: 本研究では, 報酬分布から適応的に抽出することにより, 期待報酬が多数から実質的に逸脱するアームの識別を目標とするロバストアウトリアーアーム識別(roai)の問題について検討する。 期待報酬の中央値と中央値の絶対偏差を用いて、外れ値のしきい値を計算する。 これは平均偏差や標準偏差を用いた場合に比べて、極端な外れ値が存在する場合でも外れ値のアームを識別できるため、しきい値に対するロバストな選択である。 我々の設定は、閾値が所定の値またはランクとして事前に指定されている既存の純粋な探索問題とは異なる。 これは、有望な項目の集合を特定することを目的としているアプリケーションで有用であるが、新しい疾患に対する有望な薬物の発見や、集団によって好まれる項目の特定など、このセットの基数は不明である。 ROAIのための$\delta$-PACアルゴリズムを2つ提案する。 また、対数的要因、最悪の場合下限までの一致を証明し、我々の上限は概して改善不可能であることを示している。 実験結果から,我々のアルゴリズムは,最先端技術と比較して頑健で5ドル程度のサンプル効率がよいことがわかった。

関連論文リスト

• Optimal Multi-Fidelity Best-Arm Identification [65.23078799972188]
  バンディットのベストアーム識別において、アルゴリズムは、できるだけ早く特定の精度で、最高平均報酬の腕を見つけることを任務とする。 マルチフィデリティのベストアーム識別について検討し、低コストで低いフィデリティ(正確な平均推定値を持たない)で腕をサンプリングすることを選択できる。 この問題に対処するためのいくつかの方法が提案されているが、その最適性は、特に最適な腕を特定するのに必要な総コストのゆるやかな下限のため、未解決のままである。
  論文  参考訳（メタデータ） (2024-06-05T08:02:40Z)
• lil'HDoC: An Algorithm for Good Arm Identification under Small Threshold Gap [4.666048091337632]
  グッドアーム識別(GAI)は、単一の学習者が良い腕と特定されるとすぐに腕を出力する純粋探索バンディット問題である。 本稿では,腕の期待報酬と与えられた閾値との距離を参考に,小さな閾値ギャップ下でのGAI問題に焦点を当てた。 我々は,HDoCアルゴリズムの総サンプリング複雑性を大幅に改善するLil'HDoCと呼ばれる新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-01-29T04:21:47Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
  本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。 本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。 我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
  論文  参考訳（メタデータ） (2023-10-02T08:15:52Z)
• Beyond the Best: Estimating Distribution Functionals in Infinite-Armed Bandits [40.71199236098642]
  無限武装バンディット問題では、各アームの平均報酬は未知の分布からサンプリングされる。 我々は、最大以上の分布関数の一般的なクラスを検討し、オフラインとオンラインの両方で統一されたメタアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-11-01T18:20:10Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)
• Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
  サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。 既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
  論文  参考訳（メタデータ） (2020-06-29T14:25:51Z)
• Adaptive Double-Exploration Tradeoff for Outlier Detection [31.428683644520046]
  外乱検出の文脈におけるしきい値帯域問題 (TBP) の変種について検討した。 目的は、報酬がしきい値を超える外れ値を特定することである。 個別の腕を探索し、外れ値のしきい値の探索を自動的にオフにすることで、効率的なアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2020-05-13T00:12:31Z)
• The Price of Incentivizing Exploration: A Characterization via Thompson Sampling and Sample Complexity [83.81297078039836]
  インセンティブ付き探索(Incentivized Exploring)は、武器の選択を自給自足エージェントによって制御するマルチアーム・バンディットのバージョンである。 我々は、インセンティブの価格に焦点を合わせ、インセンティブの適合性のために、広く解釈された、パフォーマンスの喪失が引き起こされる。
  論文  参考訳（メタデータ） (2020-02-03T04:58:51Z)

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

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