論文の概要: Variance-Dependent Regret Bounds for Non-stationary Linear Bandits

• arxiv url: http://arxiv.org/abs/2403.10732v1
• Date: Fri, 15 Mar 2024 23:36:55 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-19 22:04:53.150050
• Title: Variance-Dependent Regret Bounds for Non-stationary Linear Bandits
• Title（参考訳）: 非定常線形帯域に対する変数依存レギュレット境界
• Authors: Zhiyong Wang, Jize Xie, Yi Chen, John C. S. Lui, Dongruo Zhou,
• Abstract要約: 報酬分布の分散と$B_K$の分散を利用するアルゴリズムを提案する。 Restarted Weighted$textOFUL+$とRestarted$textSAVE+$の2つの新しいアルゴリズムを紹介します。 特に、V_K$が$K$よりはるかに小さい場合、我々のアルゴリズムは、異なる設定下での非定常線形バンドレットの最先端結果よりも優れている。
• 参考スコア（独自算出の注目度）: 52.872628573907434
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate the non-stationary stochastic linear bandit problem where the reward distribution evolves each round. Existing algorithms characterize the non-stationarity by the total variation budget $B_K$, which is the summation of the change of the consecutive feature vectors of the linear bandits over $K$ rounds. However, such a quantity only measures the non-stationarity with respect to the expectation of the reward distribution, which makes existing algorithms sub-optimal under the general non-stationary distribution setting. In this work, we propose algorithms that utilize the variance of the reward distribution as well as the $B_K$, and show that they can achieve tighter regret upper bounds. Specifically, we introduce two novel algorithms: Restarted Weighted$\text{OFUL}^+$ and Restarted $\text{SAVE}^+$. These algorithms address cases where the variance information of the rewards is known and unknown, respectively. Notably, when the total variance $V_K$ is much smaller than $K$, our algorithms outperform previous state-of-the-art results on non-stationary stochastic linear bandits under different settings. Experimental evaluations further validate the superior performance of our proposed algorithms over existing works.
• Abstract（参考訳）: 報酬分布が各ラウンドで進化する非定常確率線形帯域問題について検討する。 既存のアルゴリズムは、総変動予算$B_K$によって非定常性を特徴付けており、これは線形包帯の連続的な特徴ベクトルが$K$のラウンドで変化したことの総和である。 しかし、そのような量は報酬分布の期待に関してのみ非定常性を測定するため、既存のアルゴリズムは一般の非定常分布設定の下で最適化される。 本研究では,報酬分布の分散と$B_K$の分散を利用したアルゴリズムを提案する。 具体的には、Restarted Weighted$\text{OFUL}^+$とRestarted$\text{SAVE}^+$の2つの新しいアルゴリズムを紹介します。 これらのアルゴリズムは、各報酬の分散情報が既知の場合と未知の場合に対処する。 特に、V_K$ が$K$ よりもはるかに小さい場合、我々のアルゴリズムは、異なる設定下での非定常確率線形帯域において、過去の最先端の結果よりも優れている。 実験により,提案アルゴリズムの既存手法よりも優れた性能が得られた。

関連論文リスト

• 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)
• Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processes [59.61248760134937]
  本稿では,$tildeO(sqrtT+zeta)$を後悔するアルゴリズムを提案する。 提案アルゴリズムは、最近開発された線形文脈帯域からの不確実性重み付き最小二乗回帰に依存する。 本稿では,提案アルゴリズムをエピソディックなMDP設定に一般化し,まず汚職レベル$zeta$への付加的依存を実現する。
  論文  参考訳（メタデータ） (2022-12-12T15:04:56Z)
• Bandit Algorithms for Prophet Inequality and Pandora's Box [13.709418181148148]
  マルチアーメッド・バンディットモデルにおける預言不等式とPandoraのボックス問題について検討した。 我々の結果は、予言の不平等とPandoraのBoxの両面で、ほぼ最適の$tildeO(mathsfpoly(n)sqrtT)$トータル後悔アルゴリズムを提供する。
  論文  参考訳（メタデータ） (2022-11-16T00:10:35Z)
• Non-Stationary Bandits under Recharging Payoffs: Improved Planning with Sublinear Regret [34.44347218903429]
  マルチアームバンディット設定は、最近非定常状態において研究されている。 各アクションの平均的なペイオフは、前回のプレイ以来のラウンド数の増加しない機能である。 我々は,我々のアルゴリズムがサブ線形後悔を伴う帯域幅アルゴリズムにどのように変換されるかを示す。
  論文  参考訳（メタデータ） (2022-05-29T23:55:36Z)
• Variance-Aware Sparse Linear Bandits [64.70681598741417]
  余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。 ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。 我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
  論文  参考訳（メタデータ） (2022-05-26T15:55:44Z)
• 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)

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

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