論文の概要: 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アルゴリズムが既存手法よりも優れていることを示す。
関連論文リスト
- Query-Efficient Correlation Clustering with Noisy Oracle [18.6999949314543]
我々は、クラスタ化すべき$n$要素を持つ一般的なクラスタリング環境について研究する。
本稿では,Y Combinatorial Multi-Armed Banditsにおける純粋探索のパラダイムに根ざしたオンライン学習問題の2つの新しい定式化を提案する。
論文 参考訳(メタデータ) (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) - GBOSE: Generalized Bandit Orthogonalized Semiparametric Estimation [3.441021278275805]
そこで本稿では,半パラメトリック報酬モデルを用いた新たなアルゴリズムを提案する。
我々の研究は、同じアクションフィルタリング法に基づいて構築されたアルゴリズムを提案することによって、同様の報酬モデルを用いて、最先端の複雑さの別の代表的アルゴリズムの範囲を広げる。
本研究は,2本以上の腕を持つ症例に対して,既知の半パラメトリックバンディットアルゴリズムから,これらの手法の優位性を確認するためのシミュレーション結果と,その上界の複雑さを導出したものである。
論文 参考訳(メタデータ) (2023-01-20T19:39:10Z) - 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) - Thompson Sampling Algorithms for Mean-Variance Bandits [97.43678751629189]
我々は平均分散MABのためのトンプソンサンプリング型アルゴリズムを開発した。
我々はまた、ガウシアンとベルヌーイの盗賊に対する包括的後悔の分析も提供する。
我々のアルゴリズムは、全てのリスク許容度に対して既存のLCBベースのアルゴリズムを著しく上回っている。
論文 参考訳(メタデータ) (2020-02-01T15:33:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。