論文の概要: An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration
of Multi-Armed Bandit
- arxiv url: http://arxiv.org/abs/2306.09202v2
- Date: Thu, 14 Dec 2023 11:01:33 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-16 04:40:31.235476
- Title: An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration
of Multi-Armed Bandit
- Title（参考訳）: 多腕バンディットの実数値組合せ型純粋探索のための最適アルゴリズム
- Authors: Shintaro Nakamura and Masashi Sugiyama
- Abstract要約: 多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。
既存のR-CPE-MABの手法は、いわゆるトランスダクティブ線形帯域の特殊な場合と見なすことができる。
本稿では,差分探索アルゴリズム (CombGapE) を提案する。
- 参考スコア（独自算出の注目度）: 65.268245109828
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the real-valued combinatorial pure exploration problem in the
stochastic multi-armed bandit (R-CPE-MAB). We study the case where the size of
the action set is polynomial with respect to the number of arms. In such a
case, the R-CPE-MAB can be seen as a special case of the so-called transductive
linear bandits. Existing methods in the R-CPE-MAB and transductive linear
bandits have a gap of problem-dependent constant terms and logarithmic terms
between the upper and lower bounds of the sample complexity, respectively. We
close these gaps by proposing an algorithm named the combinatorial gap-based
exploration (CombGapE) algorithm, whose sample complexity upper bound matches
the lower bound. Finally, we numerically show that the CombGapE algorithm
outperforms existing methods significantly.
- Abstract（参考訳）: 確率的マルチアームバンドイット(R-CPE-MAB)における実測値の組合せ純粋探索問題について検討した。
本研究では, 作用集合の大きさがアームの数に対して多項式である場合について検討する。
そのような場合、R-CPE-MABはいわゆるトランスダクティブ線形帯域の特別な場合と見なすことができる。
R-CPE-MABとトランスダクティブ線形バンドイットの既存の手法は、それぞれ、サンプル複雑性の上界と下界の間の問題依存定数項と対数項のギャップを有する。
これらのギャップを閉じるために、コンビネートギャップベース探索(combgape)アルゴリズムというアルゴリズムを提案しました。
最後に,CombGapEアルゴリズムが既存手法よりも優れていることを示す。
関連論文リスト
- Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits [55.938644481736446]
Indexed Minimum Empirical Divergence (IMED)は、マルチアームバンディット問題に対する非常に効果的なアプローチである。
UCBベースのアルゴリズムとトンプソンサンプリングを実証的に上回ることが観察されている。
我々は、LinIMEDアルゴリズムのファミリーと呼ぶIMEDアルゴリズムの新しい線形バージョンを提案する。
論文 参考訳（メタデータ） (2024-05-24T04:11:58Z) - Query-Efficient Correlation Clustering with Noisy Oracle [17.11782578276788]
共同マルチアーマッドバンド(PE-CMAB)における純粋探索のパラダイムに根ざしたオンライン学習問題の2つの新しい定式化を導入する。
我々は,サンプリング戦略と古典近似アルゴリズムを組み合わせるアルゴリズムを設計し,それらの理論的保証について検討する。
本研究は, PE-CMABの場合のクラスタリング時アルゴリズムの最初の例であり, 基礎となるオフライン最適化問題はNP-hardである。
論文 参考訳（メタデータ） (2024-02-02T13:31:24Z) - Fixed-Budget Real-Valued Combinatorial Pure Exploration of Multi-Armed
Bandit [65.268245109828]
このアルゴリズムは,アクションクラスのサイズが指数関数的に大きい場合でも,最良のアクションを識別できる最初のアルゴリズムである。
CSAアルゴリズムの誤差確率の上限は指数の対数係数までの下界と一致することを示す。
提案手法を従来手法と実験的に比較し,アルゴリズムの性能が向上したことを示す。
論文 参考訳（メタデータ） (2023-10-24T09:47:32Z) - An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。
このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。
本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-09-30T15:57:14Z) - A Fast Algorithm for PAC Combinatorial Pure Exploration [21.376800678915558]
我々は,高い報酬を得た集合や腕の発見に対処する,CPE( Combinatorial Pure Exploration)の問題を考える。
この問題に対する従来のアルゴリズムは非常に計算集約的であり、軽度に大きな問題であっても実用的ではない。
計算量的に軽量であり,数万のアームを持つ問題に容易に適用可能な新しいCPEアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-12-08T09:52:56Z) - Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。
我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。
標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
論文 参考訳（メタデータ） (2021-07-09T16:04:24Z) - Combinatorial Pure Exploration with Bottleneck Reward Function and its
Extension to General Reward Functions [13.982295536546728]
ボトルネック報酬関数 (CPE-B) を用いたコンビネーションピュア探索問題について, 一定の信頼性と固定予算設定の下で検討する。
固定信頼と固定バジェットのアルゴリズムを両立させ,固定信頼設定のサンプル複雑性を低く設定する。
さらに、CPE-Bを一般報酬関数(CPE-G)に拡張し、非自明なサンプル複雑性を持つ一般非線形報酬関数に対する最初の固定信頼アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-02-24T06:47:51Z) - Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit
Feedback [51.21673420940346]
コンビナーシャルバンディットはマルチアームバンディットを一般化し、エージェントが腕のセットを選択し、選択したセットに含まれる各腕の騒々しい報酬を観察します。
我々は, 最善の腕を一定の信頼度で識別する純粋爆発問題と, 応答集合の構造が動作集合の1つと異なるような, より一般的な設定に注目する。
有限多面体に対するプロジェクションフリーオンライン学習アルゴリズムに基づいて、凸的に最適であり、競争力のある経験的性能を持つ最初の計算効率の良いアルゴリズムである。
論文 参考訳（メタデータ） (2021-01-21T10:35:09Z) - An Empirical Process Approach to the Union Bound: Practical Algorithms
for Combinatorial and Linear Bandits [34.06611065493047]
本稿では、信頼度と予算設定の固定化において、純探索線形帯域問題に対する近似アルゴリズムを提案する。
サンプルの複雑性がインスタンスの幾何でスケールし、アームの数に縛られた明示的な結合を避けるアルゴリズムを提供する。
また,固定予算設定における線形帯域幅に対する最初のアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-21T00:56:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。