論文の概要: Efficient kernelized bandit algorithms via exploration distributions
- arxiv url: http://arxiv.org/abs/2506.10091v1
- Date: Wed, 11 Jun 2025 18:23:43 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-13 15:37:22.383752
- Title: Efficient kernelized bandit algorithms via exploration distributions
- Title（参考訳）: 探索分布を用いた効率的なカーネル化バンディットアルゴリズム
- Authors: Bingshan Hu, Zheng He, Danica J. Sutherland,
- Abstract要約: 我々はGP-Genericと呼ばれる計算効率のよい並列化帯域幅アルゴリズムのクラスを提案する。
提案アルゴリズムは, $tildeO(gamma_TsqrtT)$ regret bounds を実現するための,幅広い具体的なアルゴリズムを実現する。
- 参考スコア（独自算出の注目度）: 13.86858382375188
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider a kernelized bandit problem with a compact arm set ${X} \subset \mathbb{R}^d $ and a fixed but unknown reward function $f^*$ with a finite norm in some Reproducing Kernel Hilbert Space (RKHS). We propose a class of computationally efficient kernelized bandit algorithms, which we call GP-Generic, based on a novel concept: exploration distributions. This class of algorithms includes Upper Confidence Bound-based approaches as a special case, but also allows for a variety of randomized algorithms. With careful choice of exploration distribution, our proposed generic algorithm realizes a wide range of concrete algorithms that achieve $\tilde{O}(\gamma_T\sqrt{T})$ regret bounds, where $\gamma_T$ characterizes the RKHS complexity. This matches known results for UCB- and Thompson Sampling-based algorithms; we also show that in practice, randomization can yield better practical results.
- Abstract（参考訳）: コンパクトなアームセット ${X} \subset \mathbb{R}^d $ と固定だが未知の報酬関数 $f^*$ と、一部の再生ケルネルヒルベルト空間 (RKHS) において有限ノルムを持つカーネル化された帯域問題を考える。
本稿では,GP-Genericと呼ばれる計算効率のよい帯域幅アルゴリズムのクラスを提案する。
このクラスのアルゴリズムは、特別なケースとしてアッパー信頼境界に基づくアプローチを含むが、様々なランダム化アルゴリズムも可能である。
探索分布の慎重な選択により,提案アルゴリズムは,RKHSの複雑性を特徴付けるために,$\tilde{O}(\gamma_T\sqrt{T})$ regret boundsを実現する,幅広い具体的なアルゴリズムを実現する。
これはUPBとトンプソンサンプリングに基づくアルゴリズムの既知の結果と一致し、実際にランダム化によってより実用的な結果が得られることを示す。
関連論文リスト
- Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - Misspecified Gaussian Process Bandit Optimization [59.30399661155574]
カーネル化されたバンディットアルゴリズムは、この問題に対して強い経験的および理論的性能を示した。
本稿では、未知関数を$epsilon$-一様近似で近似できるエンフェミス特定カーネル化帯域設定を、ある再生カーネルヒルベルト空間(RKHS)において有界ノルムを持つ関数で導入する。
提案アルゴリズムは,不特定性に関する事前知識を伴わず,$epsilon$への最適依存を実現する。
論文 参考訳（メタデータ） (2021-11-09T09:00:02Z) - Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。
O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。
さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
論文 参考訳（メタデータ） (2021-10-15T00:54:04Z) - Thompson Sampling for Unimodal Bandits [21.514495320038712]
本稿では, 半順序の腕に対して期待される報酬が一様であるアンフンモダル・バンディットに対するトンプソンサンプリングアルゴリズムを提案する。
ガウスの報酬に対して、我々のアルゴリズムの後悔は$mathcalO(log T)$であり、標準的なトンプソンサンプリングアルゴリズムよりもはるかに優れている。
論文 参考訳（メタデータ） (2021-06-15T14:40:34Z) - Corralling Stochastic Bandit Algorithms [54.10645564702416]
相関アルゴリズムの後悔は、最も報酬の高い腕を含む最高のアルゴリズムの後悔よりも悪くはないことを示す。
最高報酬と他の報酬の差は、最高報酬と他の報酬の差に依存することを示す。
論文 参考訳（メタデータ） (2020-06-16T15:33:12Z) - Multi-Scale Zero-Order Optimization of Smooth Functions in an RKHS [19.252319300590653]
ブラックボックス関数 $f:mathcalX mapto mathbbR$ は、$f$がよりスムーズで、与えられたカーネル $K$ に関連する RKHS の有界ノルムを持つという仮定の下で最適化される。
本稿では,H の局所多項式 (LP) 推定器を用いて通常の GP 代理モデルを拡張した新しいアルゴリズム (textttLP-GP-UCB) を提案する。
論文 参考訳（メタデータ） (2020-05-11T01:55:39Z) - Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
基本アルゴリズムを選択できるメタアルゴリズムを開発した。
基本アルゴリズムの1つが$O(sqrtT)$後悔している場合でも、一般的には$Omega(sqrtT)$後悔よりも良いものを得ることはできません。
論文 参考訳（メタデータ） (2020-03-03T18:46:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。