論文の概要: Anytime-Constrained Reinforcement Learning

• arxiv url: http://arxiv.org/abs/2311.05511v2
• Date: Tue, 14 Nov 2023 06:46:06 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-15 17:36:40.608678
• Title: Anytime-Constrained Reinforcement Learning
• Title（参考訳）: 時間制約強化学習
• Authors: Jeremy McMahan, Xiaojin Zhu
• Abstract要約: 制約付きマルコフ決定過程(cMDP)を任意の制約で導入・研究する。 累積コストを付加した最適決定主義的政策が存在することを示す。 非自明な概略的ポリシーの計算は一般にNPハードであることが示される。
• 参考スコア（独自算出の注目度）: 8.248274475754515
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce and study constrained Markov Decision Processes (cMDPs) with anytime constraints. An anytime constraint requires the agent to never violate its budget at any point in time, almost surely. Although Markovian policies are no longer sufficient, we show that there exist optimal deterministic policies augmented with cumulative costs. In fact, we present a fixed-parameter tractable reduction from anytime-constrained cMDPs to unconstrained MDPs. Our reduction yields planning and learning algorithms that are time and sample-efficient for tabular cMDPs so long as the precision of the costs is logarithmic in the size of the cMDP. However, we also show that computing non-trivial approximately optimal policies is NP-hard in general. To circumvent this bottleneck, we design provable approximation algorithms that efficiently compute or learn an arbitrarily accurate approximately feasible policy with optimal value so long as the maximum supported cost is bounded by a polynomial in the cMDP or the absolute budget. Given our hardness results, our approximation guarantees are the best possible under worst-case analysis.
• Abstract（参考訳）: 制約付きマルコフ決定過程(cMDP)を任意の制約で導入・研究する。 いかなる時でも、エージェントはいかなる時点でも、ほぼ確実にその予算に違反しないよう要求する。 マルコフの政策はもはや不十分であるが、累積コストで拡張された最適な決定論的政策が存在することを示す。 実際、時間制約のcMDPを非制約のMDPに還元する固定パラメータを提示する。 我々の削減は,cMDPの精度が対数的である限り,表型cMDPの時間的およびサンプル効率のよい計画および学習アルゴリズムが得られる。 しかし,非自明な近似的最適方針の計算は一般にnpハードであることが示される。 このボトルネックを回避するため、最大サポートコストがcMDPの多項式あるいは絶対予算で制限される限り、任意の精度でほぼ実現可能なポリシーを最適値で効率的に計算または学習する証明可能な近似アルゴリズムを設計する。 我々の困難さを考えると、最悪のケース分析では近似保証が最善である。

関連論文リスト

• Near-Optimal Learning and Planning in Separated Latent MDPs [70.88315649628251]
  我々は、潜在マルコフ決定過程(LMDP)の計算的および統計的側面について研究する。 このモデルでは、学習者は、未知のMDPの混合から各エポックの開始時に描画されたMDPと相互作用する。
  論文  参考訳（メタデータ） (2024-06-12T06:41:47Z)
• Policy Gradient Algorithms for Robust MDPs with Non-Rectangular Uncertainty Sets [10.26382228865201]
  非矩形不確実性集合を持つロバスト無限水平マルコフ決定過程(MDP)に対するポリシー勾配アルゴリズムを提案する。 対応するロバストなMDPは動的プログラミング技術では解決できず、実際は難解である。 そこで我々は,大域的最適性保証を提供する非矩形不確実性集合を持つ頑健なMDPに対する最初の完全解法を提案する。
  論文  参考訳（メタデータ） (2023-05-30T13:02:25Z)
• An Efficient Solution to s-Rectangular Robust Markov Decision Processes [49.05403412954533]
  テクスツ長方形ロバストマルコフ決定過程(MDP)に対する効率的なロバストな値反復法を提案する。 我々は,L_p$の水充填補題を用いて,ベルマン作用素を具体的形式で導出した。 最適な政策の正確な形を明らかにし、これは、その利点に比例する行動を起こす確率で、新しいしきい値ポリシーであることが判明した。
  論文  参考訳（メタデータ） (2023-01-31T13:54:23Z)
• Nearly Optimal Latent State Decoding in Block MDPs [74.51224067640717]
  エピソードブロック MDP では、意思決定者は少数の潜在状態から生成される豊富な観測やコンテキストにアクセスすることができる。 まず、固定動作ポリシーに基づいて生成されたデータに基づいて、潜時状態復号関数を推定することに興味がある。 次に、報酬のないフレームワークにおいて、最適に近いポリシーを学習する問題について研究する。
  論文  参考訳（メタデータ） (2022-08-17T18:49:53Z)
• Near-Optimal Sample Complexity Bounds for Constrained MDPs [25.509556551558834]
  減算CMDPにおける準最適政策を学習するために,サンプルの複雑さを極小値と下位値で表す。 CMDPの学習は,少ない制約違反を許す場合と同等に容易であるが,制約違反を要求しない場合には本質的に困難であることを示す。
  論文  参考訳（メタデータ） (2022-06-13T15:58:14Z)
• Efficient Policy Iteration for Robust Markov Decision Processes via Regularization [49.05403412954533]
  ロバストな意思決定プロセス(MDP)は、システムのダイナミクスが変化している、あるいは部分的にしか知られていない決定問題をモデル化するためのフレームワークを提供する。 最近の研究は、長方形長方形の$L_p$頑健なMDPと正規化されたMDPの等価性を確立し、標準MDPと同じレベルの効率を享受する規則化されたポリシー反復スキームを導出した。 本研究では、政策改善のステップに焦点をあて、欲求政策と最適なロバストなベルマン作用素のための具体的な形式を導出する。
  論文  参考訳（メタデータ） (2022-05-28T04:05:20Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Model-Free Algorithm and Regret Analysis for MDPs with Long-Term Constraints [38.2783003051101]
  本稿では,制約付き最適化とQ-ラーニングの概念を用いて,長期制約付きCMDPのアルゴリズムを提案する。 本研究は, 長期的制約を伴うMDPの遺残分析における最初の結果であり, 遷移確率はアプリオリではないことに留意する。
  論文  参考訳（メタデータ） (2020-06-10T17:19:29Z)
• Provably Efficient Model-Free Algorithm for MDPs with Peak Constraints [38.2783003051101]
  本稿では,有限地平線における全報酬の最大化と,各エポックにおける制約を確率1で満たすため,エージェントがポリシーを選択する,制約付きマルコフ決定プロセス(PCMDP)について考察する。 そこで本研究では,PCMDP問題を制約のない問題に変換するモデルフリーアルゴリズムを提案し,Q-ラーニングに基づくアプローチを適用した。
  論文  参考訳（メタデータ） (2020-03-11T23:23:29Z)
• Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
  制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。 本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-03-01T17:47:03Z)

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

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