論文の概要: Near-Optimal Sample Complexity Bounds for Constrained MDPs
- arxiv url: http://arxiv.org/abs/2206.06270v1
- Date: Mon, 13 Jun 2022 15:58:14 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-14 14:27:22.028664
- Title: Near-Optimal Sample Complexity Bounds for Constrained MDPs
- Title（参考訳）: 制約付きmdpの最適近傍サンプル複雑性境界
- Authors: Sharan Vaswani, Lin F. Yang, Csaba Szepesv\'ari
- Abstract要約: 減算CMDPにおける準最適政策を学習するために,サンプルの複雑さを極小値と下位値で表す。
CMDPの学習は,少ない制約違反を許す場合と同等に容易であるが,制約違反を要求しない場合には本質的に困難であることを示す。
- 参考スコア（独自算出の注目度）: 25.509556551558834
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In contrast to the advances in characterizing the sample complexity for
solving Markov decision processes (MDPs), the optimal statistical complexity
for solving constrained MDPs (CMDPs) remains unknown. We resolve this question
by providing minimax upper and lower bounds on the sample complexity for
learning near-optimal policies in a discounted CMDP with access to a generative
model (simulator). In particular, we design a model-based algorithm that
addresses two settings: (i) relaxed feasibility, where small constraint
violations are allowed, and (ii) strict feasibility, where the output policy is
required to satisfy the constraint. For (i), we prove that our algorithm
returns an $\epsilon$-optimal policy with probability $1 - \delta$, by making
$\tilde{O}\left(\frac{S A \log(1/\delta)}{(1 - \gamma)^3 \epsilon^2}\right)$
queries to the generative model, thus matching the sample-complexity for
unconstrained MDPs. For (ii), we show that the algorithm's sample complexity is
upper-bounded by $\tilde{O} \left(\frac{S A \, \log(1/\delta)}{(1 - \gamma)^5
\, \epsilon^2 \zeta^2} \right)$ where $\zeta$ is the problem-dependent Slater
constant that characterizes the size of the feasible region. Finally, we prove
a matching lower-bound for the strict feasibility setting, thus obtaining the
first near minimax optimal bounds for discounted CMDPs. Our results show that
learning CMDPs is as easy as MDPs when small constraint violations are allowed,
but inherently more difficult when we demand zero constraint violation.
- Abstract（参考訳）: マルコフ決定過程(MDPs)を解くためのサンプル複雑性の特徴付けの進歩とは対照的に、制約付きMDP(CMDPs)を解くための最適な統計複雑性はいまだ不明である。
生成モデル(シミュレータ)にアクセスして割引cmdpで最適に近いポリシーを学ぶために、サンプル複雑性の最小上限と下限を提供することで、この問題を解決する。
特に、2つの設定に対処するモデルベースアルゴリズムを設計する。
(i)小さな制約違反が許容されるような緩和実現可能性
(ii)厳格な実現可能性(制約を満たすために出力ポリシが必要)
のために
i) 提案アルゴリズムは,$\tilde{O}\left(\frac{S A \log(1/\delta)}{(1 - \gamma)^3 \epsilon^2}\right)$クエリを生成モデルに適用することにより,確率 1 - \delta$ で $\epsilon$-optimal Policy を返すことを証明した。
のために
(ii) アルゴリズムのサンプルの複雑さは、$\tilde{O} \left(\frac{S A \, \log(1/\delta)}{(1- \gamma)^5 \, \epsilon^2 \zeta^2} \right)$$\zeta$は問題依存のスレーター定数であり、実現可能な領域のサイズを特徴付ける。
最後に, 厳密な実現可能性設定に対して一致した下界を証明し, 割引CMDPに対する第1の極小最適境界を求める。
以上の結果から,CMDPの学習は制約違反を許す場合と同等に容易であるが,制約違反を要求しない場合には本質的に困難であることがわかった。
関連論文リスト
- 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) - Towards Instance-Optimality in Online PAC Reinforcement Learning [28.156332484814616]
そこで本研究では,PACの同定に要するサンプルの複雑さに対する最初のインスタンス依存下限について提案する。
我々は、citeWagenmaker22linearMDPのPEDELアルゴリズムのサンプル複雑さがこの下界に近づいたことを実証する。
論文 参考訳（メタデータ） (2023-10-31T19:26:36Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - A Near-Optimal Primal-Dual Method for Off-Policy Learning in CMDP [12.37249250512371]
制約付きマルコフ決定プロセス(CMDP)は、安全な強化学習のための重要なフレームワークである。
本稿では,オフラインデータのみを利用できるCMDP問題に焦点をあてる。
単一政治集中係数$C*$の概念を採用することで、$Omegaleft(fracminleft|mathcalS||mathcalA|,|mathcalS|+Iright C*(fracminleft|mathcalS)を確立する。
論文 参考訳（メタデータ） (2022-07-13T12:13:38Z) - Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPs [24.256960622176305]
エピソードマルコフ決定過程におけるPAC RLのサンプル複雑性について, 上界と下界の整合性について検討した。
私たちの境界は、決定論的リターンギャップ(deterministic return gap)と呼ばれる状態-作用ペアに対して、新たな最適ギャップ(sub-optimality gap)を特徴とする。
彼らの設計と分析は、最小フローや最大カットといったグラフ理論の概念を含む新しいアイデアを採用している。
論文 参考訳（メタデータ） (2022-03-17T11:19:41Z) - 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) - A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs [117.82903457289584]
有限水平マルコフ決定過程(MDPs)における新たな問題依存的下界を導出する。
我々の下界は一般の場合よりもかなり小さく、最小の作用ギャップでスケールしないことが示される。
この最後の結果($poly(H)$の条件で、$H$は地平線である)は、楽観的なアルゴリズムのポリシーギャップに基づいて、後悔の意を表すことによって達成可能であることを示す。
論文 参考訳（メタデータ） (2021-06-24T13:46:09Z) - Towards Tight Bounds on the Sample Complexity of Average-reward MDPs [39.01663172393174]
生成モデルにアクセス可能な無限水平平均回帰マルコフ決定過程の最適方針を求める。
状態-作用対あたりのサンプルを$widetildeO(t_mathrmmix epsilon-3)$ (oblivious) で解決するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-06-13T17:18:11Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22: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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。