論文の概要: An Optimal Elimination Algorithm for Learning a Best Arm

• arxiv url: http://arxiv.org/abs/2006.11647v1
• Date: Sat, 20 Jun 2020 20:21:33 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-18 22:21:50.550455
• Title: An Optimal Elimination Algorithm for Learning a Best Arm
• Title（参考訳）: 最良腕学習のための最適除去アルゴリズム
• Authors: Avinatan Hassidim, Ron Kupfer, Yaron Singer
• Abstract要約: 古典的な問題である$(epsilon,delta)$-PAC学習をベストアームとみなす。 本稿では,$(epsilon,delta)$-PAC学習を最適なアームとして提案する。
• 参考スコア（独自算出の注目度）: 37.18327505953403
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the classic problem of $(\epsilon,\delta)$-PAC learning a best arm where the goal is to identify with confidence $1-\delta$ an arm whose mean is an $\epsilon$-approximation to that of the highest mean arm in a multi-armed bandit setting. This problem is one of the most fundamental problems in statistics and learning theory, yet somewhat surprisingly its worst-case sample complexity is not well understood. In this paper, we propose a new approach for $(\epsilon,\delta)$-PAC learning a best arm. This approach leads to an algorithm whose sample complexity converges to \emph{exactly} the optimal sample complexity of $(\epsilon,\delta)$-learning the mean of $n$ arms separately and we complement this result with a conditional matching lower bound. More specifically:
• Abstract（参考訳）: 我々は、$(\epsilon,\delta)$-PAC学習という古典的な問題を考え、そのゴールは、自信を持って1-\delta$を識別することであり、その平均は、マルチアームのバンディット設定において最も高い平均的アームのそれに対する$\epsilon$-approximationである。 この問題は統計学と学習理論における最も根本的な問題の1つだが、驚くべきことに、最悪の例の複雑さはよく分かっていない。 本稿では,$(\epsilon,\delta)$-PAC学習を最適アームとする新しい手法を提案する。 このアプローチは、サンプル複雑性が \emph{exactly} に収束し、最適なサンプル複雑性が $(\epsilon,\delta)$-learning でそれぞれ$n$ armsの平均を学習するアルゴリズムに繋がる。 具体的には

関連論文リスト

• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• Optimal Top-Two Method for Best Arm Identification and Fluid Analysis [15.353009236788262]
  最適な腕識別問題に対する最適トップ2型アルゴリズムを提案する。 提案アルゴリズムは$delta rightarrow 0$として最適であることを示す。
  論文  参考訳（メタデータ） (2024-03-14T06:14:07Z)
• Optimal Batched Best Arm Identification [31.794242669480106]
  バッチ化されたベストアーム識別(BBAI)問題について検討し、学習者のゴールは、ポリシーをできるだけ少なく変更しながら、最適なアームを識別することである。 特に、ある小さな定数$delta>0$に対して、確率1-delta$の最良のアームを見つけることを目指している。 本稿では,Tri-BBAIアルゴリズムとOpt-BBAIアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-10-21T22:55:50Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• Revisiting Simple Regret Minimization in Multi-Armed Bandits [33.88679679593314]
  単純な後悔は、最高の腕や$epsilon$-good腕を欠く確率よりもあまり一般的ではない。 本稿では,データ豊かさ (Tge n$) とデータ貧弱さ (T le n$) の両面において,単純な後悔の上限を改良した。 より困難なデータ・ポーア・レシエーションのために、少なくとも1回は各腕をサンプリングすることなく、同じ改善を享受できるブラッケティングSH(BSH)を提案する。
  論文  参考訳（メタデータ） (2022-10-30T18:31:03Z)
• Best-Arm Identification in Correlated Multi-Armed Bandits [9.180690233707645]
  本稿では,武器間の相関に関するドメイン知識を捉えた新しい相関バンディットフレームワークを提案する。 C-LUCBで得られた全サンプルは$mathcalOleft(sum_k in MathcalC logleft(frac1deltaright)$であり、通常の$mathcalOleft(sum_k in MathcalC logleft(frac1deltaright)$とは対照的である。
  論文  参考訳（メタデータ） (2021-09-10T15:41:07Z)
• Bandits with many optimal arms [68.17472536610859]
  最適アームの割合は$p*$、最適アームとサブ最適化アームの間の最小平均ギャップは$Delta$と書きます。 我々は,累積的後悔設定と最良腕識別設定の両方において最適な学習率を特徴付ける。
  論文  参考訳（メタデータ） (2021-03-23T11:02:31Z)
• Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
  我々は、腕の総数が膨大であることができるトップ$ k$極端な文脈的包帯問題を研究します。 まず,Inverse Gap Weighting戦略を用いて,非極端に実現可能な設定のアルゴリズムを提案する。 我々のアルゴリズムは、$O(ksqrt(A-k+1)T log (|mathcalF|T))$である。
  論文  参考訳（メタデータ） (2021-02-15T19:10:52Z)
• Explicit Best Arm Identification in Linear Bandits Using No-Regret Learners [17.224805430291177]
  線形パラメータ化マルチアームバンドにおけるベストアーム識別の問題について検討する。 そこで本研究では,この問題を解決するために,明示的に実装可能かつ証明可能な順序-最適サンプル-複雑度アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-13T05:00:01Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)

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

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