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

• arxiv url: http://arxiv.org/abs/2506.18186v2
• Date: Sun, 19 Oct 2025 18:24:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-25 00:56:38.420787
• 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) における資源配分について,未知および非定常力学の下で検討する。 我々は,時変カーネルに適応しながら計算効率を保ちながら,スライディング・ウィンドウ・オンラインウィトル (SW-Whittle) ポリシーを提案する。 我々のアルゴリズムは一貫してベースラインを上回り、様々な非定常環境において最も低い累積的後悔を達成している。
• 参考スコア（独自算出の注目度）: 24.314013749328677
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study optimal resource allocation in restless multi-armed bandits (RMABs) under unknown and non-stationary dynamics. Solving RMABs optimally is PSPACE-hard even with full knowledge of model parameters, and while the Whittle index policy offers asymptotic optimality with low computational cost, it requires access to stationary transition kernels - an unrealistic assumption in many applications. To address this challenge, we propose a Sliding-Window Online Whittle (SW-Whittle) policy that remains computationally efficient while adapting to time-varying kernels. Our algorithm achieves a dynamic regret of $\tilde O(T^{2/3}\tilde V^{1/3}+T^{4/5})$ for large RMABs, where $T$ is the number of episodes and $\tilde V$ is the total variation distance between consecutive transition kernels. Importantly, we handle the challenging case where the variation budget is unknown in advance by combining a Bandit-over-Bandit framework with our sliding-window design. Window lengths are tuned online as a function of the estimated variation, while Whittle indices are computed via an upper-confidence-bound of the estimated transition kernels and a bilinear optimization routine. Numerical experiments demonstrate that our algorithm consistently outperforms baselines, achieving the lowest cumulative regret across a range of non-stationary environments.
• Abstract（参考訳）: 本研究では,レスレスマルチアームバンド (RMAB) における資源配分について,未知および非定常力学の下で検討する。 RMABを最適に解くことは、モデルパラメータの完全な知識を持つにもかかわらず、PSPACE-hardであり、Whittleインデックスポリシーは計算コストの低い漸近的最適性を提供するが、多くのアプリケーションにおいて定常遷移カーネルへのアクセスを必要とする。 この課題に対処するために、時変カーネルに適応しながら計算効率を保ちながらSliding-Window Online Whittle (SW-Whittle) ポリシーを提案する。 我々のアルゴリズムは、大きなRMABに対して$\tilde O(T^{2/3}\tilde V^{1/3}+T^{4/5})$を動的に後悔させる。 重要なことは、Bandit-over-Banditフレームワークとスライディングウインドウ設計を組み合わせることで、事前に変動予算が不明な場合に対処する。 ウィンドウ長は推定変動の関数としてオンラインで調整され、Whittleインデックスは推定された遷移カーネルの上層信頼バウンドと双線形最適化ルーチンを介して計算される。 数値実験により,本アルゴリズムはベースラインを一貫して上回り,非定常環境において最小の累積後悔を達成できることが示された。

関連論文リスト

• 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)
• Large-scale Optimization of Partial AUC in a Range of False Positive Rates [51.12047280149546]
  ROC曲線 (AUC) の下の領域は、機械学習において最も広く使われている分類モデルのパフォーマンス指標の1つである。 近年の封筒平滑化技術に基づく効率的な近似勾配降下法を開発した。 提案アルゴリズムは,効率のよい解法を欠くランク付けされた範囲損失の和を最小化するためにも利用できる。
  論文  参考訳（メタデータ） (2022-03-03T03:46:18Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。 DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
  論文  参考訳（メタデータ） (2021-07-06T21:59:49Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-01T18:43:32Z)
• 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)

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

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