論文の概要: An Optimization-based Algorithm for Non-stationary Kernel Bandits
without Prior Knowledge
- arxiv url: http://arxiv.org/abs/2205.14775v1
- Date: Sun, 29 May 2022 21:32:53 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-31 14:06:55.478649
- Title: An Optimization-based Algorithm for Non-stationary Kernel Bandits
without Prior Knowledge
- Title(参考訳): 事前知識のない非定常カーネル帯域最適化アルゴリズム
- Authors: Kihyuk Hong, Yuhang Li, Ambuj Tewari
- Abstract要約: 本研究では,非定常性の度合いの事前知識を必要としない非定常カーネル帯域幅のアルゴリズムを提案する。
我々のアルゴリズムは、非定常カーネル帯域設定に関する以前の研究よりも、より厳密な動的後悔を享受する。
- 参考スコア(独自算出の注目度): 23.890686553141798
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose an algorithm for non-stationary kernel bandits that does not
require prior knowledge of the degree of non-stationarity. The algorithm
follows randomized strategies obtained by solving optimization problems that
balance exploration and exploitation. It adapts to non-stationarity by
restarting when a change in the reward function is detected. Our algorithm
enjoys a tighter dynamic regret bound than previous work on the non-stationary
kernel bandit setting. Moreover, when applied to the non-stationary linear
bandit setting by using a linear kernel, our algorithm is nearly minimax
optimal, solving an open problem in the non-stationary linear bandit
literature. We extend our algorithm to use a neural network for dynamically
adapting the feature mapping to observed data. We prove a dynamic regret bound
of the extension using the neural tangent kernel theory. We demonstrate
empirically that our algorithm and the extension can adapt to varying degrees
of non-stationarity.
- Abstract(参考訳): 我々は,非定常なカーネルバンドに対する事前知識を必要としないアルゴリズムを提案する。
このアルゴリズムは探索と利用のバランスをとる最適化問題を解くことによって得られるランダム化戦略に従う。
報酬関数の変化が検出されたときに再起動することで、非定常に適応する。
このアルゴリズムは、非定常カーネルバンディット設定における以前の作業よりも、より強固な動的後悔を味わう。
さらに、線形カーネルを用いて非定常線形バンドイット設定に適用した場合、このアルゴリズムは最小限の最適値であり、非定常線形バンドイット文献の開問題を解く。
我々は、観測データに特徴マッピングを動的に適応するためにニューラルネットワークを使用するようにアルゴリズムを拡張した。
我々は神経接核理論を用いて拡張の動的後悔の限界を証明する。
我々のアルゴリズムと拡張が様々な非定常性に適応できることを実証的に証明する。
関連論文リスト
- Can Decentralized Stochastic Minimax Optimization Algorithms Converge
Linearly for Finite-Sum Nonconvex-Nonconcave Problems? [56.62372517641597]
分散化されたミニマックス最適化は、幅広い機械学習に応用されているため、ここ数年で活発に研究されている。
本稿では,非コンカブ問題に対する2つの新しい分散化ミニマックス最適化アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-04-24T02:19:39Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳(メタデータ) (2023-02-01T08:50:48Z) - Non-stationary Risk-sensitive Reinforcement Learning: Near-optimal
Dynamic Regret, Adaptive Detection, and Separation Design [9.554944575754638]
エピソード非定常マルコフ決定過程(MDP)におけるエントロピー的リスク尺度に基づくリスク感受性強化学習(RL)について検討する。
本稿では,再起動型アルゴリズムであるRestart-RSMBとRestart-RSQを提案する。
この研究は、文献における非定常リスク感受性RLに対する最初の非漸近的理論解析を提供する。
論文 参考訳(メタデータ) (2022-11-19T22:40:09Z) - Lifelong Bandit Optimization: No Prior and No Regret [70.94238868711952]
我々は,過去の経験から学習することで環境に適応するアルゴリズムであるLIBOを開発した。
カーネルが未知だが、すべてのタスク間で共有されるカーネル構造を仮定する。
我々のアルゴリズムは、任意のカーネル化または線形バンディットアルゴリズムと組み合わせて、最適な性能を保証できる。
論文 参考訳(メタデータ) (2022-10-27T14:48:49Z) - On Adaptivity in Non-stationary Stochastic Optimization With Bandit
Feedback [11.208914594208654]
集約された関数の変化が事前認識されている場合、単純な再起動アルゴリズムが最適の動的後悔を達成できることが示される。
また,静止ベンチマークに対して良好な後悔を達成するアルゴリズムを,動的ベンチマークに対して良い後悔を与えるアルゴリズムに自動的に変換できることを示す。
論文 参考訳(メタデータ) (2022-10-11T16:16:34Z) - Low-rank Tensor Learning with Nonconvex Overlapped Nuclear Norm
Regularization [44.54772242784423]
低ランク学習行列に対する効率的な非正規化アルゴリズムを開発した。
提案アルゴリズムは、高価な折り畳み/折り畳み問題を回避することができる。
実験の結果,提案アルゴリズムは既存の状態よりも効率的で空間が広いことがわかった。
論文 参考訳(メタデータ) (2022-05-06T07:47:10Z) - Online Limited Memory Neural-Linear Bandits with Likelihood Matching [53.18698496031658]
本研究では,探索学習と表現学習の両方が重要な役割を果たす課題を解決するために,ニューラルネットワークの帯域について検討する。
破滅的な忘れ込みに対して耐性があり、完全にオンラインである可能性の高いマッチングアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-02-07T14:19:07Z) - Experimental Design for Regret Minimization in Linear Bandits [19.8309784360219]
オンライン・リニア・バンドレットにおける後悔を最小限に抑える設計に基づく新しいアルゴリズムを提案する。
我々は、現在最先端の有限時間後悔保証を提供し、このアルゴリズムが帯域幅と半帯域幅の両方のフィードバックシステムに適用可能であることを示す。
論文 参考訳(メタデータ) (2020-11-01T17:59:19Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳(メタデータ) (2020-10-23T09:12:47Z) - Corruption-Tolerant Gaussian Process Bandit Optimization [130.60115798580136]
未知(典型的には非生成)関数を有界ノルムで最適化する問題を考察する。
我々は「高速だが非ローバスト」と「スロー」に基づく高速スローGP-UCBに基づくアルゴリズムを提案する。
ある種の依存関係は、汚職レベルによっては要求できない、と我々は主張する。
論文 参考訳(メタデータ) (2020-03-04T09:46:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。