Fugu-MT 論文翻訳(概要): Sample Complexity Bounds for Linear Constrained MDPs with a Generative Model

論文の概要: Sample Complexity Bounds for Linear Constrained MDPs with a Generative Model

arxiv url: http://arxiv.org/abs/2507.02089v1
Date: Wed, 02 Jul 2025 19:07:37 GMT
ステータス: 翻訳完了
システム内更新日: 2025-07-04 15:37:15.091777
Title: Sample Complexity Bounds for Linear Constrained MDPs with a Generative Model
Title（参考訳）: 生成モデルを用いた線形拘束型MDPのサンプル複素性境界
Authors: Xingtu Liu, Lin F. Yang, Sharan Vaswani,
Abstract要約: 無限水平$gamma$-discounted (linear) constrained Markov decision process (CMDPs) を考える。目的は、期待累積制約の対象となる累積報酬を最大化する政策を見つけることである。ブラックボックスの制約のないMPPソルバを活用できる原始双対フレームワークを提案する。
参考スコア（独自算出の注目度）: 16.578348944264505
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We consider infinite-horizon $\gamma$-discounted (linear) constrained Markov decision processes (CMDPs) where the objective is to find a policy that maximizes the expected cumulative reward subject to expected cumulative constraints. Given access to a generative model, we propose to solve CMDPs with a primal-dual framework that can leverage any black-box unconstrained MDP solver. For linear CMDPs with feature dimension $d$, we instantiate the framework by using mirror descent value iteration (\texttt{MDVI})~\citep{kitamura2023regularization} an example MDP solver. We provide sample complexity bounds for the resulting CMDP algorithm in two cases: (i) relaxed feasibility, where small constraint violations are allowed, and (ii) strict feasibility, where the output policy is required to exactly satisfy the constraint. For (i), we prove that the algorithm can return an $\epsilon$-optimal policy with high probability by using $\tilde{O}\left(\frac{d^2}{(1-\gamma)^4\epsilon^2}\right)$ samples. We note that these results exhibit a near-optimal dependence on both $d$ and $\epsilon$. For (ii), we show that the algorithm requires $\tilde{O}\left(\frac{d^2}{(1-\gamma)^6\epsilon^2\zeta^2}\right)$ samples, where $\zeta$ is the problem-dependent Slater constant that characterizes the size of the feasible region. Finally, we instantiate our framework for tabular CMDPs and show that it can be used to recover near-optimal sample complexities in this setting.
Abstract（参考訳）: 無限水平$\gamma$-discounted (linear) constrained Markov decision process (CMDP) を考える。生成モデルへのアクセスを前提として,ブラックボックスの制約のないMPPソルバを活用可能なプリミティブ・デュアル・フレームワークを用いてCMDPを解くことを提案する。特徴次元$d$の線形CMDPに対しては、MDPソルバの例であるミラー降下値反復(\texttt{MDVI})~\citep{kitamura2023regularization} を用いて、フレームワークをインスタンス化する。結果のCMDPアルゴリズムに対して,2つのケースでサンプル複雑性境界を提供する。 (i)少額の制約違反が許される実施可能性の緩和及び (ii)厳格な実現可能性、すなわち、制約を正確に満たすために出力ポリシーが必要である。対訳対訳対訳対訳対訳対訳対 i) このアルゴリズムは, $\tilde{O}\left(\frac{d^2}{(1-\gamma)^4\epsilon^2}\right)$サンプルを用いて,高い確率で$\epsilon$-optimal Policyを返却できることを示す。これらの結果は$d$と$\epsilon$の両方にほぼ最適に依存する。対訳対訳対訳対訳対訳対訳対 (ii) このアルゴリズムには$\tilde{O}\left(\frac{d^2}{(1-\gamma)^6\epsilon^2\zeta^2}\right)$サンプルが必要である。最後に, 表状CMDPのためのフレームワークをインスタンス化し, この設定において, ほぼ最適サンプルの複雑さの回復に有効であることを示す。

関連論文リスト

Primal-Dual Sample Complexity Bounds for Constrained Markov Decision Processes with Multiple Constraints [0.0]
本稿では,遷移力学が不明な場合,CMDP(Constrained Markov Decision Processs)を$d > 1$制約で解くという課題に対処する。複数の制約を持つ無限水平CMDPのモデルベースアルゴリズムを提案する。
論文参考訳（メタデータ） (2025-03-09T20:10:35Z)
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 Average Reward MDPs [6.996002801232415]
平均回帰マルコフ決定過程(MDP)において,$varepsilon$-optimal Policyを生成モデルで学習する際のサンプル複雑性について検討した。我々は、$widetildeOleft(SAfracH (1-gamma)2varepsilon2 right)$, ここで、$H$は最適ポリシーのバイアス関数のスパンであり、$SA$は状態作用空間の濃度である。
論文参考訳（メタデータ） (2023-11-22T15:34:44Z)
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)
Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
論文参考訳（メタデータ） (2022-10-05T22:52:00Z)
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)
Settling the Sample Complexity of Model-Based Offline Reinforcement Learning [50.5790774201146]
オフライン強化学習(RL)は、事前収集されたデータを用いて、さらなる探索を行わずに学習する。事前のアルゴリズムや分析は、最適なサンプルの複雑さに悩まされるか、サンプルの最適性に到達するために高いバーンインコストがかかるかのいずれかである。モデルベース(あるいは"プラグイン")アプローチは,バーンインコストを伴わずに,最小限のサンプル複雑性を実現することを実証する。
論文参考訳（メタデータ） (2022-04-11T17:26:19Z)
Towards Painless Policy Optimization for Constrained MDPs [46.12526917024248]
我々は、無限の地平線における政策最適化、$gamma$-discounted constrained Markov decision process (CMDP)について研究する。我々の目標は、小さな制約違反で大きな期待された報酬を達成する政策を返却することである。本稿では,任意のアルゴリズムに対して,報酬の準最適性と制約違反を拘束できる汎用的原始双対フレームワークを提案する。
論文参考訳（メタデータ） (2022-04-11T15:08:09Z)
Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processes [61.11090361892306]
Reward-free reinforcement learning (RL) は、エージェントが探索中に報酬関数にアクセスできないような環境を考える。この分離は線形MDPの設定には存在しないことを示す。我々は$d$次元線形 MDP における報酬のない RL に対する計算効率の良いアルゴリズムを開発した。
論文参考訳（メタデータ） (2022-01-26T22:09:59Z)
Towards Tight Bounds on the Sample Complexity of Average-reward MDPs [39.01663172393174]
生成モデルにアクセス可能な無限水平平均回帰マルコフ決定過程の最適方針を求める。状態-作用対あたりのサンプルを$widetildeO(t_mathrmmix epsilon-3)$ (oblivious) で解決するアルゴリズムを提案する。
論文参考訳（メタデータ） (2021-06-13T17:18:11Z)
Efficiently Solving MDPs with Stochastic Mirror Descent [38.30919646721354]
線形モデルに与えられた無限水平マルコフ決定過程(MDP)を近似的に解くための統一的な枠組みを提案する。これらの結果は、より一般的なミラー降下フレームワークを用いて、単純なドメインとボックスドメインで大域的なサドルポイント問題を解くことによって達成される。
論文参考訳（メタデータ） (2020-08-28T17:58:40Z)

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

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