論文の概要: Achieving O(1/N) Optimality Gap in Restless Bandits through Diffusion Approximation

• arxiv url: http://arxiv.org/abs/2410.15003v1
• Date: Sat, 19 Oct 2024 06:29:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-22 13:15:47.161991
• Title: Achieving O(1/N) Optimality Gap in Restless Bandits through Diffusion Approximation
• Title（参考訳）: 拡散近似によるレスレスバンドのO(1/N)最適ギャップの実現
• Authors: Chen Yan, Weina Wang, Lei Ying,
• Abstract要約: 有限地平線レスレスト・マルチアーマッド・バンドイット(RMAB)問題を$N$等質アームで検討する。 我々の新しい拡散解法は、LP上界よりも真の最適値に対して$O (1/sqrtN)$の最適性ギャップを達成する。 これらの洞察は、縮退の有無にかかわらず、RMABに対して$O (1/sqrtN)$Optimity gapを超えるポリシーを構築するための道を開く。
• 参考スコア（独自算出の注目度）: 21.34216861973257
• License:
• Abstract: We study the finite horizon Restless Multi-Armed Bandit (RMAB) problem with $N$ homogeneous arms, focusing on the challenges posed by degenerate RMABs, which are prevalent in practical applications. While previous work has shown that Linear Programming (LP)-based policies achieve exponentially fast convergence relative to the LP upper bound in non-degenerate models, applying these LP-based policies to degenerate RMABs results in slower convergence rates of $O(1/\sqrt{N})$. We construct a diffusion system that incorporates both the mean and variance of the stochastic processes, in contrast to the fluid system from the LP, which only accounts for the mean, thereby providing a more accurate representation of RMAB dynamics. Consequently, our novel diffusion-resolving policy achieves an optimality gap of $O(1/N)$ relative to the true optimal value, rather than the LP upper bound, revealing that the fluid approximation and the LP upper bound are too loose in degenerate settings. These insights pave the way for constructing policies that surpass the $O(1/\sqrt{N})$ optimality gap for any RMAB, whether degenerate or not.
• Abstract（参考訳）: N$均質なアームを用いた有限地平線レスレスト・マルチアーマッド・バンドイット(RMAB)問題について検討し, RMABの退化に伴う課題に着目した。 従来の研究は、線形プログラミング(LP)に基づくポリシーが非退化モデルにおけるLP上界に対して指数関数的に高速収束を達成することを示したが、これらのLPベースのポリシーを適用してRMABを退化させると、O(1/\sqrt{N})$の収束が遅くなることを示した。 本研究では,平均値のみを考慮に入れたLPからの流体系とは対照的に,確率過程の平均値と分散値の両方を組み込んだ拡散系を構築し,RMAB力学のより正確な表現を提供する。 その結果, この拡散解法は, LP上界よりも真の最適値に対して$O(1/N)$の最適性ギャップを達成し, 流動近似とLP上界は縮退した設定では小さすぎることが明らかとなった。 これらの洞察は、縮退するか否かに関わらず、任意のRMABに対して$O(1/\sqrt{N})$Optimity gapを超えるポリシーを構築するための道を開く。

関連論文リスト

• Sample-Efficient Constrained Reinforcement Learning with General Parameterization [35.22742439337603]
  エージェントの目標は、無限の地平線上で期待される割引報酬の和を最大化することである。 我々は,世界最適性ギャップを$epsilon$で保証し,制約違反を$epsilon$で保証するPrimal-Dual Accelerated Natural Policy Gradient (PD-ANPG)アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-05-17T08:39:05Z)
• Improved Communication-Privacy Trade-offs in $L_2$ Mean Estimation under Streaming Differential Privacy [47.997934291881414]
  既存の平均推定スキームは、通常、$L_infty$幾何に最適化され、ランダムな回転や、$L$幾何に適応するカシンの表現に依存する。 本稿では,スパシフィケーションに固有のランダム性をDPに組み込んだ,スパシフィケーションガウシアン機構の新たなプライバシ会計手法を提案する。 従来の手法とは異なり、我々の会計アルゴリズムは直接$L$幾何で動作し、ガウスの機構に迅速に収束するMSEが得られる。
  論文  参考訳（メタデータ） (2024-05-02T03:48:47Z)
• Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation [53.17668583030862]
  一般関数近似の文脈において,無限水平平均逆マルコフ決定過程(AMDP)について検討する。 最適化最適化(LOOP)と呼ばれる新しいアルゴリズムフレームワークを提案する。 我々は LOOP がサブ線形 $tildemathcalO(mathrmpoly(d, mathrmsp(V*)) sqrtTbeta )$ regret を達成することを示す。
  論文  参考訳（メタデータ） (2024-04-19T06:24:22Z)
• Theoretical guarantees on the best-of-n alignment policy [110.21094183592358]
  基本方針と最良$n$ポリシーのKL分散は、$log (n) - (n-1)/n.$と等しいことを示す。 KLの発散に対する新しい推定器を提案し、いくつかの例を通して厳密な近似を与えることを実証的に示す。
  論文  参考訳（メタデータ） (2024-01-03T18:39:13Z)
• Multi-Agent Bayesian Optimization with Coupled Black-Box and Affine Constraints [21.38692458445459]
  ブラックボックス制約と既知のアフィン制約を結合した分散マルチエージェントベイズ最適化の問題について検討する。 単一エージェントの場合と同様の後悔/違反境界を実現するアルゴリズムが提案されている。
  論文  参考訳（メタデータ） (2023-10-02T08:07:36Z)
• Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coverage [15.858892479232656]
  頑健なオフライン強化学習(ロバストオフラインRL)について検討する。 我々は、Douubly Pessimistic Model-based Policy Optimization(P2MPO$)と呼ばれる汎用アルゴリズムフレームワークを提案する。 P2MPO$は$tildemathcalO(n-1/2)$コンバーゼンスレートで、$n$はデータセットサイズである。
  論文  参考訳（メタデータ） (2023-05-16T17:58:05Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Foolish Crowds Support Benign Overfitting [20.102619493827024]
  ガウスデータによる線形回帰に対するスパース補間手順の過大なリスクの低い境界を証明した。 ここでは, 騒音の適応による害は, 様々な方向に拡げることによって改善されるが, この分析は「群衆の知恵」の利点を露呈する。
  論文  参考訳（メタデータ） (2021-10-06T16:56:37Z)
• A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs [117.82903457289584]
  有限水平マルコフ決定過程(MDPs)における新たな問題依存的下界を導出する。 我々の下界は一般の場合よりもかなり小さく、最小の作用ギャップでスケールしないことが示される。 この最後の結果($poly(H)$の条件で、$H$は地平線である)は、楽観的なアルゴリズムのポリシーギャップに基づいて、後悔の意を表すことによって達成可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-24T13:46:09Z)
• Softmax Policy Gradient Methods Can Take Exponential Time to Converge [60.98700344526674]
  Softmax Policy gradient(PG)メソッドは、現代の強化学習におけるポリシー最適化の事実上の実装の1つです。 ソフトマックス PG 法は、$mathcalS|$ および $frac11-gamma$ の観点から指数時間で収束できることを実証する。
  論文  参考訳（メタデータ） (2021-02-22T18:56:26Z)

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

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