論文の概要: Batched Kernelized Bandits: Refinements and Extensions

• arxiv url: http://arxiv.org/abs/2603.12627v1
• Date: Fri, 13 Mar 2026 03:59:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-16 17:38:11.89059
• Title: Batched Kernelized Bandits: Refinements and Extensions
• Title（参考訳）: Batched Kernelized Bandits: リファインメントと拡張
• Authors: Chenkai Ma, Keqin Chen, Jonathan Scarlett,
• Abstract要約: 我々は,ブラックボックス最適化の問題点について考察する。 アルゴリズム上の上限について (Li と Scarlett, 2022) は、B=O(log T)$ バッチが最適に近い後悔を得るのに十分であることを示している。 本稿では,ロバストなBPEアルゴリズムを提案するとともに,不規則な設定と同じ境界を生じる累積的後悔の概念を示す。
• 参考スコア（独自算出の注目度）: 35.245032604238276
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we consider the problem of black-box optimization with noisy feedback revealed in batches, where the unknown function to optimize has a bounded norm in some Reproducing Kernel Hilbert Space (RKHS). We refer to this as the Batched Kernelized Bandits problem, and refine and extend existing results on regret bounds. For algorithmic upper bounds, (Li and Scarlett, 2022) shows that $B=O(\log\log T)$ batches suffice to attain near-optimal regret, where $T$ is the time horizon and $B$ is the number of batches. We further refine this by (i) finding the optimal number of batches including constant factors (to within $1+o(1)$), and (ii) removing a factor of $B$ in the regret bound. For algorithm-independent lower bounds, noticing that existing results only apply when the batch sizes are fixed in advance, we present novel lower bounds when the batch sizes are chosen adaptively, and show that adaptive batches have essentially same minimax regret scaling as fixed batches. Furthermore, we consider a robust setting where the goal is to choose points for which the function value remains high even after an adversarial perturbation. We present the robust-BPE algorithm, and show that a suitably-defined cumulative regret notion incurs the same bound as the non-robust setting, and derive a simple regret bound significantly below that of previous work.
• Abstract（参考訳）: 本稿では,ある再生カーネルヒルベルト空間(RKHS)において,未知の関数が有界なノルムを持つような,ノイズの多いフィードバックを伴うブラックボックス最適化の問題について考察する。 我々はこれをバッチ化されたカーネル化バンドイッツ問題と呼び、後悔境界に関する既存の結果を洗練・拡張する。 アルゴリズム上の上限について、 (Li and Scarlett, 2022) は、$B=O(\log\log T)$ バッチが最適に近い後悔を達成するのに十分であることを示している。 私たちはこれをさらに洗練します。 (i)定数要素を含むバッチの最適数(1+o(1)$以内)、及び (ii)後悔の束縛でB$の要素を除去すること。 アルゴリズム非依存の下位境界については,バッチサイズが予め固定された場合にのみ既存の結果が適用できることに気付き,バッチサイズが適応的に選択された場合に新しい下位境界を示す。 さらに, 対向摂動後の関数値が高い点を選択することを目標とするロバストな設定を考察する。 本稿では,ロバストなBPEアルゴリズムを提案するとともに,既定の累積的後悔概念が非ロバストな設定と同じ境界を生じさせることを示す。

関連論文リスト

• Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedback [39.83169162678798]
  本稿では,Best-Both-Worlds (BoBW) フレームワークにおいて,逆選択遅延を用いたマルチアームバンディット問題について検討する。 我々の主な貢献は、各設定の既知の下界を個別にマッチングする新しいアルゴリズムである。 これは$sum_i>0left(log T/Delta_iright) + frac1Ksum Delta_i sigma_max$で、$Delta_i$はarm $i$と$のサブ最適ギャップである。
  論文  参考訳（メタデータ） (2025-05-30T04:05:52Z)
• Tangential Randomization in Linear Bandits (TRAiL): Guaranteed Inference and Regret Bounds [1.03590082373586]
  本稿では,線形帯域探索アルゴリズムTRAiLの提案と解析を行う。 TraiLは、設計(回帰器)行列の最小固有値によって測定された推論品質の$Omega(sqrtT)$成長を保証する。 我々は,期待された後悔に対して,任意のアルゴリズムに対して$Omega(sqrtT)$ minimax小境界を特徴付ける。
  論文  参考訳（メタデータ） (2024-11-19T01:08:13Z)
• Improved Regret for Bandit Convex Optimization with Delayed Feedback [50.46856739179311]
  遅延フィードバックを伴うバンド凸最適化(BCO)。 我々は,新しいアルゴリズムを開発し,一般にO(sqrtnT3/4+sqrtdT)$の後悔境界を満足していることを証明する。 提案アルゴリズムは,強い凸関数に対して$O((nT)2/3log/3T+dlog T)$に制限された後悔を改善することができることを示す。
  論文  参考訳（メタデータ） (2024-02-14T13:08:26Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• 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)
• Lenient Regret for Multi-Armed Bandits [72.56064196252498]
  エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。 アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。 我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
  論文  参考訳（メタデータ） (2020-08-10T08:30:52Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• Regret and Belief Complexity Trade-off in Gaussian Process Bandits via Information Thresholding [42.669970064867556]
  GPバンディットアルゴリズムの残差境界と後部分布の複雑さのトレードオフを特徴付ける方法を示す。 大域的最適化に応用したGPバンディットアルゴリズムの精度と複雑性のトレードオフを観察する。
  論文  参考訳（メタデータ） (2020-03-23T21:05:15Z)

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

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