論文の概要: Online Learning of Whittle Indices for Restless Bandits with Non-Stationary Transition Kernels

• arxiv url: http://arxiv.org/abs/2506.18186v1
• Date: Sun, 22 Jun 2025 22:04:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-24 19:06:36.794379
• Title: Online Learning of Whittle Indices for Restless Bandits with Non-Stationary Transition Kernels
• Title（参考訳）: 非定常遷移カーネルを用いたレストレスバンドのウィトル指標のオンライン学習
• Authors: Md Kamran Chowdhury Shisher, Vishrant Tripathi, Mung Chiang, Christopher G. Brinton,
• Abstract要約: 本研究では,レスレスマルチアーム・バンディット(RMAB)の資源割り当てについて,未知の非定常的設定で検討する。 本稿では,Whittleインデックスのオンライン学習アルゴリズムを提案する。 本アルゴリズムは,非定常環境におけるベースラインと比較して,最小の累積後悔率で優れた性能を実現する。
• 参考スコア（独自算出の注目度）: 15.044145268931624
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider optimal resource allocation for restless multi-armed bandits (RMABs) in unknown, non-stationary settings. RMABs are PSPACE-hard to solve optimally, even when all parameters are known. The Whittle index policy is known to achieve asymptotic optimality for a large class of such problems, while remaining computationally efficient. In many practical settings, however, the transition kernels required to compute the Whittle index are unknown and non-stationary. In this work, we propose an online learning algorithm for Whittle indices in this setting. Our algorithm first predicts current transition kernels by solving a linear optimization problem based on upper confidence bounds and empirical transition probabilities calculated from data over a sliding window. Then, it computes the Whittle index associated with the predicted transition kernels. We design these sliding windows and upper confidence bounds to guarantee sub-linear dynamic regret on the number of episodes $T$, under the condition that transition kernels change slowly over time (rate upper bounded by $\epsilon=1/T^k$ with $k>0$). Furthermore, our proposed algorithm and regret analysis are designed to exploit prior domain knowledge and structural information of the RMABs to accelerate the learning process. Numerical results validate that our algorithm achieves superior performance in terms of lowest cumulative regret relative to baselines in non-stationary environments.
• Abstract（参考訳）: 本研究では,レスレスマルチアーム・バンディット(RMAB)の資源割り当てについて,未知の非定常的設定で検討する。 RMABは、全てのパラメータが知られている場合でも、最適に解決するPSPACEハードである。 ウィトル指数ポリシは、計算効率を保ちながら、そのような問題の大きなクラスに対して漸近的最適性を達成することが知られている。 しかし、多くの実践的な設定において、ウィトル指数を計算するのに必要な遷移カーネルは未知であり、非定常である。 本研究では,Whittleインデックスのオンライン学習アルゴリズムを提案する。 提案アルゴリズムは,スライディングウインドウ上のデータから算出した上限値と経験的遷移確率に基づいて線形最適化問題を解くことにより,現在の遷移カーネルを予測する。 そして、予測された遷移カーネルに関連するWhittleインデックスを算出する。 これらのスライディングウィンドウとアッパー信頼境界を設計し、トランジションカーネルが時間とともにゆっくりと変化するという条件の下で、エピソード数$T$($\epsilon=1/T^k$ with $k>0$)のサブ線形動的後悔を保証する。 さらに,提案アルゴリズムと後悔分析は,RMABの事前知識と構造情報を利用して学習プロセスを高速化するように設計されている。 非定常環境におけるベースラインに対する最小累積後悔率の観点から,本アルゴリズムが優れた性能を達成できることを数値計算により検証した。

関連論文リスト

• Near-Optimal Algorithm for Non-Stationary Kernelized Bandits [6.379833644595456]
  時変ベイズ最適化(英語版)とも呼ばれる非定常カーネル化バンドイット問題(KB)について検討する。 我々は,2乗指数およびマタン核を持つ非定常KBに対して,アルゴリズムに依存しない最初のリフレッシュローバウンドを示す。 本稿では,ランダムな置換による位相除去を再開する手法を提案する。
  論文  参考訳（メタデータ） (2024-10-21T14:28:26Z)
• Efficient Convex Algorithms for Universal Kernel Learning [46.573275307034336]
  カーネルの理想的な集合: 線形パラメータ化(トラクタビリティ)を認める; すべてのカーネルの集合に密着する(正確性)。 従来のカーネル最適化アルゴリズムは分類に限られており、計算に複雑なセミデフィニティプログラミング(SDP)アルゴリズムに依存していた。 本稿では,従来のSDP手法と比較して計算量を大幅に削減するSVD-QCQPQPアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-15T04:57:37Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [61.98523595657983]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Learning to Optimize with Stochastic Dominance Constraints [103.26714928625582]
  本稿では,不確実量を比較する問題に対して,単純かつ効率的なアプローチを開発する。 我々はラグランジアンの内部最適化をサロゲート近似の学習問題として再考した。 提案したライト-SDは、ファイナンスからサプライチェーン管理に至るまで、いくつかの代表的な問題において優れた性能を示す。
  論文  参考訳（メタデータ） (2022-11-14T21:54:31Z)
• An Optimization-based Algorithm for Non-stationary Kernel Bandits without Prior Knowledge [23.890686553141798]
  本研究では,非定常性の度合いの事前知識を必要としない非定常カーネル帯域幅のアルゴリズムを提案する。 我々のアルゴリズムは、非定常カーネル帯域設定に関する以前の研究よりも、より厳密な動的後悔を享受する。
  論文  参考訳（メタデータ） (2022-05-29T21:32:53Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Taming neural networks with TUSLA: Non-convex learning via adaptive stochastic gradient Langevin algorithms [0.0]
  我々は問題ランゲダイナミクス(SGLD)に基づく適切に構築された勾配アルゴリズムを提案する。 また、新しいアルゴリズムの収束特性の利用に関する漸近解析も提供する。 TUSLAアルゴリズムのルーツは、カプタメド・エウラーの発達係数を持つテーミングプロセスに基づいている。
  論文  参考訳（メタデータ） (2020-06-25T16:06:22Z)
• Better Parameter-free Stochastic Optimization with ODE Updates for Coin-Betting [31.60239268539764]
  PFSGDアルゴリズムは最適理論性能を達成しながら、学習速度の設定を必要としない。 そこで本稿では, トランク型モデル上での連続時間Coin-Bettingに基づく新しいパラメータフリーアルゴリズムにより, 経験的ギャップを埋める。 この新しいパラメータフリーアルゴリズムは「最良のデフォルト」学習率でアルゴリズムを上回り、チューニングの必要なく微調整されたベースラインの性能とほぼ一致していることを示す。
  論文  参考訳（メタデータ） (2020-06-12T23:10:25Z)

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

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