論文の概要: Resource Allocation in Multi-armed Bandit Exploration: Overcoming Sublinear Scaling with Adaptive Parallelism

• arxiv url: http://arxiv.org/abs/2011.00330v2
• Date: Sat, 5 Jun 2021 19:25:31 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-01 04:22:26.178428
• Title: Resource Allocation in Multi-armed Bandit Exploration: Overcoming Sublinear Scaling with Adaptive Parallelism
• Title（参考訳）: マルチアームバンディット探査における資源配分:適応並列性によるサブリニアスケーリングの克服
• Authors: Brijen Thananjeyan, Kirthevasan Kandasamy, Ion Stoica, Michael I. Jordan, Ken Goldberg, Joseph E. Gonzalez
• Abstract要約: 腕の引っ張りに様々な量の資源を割り当てることができる分割可能な資源にアクセス可能な場合,マルチアームの帯状地における探索について検討する。 特に、分散コンピューティングリソースの割り当てに重点を置いており、プル毎により多くのリソースを割り当てることで、結果をより早く得ることができます。
• 参考スコア（独自算出の注目度）: 107.48538091418412
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study exploration in stochastic multi-armed bandits when we have access to a divisible resource that can be allocated in varying amounts to arm pulls. We focus in particular on the allocation of distributed computing resources, where we may obtain results faster by allocating more resources per pull, but might have reduced throughput due to nonlinear scaling. For example, in simulation-based scientific studies, an expensive simulation can be sped up by running it on multiple cores. This speed-up however, is partly offset by the communication among cores, which results in lower throughput than if fewer cores were allocated per trial to run more trials in parallel. In this paper, we explore these trade-offs in two settings. First, in a fixed confidence setting, we need to find the best arm with a given target success probability as quickly as possible. We propose an algorithm which trades off between information accumulation and throughput and show that the time taken can be upper bounded by the solution of a dynamic program whose inputs are the gaps between the sub-optimal and optimal arms. We also prove a matching hardness result. Second, we present an algorithm for a fixed deadline setting, where we are given a time deadline and need to maximize the probability of finding the best arm. We corroborate our theoretical insights with simulation experiments that show that the algorithms consistently match or outperform baseline algorithms on a variety of problem instances.
• Abstract（参考訳）: 各種のアームプルに割り当て可能なリソースを分割して利用できる場合, 確率的マルチアームバンディットの探索について検討する。 特に分散コンピューティングリソースの割り当てに注目し、プル毎により多くのリソースを割り当てることでより早く結果を得ることができるが、非線形スケーリングによってスループットが低下する可能性がある。 例えば、シミュレーションに基づく科学研究では、複数のコア上で実行することで、高価なシミュレーションを起動することができる。 しかし、このスピードアップはコア間の通信によって部分的に相殺されるため、トライアル毎にコアが割り当てられた回数がより少ない場合よりもスループットが低下する。 本稿では,このトレードオフを2つの設定で検討する。 まず、一定の信頼性設定で、与えられた目標成功確率の最高のアームをできるだけ早く見つける必要があります。 本稿では,情報蓄積とスループットのトレードオフを行うアルゴリズムを提案し,入力が準最適アームと最適アームのギャップである動的プログラムの解によって,処理時間を上限にすることができることを示す。 また、一致した硬度の結果も証明する。 第2に,固定期限設定のためのアルゴリズムを提案する。そこでは期限が与えられ,最善のアームを見つける確率を最大化する必要がある。 我々は、アルゴリズムが様々な問題インスタンスのベースラインアルゴリズムに一貫した一致または性能を示すことを示すシミュレーション実験で、理論的な洞察を裏付ける。

関連論文リスト

• A Mirror Descent-Based Algorithm for Corruption-Tolerant Distributed Gradient Descent [57.64826450787237]
  本研究では, 分散勾配降下アルゴリズムの挙動を, 敵対的腐敗の有無で解析する方法を示す。 汚職耐性の分散最適化アルゴリズムを設計するために、(怠慢な)ミラー降下からアイデアをどう使うかを示す。 MNISTデータセットの線形回帰、サポートベクトル分類、ソフトマックス分類に基づく実験は、我々の理論的知見を裏付けるものである。
  論文  参考訳（メタデータ） (2024-07-19T08:29:12Z)
• Optimal Multi-Fidelity Best-Arm Identification [65.23078799972188]
  バンディットのベストアーム識別において、アルゴリズムは、できるだけ早く特定の精度で、最高平均報酬の腕を見つけることを任務とする。 マルチフィデリティのベストアーム識別について検討し、低コストで低いフィデリティ(正確な平均推定値を持たない)で腕をサンプリングすることを選択できる。 この問題に対処するためのいくつかの方法が提案されているが、その最適性は、特に最適な腕を特定するのに必要な総コストのゆるやかな下限のため、未解決のままである。
  論文  参考訳（メタデータ） (2024-06-05T08:02:40Z)
• Best Arm Identification in Batched Multi-armed Bandit Problems [3.908867017036043]
  近年のマルチアームバンディット問題は、多くの実生活シナリオにおいて、腕をバッチでサンプリングする必要がある。 最適な腕の識別に異なる理論的設定の目的を組み込むことができる一般的な線形プログラミングフレームワークを導入する。 数値実験により,UCB型サンプリング法やトンプソン型サンプリング法と比較して,アルゴリズムの性能も良好であることを示した。
  論文  参考訳（メタデータ） (2023-12-21T14:16:38Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。 これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。 合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
  論文  参考訳（メタデータ） (2022-02-09T06:05:05Z)
• Multi-armed Bandit Algorithms on System-on-Chip: Go Frequentist or Bayesian? [0.0]
  Multi-armed Bandit (MAB)アルゴリズムは、複数の腕の中で最高の腕を識別する。 再構成可能でインテリジェントなMAB(RI-MAB)フレームワークを提案する。
  論文  参考訳（メタデータ） (2021-06-05T10:07:31Z)
• Adaptive Algorithms for Multi-armed Bandit with Composite and Anonymous Feedback [32.62857394584907]
  複合および匿名フィードバックによるマルチアームバンディット(MAB)問題を研究する。 本稿では,逆の場合と非逆の場合の適応アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-12-13T12:25:41Z)
• On Regret with Multiple Best Arms [12.315392649501101]
  バンディット設定における複数のベスト/ニア最適アームの存在に関する後悔問題について検討する。 我々の目標は、問題の未知の硬さに自動的に適応できるアルゴリズムを設計することです。
  論文  参考訳（メタデータ） (2020-06-26T04:01:46Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)

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

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