論文の概要: Nearly-Optimal Algorithm for Adversarial Kernelized Bandits

• arxiv url: http://arxiv.org/abs/2605.10299v1
• Date: Mon, 11 May 2026 09:56:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-12 23:28:50.715755
• Title: Nearly-Optimal Algorithm for Adversarial Kernelized Bandits
• Title（参考訳）: 逆角化帯域に対する準最適アルゴリズム
• Authors: Shogo Iwazaki,
• Abstract要約: 本稿では,敵対的環境下での核化バンディット(ガウス過程バンディットとも呼ばれる)について検討する。 指数関数的重み付けアルゴリズムは$tildeO(sqrtT _T)$逆後悔を達成し,$T$と$_T$はラウンド数と最大情報ゲインを示す。
• 参考スコア（独自算出の注目度）: 5.753274939310764
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper studies kernelized bandits (also known as Gaussian process bandits) in an adversarial environment, where the reward functions in a known reproducing kernel Hilbert space (RKHS) may be adversarially chosen at each round. We show that the exponential-weight algorithm achieves $\tilde{O}(\sqrt{T γ_T})$ adversarial regret, where $T$ and $γ_T$ denote the number of total rounds and the maximum information gain, respectively. For squared exponential (SE) and $ν$-Matérn kernels, we also show algorithm-independent lower bounds that guarantee the optimality of our algorithm up to polylogarithmic factors. Furthermore, we present a computationally efficient variant of our algorithm using Nyström approximation while maintaining nearly optimal regret guarantees.
• Abstract（参考訳）: 本稿では,各ラウンドにおいて,既知の再生カーネルヒルベルト空間(RKHS)における報酬関数を逆選択できる対向環境において,カーネル化された帯域幅(ガウス過程帯域幅(Gaussian process bandits))を研究する。 指数重み付きアルゴリズムは、それぞれラウンド数と情報ゲインの最大値を表す$T$と$γ_T$の対逆後悔を達成できることを示す。 平方指数 (SE) と$ν$-Matérn のカーネルに対しては、アルゴリズムの最適性を保証するアルゴリズムに依存しない下界も示している。 さらに,Nyström近似を用いたアルゴリズムの計算効率のよい変種を提案する。

関連論文リスト

• Efficient kernelized bandit algorithms via exploration distributions [13.86858382375188]
  我々はGP-Genericと呼ばれる計算効率のよい並列化帯域幅アルゴリズムのクラスを提案する。 提案アルゴリズムは, $tildeO(gamma_TsqrtT)$ regret bounds を実現するための,幅広い具体的なアルゴリズムを実現する。
  論文  参考訳（メタデータ） (2025-06-11T18:23:43Z)
• Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimization [63.8557841188626]
  期待されている改善(EI)アルゴリズムは、不確実性の下で最適化するための最も一般的な戦略の1つである。 本稿では,GP予測平均を通した標準既存値を持つEIの変種を提案する。 我々のアルゴリズムは収束し、$mathcal O(gamma_TsqrtT)$の累積後悔境界を達成することを示す。
  論文  参考訳（メタデータ） (2022-03-15T13:17:53Z)
• A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian Process Bandits [118.22458816174144]
  そこで本稿では,エポックで動作するロバストな除去型アルゴリズムを提案し,探索と頻繁な切替を併用して,小さなアクションサブセットを選択し,各アクションを複数タイミングで実行する。 我々のアルゴリズムであるGP Robust Phased Elimination (RGP-PE) は、探索とエクスプロイトによる汚職に対するロバストネスのバランスに成功している。 GPバンディット設定におけるロバスト性の最初の実証的研究を行い,アルゴリズムが様々な敵攻撃に対してロバストであることを示す。
  論文  参考訳（メタデータ） (2022-02-03T21:19:36Z)
• 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)
• Optimal Order Simple Regret for Gaussian Process Bandits [6.84224661918159]
  純粋な探索アルゴリズムは既存の境界よりもかなり厳密であることを示す。 この後悔は、カーネル上の低い境界が知られている場合に、対数的に最適であることを示す。
  論文  参考訳（メタデータ） (2021-08-20T16:49:32Z)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。