論文の概要: Polynomial-Time Approximability of Constrained Reinforcement Learning

• arxiv url: http://arxiv.org/abs/2502.07764v1
• Date: Tue, 11 Feb 2025 18:47:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-12 14:08:32.477894
• Title: Polynomial-Time Approximability of Constrained Reinforcement Learning
• Title（参考訳）: 制約付き強化学習における多項式時間近似可能性
• Authors: Jeremy McMahan,
• Abstract要約: 一般化されたマルコフ決定過程の近似の計算複雑性について検討する。 私たちの貢献は、最適に制約されたポリシーを見つけるための時間(0,epsilon)$-additive approximationの設計です。
• 参考スコア（独自算出の注目度）: 1.223779595809275
• License:
• Abstract: We study the computational complexity of approximating general constrained Markov decision processes. Our primary contribution is the design of a polynomial time $(0,\epsilon)$-additive bicriteria approximation algorithm for finding optimal constrained policies across a broad class of recursively computable constraints, including almost-sure, chance, expectation, and their anytime variants. Matching lower bounds imply our approximation guarantees are optimal so long as $P \neq NP$. The generality of our approach results in answers to several long-standing open complexity questions in the constrained reinforcement learning literature. Specifically, we are the first to prove polynomial-time approximability for the following settings: policies under chance constraints, deterministic policies under multiple expectation constraints, policies under non-homogeneous constraints (i.e., constraints of different types), and policies under constraints for continuous-state processes.
• Abstract（参考訳）: 一般化されたマルコフ決定過程の近似の計算複雑性について検討する。 我々の主な貢献は多項式時間$(0,\epsilon)$-additive bicriteria approximationアルゴリズムの設計であり、ほぼ確実性、確率、期待値、およびその時変量を含む計算可能制約の幅広いクラスにわたって最適な制約付きポリシーを求める。 下限とのマッチングは、我々の近似保証が$P \neq NP$である限り最適であることを意味する。 提案手法の汎用性は,制約付き強化学習文献における長期にわたるオープン複雑性問題への回答をもたらす。 具体的には、確率制約の下でのポリシー、複数の期待制約下での決定的ポリシー、非同次制約下でのポリシー(例えば、異なるタイプの制約)、連続状態プロセスにおける制約下でのポリシーである。

関連論文リスト

• Landscape of Policy Optimization for Finite Horizon MDPs with General State and Action [10.219627570276689]
  我々は、一般的な状態と空間を持つマルコフ決定過程のクラスのためのフレームワークを開発する。 勾配法は非漸近条件で大域的最適ポリシーに収束することを示す。 その結果,多周期インベントリシステムにおける最初の複雑性が確立された。
  論文  参考訳（メタデータ） (2024-09-25T17:56:02Z)
• Last-Iterate Global Convergence of Policy Gradients for Constrained Reinforcement Learning [62.81324245896717]
  我々はC-PGと呼ばれる探索非依存のアルゴリズムを導入し、このアルゴリズムは(弱)勾配支配仮定の下でのグローバルな最終点収束を保証する。 制約付き制御問題に対して,我々のアルゴリズムを数値的に検証し,それらを最先端のベースラインと比較する。
  論文  参考訳（メタデータ） (2024-07-15T14:54:57Z)
• Deterministic Policies for Constrained Reinforcement Learning in Polynomial Time [1.223779595809275]
  本アルゴリズムは,制約付き強化学習問題に対するほぼ最適決定性ポリシーを効率的に計算する。 我々の研究は、2つの長年の研究にまたがる3つのオープンな疑問に答える。
  論文  参考訳（メタデータ） (2024-05-23T05:27:51Z)
• Towards Instance-Optimality in Online PAC Reinforcement Learning [28.156332484814616]
  そこで本研究では,PACの同定に要するサンプルの複雑さに対する最初のインスタンス依存下限について提案する。 我々は、citeWagenmaker22linearMDPのPEDELアルゴリズムのサンプル複雑さがこの下界に近づいたことを実証する。
  論文  参考訳（メタデータ） (2023-10-31T19:26:36Z)
• High-probability sample complexities for policy evaluation with linear function approximation [88.87036653258977]
  本研究では,2つの広く利用されている政策評価アルゴリズムに対して,最適線形係数の予め定義された推定誤差を保証するために必要なサンプル複素量について検討する。 高確率収束保証に縛られた最初のサンプル複雑性を確立し、許容レベルへの最適依存を実現する。
  論文  参考訳（メタデータ） (2023-05-30T12:58:39Z)
• Policy learning "without" overlap: Pessimism and generalized empirical Bernstein's inequality [94.89246810243053]
  本論文は,事前収集した観測値を利用して最適な個別化決定規則を学習するオフライン政策学習について検討する。 既存の政策学習法は、一様重なりの仮定、すなわち、全ての個々の特性に対する全ての作用を探索する正当性は、境界を低くしなければならない。 我々は,点推定の代わりに低信頼度境界(LCB)を最適化する新しいアルゴリズムであるPPLを提案する。
  論文  参考訳（メタデータ） (2022-12-19T22:43:08Z)
• Nearly Optimal Latent State Decoding in Block MDPs [74.51224067640717]
  エピソードブロック MDP では、意思決定者は少数の潜在状態から生成される豊富な観測やコンテキストにアクセスすることができる。 まず、固定動作ポリシーに基づいて生成されたデータに基づいて、潜時状態復号関数を推定することに興味がある。 次に、報酬のないフレームワークにおいて、最適に近いポリシーを学習する問題について研究する。
  論文  参考訳（メタデータ） (2022-08-17T18:49:53Z)
• Provable Reinforcement Learning with a Short-Term Memory [68.00677878812908]
  我々はPMDPsの新しいサブクラスについて研究し、その潜在状態は、最近の短い長さ$m$の履歴によって復号化することができる。 特に、リッチ・オブザーブレーション・セッティングにおいて、指数関数的にスケールするサンプル複雑性を持つ新しい「モーメントマッチング」アプローチを用いて、新しいアルゴリズムを開発する。 以上の結果から,これらの環境下での強化学習には短期記憶が十分であることが示唆された。
  論文  参考訳（メタデータ） (2022-02-08T16:39:57Z)
• The Geometry of Memoryless Stochastic Policy Optimization in Infinite-Horizon POMDPs [0.0]
  我々は、無限水平部分観測可能な決定プロセスにおいて、最高のメモリレスポリシーを見つけるという問題を考察する。 本研究では, 減算された状態-作用周波数と予測累積報酬が政策の関数であり, その度合いは部分観測可能性の度合いによって決定されることを示す。
  論文  参考訳（メタデータ） (2021-10-14T14:42:09Z)
• CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guarantee [61.176159046544946]
  安全強化学習(SRL)問題では、エージェントは期待される全報酬を最大化し、一定の制約の違反を避けるために環境を探索する。 これは、大域的最適ポリシーを持つSRLアルゴリズムの最初の分析である。
  論文  参考訳（メタデータ） (2020-11-11T16:05:14Z)
• Model-Free Algorithm and Regret Analysis for MDPs with Long-Term Constraints [38.2783003051101]
  本稿では,制約付き最適化とQ-ラーニングの概念を用いて,長期制約付きCMDPのアルゴリズムを提案する。 本研究は, 長期的制約を伴うMDPの遺残分析における最初の結果であり, 遷移確率はアプリオリではないことに留意する。
  論文  参考訳（メタデータ） (2020-06-10T17:19:29Z)

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

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