論文の概要: Near-Optimal Sample Complexity Bounds for Constrained Average-Reward MDPs

• arxiv url: http://arxiv.org/abs/2509.16586v1
• Date: Sat, 20 Sep 2025 09:19:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-23 18:58:15.873181
• Title: Near-Optimal Sample Complexity Bounds for Constrained Average-Reward MDPs
• Title（参考訳）: 制約付き平均逆MDPにおける近距離サンプル複雑度境界
• Authors: Yukuan Wei, Xudong Li, Lin F. Yang,
• Abstract要約: 制約付き平均回帰MDPにおける$epsilon$-optimal Policyを生成モデルで学習する際のサンプル複雑性について検討した。 本結果は,制約付き平均回帰MDPの複雑性の理解における理論的ギャップを埋めるものである。
• 参考スコア（独自算出の注目度）: 6.237808815887583
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recent advances have significantly improved our understanding of the sample complexity of learning in average-reward Markov decision processes (AMDPs) under the generative model. However, much less is known about the constrained average-reward MDP (CAMDP), where policies must satisfy long-run average constraints. In this work, we address this gap by studying the sample complexity of learning an $\epsilon$-optimal policy in CAMDPs under a generative model. We propose a model-based algorithm that operates under two settings: (i) relaxed feasibility, which allows small constraint violations, and (ii) strict feasibility, where the output policy satisfies the constraint. We show that our algorithm achieves sample complexities of $\tilde{O}\left(\frac{S A (B+H)}{ \epsilon^2}\right)$ and $\tilde{O} \left(\frac{S A (B+H)}{\epsilon^2 \zeta^2} \right)$ under the relaxed and strict feasibility settings, respectively. Here, $\zeta$ is the Slater constant indicating the size of the feasible region, $H$ is the span bound of the bias function, and $B$ is the transient time bound. Moreover, a matching lower bound of $\tilde{\Omega}\left(\frac{S A (B+H)}{ \epsilon^2\zeta^2}\right)$ for the strict feasibility case is established, thus providing the first minimax-optimal bounds for CAMDPs. Our results close the theoretical gap in understanding the complexity of constrained average-reward MDPs.
• Abstract（参考訳）: 近年の進歩は、生成モデルに基づく平均回帰マルコフ決定過程(AMDP)における学習のサンプル複雑さの理解を著しく改善した。 しかし、政策が長期平均制約を満たさなければならない制約付き平均回帰MDP(CAMDP)についてはあまり知られていない。 本研究では,CAMDP における$\epsilon$-optimal policy を生成モデルで学習する際のサンプル複雑性について検討し,このギャップに対処する。 本稿では,2つの設定の下で動作可能なモデルベースアルゴリズムを提案する。 (i)制限違反の少ない実施性、及び (ii) 出力ポリシが制約を満たす厳格な実現可能性。 本アルゴリズムは, 緩和および厳密な実現性設定の下で, $\tilde{O}\left(\frac{S A (B+H)}{ \epsilon^2}\right)$ および $\tilde{O} \left(\frac{S A (B+H)}{\epsilon^2 \zeta^2} \right)$ のサンプル複素量を達成することを示す。 ここで、$\zeta$は実現可能な領域のサイズを示すスレーター定数であり、$H$はバイアス関数のスパンバウンドであり、$B$は過渡時間バウンドである。 さらに、厳密な実現可能性の場合、$\tilde{\Omega}\left(\frac{S A (B+H)}{ \epsilon^2\zeta^2}\right)$の一致した下界が確立され、CAMDP に対する最初のミニマックス最適境界が提供される。 本結果は,制約付き平均回帰MDPの複雑性の理解における理論的ギャップを埋めるものである。

関連論文リスト

• Sample Complexity Bounds for Linear Constrained MDPs with a Generative Model [16.578348944264505]
  無限水平$gamma$-discounted (linear) constrained Markov decision process (CMDPs) を考える。 目的は、期待累積制約の対象となる累積報酬を最大化する政策を見つけることである。 ブラックボックスの制約のないMPPソルバを活用できる原始双対フレームワークを提案する。
  論文  参考訳（メタデータ） (2025-07-02T19:07:37Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs [6.996002801232415]
  平均回帰マルコフ決定過程(MDP)において,$varepsilon$-optimal Policyを生成モデルで学習する際のサンプル複雑性について検討した。 MDP を弱通信するためには、$widetildeO(SAfracHvarepsilon2 )$, $H$ は最適ポリシーのバイアス関数のスパンであり、$SA$ は状態作用空間の濃度である。
  論文  参考訳（メタデータ） (2024-03-18T04:52:11Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。 我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
  論文  参考訳（メタデータ） (2022-12-01T15:57:58Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Near-Optimal Sample Complexity Bounds for Constrained MDPs [25.509556551558834]
  減算CMDPにおける準最適政策を学習するために,サンプルの複雑さを極小値と下位値で表す。 CMDPの学習は,少ない制約違反を許す場合と同等に容易であるが,制約違反を要求しない場合には本質的に困難であることを示す。
  論文  参考訳（メタデータ） (2022-06-13T15:58:14Z)
• Towards Tight Bounds on the Sample Complexity of Average-reward MDPs [39.01663172393174]
  生成モデルにアクセス可能な無限水平平均回帰マルコフ決定過程の最適方針を求める。 状態-作用対あたりのサンプルを$widetildeO(t_mathrmmix epsilon-3)$ (oblivious) で解決するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-13T17:18:11Z)
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity [67.02490430380415]
  モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。 また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
  論文  参考訳（メタデータ） (2020-07-15T03:25:24Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。 最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。 対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
  論文  参考訳（メタデータ） (2020-05-26T17:53:18Z)

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

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