論文の概要: Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs

• arxiv url: http://arxiv.org/abs/2606.14095v2
• Date: Mon, 15 Jun 2026 02:53:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-16 13:45:31.300749
• Title: Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs
• Title（参考訳）: Lyapunov-based Sample Complexity Analysis for Weakly Coupled MDPs
• Authors: Tianhao Wu, Matthew Zurek, Weina Wang, Qiaomin Xie,
• Abstract要約: We study the sample complexity of learning in average-reward weak-upupled Markov decision process (WCMDPs) and Restless Bandits (RBs)。 弱結合構造を利用することで、準最適ポリシーは、サンプルの複雑さと計算複雑性によって、$N$で学習できることが示される。
• 参考スコア（独自算出の注目度）: 20.54731804867887
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the sample complexity of learning in average-reward weakly-coupled Markov decision processes (WCMDPs) and Restless Bandits (RBs) under a generative model. Naive reduction to a tabular MDP leads to high complexity bounds as the state-action space is exponentially large in the number of arms $N$. By exploiting the weakly coupled structure, we show that near-optimal policies can be learned with sample and computational complexities that are polynomial in $N$. Specifically, we analyze the plug-in approach, which applies an efficient planning algorithm to an empirical model estimated from data. For fully heterogeneous WCMDPs, we establish the first finite-sample PAC guarantee with polynomial complexity and an $O(1/\sqrt{N})$ optimality gap. For homogeneous RBs, we further prove that a smaller optimality gap is achievable under mild structural assumptions. A primary technical contribution of our work is a novel Lyapunov-based analysis framework. Unlike classical approaches that rely on the difficult-to-control bias function, our framework uses an explicitly constructed Lyapunov function along with a drift transfer technique between the true and empirical models. A key step of independent interest in our framework is a fine-grained perturbation analysis for the underlying linear programming (LP) relaxation, which provides a general tool for analyzing LP-based policies and weakly-coupled systems.
• Abstract（参考訳）: 平均回帰弱結合マルコフ決定過程 (WCMDPs) とレストレス帯域 (RBs) における学習の複雑さについて, 生成モデルを用いて検討した。 表状MDPへのナイーブ還元は、状態作用空間が腕数$N$で指数関数的に大きいため、高い複雑性境界をもたらす。 弱結合構造を利用することで、N$の多項式である標本および計算複雑性を用いて準最適ポリシーを学習できることが示される。 具体的には、データから推定した経験的モデルに効率的な計画アルゴリズムを適用するプラグインアプローチを分析する。 完全不均一な WCMDP に対して、多項式複雑性と$O(1/\sqrt{N})$Optimity gap を持つ最初の有限サンプルPACを保証する。 均質な RB に対して、より小さな最適性ギャップは、穏やかな構造的仮定の下で達成可能であることをさらに証明する。 我々の研究の主な技術的貢献は、新しいリャプノフに基づく分析フレームワークである。 制御が難しいバイアス関数に依存する古典的アプローチとは異なり、我々のフレームワークは、真と経験的モデルの間のドリフト転送技術とともに、明示的に構築されたリャプノフ関数を使用する。 我々のフレームワークにおける独立性の重要なステップは、根底にある線形プログラミング(LP)緩和のためのきめ細かい摂動解析であり、LPベースのポリシーや弱い結合系を解析するための一般的なツールを提供する。

関連論文リスト

• Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
  ROC曲線の下の領域(AUC)は、クラス不均衡と決定制約の両方を持つ実世界のシナリオにおける重要な評価指標である。 PAUC最適化の近似ギャップを埋めるために,2つの簡単なインスタンス単位のミニマックス修正を提案する。 得られたアルゴリズムは、サンプルサイズと典型的な一方方向と双方向のPAUCに対して$O(-2/3)$の収束率の線形パーイテレーション計算複雑性を享受する。
  論文  参考訳（メタデータ） (2025-12-01T02:52:33Z)
• On The Sample Complexity Bounds In Bilevel Reinforcement Learning [49.19950489963245]
  二段階強化学習(BRL)は、生成モデルを調整するための強力なフレームワークとして登場した。 連続状態-作用複雑性において$mathcalO(epsilon)$の最初のサンプルを示す。 我々の分析は、既存の$mathcalO(epsilon)$のバウンダリで、複雑さを改善します。
  論文  参考訳（メタデータ） (2025-03-22T04:22:04Z)
• Model-Based RL for Mean-Field Games is not Statistically Harder than Single-Agent RL [57.745700271150454]
  モデルに基づく関数近似を用いた平均フィールドゲーム(MFG)における強化学習のサンプル複雑性について検討した。 本稿では、モデルクラスの複雑性を特徴付けるためのより効果的な概念である部分モデルベースエルダー次元(P-MBED)を紹介する。
  論文  参考訳（メタデータ） (2024-02-08T14:54:47Z)
• 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)
• PAC Reinforcement Learning for Predictive State Representations [60.00237613646686]
  部分的に観察可能な力学系におけるオンライン強化学習(RL)について検討する。 我々は、他のよく知られたモデルをキャプチャする表現モデルである予測状態表現(PSR)モデルに焦点を当てる。 我々は,サンプル複雑性のスケーリングにおいて,ほぼ最適なポリシを学習可能な,PSRのための新しいモデルベースアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-07-12T17:57:17Z)
• A general sample complexity analysis of vanilla policy gradient [101.16957584135767]
  政策勾配(PG)は、最も一般的な強化学習(RL)問題の1つである。 PG軌道の「バニラ」理論的理解は、RL問題を解く最も一般的な方法の1つである。
  論文  参考訳（メタデータ） (2021-07-23T19:38:17Z)
• Pessimistic Model-based Offline RL: PAC Bounds and Posterior Sampling under Partial Coverage [33.766012922307084]
  一般関数近似を用いたモデルに基づくオフライン強化学習について検討する。 本稿では、一般関数クラスを活用し、ペシミズムを符号化するために制約を用いる制約付きポリシー最適化(CPPO)というアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-07-13T16:30:01Z)

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

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