論文の概要: 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) - 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) - Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。
我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。
標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
論文 参考訳（メタデータ） (2021-07-09T16:04:24Z) - Parallelizing Contextual Linear Bandits [82.65675585004448]
並列な)コンテキスト線形バンディットアルゴリズムの族を提示し、その遺残はそれらの完全シーケンシャルなアルゴリズムとほぼ同一である。
また,これらの並列アルゴリズムについて,材料発見や生物配列設計の問題など,いくつかの領域で実証評価を行った。
論文 参考訳（メタデータ） (2021-05-21T22:22:02Z) - 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) - An Empirical Process Approach to the Union Bound: Practical Algorithms
for Combinatorial and Linear Bandits [34.06611065493047]
本稿では、信頼度と予算設定の固定化において、純探索線形帯域問題に対する近似アルゴリズムを提案する。
サンプルの複雑性がインスタンスの幾何でスケールし、アームの数に縛られた明示的な結合を避けるアルゴリズムを提供する。
また,固定予算設定における線形帯域幅に対する最初のアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-21T00:56:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。