論文の概要: Near-Optimal Sample Complexity for Online Constrained MDPs

• arxiv url: http://arxiv.org/abs/2602.15076v1
• Date: Mon, 16 Feb 2026 05:16:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-18 16:03:17.857744
• Title: Near-Optimal Sample Complexity for Online Constrained MDPs
• Title（参考訳）: オンライン拘束型MDPにおける準最適サンプル複雑度
• Authors: Chang Liu, Yunfan Li, Lin F. Yang,
• Abstract要約: CMDP(Constrained Markov Decision Processs)は、性能を最適化しながら安全性の制約を強制するために一般的に用いられる。 既存の手法は、しばしば重大な安全違反に悩まされるか、あるいは準最適ポリシーを生成するために高いサンプルの複雑さを必要とする。 本稿では,後悔と制約違反のバランスをとるモデルベース原始双対アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 10.479589616736193
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Safety is a fundamental challenge in reinforcement learning (RL), particularly in real-world applications such as autonomous driving, robotics, and healthcare. To address this, Constrained Markov Decision Processes (CMDPs) are commonly used to enforce safety constraints while optimizing performance. However, existing methods often suffer from significant safety violations or require a high sample complexity to generate near-optimal policies. We address two settings: relaxed feasibility, where small violations are allowed, and strict feasibility, where no violation is allowed. We propose a model-based primal-dual algorithm that balances regret and bounded constraint violations, drawing on techniques from online RL and constrained optimization. For relaxed feasibility, we prove that our algorithm returns an $\varepsilon$-optimal policy with $\varepsilon$-bounded violation with arbitrarily high probability, requiring $\tilde{O}\left(\frac{SAH^3}{\varepsilon^2}\right)$ learning episodes, matching the lower bound for unconstrained MDPs. For strict feasibility, we prove that our algorithm returns an $\varepsilon$-optimal policy with zero violation with arbitrarily high probability, requiring $\tilde{O}\left(\frac{SAH^5}{\varepsilon^2ζ^2}\right)$ learning episodes, where $ζ$ is the problem-dependent Slater constant characterizing the size of the feasible region. This result matches the lower bound for learning CMDPs with access to a generative model. Our results demonstrate that learning CMDPs in an online setting is as easy as learning with a generative model and is no more challenging than learning unconstrained MDPs when small violations are allowed.
• Abstract（参考訳）: 安全は強化学習(RL)における基本的な課題であり、特に自律運転、ロボティクス、ヘルスケアといった現実世界の応用において重要である。 これを解決するために、CMDP(Constrained Markov Decision Processs)は、性能を最適化しながら安全性の制約を強制するために一般的に使用される。 しかし、既存の手法は、しばしば重大な安全違反に悩まされるか、あるいは、ほぼ最適ポリシーを生成するために、高いサンプルの複雑さを必要とする。 我々は2つの設定に対処する:緩和された実現可能性、小さな違反を許す、厳格な実現可能性、違反を許さないこと。 本稿では,オンラインRLの手法と制約付き最適化に基づいて,後悔と制約違反のバランスをとるモデルベース原始双対アルゴリズムを提案する。 緩和可能な実現可能性のために、我々のアルゴリズムは、任意に高い確率で$\varepsilon$-bounded violationを伴い、$\tilde{O}\left(\frac{SAH^3}{\varepsilon^2}\right)$学習エピソードを返却し、制約のないMDPの下位境界と一致することを証明している。 厳密な実現可能性のために、我々のアルゴリズムは、任意の確率でゼロ違反の$\varepsilon$-optimal Policyを返し、$\tilde{O}\left(\frac{SAH^5}{\varepsilon^2\right)$学習エピソードを必要とする。 この結果は、CMDPを学習するための低い境界と、生成モデルへのアクセスとを一致させる。 その結果、オンライン環境でのCMDPの学習は、生成モデルで学習するのと同じくらい簡単であり、小さな違反が許されるときの制約のないMDPの学習ほど困難ではないことが示された。

関連論文リスト

• Beyond Slater's Condition in Online CMDPs with Stochastic and Adversarial Constraints [33.41566575424402]
  本研究では, エンフォリンエピソード制約マルコフ決定過程(CMDP)について, 双方の制約下で検討した。 ストラディらによって導入された最先端のベスト・オブ・ボディーズ・アルゴリズムを大幅に改善する新しいアルゴリズムを提案する。 Slater の条件を使わずにサブリニア制約違反を保証し,インフン制約された最適値に対してサブリニア$alpha$-regret を保証する。
  論文  参考訳（メタデータ） (2025-09-24T13:38:32Z)
• Near-Optimal Sample Complexity Bounds for Constrained Average-Reward MDPs [6.237808815887583]
  制約付き平均回帰MDPにおける$epsilon$-optimal Policyを生成モデルで学習する際のサンプル複雑性について検討した。 本結果は,制約付き平均回帰MDPの複雑性の理解における理論的ギャップを埋めるものである。
  論文  参考訳（メタデータ） (2025-09-20T09:19:42Z)
• Truly No-Regret Learning in Constrained MDPs [61.78619476991494]
  未知のCMDPで学習するモデルベース原始双対アルゴリズムを提案する。 提案アルゴリズムは,誤差のキャンセルを伴わずにサブ線形後悔を実現する。
  論文  参考訳（メタデータ） (2024-02-24T09:47:46Z)
• When is Agnostic Reinforcement Learning Statistically Tractable? [76.1408672715773]
  エンフスパンニング容量と呼ばれる新しい複雑性測度は、設定された$Pi$にのみ依存し、MDPダイナミクスとは独立である。 我々は、学習するためにスーパーポリノミカルな数のサンプルを必要とする制限付きスパンリング能力を持つポリシークラス$Pi$が存在することを示した。 これにより、生成的アクセスとオンラインアクセスモデルの間の学習可能性の驚くほどの分離が明らかになる。
  論文  参考訳（メタデータ） (2023-10-09T19:40:54Z)
• Model-Free, Regret-Optimal Best Policy Identification in Online CMDPs [17.62509045102346]
  本稿では,CMDP(Constrained Markov Decision Processs)における最適ポリシー識別問題について考察する。 私たちは、モデルフリーで、後悔の少ないアルゴリズムに興味を持ち、確率の高いほぼ最適なポリシーを特定しています。 オンラインCMDPのサブ線形後悔と制約違反を伴う既存のモデルフリーアルゴリズムでは、最適ポリシーに対する収束保証は提供されない。
  論文  参考訳（メタデータ） (2023-09-27T04:33:09Z)
• 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)
• 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)
• Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approach [37.80609997145897]
  強化学習は、環境と対話しながらシーケンシャルな決定を行う必要があるアプリケーションで広く使われている。 決定要件がいくつかの安全制約を満たすことを含むと、問題はより難しくなります。 CMDP問題をモデルのない方法で解き、$epsilon$-optimal cumulative rewardを$epsilon$-factible Policyで達成することができる。 ここでの重要な疑問は、制約違反ゼロで$epsilon$-optimal cumulative rewardを達成できるかどうかである。
  論文  参考訳（メタデータ） (2021-09-13T21:27:03Z)

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

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