論文の概要: Constrained Feedback Learning for Non-Stationary Multi-Armed Bandits

• arxiv url: http://arxiv.org/abs/2509.15073v1
• Date: Thu, 18 Sep 2025 15:35:32 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-19 17:26:53.303504
• Title: Constrained Feedback Learning for Non-Stationary Multi-Armed Bandits
• Title（参考訳）: 非定常多要素帯域に対する制約付きフィードバック学習
• Authors: Shaoang Li, Jian Li,
• Abstract要約: 非定常的なマルチアームバンドは、報酬分布のシフトを検出し、応答するメカニズムを組み込むことで、エージェントが変化する環境に適応できるようにする。 本稿では,非定常マルチアームバンドにおいて,報酬フィードバックの可利用性を制限する制約付きフィードバックの新しいモデルを提案する。 本稿では,この設定において,ほぼ最適な動的後悔を実現するための,最初の事前自由なアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 9.351444106520516
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Non-stationary multi-armed bandits enable agents to adapt to changing environments by incorporating mechanisms to detect and respond to shifts in reward distributions, making them well-suited for dynamic settings. However, existing approaches typically assume that reward feedback is available at every round - an assumption that overlooks many real-world scenarios where feedback is limited. In this paper, we take a significant step forward by introducing a new model of constrained feedback in non-stationary multi-armed bandits, where the availability of reward feedback is restricted. We propose the first prior-free algorithm - that is, one that does not require prior knowledge of the degree of non-stationarity - that achieves near-optimal dynamic regret in this setting. Specifically, our algorithm attains a dynamic regret of $\tilde{\mathcal{O}}({K^{1/3} V_T^{1/3} T }/{ B^{1/3}})$, where $T$ is the number of rounds, $K$ is the number of arms, $B$ is the query budget, and $V_T$ is the variation budget capturing the degree of non-stationarity.
• Abstract（参考訳）: 非定常的なマルチアームバンドは、報酬分布のシフトを検出し、応答する機構を組み込むことで、エージェントが変化する環境に適応できるようにし、動的設定に適している。 しかし、既存のアプローチでは、通常、報酬のフィードバックはすべてのラウンドで利用できると仮定します。 本稿では,非定常型マルチアームバンドにおいて,報酬フィードバックの可利用性を制限する制約付きフィードバックの新しいモデルを導入することにより,大きな一歩を踏み出す。 非定常性の度合いの事前知識を必要としない最初の事前自由なアルゴリズムを提案し、この設定でほぼ最適な動的後悔を実現する。 具体的には、我々のアルゴリズムは、$\tilde{\mathcal{O}}({K^{1/3} V_T^{1/3} T }/{B^{1/3}})$, $T$ はラウンド数、$K$ はアーム数、$B$ はクエリ予算、$V_T$ は非定常性の度合いを測る変動予算である。

関連論文リスト

• Catoni-Style Change Point Detection for Regret Minimization in Non-Stationary Heavy-Tailed Bandits [31.212504858546232]
  ヘビーテールの片側定常バンディット問題に対処する。 重み付き分布に適した新しいカタニスタイル変化点検出戦略を提案する。 本稿では,この変化点検出戦略と楽観的アルゴリズムを組み合わせたロバストCPD-UCBを提案する。
  論文  参考訳（メタデータ） (2025-05-26T14:40:47Z)
• Continuous K-Max Bandits [54.21533414838677]
  我々は、連続的な結果分布と弱い値-インデックスフィードバックを持つ、$K$-Maxのマルチアームバンディット問題について検討する。 この設定は、レコメンデーションシステム、分散コンピューティング、サーバスケジューリングなどにおいて重要なアプリケーションをキャプチャします。 我々の重要な貢献は、適応的な離散化とバイアス補正された信頼境界を組み合わせた計算効率の良いアルゴリズムDCK-UCBである。
  論文  参考訳（メタデータ） (2025-02-19T06:37:37Z)
• 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)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• 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)
• Top $K$ Ranking for Multi-Armed Bandit with Noisy Evaluations [102.32996053572144]
  我々は,各ラウンドの開始時に,学習者が各アームの真の報酬について,ノイズのない独立した評価を受けるマルチアームバンディット・セッティングを考える。 評価の方法によって異なるアルゴリズムアプローチと理論的保証を導出する。
  論文  参考訳（メタデータ） (2021-12-13T09:48:54Z)
• Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach [42.021871809877595]
  近静止環境における最適な後悔を伴う強化学習アルゴリズムを、非定常環境における最適な動的後悔を伴う別のアルゴリズムに変換するブラックボックス還元を提案する。 提案手法は, 線形包帯, エピソードMDP, 無限水平MDPの技量を有意に改善することを示す。
  論文  参考訳（メタデータ） (2021-02-10T12:43:31Z)
• Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
  我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。 いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。 文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
  論文  参考訳（メタデータ） (2020-07-07T09:00:57Z)
• Adaptive Discretization against an Adversary: Lipschitz bandits, Dynamic Pricing, and Auction Tuning [56.23358327635815]
  リプシッツ・バンディット(Lipschitz bandits)は、大規模で構造化された行動空間を研究する多腕バンディットの顕著なバージョンである。 ここでの中心的なテーマは、アクション空間の適応的な離散化であり、より有望な領域で徐々にズームインする'である。 逆バージョンにおける適応的な離散化のための最初のアルゴリズムを提供し、インスタンス依存の後悔境界を導出する。
  論文  参考訳（メタデータ） (2020-06-22T16:06:25Z)

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

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