論文の概要: Achieving $\tilde{\mathcal{O}}(1/N)$ Optimality Gap in Restless Bandits through Gaussian Approximation
- arxiv url: http://arxiv.org/abs/2410.15003v2
- Date: Sun, 25 May 2025 18:42:22 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-27 14:32:52.839946
- Title: Achieving $\tilde{\mathcal{O}}(1/N)$ Optimality Gap in Restless Bandits through Gaussian Approximation
- Title（参考訳）: ガウス近似によるレストレスバンドにおける$\tilde{\mathcal{O}}(1/N)$Optimality Gapの達成
- Authors: Chen Yan, Weina Wang, Lei Ying,
- Abstract要約: 有限水平Multiform Armed Bandit (RMAB) 問題を$N$等質アームを用いて検討する。
我々のアプローチは、平均だけでなくRMAB力学の分散も捉えるガウス系の構築に基づいている。
これは、RMABを退化させるための$tildemathcalO (1/N)$Optimity gapを確立する最初の結果である。
- 参考スコア（独自算出の注目度）: 21.34216861973257
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the finite-horizon Restless Multi-Armed Bandit (RMAB) problem with $N$ homogeneous arms. Prior work has shown that when an RMAB satisfies a non-degeneracy condition, Linear-Programming-based (LP-based) policies derived from the fluid approximation, which captures the mean dynamics of the system, achieve an exponentially small optimality gap. However, it is common for RMABs to be degenerate, in which case LP-based policies can result in a $\Theta(1/\sqrt{N})$ optimality gap per arm. In this paper, we propose a novel Stochastic-Programming-based (SP-based) policy that, under a uniqueness assumption, achieves an $\tilde{\mathcal{O}}(1/N)$ optimality gap for degenerate RMABs. Our approach is based on the construction of a Gaussian stochastic system that captures not only the mean but also the variance of the RMAB dynamics, resulting in a more accurate approximation than the fluid approximation. We then solve a stochastic program for this system to obtain our policy. This is the first result to establish an $\tilde{\mathcal{O}}(1/N)$ optimality gap for degenerate RMABs.
- Abstract（参考訳）: 有限水平レストレス・マルチアーメッド・バンドイット(RMAB)問題を$N$等質アームで検討する。
従来の研究は、RMABが非退化条件を満たすと、系の平均力学を捉える流体近似から導かれる線形プログラミング(LPベース)ポリシーが指数的に小さな最適性ギャップを達成できることを示した。
しかし、RMABは退化することが一般的であり、この場合、LPベースのポリシーは腕ごとの最適性ギャップが$\Theta(1/\sqrt{N})となる。
本稿では,Stochastic-Programming-based (SP-based) ポリシーを提案する。これは一意性仮定の下で,RMABを退化するための$\tilde{\mathcal{O}}(1/N)$の最適性ギャップを実現する。
我々のアプローチは、平均だけでなくRMABダイナミクスの分散も捉えるガウス確率系の構築に基づいており、結果として流体近似よりも正確な近似が得られる。
そして、このシステムのための確率的プログラムを解き、ポリシーを得る。
これは、縮退RMABに対する$\tilde{\mathcal{O}}(1/N)$Optimity gapを確立する最初の結果である。
関連論文リスト
- Nearly Optimal Sample Complexity of Offline KL-Regularized Contextual Bandits under Single-Policy Concentrability [49.96531901205305]
我々は,オフラインの文脈的包帯に対する単一政治中心性の下でのサンプル複雑性を$tildeO(epsilon-1)$とするemphfirstアルゴリズムを提案する。
我々の証明は、KL正則化の強い凸性と、真の報酬と悲観的推定子のギャップの条件的非負性を利用する。
我々は,このアルゴリズムを文脈的デュエル帯域に拡張し,ほぼ最適なサンプル複雑性を実現する。
論文 参考訳（メタデータ） (2025-02-09T22:14:45Z) - 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) - Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraints [26.008426384903764]
オフライン強化学習(RL)は、事前に収集されたデータセットを使用して、マルコフ決定プロセス(MDP)の最適ポリシーを見つけることを目的としている。
本研究では,オフラインRLにおけるマルコフ決定過程の線形プログラミング (LP) の再検討を行う。
論文 参考訳（メタデータ） (2022-12-28T15:28:12Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。