論文の概要: Sliding-Window Thompson Sampling for Non-Stationary Settings

• arxiv url: http://arxiv.org/abs/2409.05181v3
• Date: Sat, 14 Jun 2025 11:39:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-17 17:28:44.781173
• Title: Sliding-Window Thompson Sampling for Non-Stationary Settings
• Title（参考訳）: 非定常設定のためのスライディング・ウィンドウトンプソンサンプリング
• Authors: Marco Fiandri, Alberto Maria Metelli, Francesco Trovò,
• Abstract要約: NS-MAB(Non-stationary Multi-armed Bandits)は、シーケンシャルな意思決定問題をモデル化する。 我々は既存の作業の修正と一般化を行うNS-MABのためのトンプソンサンプリングインスパイアされたアルゴリズムを解析する。
• 参考スコア（独自算出の注目度）: 20.143361197609934
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Non-stationary multi-armed bandits (NS-MABs) model sequential decision-making problems in which the expected rewards of a set of actions, a.k.a.~arms, evolve over time. In this paper, we fill a gap in the literature by providing a novel analysis of Thompson sampling-inspired (TS) algorithms for NS-MABs that both corrects and generalizes existing work. Specifically, we study the cumulative frequentist regret of two algorithms based on sliding-window TS approaches with different priors, namely $\textit{Beta-SWTS}$ and $\textit{$\gamma$-SWGTS}$. We derive a unifying regret upper bound for these algorithms that applies to any arbitrary NS-MAB (with either Bernoulli or subgaussian rewards). Our result introduces new indices that capture the inherent sources of complexity in the learning problem. Then, we specialize our general result to two of the most common NS-MAB settings: the $\textit{abruptly changing}$ and the $\textit{smoothly changing}$ environments, showing that it matches state-of-the-art results. Finally, we evaluate the performance of the analyzed algorithms in simulated environments and compare them with state-of-the-art approaches for NS-MABs.
• Abstract（参考訳）: NS-MAB(Non-stationary multi-armed bandits)は、一連のアクションの期待される報酬(つまり、腕)が時間とともに進化するシーケンシャルな意思決定問題をモデル化する。 本稿では,既存の作業の修正と一般化を両立するNS-MABに対して,トンプソンサンプリングインスパイアされたTS(Thompson sample-inspired)アルゴリズムの新たな解析を行うことにより,文献のギャップを埋める。 具体的には、スライディングウインドウのTSアプローチに基づく2つのアルゴリズムの累積的頻繁な後悔、すなわち$\textit{Beta-SWTS}$と$\textit{$\gamma$-SWGTS}$について検討する。 我々は、任意のNS-MAB(ベルヌーイあるいはガウスの報酬を含む)に適用するこれらのアルゴリズムに対する一意的な後悔の上界を導出する。 その結果,学習問題の複雑さの原因を捉える指標が新たに導入された。 次に、私たちの一般的な結果を、最も一般的なNS-MAB設定である$\textit{abruptly changing}$と$\textit{smoothly changing}$環境の2つに特化させ、それが最先端の結果と一致することを示す。 最後に、シミュレーション環境における解析アルゴリズムの性能を評価し、NS-MABの最先端手法と比較する。

関連論文リスト

• Generalized Linear Bandits with Limited Adaptivity [12.112051468737596]
  限定適応性の制約内における一般化線形文脈帯域問題について検討する。 我々は2つのアルゴリズム, $textttB-GLinCB$ と $textttRS-GLinCB$ を提示した。
  論文  参考訳（メタデータ） (2024-04-10T08:47:57Z)
• 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)
• Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
  一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。 既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。 G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
  論文  参考訳（メタデータ） (2024-01-14T14:14:19Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Discounted Thompson Sampling for Non-Stationary Bandit Problems [13.656518163592349]
  NS-MAB(Non-stationary multi-armed bandit)問題も最近注目されている。 非定常条件の両方に対処するため,ガウシアン先行値を用いたディスカウントトンプソンサンプリング(DS-TS)を提案する。 我々のアルゴリズムは、トンプソンサンプリングに割引係数を組み込むことにより、変化に順応的に適応する。
  論文  参考訳（メタデータ） (2023-05-18T05:29:52Z)
• Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximation [69.0695698566235]
  線形関数近似による強化学習と,コスト関数の逆変化について検討した。 本稿では,未知のダイナミクスと帯域幅フィードバックの一般設定に挑戦する,計算効率のよいポリシ最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T17:26:39Z)
• ANACONDA: An Improved Dynamic Regret Algorithm for Adaptive Non-Stationary Dueling Bandits [20.128001589147512]
  本研究では,非定常デュエル帯域の問題について検討し,この問題に対する適応的動的後悔アルゴリズムを提案する。 ほぼ最適の $tildeO(sqrtStexttCW T)$ dynamic regret bound を示します。
  論文  参考訳（メタデータ） (2022-10-25T20:26:02Z)
• Bayesian decision-making under misspecified priors with applications to meta-learning [64.38020203019013]
  トンプソンサンプリングやその他のシーケンシャルな意思決定アルゴリズムは、文脈的包帯における探索と探索のトレードオフに取り組むための一般的なアプローチである。 性能は不特定な事前条件で優雅に低下することを示す。
  論文  参考訳（メタデータ） (2021-07-03T23:17:26Z)
• Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
  我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。 いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。 文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
  論文  参考訳（メタデータ） (2020-07-07T09:00:57Z)

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

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