論文の概要: Non-Stationary Restless Multi-Armed Bandits with Provable Guarantee

• arxiv url: http://arxiv.org/abs/2508.10804v1
• Date: Thu, 14 Aug 2025 16:26:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-15 22:24:48.409017
• Title: Non-Stationary Restless Multi-Armed Bandits with Provable Guarantee
• Title（参考訳）: 保証可能な非定常レストレスマルチアームバンド
• Authors: Yu-Heng Hung, Ping-Chun Hsieh, Kai Wang,
• Abstract要約: オンラインレスレス・マルチアーム・バンディット(RMAB)は、各アームが固定状態遷移と報酬を持った静止マルコフ決定プロセス(MDP)に従うと仮定している。 医療やレコメンデーションシステムのような現実世界のアプリケーションでは、これらの仮定は静止しないダイナミクスによって壊れることが多い。 提案手法は,スライディングウィンドウ強化学習(RL)と上位信頼境界(UCB)機構を統合し,遷移力学とその変動を同時に学習する。
• 参考スコア（独自算出の注目度）: 14.201646000111868
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Online restless multi-armed bandits (RMABs) typically assume that each arm follows a stationary Markov Decision Process (MDP) with fixed state transitions and rewards. However, in real-world applications like healthcare and recommendation systems, these assumptions often break due to non-stationary dynamics, posing significant challenges for traditional RMAB algorithms. In this work, we specifically consider $N$-armd RMAB with non-stationary transition constrained by bounded variation budgets $B$. Our proposed \rmab\; algorithm integrates sliding window reinforcement learning (RL) with an upper confidence bound (UCB) mechanism to simultaneously learn transition dynamics and their variations. We further establish that \rmab\; achieves $\widetilde{\mathcal{O}}(N^2 B^{\frac{1}{4}} T^{\frac{3}{4}})$ regret bound by leveraging a relaxed definition of regret, providing a foundational theoretical framework for non-stationary RMAB problems for the first time.
• Abstract（参考訳）: オンラインレスレス・マルチアーム・バンディット(RMAB)は、通常、各腕が固定状態遷移と報酬を伴う静止マルコフ決定過程(MDP)に従うと仮定する。 しかしながら、ヘルスケアやレコメンデーションシステムのような現実世界のアプリケーションでは、これらの仮定は非定常的ダイナミクスによってしばしば失敗し、従来のRMABアルゴリズムには重大な課題が生じる。 本研究では、非定常遷移を持つ$N$-armd RMABについて、有界変動予算で制約された$B$について検討する。 提案アルゴリズムは,スライディングウィンドウ強化学習(RL)と上位信頼境界(UCB)機構を統合し,遷移力学とその変分を同時に学習する。 さらに \rmab\; が $\widetilde{\mathcal{O}}(N^2 B^{\frac{1}{4}} T^{\frac{3}{4}})$ regret bound を達成することを証明した。

関連論文リスト

• From Theory to Practice with RAVEN-UCB: Addressing Non-Stationarity in Multi-Armed Bandits through Variance Adaptation [13.490692458295301]
  RAVEN-UCBは,分散適応による理論リガーと実用効率を組み合わせた新しいアルゴリズムである。 これは UCB1 と UCB-V よりも厳密な後悔境界を達成し、ギャップ依存の残差は$K sigma_max2 log T / Delta$ であり、ギャップ非依存の残差は$sqrtK T log T$ である。
  論文  参考訳（メタデータ） (2025-06-03T14:35:04Z)
• Influential Bandits: Pulling an Arm May Change the Environment [44.71145269686588]
  現実世界のアプリケーションは、しばしば非定常環境と武器間の相互依存を含む。 本稿では,未知の,対称な正の半定値相互作用行列による腕間相互作用をモデル化する,影響力のあるバンドイット問題を提案する。 我々は,損失ダイナミクスの構造に合わせて,低信頼境界(LCB)推定器に基づく新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-04-11T02:05:51Z)
• Continuous K-Max Bandits [54.21533414838677]
  我々は、連続的な結果分布と弱い値-インデックスフィードバックを持つ、$K$-Maxのマルチアームバンディット問題について検討する。 この設定は、レコメンデーションシステム、分散コンピューティング、サーバスケジューリングなどにおいて重要なアプリケーションをキャプチャします。 我々の重要な貢献は、適応的な離散化とバイアス補正された信頼境界を組み合わせた計算効率の良いアルゴリズムDCK-UCBである。
  論文  参考訳（メタデータ） (2025-02-19T06:37:37Z)
• Combinatorial Multivariant Multi-Armed Bandits with Applications to Episodic Reinforcement Learning and Beyond [58.39457881271146]
  CMAB(Multi-armed bandits)の多変量および確率的トリガーアーム(CMAB-MT)を用いた新しい枠組みを導入する。 CMAB-MTは既存のCMABと比べ、モデリング能力を高めるだけでなく、多変量確率変数の異なる統計特性を活用することで結果を改善することができる。 本フレームワークは, エピソード強化学習(RL)や商品分布の確率的最大カバレッジなど, 応用として多くの重要な問題を含むことができる。
  論文  参考訳（メタデータ） (2024-06-03T14:48:53Z)
• Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms [59.8188496313214]
  半帯域 (CMAB) について検討し, 半帯域 (CMAB) におけるバッチサイズ (K$) の依存性の低減に着目した。 まず,確率的に引き起こされるアーム(CMAB-T)を用いたCMABの設定に対して,分散を考慮した信頼区間を持つBCUCB-Tアルゴリズムを提案する。 次に,独立アームを用いた非トリガ型CMABの設定に対して,TPVM条件の非トリガ型を利用したSESCBアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-31T13:09:39Z)
• Optimistic Whittle Index Policy: Online Learning for Restless Bandits [31.312043984489666]
  遷移力学を学習するためのWhittleインデックスポリシーに基づく,最初のオンライン学習アルゴリズムを提案する。 我々のアルゴリズムUCWhittleは、RMABを未知の遷移で解くために、サブ線形$O(sqrtT log T)$の頻繁な後悔を実現する。
  論文  参考訳（メタデータ） (2022-05-30T18:32:20Z)
• Robust Restless Bandits: Tackling Interval Uncertainty with Deep Reinforcement Learning [31.515757763077065]
  我々は、レスレス・マルチアーム・バンディット(RMAB)の一般化であるRobust Restless Banditsを紹介する。 遷移が区間不確実性によって与えられる場合、最小限の後悔目標に対する解を開発する。 RMABPPOはRMABを解くための新しい深層強化学習アルゴリズムである。
  論文  参考訳（メタデータ） (2021-07-04T17:21:26Z)
• Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss [145.54544979467872]
  マルコフ決定過程(CMDP)に対するオンライン学習の検討 本稿では,遷移モデルから標本化した軌跡のみを必要とする,新しいEmphupper confidence primal-dualアルゴリズムを提案する。 我々の分析では、ラグランジュ乗算過程の新たな高確率ドリフト解析を、高信頼強化学習の記念後悔解析に組み入れている。
  論文  参考訳（メタデータ） (2020-03-02T05:02:23Z)

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

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