論文の概要: A Fast Algorithm for PAC Combinatorial Pure Exploration
- arxiv url: http://arxiv.org/abs/2112.04197v1
- Date: Wed, 8 Dec 2021 09:52:56 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-09 14:36:18.620309
- Title: A Fast Algorithm for PAC Combinatorial Pure Exploration
- Title（参考訳）: PACコンビネーション純粋探索のための高速アルゴリズム
- Authors: Noa Ben-David and Sivan Sabato
- Abstract要約: 我々は,高い報酬を得た集合や腕の発見に対処する,CPE( Combinatorial Pure Exploration)の問題を考える。
この問題に対する従来のアルゴリズムは非常に計算集約的であり、軽度に大きな問題であっても実用的ではない。
計算量的に軽量であり,数万のアームを持つ問題に容易に適用可能な新しいCPEアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 21.376800678915558
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of Combinatorial Pure Exploration (CPE), which deals
with finding a combinatorial set or arms with a high reward, when the rewards
of individual arms are unknown in advance and must be estimated using arm
pulls. Previous algorithms for this problem, while obtaining sample complexity
reductions in many cases, are highly computationally intensive, thus making
them impractical even for mildly large problems. In this work, we propose a new
CPE algorithm in the PAC setting, which is computationally light weight, and so
can easily be applied to problems with tens of thousands of arms. This is
achieved since the proposed algorithm requires a very small number of
combinatorial oracle calls. The algorithm is based on successive acceptance of
arms, along with elimination which is based on the combinatorial structure of
the problem. We provide sample complexity guarantees for our algorithm, and
demonstrate in experiments its usefulness on large problems, whereas previous
algorithms are impractical to run on problems of even a few dozen arms. The
code for the algorithms and experiments is provided at
https://github.com/noabdavid/csale.
- Abstract（参考訳）: 我々は,各アームの報酬が事前に不明であり,アームプルを用いて推定する必要がある場合に,組合せ集合や腕の報酬の高い発見を扱うコンビネーショナル純粋探索(CPE)の問題を考える。
この問題の以前のアルゴリズムは、多くのケースでサンプル複雑性の低減を得るが、計算量が非常に集中しており、比較的大きな問題であっても実用的ではない。
本研究では,pac設定における新しいcpeアルゴリズムを提案する。これは計算量的に軽量であり,数万の腕を持つ問題に容易に適用できる。
これは、提案アルゴリズムがごく少数の組合せオラクル呼び出しを必要とするためである。
このアルゴリズムは、問題の組合せ構造に基づく排除とともに、連続的なアームの受け入れに基づく。
提案アルゴリズムは,大規模な問題に対して有効性を示すとともに,従来のアルゴリズムは数ダースの腕でも問題を実行するには実用的でないことを示す。
アルゴリズムと実験のコードはhttps://github.com/noabdavid/csale.comにある。
関連論文リスト
- Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳（メタデータ） (2023-12-19T13:17:43Z) - Fixed-Budget Real-Valued Combinatorial Pure Exploration of Multi-Armed
Bandit [65.268245109828]
このアルゴリズムは,アクションクラスのサイズが指数関数的に大きい場合でも,最良のアクションを識別できる最初のアルゴリズムである。
CSAアルゴリズムの誤差確率の上限は指数の対数係数までの下界と一致することを示す。
提案手法を従来手法と実験的に比較し,アルゴリズムの性能が向上したことを示す。
論文 参考訳（メタデータ） (2023-10-24T09:47:32Z) - On Universally Optimal Algorithms for A/B Testing [49.429419538826444]
ベルヌーイ報奨を伴う多腕バンディットにおける固定予算によるベストアーム識別の問題について検討する。
A/Bテスト問題としても知られる2つのアームの問題に対して,各アームを等しくサンプリングするアルゴリズムが存在しないことを証明した。
論文 参考訳（メタデータ） (2023-08-23T08:38:53Z) - An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration
of Multi-Armed Bandit [65.268245109828]
多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。
既存のR-CPE-MABの手法は、いわゆるトランスダクティブ線形帯域の特殊な場合と見なすことができる。
本稿では,差分探索アルゴリズム (CombGapE) を提案する。
論文 参考訳（メタデータ） (2023-06-15T15:37:31Z) - Practical, Provably-Correct Interactive Learning in the Realizable
Setting: The Power of True Believers [12.09273192079783]
我々は、対話型学習を実現可能な設定で検討し、最適な腕の識別からアクティブな分類に至るまでの問題に対処する一般的な枠組みを開発する。
我々は,最小限の値と対数係数とを一致させる,計算効率のよい新しいアルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-11-09T02:33:36Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Refined bounds for algorithm configuration: The knife-edge of dual class
approximability [94.83809668933021]
トレーニングセットが、トレーニングセット上でのパラメータの平均メトリックのパフォーマンスが、予想される将来的なパフォーマンスに最も近いことを保証するために、どの程度の規模が必要かを調査する。
この近似が L-無限ノルムの下で成り立つなら、強いサンプル複雑性境界を与えることができる。
我々は、コンピュータ科学において最も強力なツールの一つである整数プログラミングの文脈において、我々の限界を実証的に評価する。
論文 参考訳（メタデータ） (2020-06-21T15:32:21Z) - An Empirical Process Approach to the Union Bound: Practical Algorithms
for Combinatorial and Linear Bandits [34.06611065493047]
本稿では、信頼度と予算設定の固定化において、純探索線形帯域問題に対する近似アルゴリズムを提案する。
サンプルの複雑性がインスタンスの幾何でスケールし、アームの数に縛られた明示的な結合を避けるアルゴリズムを提供する。
また,固定予算設定における線形帯域幅に対する最初のアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-21T00:56:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。