論文の概要: Regret and Belief Complexity Trade-off in Gaussian Process Bandits via
Information Thresholding
- arxiv url: http://arxiv.org/abs/2003.10550v3
- Date: Mon, 21 Mar 2022 21:12:54 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-21 00:00:28.206837
- Title: Regret and Belief Complexity Trade-off in Gaussian Process Bandits via
Information Thresholding
- Title（参考訳）: 情報共有によるガウス過程帯域のレグレットと複雑度トレードオフ
- Authors: Amrit Singh Bedi, Dheeraj Peddireddy, Vaneet Aggarwal, Brian M.
Sadler, and Alec Koppel
- Abstract要約: GPバンディットアルゴリズムの残差境界と後部分布の複雑さのトレードオフを特徴付ける方法を示す。
大域的最適化に応用したGPバンディットアルゴリズムの精度と複雑性のトレードオフを観察する。
- 参考スコア（独自算出の注目度）: 42.669970064867556
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Bayesian optimization is a framework for global search via maximum a
posteriori updates rather than simulated annealing, and has gained prominence
for decision-making under uncertainty. In this work, we cast Bayesian
optimization as a multi-armed bandit problem, where the payoff function is
sampled from a Gaussian process (GP). Further, we focus on action selections
via upper confidence bound (UCB) or expected improvement (EI) due to their
prevalent use in practice. Prior works using GPs for bandits cannot allow the
iteration horizon $T$ to be large, as the complexity of computing the posterior
parameters scales cubically with the number of past observations. To circumvent
this computational burden, we propose a simple statistical test: only
incorporate an action into the GP posterior when its conditional entropy
exceeds an $\epsilon$ threshold. Doing so permits us to precisely characterize
the trade-off between regret bounds of GP bandit algorithms and complexity of
the posterior distributions depending on the compression parameter $\epsilon$
for both discrete and continuous action sets. To best of our knowledge, this is
the first result which allows us to obtain sublinear regret bounds while still
maintaining sublinear growth rate of the complexity of the posterior which is
linear in the existing literature. Moreover, a provably finite bound on the
complexity could be achieved but the algorithm would result in
$\epsilon$-regret which means $\textbf{Reg}_T/T \rightarrow
\mathcal{O}(\epsilon)$ as $T\rightarrow \infty$. Experimentally, we observe
state of the art accuracy and complexity trade-offs for GP bandit algorithms
applied to global optimization, suggesting the merits of compressed GPs in
bandit settings.
- Abstract（参考訳）: ベイズ最適化は、シミュレーションされたアニーリングではなく、最大1回の更新によるグローバル検索のためのフレームワークであり、不確実性の下での意思決定の優位性を高めている。
本研究では,gaussian process (gp) からペイオフ関数をサンプリングしたマルチアームバンディット問題としてベイズ最適化を適用した。
さらに,本研究は,高信頼境界 (UCB) や期待改善 (EI) による行動選択に着目した。
バンドイットにGPを用いた以前の研究では、過去の観測回数と計算の複雑さが3倍にスケールするため、イテレーションの地平線が$T$になることができない。
この計算負担を回避するため,条件エントロピーが$\epsilon$閾値を超える場合にのみ,GP後部に作用を組み込むという単純な統計的テストを提案する。
これにより、GPバンディットアルゴリズムの残差境界と、離散的および連続的なアクションセットの圧縮パラメータ$\epsilon$に依存する後続分布の複雑さとの間のトレードオフを正確に特徴づけることができる。
私たちの知る限りでは、これは既存の文献では線形である後方の複雑さのsublinear growth rateを維持しながら、sublinear regret boundsを得ることができる最初の結果である。
さらに、複雑性の証明可能な有限境界は達成できるが、アルゴリズムは$\epsilon$-regret(つまり$\textbf{Reg}_T/T \rightarrow \mathcal{O}(\epsilon)$ as $T\rightarrow \infty$)となる。
実験では,グローバル最適化に適用したgpバンディットアルゴリズムの精度と複雑性のトレードオフを観察し,バンディット設定における圧縮gpsのメリットを示唆する。
関連論文リスト
- Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
報酬分布の分散と$B_K$の分散を利用するアルゴリズムを提案する。
Restarted Weighted$textOFUL+$とRestarted$textSAVE+$の2つの新しいアルゴリズムを紹介します。
特に、V_K$が$K$よりはるかに小さい場合、我々のアルゴリズムは、異なる設定下での非定常線形バンドレットの最先端結果よりも優れている。
論文 参考訳（メタデータ） (2024-03-15T23:36:55Z) - 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) - 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) - Weighted Gaussian Process Bandits for Non-stationary Environments [30.49357960656324]
We developed WGP-UCB, a novel UCB-type algorithm based on weighted Gaussian process regression。
鍵となる課題は、無限次元の特徴写像を扱う方法である。
重み付き最大情報ゲインに対して、普遍的上界と重み依存上界を提供する。
論文 参考訳（メタデータ） (2021-07-06T03:37:33Z) - Adversarial Robustness Guarantees for Gaussian Processes [22.403365399119107]
ガウス過程(GP)は、モデルの不確実性の原理的計算を可能にし、安全性に重要なアプリケーションに魅力的です。
境界付き摂動に対するモデル決定の不変性として定義されるGPの対向的堅牢性を分析するためのフレームワークを提案する。
我々は境界を洗練し、任意の$epsilon > 0$に対して、我々のアルゴリズムが有限個の反復で実際の値に$epsilon$-closeの値に収束することを保証していることを示す分岐とバウンドのスキームを開発する。
論文 参考訳（メタデータ） (2021-04-07T15:14:56Z) - Lenient Regret and Good-Action Identification in Gaussian Process
Bandits [43.03669155559218]
我々は、あるしきい値を超える関数値が「十分良い」という緩和された最適化基準の下で、ガウス過程(GP)バンディットの問題を研究する。
実用面では、既知のしきい値に従って1つの「良い行動」を見つけることの問題を考えるとともに、しきい値の知識を生かしたいくつかの善行動識別アルゴリズムを導入する。
論文 参考訳（メタデータ） (2021-02-11T01:16:58Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。