論文の概要: PAC Best Arm Identification Under a Deadline
- arxiv url: http://arxiv.org/abs/2106.03221v1
- Date: Sun, 6 Jun 2021 19:48:32 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-08 18:49:58.068901
- Title: PAC Best Arm Identification Under a Deadline
- Title（参考訳）: デッドライン下のPACベストアーム識別
- Authors: Brijen Thananjeyan, Kirthevasan Kandasamy, Ion Stoica, Michael I.
Jordan, Ken Goldberg, Joseph E. Gonzalez
- Abstract要約: 我々は$(epsilon, delta)$-PACベストアーム識別について研究し、意思決定者は少なくとも1 - delta$の確率で最適なアームを識別し、アームプルの数を最小化する(サンプル)。
この作業では、決定者はT$ラウンドの期限が与えられ、各ラウンドで、どのアームを引っ張るか、何回引っ張るかを適応的に選ぶことができる。
本稿では,この設定のための新しいアルゴリズムであるElastic Batch Racing (EBR)を提案する。
- 参考スコア（独自算出の注目度）: 101.10352416022559
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study $(\epsilon, \delta)$-PAC best arm identification, where a
decision-maker must identify an $\epsilon$-optimal arm with probability at
least $1 - \delta$, while minimizing the number of arm pulls (samples). Most of
the work on this topic is in the sequential setting, where there is no
constraint on the \emph{time} taken to identify such an arm; this allows the
decision-maker to pull one arm at a time. In this work, the decision-maker is
given a deadline of $T$ rounds, where, on each round, it can adaptively choose
which arms to pull and how many times to pull them; this distinguishes the
number of decisions made (i.e., time or number of rounds) from the number of
samples acquired (cost). Such situations occur in clinical trials, where one
may need to identify a promising treatment under a deadline while minimizing
the number of test subjects, or in simulation-based studies run on the cloud,
where we can elastically scale up or down the number of virtual machines to
conduct as many experiments as we wish, but need to pay for the resource-time
used. As the decision-maker can only make $T$ decisions, she may need to pull
some arms excessively relative to a sequential algorithm in order to perform
well on all possible problems. We formalize this added difficulty with two
hardness results that indicate that unlike sequential settings, the ability to
adapt to the problem difficulty is constrained by the finite deadline. We
propose Elastic Batch Racing (EBR), a novel algorithm for this setting and
bound its sample complexity, showing that EBR is optimal with respect to both
hardness results. We present simulations evaluating EBR in this setting, where
it outperforms baselines by several orders of magnitude.
- Abstract（参考訳）: 我々は、$(\epsilon, \delta)$-PACベストアーム識別を研究し、意思決定者は、少なくとも1 - \delta$の確率で$\epsilon$-optimal armを識別し、アームプルの数を最小化する(サンプル)。
このトピックに関するほとんどの作業はシーケンシャルな設定で行われており、そのようなアームを特定するために使われる \emph{time} に制約はない。
この作業では、意思決定者はt$ラウンドの期限が与えられ、各ラウンドにおいて、どのアームを引くか、何回引くかを適応的に選択することができる。
このような状況は、テスト対象の数を最小化しながら、期限付きで有望な治療を特定できる臨床試験や、シミュレーションベースの研究をクラウド上で実行し、仮想マシンの数を弾力的にスケールアップまたは縮小して、私たちが望む限り多くの実験を行うことができるが、使用したリソース時間に対して支払う必要がある、という臨床試験で発生します。
意思決定者は、t$の意思決定しかできないので、あらゆる可能な問題にうまく取り組むためには、シーケンシャルなアルゴリズムに対して過度に手を差し伸べる必要があるかもしれない。
この難易度を2つの難易度で定式化し、逐次的な設定とは異なり、難易度に適応する能力は有限の期限によって制約されることを示した。
本稿では,この設定のための新しいアルゴリズムであるElastic Batch Racing (EBR)を提案する。
本研究では,この設定におけるERRの評価を行い,数桁の精度でベースラインを上回ります。
関連論文リスト
- Contextual Bandits with Arm Request Costs and Delays [19.263086804406786]
本稿では,時間的遅延と関連するコストを伴って,新たなアームセットを要求できるコンテキスト的バンディット問題の拡張を提案する。
この設定では、学習者は、各選択が1つの時間単位を取るように、決定セットから複数のアームを選択することができる。
我々は、武器を効果的に選択し、新しい武器を要求する適切な時間を決定するアルゴリズムを設計し、彼らの後悔を最小限に抑える。
論文 参考訳（メタデータ） (2024-10-17T00:44:50Z) - Pure Exploration for Constrained Best Mixed Arm Identification with a Fixed Budget [6.22018632187078]
固定予算の制約付きベスト・ミックスアーム識別(CBMAI)問題を導入する。
目標は、与えられた学習予算$N$で、期待されるコストの制約によって期待される報酬を最大化する最高の混合アームを見つけることである。
我々は、(最良の混合アームの支持の)誤識別に関する理論上の上限を提供し、予算$N$で指数関数的に崩壊することを示す。
論文 参考訳（メタデータ） (2024-05-23T22:35:11Z) - Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳（メタデータ） (2023-12-19T13:17:43Z) - Best Arm Identification in Restless Markov Multi-Armed Bandits [85.55466536537293]
マルチアームバンディット環境における最適な腕を特定することの問題点について検討する。
決定エンティティは、上限誤差確率を条件として、ベストアームのインデックスをできるだけ早く見つけることを希望する。
このポリシーは、$R$に依存する上限を達成し、$Rtoinfty$として単調に増加しないことを示す。
論文 参考訳（メタデータ） (2022-03-29T04:58:04Z) - Selective Sampling for Online Best-arm Identification [19.767267982167578]
潜在的なオプションのセットが与えられた場合、学習者は1-delta$以上の確率で計算することを目指している。
この研究の主な成果は、ラベル付きサンプルと停止時間の間のトレードオフを正確に特徴づけるものである。
我々のフレームワークは、以前の作業で改善されたバイナリ分類をキャプチャするのに十分な一般性を持っている。
論文 参考訳（メタデータ） (2021-10-28T03:02:08Z) - Continuous Time Bandits With Sampling Costs [17.412117389855222]
連続時間マルチアームバンディット問題 (CTMAB) を考えると, 学習者は任意の間隔で何回でもアームをサンプリングし, サンプルからランダムな報酬を得ることができる。
サンプリング周波数の関数として、大きな報酬を得ることとサンプリングコストをもたらすことにはトレードオフがある。
目的は後悔を最小限に抑える学習アルゴリズムを設計することであり、これはオラクルのポリシーと学習アルゴリズムの報酬の差として定義される。
論文 参考訳（メタデータ） (2021-07-12T10:00:35Z) - Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
マルコフ決定過程における純粋探索問題について検討する。
エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
論文 参考訳（メタデータ） (2021-06-05T09:16:28Z) - Resource Allocation in Multi-armed Bandit Exploration: Overcoming
Sublinear Scaling with Adaptive Parallelism [107.48538091418412]
腕の引っ張りに様々な量の資源を割り当てることができる分割可能な資源にアクセス可能な場合,マルチアームの帯状地における探索について検討する。
特に、分散コンピューティングリソースの割り当てに重点を置いており、プル毎により多くのリソースを割り当てることで、結果をより早く得ることができます。
論文 参考訳（メタデータ） (2020-10-31T18:19:29Z) - Lenient Regret for Multi-Armed Bandits [72.56064196252498]
エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。
アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。
我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
論文 参考訳（メタデータ） (2020-08-10T08:30:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。