論文の概要: Fooling Algorithms in Non-Stationary Bandits using Belief Inertia

• arxiv url: http://arxiv.org/abs/2511.05620v1
• Date: Thu, 06 Nov 2025 22:16:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-11 21:18:44.504158
• Title: Fooling Algorithms in Non-Stationary Bandits using Belief Inertia
• Title（参考訳）: 信頼慣性を用いた非定常帯域における摂食アルゴリズム
• Authors: Gal Mendelson, Eyal Tadmor,
• Abstract要約: アルゴリズムの実証的信念が、過去の報酬平均を通じてエンコードされ、変化後の新たな証拠に抵抗するモーメントをいかに生み出すかを示す。 解析を非定常性を扱うために定期的に再起動するアルゴリズムに拡張し、たとえ最悪の場合の後悔が T において線形であることを証明する。
• 参考スコア（独自算出の注目度）: 0.8307668828380427
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of worst case regret in piecewise stationary multi armed bandits. While the minimax theory for stationary bandits is well established, understanding analogous limits in time-varying settings is challenging. Existing lower bounds rely on what we refer to as infrequent sampling arguments, where long intervals without exploration allow adversarial reward changes that induce large regret. In this paper, we introduce a fundamentally different approach based on a belief inertia argument. Our analysis captures how an algorithm's empirical beliefs, encoded through historical reward averages, create momentum that resists new evidence after a change. We show how this inertia can be exploited to construct adversarial instances that mislead classical algorithms such as Explore Then Commit, epsilon greedy, and UCB, causing them to suffer regret that grows linearly with T and with a substantial constant factor, regardless of how their parameters are tuned, even with a single change point. We extend the analysis to algorithms that periodically restart to handle non stationarity and prove that, even then, the worst case regret remains linear in T. Our results indicate that utilizing belief inertia can be a powerful method for deriving sharp lower bounds in non stationary bandits.
• Abstract（参考訳）: 本研究は,複数武装包帯の断片的固定化における最悪の症例後悔の問題について考察する。 定常包帯のミニマックス理論は確立されているが、時変設定における類似の極限を理解することは困難である。 既存の下限は、探索無しの長い間隔が、大きな後悔を引き起こす敵の報酬の変化を許容する、頻度の低いサンプリング引数と呼ばれるものに依存している。 本稿では,信念的慣性論に基づく根本的に異なるアプローチを提案する。 我々の分析は、アルゴリズムの実証的な信念が、過去の報酬平均を通じてエンコードされ、変化後に新しい証拠に抵抗するモーメントをいかに生成するかを捉えます。 本研究では,従来のアルゴリズムであるExplore Then Commit, epsilon greedy, UCB を誤って導出する逆数列の構築にこの慣性を利用する方法を示す。 我々は、非定常性を扱うために定期的に再起動するアルゴリズムに解析を拡張し、なおかつ、最悪の場合の後悔がTで線形であることを証明する。

関連論文リスト

• Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback [61.49239204705301]
  本研究では,有限水平マルコフ決定過程(MDP)におけるオンライン学習について,包括的包括的包括的フィードバックモデルを用いて検討する。 本研究は, オンライン最短経路問題の近年の進展に触発された, 占領対策, 自己拘束技術, 新たな損失推定器の組合せに依拠する。
  論文  参考訳（メタデータ） (2025-10-20T02:28:08Z)
• A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial Semi-Bandits, Linear Bandits, and MDPs [18.199326045904996]
  オンライン学習のためのFTRL(Follow The Regularized Leader)の新たな分析結果を得た。 我々の新しい後悔分解は、FTRLが正則化器のヘシアンに穏やかな仮定の下で複数のラウンドで安定であることを示している。
  論文  参考訳（メタデータ） (2023-05-15T13:21:50Z)
• Revisiting Weighted Strategy for Non-stationary Parametric Bandits [82.1942459195896]
  本稿では,非定常パラメトリックバンディットの重み付け戦略を再考する。 より単純な重みに基づくアルゴリズムを生成する改良された分析フレームワークを提案する。 我々の新しいフレームワークは、他のパラメトリックバンディットの後悔の限界を改善するのに使える。
  論文  参考訳（メタデータ） (2023-03-05T15:11:14Z)
• Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPs [10.68896183306706]
  強化学習は、長期計画の地平線と未知の遷移カーネルのさらなる困難を伴って、多武装のバンディット問題を一般化する。 また, 無限水平割引マルコフ決定過程において, 逆帯域設定における最適後悔を達成するために, 徐々に変化する逆帯域設定アルゴリズムが最適後悔を達成できることを示す。
  論文  参考訳（メタデータ） (2022-05-18T16:40:30Z)
• On Slowly-varying Non-stationary Bandits [25.305949034527202]
  我々は、ゆっくりと変化する性質を持つ非定常包帯の動的後悔を考察する。 我々は、ゆっくりと変化する非定常帯域に対して、最初のインスタンス依存後悔上限を確立する。 我々のアルゴリズムは基本的にミニマックス最適であることを示す。
  論文  参考訳（メタデータ） (2021-10-25T12:56:19Z)
• Break your Bandit Routine with LSD Rewards: a Last Switch Dependent Analysis of Satiation and Seasonality [6.146046338698175]
  そこで本研究では,腕が最後に動作を切り替えて以降の時間経過によって,腕の期待される報酬が完全に決定される,新たな非定常バンディット問題を導入する。 我々のモデルは、遅延依存報酬の概念を一般化し、報酬関数に関するほとんどの仮定を緩和する。 我々はアルゴリズムを証明し、最適な非定常ポリシーに関してその後悔を証明した。
  論文  参考訳（メタデータ） (2021-10-22T14:53:13Z)
• Be Greedy in Multi-Armed Bandits [22.301793734117805]
  グレディアルゴリズムは、各ラウンドで局所最適選択を行う、シーケンシャルな決定問題の最も単純なものである。 We provide a generic worst-case bound on the regret of the Greedy algorithm。 連続・無限・多武装バンディット問題において,ほぼ最適の最悪の後悔境界を検証できることを証明した。
  論文  参考訳（メタデータ） (2021-01-04T16:47:02Z)
• Learning from History for Byzantine Robust Optimization [52.68913869776858]
  分散学習の重要性から,ビザンチンの堅牢性が近年注目されている。 既存のロバストアグリゲーションルールの多くは、ビザンチンの攻撃者がいなくても収束しない可能性がある。
  論文  参考訳（メタデータ） (2020-12-18T16:22:32Z)
• Corruption-Tolerant Gaussian Process Bandit Optimization [130.60115798580136]
  未知(典型的には非生成)関数を有界ノルムで最適化する問題を考察する。 我々は「高速だが非ローバスト」と「スロー」に基づく高速スローGP-UCBに基づくアルゴリズムを提案する。 ある種の依存関係は、汚職レベルによっては要求できない、と我々は主張する。
  論文  参考訳（メタデータ） (2020-03-04T09:46:58Z)

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

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