論文の概要: Noise-Adaptive Confidence Sets for Linear Bandits and Application to
Bayesian Optimization
- arxiv url: http://arxiv.org/abs/2402.07341v1
- Date: Mon, 12 Feb 2024 00:19:09 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-13 16:07:53.540168
- Title: Noise-Adaptive Confidence Sets for Linear Bandits and Application to
Bayesian Optimization
- Title（参考訳）: 線形バンドイットの雑音適応信頼集合とベイズ最適化への応用
- Authors: Kwang-Sung Jun, Jungtaek Kim
- Abstract要約: 事前の未知のノイズレベルに適応することは、シーケンシャルな意思決定において非常に重要であるが難しい問題である。
未知のガウスパラメータ $sigma_*2$ に半適応的な新しい信頼集合を提案する。
有界報酬に対しては,先行技術により数値性能が大幅に向上した新しい分散適応型信頼セットを提案する。
- 参考スコア（独自算出の注目度）: 18.046410771894788
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Adapting to a priori unknown noise level is a very important but challenging
problem in sequential decision-making as efficient exploration typically
requires knowledge of the noise level, which is often loosely specified. We
report significant progress in addressing this issue in linear bandits in two
respects. First, we propose a novel confidence set that is `semi-adaptive' to
the unknown sub-Gaussian parameter $\sigma_*^2$ in the sense that the
(normalized) confidence width scales with $\sqrt{d\sigma_*^2 + \sigma_0^2}$
where $d$ is the dimension and $\sigma_0^2$ is the specified sub-Gaussian
parameter (known) that can be much larger than $\sigma_*^2$. This is a
significant improvement over $\sqrt{d\sigma_0^2}$ of the standard confidence
set of Abbasi-Yadkori et al. (2011), especially when $d$ is large. We show that
this leads to an improved regret bound in linear bandits. Second, for bounded
rewards, we propose a novel variance-adaptive confidence set that has a much
improved numerical performance upon prior art. We then apply this confidence
set to develop, as we claim, the first practical variance-adaptive linear
bandit algorithm via an optimistic approach, which is enabled by our novel
regret analysis technique. Both of our confidence sets rely critically on
`regret equality' from online learning. Our empirical evaluation in Bayesian
optimization tasks shows that our algorithms demonstrate better or comparable
performance compared to existing methods.
- Abstract（参考訳）: 事前の未知のノイズレベルに適応することは、シーケンシャルな意思決定において非常に重要であるが難しい問題であり、効率的な探索には、しばしば緩やかに特定されるノイズレベルに関する知識が必要である。
2つの点で線形帯域でこの問題に対処する上で大きな進歩を報告した。
まず、未知の準ガウスパラメータ $\sigma_*^2$ に対して $d$ が次元であり $\sqrt{d\sigma_*^2 + \sigma_0^2}$ が $\sigma_*^2$ よりもはるかに大きい特定のサブガウスパラメータ (既知の) であるような、未知のサブガウスパラメータ $\sigma_*^2$ に 'semi-adaptive' な新しい信頼集合を提案する。
これは Abbasi-Yadkori et al. (2011) の標準信頼集合の $\sqrt{d\sigma_0^2}$ よりも大幅に改善されている。
このことは, 線形包帯における後悔の抑制につながることを示す。
第二に, 有界報酬に対して, 先行技術における数値性能が大幅に向上した新しい分散適応信頼度セットを提案する。
次に,この信頼セットを適用し,新たな後悔分析手法によって実現される楽観的アプローチを通じて,最初の実用的分散適応線形バンディットアルゴリズムを開発する。
いずれの信頼セットも、オンライン学習の‘regret equality’に批判的に依存しています。
ベイズ最適化タスクにおける経験的評価から,提案アルゴリズムは既存手法よりも優れた性能を示した。
関連論文リスト
- 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) - Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。
本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。
我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
論文 参考訳（メタデータ） (2023-10-02T08:15:52Z) - Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises:
High-Probability Bound, In-Expectation Rate and Initial Distance Adaptation [22.758674468435302]
重尾雑音系では、勾配と真の速度の差は有限の$p-thモーメントを持つと仮定される。
本稿では,重み付き雑音を用いた非平滑凸最適化の包括的解析を行う。
論文 参考訳（メタデータ） (2023-03-22T03:05:28Z) - Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement
Learning: Adaptivity and Computational Efficiency [90.40062452292091]
本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。
我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。
また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-21T00:17:24Z) - Extra-Newton: A First Approach to Noise-Adaptive Accelerated
Second-Order Methods [57.050204432302195]
本研究では,2次スムーズな凸関数を最小化するための普遍的かつ適応的な2次法を提案する。
我々のアルゴリズムは、オラクルフィードバックが分散$sigma2$であるときに$O(sigma / sqrtT)$収束を達成し、決定論的オラクルで$O(1 / T3)$に収束を改善する。
論文 参考訳（メタデータ） (2022-11-03T14:12:51Z) - Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。
逆汚染レベルに適応する分散認識アルゴリズムをC$で提案する。
論文 参考訳（メタデータ） (2021-10-25T02:53:24Z) - Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。
いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。
文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
論文 参考訳（メタデータ） (2020-07-07T09:00:57Z) - Differentiable Linear Bandit Algorithm [6.849358422233866]
アッパー信頼境界は、線形多腕バンディット問題の最も一般的な方法である。
勾配上昇による信頼度を学習できる勾配推定器を導入する。
提案アルゴリズムは,腕の特徴の次元を$d$で,信頼度を$hatbeta$で学習したサイズを$tildemathcalO(hatbetasqrtdT)$上限とする。
論文 参考訳（メタデータ） (2020-06-04T16:43:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。