論文の概要: Non-stationary Linear Bandits Revisited
- arxiv url: http://arxiv.org/abs/2103.05324v1
- Date: Tue, 9 Mar 2021 10:07:17 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-10 14:53:16.623528
- Title: Non-stationary Linear Bandits Revisited
- Title（参考訳）: 非定常線形バンドの再訪
- Authors: Peng Zhao and Lijun Zhang
- Abstract要約: 非定常線形帯域は、時間変化の根底にある回帰パラメータを持つ線形帯域の変種である。
これらのアルゴリズムに対して,$widetildeO(T3/4(1+P_T)1/4)$ dynamic regretを証明した。
- 参考スコア（独自算出の注目度）: 26.082923174615495
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this note, we revisit non-stationary linear bandits, a variant of
stochastic linear bandits with a time-varying underlying regression parameter.
Existing studies develop various algorithms and show that they enjoy an
$\widetilde{O}(T^{2/3}(1+P_T)^{1/3})$ dynamic regret, where $T$ is the time
horizon and $P_T$ is the path-length that measures the fluctuation of the
evolving unknown parameter. However, we discover that a serious technical flaw
makes the argument ungrounded. We revisit the analysis and present a fix.
Without modifying original algorithms, we can prove an
$\widetilde{O}(T^{3/4}(1+P_T)^{1/4})$ dynamic regret for these algorithms,
slightly worse than the rate as was anticipated. We also show some
impossibility results for the key quantity concerned in the regret analysis.
Note that the above dynamic regret guarantee requires an oracle knowledge of
the path-length $P_T$. Combining the bandit-over-bandit mechanism, we can also
achieve the same guarantee in a parameter-free way.
- Abstract（参考訳）: 本稿では,時間変化に基づく回帰パラメータを持つ確率線形帯域の変種である非定常線形帯域を再検討する。
既存の研究は様々なアルゴリズムを開発し、進化した未知のパラメータの変動を測定するパス長である$T$(T^{2/3)(1+P_T)^{1/3})$ dynamic regret(英語版)を楽しんでいることを示す。
しかし、深刻な技術的欠陥が議論を根拠にしていることに気付く。
分析を再検討し、修正を加えます。
元のアルゴリズムを変更することなく、予想された速度よりもわずかに劣る$\widetilde{O}(T^{3/4)(1+P_T)^{1/4})$ dynamic regretを証明できる。
また,後悔分析の鍵となる量について,いくつかの予測不能な結果を示す。
上記の動的後悔の保証は、パス長$P_T$のオラクル知識を必要とすることに注意。
bandit-over-bandit機構を組み合わせることで、パラメータフリーな方法で同じ保証を実現できる。
関連論文リスト
- 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) - 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) - Linear bandits with polylogarithmic minimax regret [8.97780713904412]
本研究では,未知ベクトルに近づいた単位球上での動作を選択すると,サブガウス雑音パラメータが線形に消滅する線形帯域の雑音モデルについて検討する。
我々は,この問題に対するアルゴリズムを導入し,この最小限の後悔のスケーリングを,時間軸で$log3(T)$,時間軸で$T$として示す。
論文 参考訳（メタデータ） (2024-02-19T10:56:47Z) - Revisiting Weighted Strategy for Non-stationary Parametric Bandits [82.1942459195896]
本稿では,非定常パラメトリックバンディットの重み付け戦略を再考する。
より単純な重みに基づくアルゴリズムを生成する改良された分析フレームワークを提案する。
我々の新しいフレームワークは、他のパラメトリックバンディットの後悔の限界を改善するのに使える。
論文 参考訳（メタデータ） (2023-03-05T15:11:14Z) - Variance-Aware Sparse Linear Bandits [64.70681598741417]
余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。
ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。
我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
論文 参考訳（メタデータ） (2022-05-26T15:55:44Z) - Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。
いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。
文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
論文 参考訳（メタデータ） (2020-07-07T09:00:57Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z) - Simultaneously Learning Stochastic and Adversarial Episodic MDPs with
Known Transition [38.28925339231888]
我々は,世界最良保証付きの最初のアルゴリズムを開発した。
損失が逆ならば、$mathcalO(log T)$ regretを達成します。
より一般的には、中間設定で $tildemathcalO(sqrtC)$ regret を達成する。
論文 参考訳（メタデータ） (2020-06-10T01:59:34Z) - A new regret analysis for Adam-type algorithms [78.825194932103]
理論的には、オンライン凸最適化に対する後悔の保証は、急速に崩壊する$beta_1to0$スケジュールを必要とする。
最適なデータ依存リセット境界を一定の$beta_1$で導出できる新しいフレームワークを提案する。
論文 参考訳（メタデータ） (2020-03-21T19:19:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。